Conflict analysis in mixed integer programming

DOI10.1016/j.disopt.2006.10.006zbMath1169.90414OpenAlexW1990267895MaRDI QIDQ2471271

Publication date: 22 February 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.10.006

zbMATH Keywords

mixed integer programming branch-and-cut SAT conflict analysis infeasible mixed integer programming

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Deterministic global optimization of binary hybrid distillation/melt-crystallization processes based on relaxed MINLP formulations ⋮ Improving branch-and-cut performance by random sampling ⋮ Three ideas for a feasibility pump for nonconvex MINLP ⋮ Incorporating bounds from decision diagrams into integer programming ⋮ Applying oracles of on-demand accuracy in two-stage stochastic programming -- a computational study ⋮ Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ Theoretical challenges towards cutting-plane selection ⋮ A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem ⋮ Models and algorithms for packing rectangles into the smallest square ⋮ Mixed integer programming models for job shop scheduling: A computational analysis ⋮ Cutting plane versus compact formulations for uncertain (integer) linear programs ⋮ Mixed integer nonlinear programming tools: an updated practical overview ⋮ Improved branch-cut-and-price for capacitated vehicle routing ⋮ Side-channel cryptographic attacks using pseudo-Boolean optimization ⋮ Transferring information across restarts in MIP ⋮ Comments on: ``On learning and branching: a survey ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ An abstract model for branching and its application to mixed integer programming ⋮ Online learning for scheduling MIP heuristics ⋮ A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows ⋮ Irreducible infeasible subsystems of semidefinite systems ⋮ Orbitopal fixing ⋮ Progress in mathematical programming solvers from 2001 to 2020 ⋮ Achieving consistency with cutting planes ⋮ Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming ⋮ Progress in presolving for mixed integer programming ⋮ Domain reduction techniques for global NLP and MINLP optimization ⋮ SCIP-Jack -- a solver for STP and variants with parallelization extensions ⋮ Dantzig-Wolfe decomposition and branch-and-price solving in G12 ⋮ A Boolean satisfiability approach to the resource-constrained project scheduling problem ⋮ Improving the Randomization Step in Feasibility Pump ⋮ Clique-based facets for the precedence constrained knapsack problem ⋮ A space-indexed formulation of packing boxes into a larger box ⋮ Studying the effective brain connectivity using multiregression dynamic models ⋮ Branching on nonchimerical fractionalities ⋮ Optimized load planning of trains in intermodal transportation ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem ⋮ Constraint Integer Programming: A New Approach to Integrate CP and MIP ⋮ Counting Solutions of Integer Programs Using Unrestricted Subtree Detection ⋮ Undercover: a primal MINLP heuristic exploring a largest sub-MIP ⋮ Nutmeg: a MIP and CP hybrid solver using branch-and-check ⋮ Strong-branching inequalities for convex mixed integer nonlinear programs ⋮ Branch-and-cut-and-price for capacitated connected facility location ⋮ Using dual presolving reductions to reformulate cumulative constraints ⋮ SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework ⋮ Boosting the feasibility pump ⋮ A computational comparison of symmetry handling methods for mixed integer programs ⋮ An Exact Rational Mixed-Integer Programming Solver ⋮ Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs ⋮ Generalized coefficient strengthening cuts for mixed integer programming ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph ⋮ Shift-and-propagate ⋮ Constraint programming-based column generation ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ Heuristic solutions to the long-term unit commitment problem with cogeneration plants ⋮ Alternating control tree search for knapsack/covering problems ⋮ Experiments with conflict analysis in mixed integer programming ⋮ Constraint programming-based column generation ⋮ Information-based branching schemes for binary linear mixed integer problems ⋮ Modeling, inference and optimization of regulatory networks based on time series data ⋮ A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation ⋮ Measuring the Impact of Branching Rules for Mixed-Integer Programming ⋮ How important are branching decisions: fooling MIP solvers ⋮ Improving strong branching by domain propagation ⋮ SCIP: solving constraint integer programs ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Structure-driven fix-and-propagate heuristics for mixed integer programming ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Branch-and-cut approaches for chance-constrained formulations of reliable network design problems ⋮ A hybrid branch-and-bound approach for exact rational mixed-integer programming ⋮ RENS. The optimal rounding ⋮ Presolve Reductions in Mixed Integer Programming ⋮ Parallelization of the FICO Xpress-Optimizer ⋮ PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite ⋮ A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers ⋮ Computational aspects of infeasibility analysis in mixed integer programming ⋮ Mixed integer nonlinear programming tools: a practical overview ⋮ Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search ⋮ Conflict Analysis for MINLP ⋮ Conflict-Driven Heuristics for Mixed Integer Programming ⋮ Feasibility pump 2.0 ⋮ Toward unification of exact and heuristic optimization methods ⋮ Application of mixed integer quadratic program to shortest vector problems ⋮ An inexact programming approach for urban electric power systems management under random-interval-parameter uncertainty ⋮ Linearization and parallelization schemes for convex mixed-integer nonlinear optimization

Uses Software

Cites Work