Conflict graphs in solving integer programming problems
From MaRDI portal
Publication:1969889
DOI10.1016/S0377-2217(99)00015-6zbMath0959.90034OpenAlexW2041754841MaRDI QIDQ1969889
Savelsbergh, Martin W. P., Nemhauser, George I., Atamtürk, Alper
Publication date: 2 May 2001
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0377-2217(99)00015-6
Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Boolean programming (90C09)
Related Items
A Lagrangean decomposition for the maximum independent set problem applied to map labeling, A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems, Incorporating bounds from decision diagrams into integer programming, Integer programming techniques for the nurse rostering problem, Integer constraints for enhancing interpretability in linear regression, The matching relaxation for a class of generalized set partitioning problems, Set covering problem with conflict constraints, A computational study of conflict graphs and aggressive cut separation in integer programming, Branch-and-cut for linear programs with overlapping SOS1 constraints, Theoretical challenges towards cutting-plane selection, A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem, Tighter MIP formulations for the discretised unit commitment problem with MIN-stop ramping constraints, Crew Assignment with Duty Time Limits for Transport Services: Tight Multicommodity Models, Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem, Transferring information across restarts in MIP, Global optimization of MIQCPs with dynamic piecewise relaxations, Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model, A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph, Integer programming methods for solving binary interdiction games, Strong formulation for the spot 5 daily photograph scheduling problem, Mixed-Integer programming models for irregular strip packing based on vertical slices and feasibility cuts, Exact Solution Algorithms for the Chordless Cycle Problem, A branch and bound algorithm for robust binary optimization with budget uncertainty, Progress in presolving for mixed integer programming, Domain reduction techniques for global NLP and MINLP optimization, Optimal Network Design with End-to-End Service Requirements, BFC, A branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0--1 programs., Automated knowledge source selection and service composition, Strong-branching inequalities for convex mixed integer nonlinear programs, Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON, A computational comparison of symmetry handling methods for mixed integer programs, Conflict analysis in mixed integer programming, Generalized coefficient strengthening cuts for mixed integer programming, Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, General cut-generating procedures for the stable set polytope, Safe dike heights at minimal costs: an integer programming approach, Preprocessing and cut generation techniques for multi-objective binary programming, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, The maximum common edge subgraph problem: A polyhedral investigation, Progress in computational mixed integer programming -- a look back from the other side of the tipping point, A branch and cut algorithm for minimum spanning trees under conflict constraints, Cutting planes in integer and mixed integer programming, A branch-and-cut algorithm for the maximum cardinality stable set problem, A LP-based heuristic for a time-constrained routing problem, Preprocessing and cutting planes with conflict graphs, A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem, Structure-driven fix-and-propagate heuristics for mixed integer programming, On identifying dominant cliques., A decomposition approach for the probabilistic maximal covering location-allocation problem, Presolve Reductions in Mixed Integer Programming, Strengthened clique-family inequalities for the stable set polytope, Strong bounds for resource constrained project scheduling: preprocessing and cutting planes, Worst-case analysis of clique MIPs
Uses Software
Cites Work
- MINTO, a Mixed INTeger Optimizer
- A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems
- Degree-two Inequalities, Clique Facets, and Biperfect Graphs
- Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
- Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
- Solving Airline Crew Scheduling Problems by Branch-and-Cut
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Reducibility among Combinatorial Problems
- On the facial structure of set packing polyhedra
- Technical Note—An Improved Branch-and-Bound Method for Integer Programming
