Experiments with conflict analysis in mixed integer programming
From MaRDI portal
Publication:2011593
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.
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
Cites work
- scientific article; zbMATH DE number 1187159 (Why is no real title available?)
- scientific article; zbMATH DE number 1149402 (Why is no real title available?)
- A Computational Study of Search Strategies for Mixed Integer Programming
- A tree-search algorithm for mixed integer programming problems
- An Automatic Method of Solving Discrete Programming Problems
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- Conflict analysis in mixed integer programming
- Efficient intelligent backtracking using linear programming
- Experiments in mixed-integer linear programming
- Experiments with conflict analysis in mixed integer 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
- MIPLIB 2003
- Noncommercial software for mixed-integer linear programming
- Shift-and-propagate
- Undercover: a primal MINLP heuristic exploring a largest sub-MIP
Cited in
(13)- Linearization and parallelization schemes for convex mixed-integer nonlinear optimization
- Computational aspects of infeasibility analysis in mixed integer programming
- Experiments with conflict analysis in mixed integer programming
- IntSat: integer linear programming by conflict-driven constraint learning
- 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
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)
