Branch-and-cut for linear programs with overlapping SOS1 constraints
From MaRDI portal
Publication:1646682
DOI10.1007/s12532-017-0122-5zbMath1402.90095OpenAlexW2343806840MaRDI QIDQ1646682
Tobias Fischer, Marc E. Pfetsch
Publication date: 25 June 2018
Published in: Mathematical Programming Computation (Search for Journal in Brave)
Full work available at URL: http://www.optimization-online.org/DB_HTML/2015/04/4853.html
mixed integer programmingbranch-and-cutcomplementarity constraintsspecial ordered setsbipartite branchingSOS1 branching
Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
Related Items
New classes of facets for complementarity knapsack problems, Monoidal cut strengthening and generalized mixed-integer rounding for disjunctions and complementarity constraints, Solving linear programs with complementarity constraints using branch-and-cut, On the structure of linear programs with overlapping cardinality constraints, An enhanced logical benders approach for linear programs with complementarity constraints, Recovery under side constraints
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Heuristics for convex mixed integer nonlinear programs
- On linear programs with linear complementarity constraints
- Branch-and-cut for complementarity-constrained optimization
- SCIP: solving constraint integer programs
- Implementations of special ordered sets in MP software
- A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints
- Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
- Representability in mixed integer programming. I: Characterization results
- Mutual exclusion scheduling
- A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints
- A polyhedral study of the cardinality constrained knapsack problem
- A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
- Nurse scheduling with tabu search and strategic oscillation
- Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph
- Future paths for integer programming and links to artificial intelligence
- A note on greedy algorithms for the maximum weighted independent set problem
- Branching rules revisited
- Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints
- Conflict graphs in solving integer programming problems
- Measuring the impact of primal heuristics
- New branch-and-Cut algorithm for bilevel linear programming
- Conflict analysis in mixed integer programming
- Cutting-planes for programs with disjunctive constraints
- Branch-and-cut for combinatorial optimization problems without auxiliary binary variables
- The Knapsack Problem with Conflict Graphs
- On the Global Solution of Linear Programs with Linear Complementarity Constraints
- APPROXIMATE ALGORITHMS FOR THE MULTIPLE-CHOICE CONTINUOUS KNAPSACK PROBLEMS
- Transportation problem with nonlinear side constraints a branch and bound approach
- Practical Solution of Large Mixed Integer Programming Problems with Umpire
- THE MULTIPLE-CHOICE KNAPSACK PROBLEM
- The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- The capacity of wireless networks
- An approximation scheme for bin packing with conflicts
- Algorithm 457: finding all cliques of an undirected graph
- Facets of the Complementarity Knapsack Polytope
- The mixed vertex packing problem.
