Experiments with conflict analysis in mixed integer programming
From MaRDI portal
Publication:2011593
DOI10.1007/978-3-319-59776-8_17zbMATH Open1489.68261arXiv1611.07887OpenAlexW2555363809MaRDI QIDQ2011593FDOQ2011593
Authors: Jakob Witzig, Timo Berthold, Stefan Heinz 
Publication date: 4 August 2017
Abstract: The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis are one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine these approaches. Experiments are carried out on general MIP instances from standard public test sets such as MIPLIB; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.
Full work available at URL: https://arxiv.org/abs/1611.07887
Recommendations
- Conflict analysis in mixed integer programming
- Computational aspects of infeasibility analysis in mixed integer programming
- Analyzing Infeasible Mixed-Integer and Integer Linear Programs
- Detecting infeasibility and generating cuts for mixed integer programming using constraint programming
- Conflict graphs in solving integer programming problems
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Mixed integer programming (90C11)
Cites Work
- MIPLIB 2003
- A Computational Study of Search Strategies for Mixed Integer Programming
- An Automatic Method of Solving Discrete Programming Problems
- Conflict analysis in mixed integer programming
- Noncommercial software for mixed-integer linear programming
- Title not available (Why is that?)
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- A tree-search algorithm for mixed integer programming problems
- Undercover: a primal MINLP heuristic exploring a largest sub-MIP
- Title not available (Why is that?)
- Experiments in mixed-integer linear programming
- Efficient intelligent backtracking using linear programming
- Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
- Information-based branching schemes for binary linear mixed integer problems
- Shift-and-propagate
- Experiments with conflict analysis in mixed integer programming
Cited In (13)
- Computational aspects of infeasibility analysis in mixed integer programming
- IntSat: integer linear programming by conflict-driven constraint learning
- Experiments with conflict analysis in mixed integer programming
- Conflict Analysis for MINLP
- Conflict-Driven Heuristics for Mixed Integer Programming
- K-best feasible clusters - ranking optimal solutions from an infeasible LP
- Conflict graphs in solving integer programming problems
- Conflict analysis in mixed integer programming
- Transferring information across restarts in MIP
- Structure-driven fix-and-propagate heuristics for mixed integer programming
- Outer approximation with conic certificates for mixed-integer convex problems
- Irreducible infeasible subsystems of semidefinite systems
- Linearization and parallelization schemes for convex mixed-integer nonlinear optimization
Uses Software
This page was built for publication: Experiments with conflict analysis in mixed integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011593)
