Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems

DOI10.1137/0606047zbMath0592.90070MaRDI QIDQ3722274

Egon Balas

Publication date: 1985

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e267e3b2dd4b625b78028a919cf8696773bfc00d

zbMATH Keywords

disjunctive programming; relaxations; network synthesis; fixed charge network flow problems; machine sequencing; approximations to the convex hull of the feasible set; convexification of discrete optimization problems; critical path problems; unions of polyhedra

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C10: Integer programming

90B35: Deterministic scheduling theory in operations research

90B10: Deterministic network models in operations research

52Bxx: Polytopes and polyhedra

Related Items

Stability in disjunctive linear optimization I: continuity of the feasible set, Lift-and-project for mixed 0-1 programming: recent progress, Logic-based modeling and solution of nonlinear discrete/continuous optimization problems, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems, Projection, lifting and extended formulation integer and combinatorial optimization, Lifting inequalities: a framework for generating strong cuts for nonlinear programs, On optimality and duality theorems of nonlinear disjunctive fractional minmax programs, Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs, A study on optimality and duality theorems of nonlinear generalized disjunctive fractional programming, Valid inequalities for mixed integer linear programs, A compact formulation of the ring loading problem with integer demand splitting, A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions, On the convex hull of the union of certain polyhedra, An algorithm for disjunctive programs, Using separation algorithms to generate mixed integer model reformulations, Two mixed integer programming formulations arising in manufacturing management, A cutting-plane approach to mixed 0-1 stochastic integer programs, A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems, A modified lift-and-project procedure, Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Disjunctive cuts for continuous linear bilevel programming, Exact MAX-2SAT solution via lift-and-project closure, A class of stochastic programs with decision dependent uncertainty, On the optimality of nonlinear fractional disjunctive programming problems, Representation for multiple right-hand sides, Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints

Cites Work

• Optimization with disjunctive constraints
• Strengthening cuts for mixed integer programs
• Facial disjunctive programs and sequences of cutting-planes
• The perfectly matchable subgraph polytope of a bipartite graph
• Cutting planes from conditional bounds: A new approach to set covering
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Disjunctive Programming
• Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item