Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems

DOI10.1137/0606047zbMath0592.90070OpenAlexW1972997295MaRDI QIDQ3722274

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

Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10) Polytopes and polyhedra (52Bxx)

Related Items (only showing first 100 items - show all)

A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems ⋮ Optimization of capacity expansion in potential-driven networks including multiple looping: a comparison of modelling approaches ⋮ Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems ⋮ A lift-and-project cutting plane algorithm for mixed 0-1 programs ⋮ On the mixing set with a knapsack constraint ⋮ Trajectory planning for autonomous underwater vehicles in the presence of obstacles and a nonlinear flow field using mixed integer nonlinear programming ⋮ Perspective Reformulation and Applications ⋮ Mathematical Programming Models and Exact Algorithms ⋮ Computational approaches for mixed integer optimal control problems with indicator constraints ⋮ Duality for mixed-integer convex minimization ⋮ Lifting inequalities: a framework for generating strong cuts for nonlinear programs ⋮ Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems ⋮ Supplier selection in the processed food industry under uncertainty ⋮ Strong valid inequalities for orthogonal disjunctions and bilinear covering sets ⋮ Representation for multiple right-hand sides ⋮ Ideal, non-extended formulations for disjunctive constraints admitting a network representation ⋮ Cutting Plane Algorithm for Convex Generalized Disjunctive Programs ⋮ Convex hull characterizations of lexicographic orderings ⋮ Strong formulations for quadratic optimization with M-matrices and indicator variables ⋮ Operating room scheduling with generalized disjunctive programming ⋮ On optimizing over lift-and-project closures ⋮ A modified lift-and-project procedure ⋮ On the convex hull of the union of certain polyhedra ⋮ On optimality and duality theorems of nonlinear disjunctive fractional minmax programs ⋮ Global optimization of MIQCPs with dynamic piecewise relaxations ⋮ Solving linear optimization over arithmetic constraint formula ⋮ Global optimization of bilinear programs with a multiparametric disaggregation technique ⋮ Global optimization of disjunctive programs ⋮ A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function ⋮ Mathematical programming formulations for piecewise polynomial functions ⋮ Optimization Modulo Theories with Linear Rational Costs ⋮ Simultaneous Convexification of Bilinear Functions over Polytopes with Application to Network Interdiction ⋮ A computational study of perspective cuts ⋮ Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints ⋮ A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints ⋮ Convex envelopes generated from finitely many compact convex sets ⋮ Achieving consistency with cutting planes ⋮ A hierarchy of relaxations for linear generalized disjunctive programming ⋮ Partial Outer Convexification for Traffic Light Optimization in Road Networks ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ A hierarchy of relaxations for nonlinear convex generalized disjunctive programming ⋮ The st-bond polytope on series-parallel graphs ⋮ An exact approach for solving integer problems under probabilistic constraints with random technology matrix ⋮ Mixed-integer nonlinear programs featuring ``on/off constraints ⋮ Network Models with Unsplittable Node Flows with Application to Unit Train Scheduling ⋮ An algorithm for disjunctive programs ⋮ Using separation algorithms to generate mixed integer model reformulations ⋮ Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ Numerical solution of optimal control problems with explicit and implicit switches ⋮ Global optimization of generalized semi-infinite programs using disjunctive programming ⋮ New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints ⋮ Disjunctive cuts for continuous linear bilevel programming ⋮ Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming ⋮ Exact MAX-2SAT solution via lift-and-project closure ⋮ Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques ⋮ Cutting planes from extended LP formulations ⋮ A study on optimality and duality theorems of nonlinear generalized disjunctive fractional programming ⋮ Circuit and bond polytopes on series-parallel graphs ⋮ A class of valid inequalities for multilinear 0-1 optimization problems ⋮ Extended formulations in combinatorial optimization ⋮ A new lift-and-project operator ⋮ Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems ⋮ Discrete and continuous-time formulations for dealing with break periods: preemptive and non-preemptive scheduling ⋮ RLT: A unified approach for discrete and continuous nonconvex optimization ⋮ RLT insights into lift-and-project closures ⋮ Lift-and-project for mixed 0-1 programming: recent progress ⋮ Integral polyhedra related to integer multicommodity flows on a cycle ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ Modeling disjunctive constraints with a logarithmic number of binary variables and constraints ⋮ A finite \(\epsilon\)-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables ⋮ Extended formulations in combinatorial optimization ⋮ Unnamed Item ⋮ Stability in disjunctive linear optimization I: continuity of the feasible set ⋮ Outer approximation for integer nonlinear programs via decision diagrams ⋮ A class of stochastic programs with decision dependent uncertainty ⋮ Valid inequalities for mixed integer linear programs ⋮ Extended formulations for vertex cover ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Separation routine and extended formulations for the stable set problem in claw-free graphs ⋮ On the optimality of nonlinear fractional disjunctive programming problems ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Convexification techniques for linear complementarity constraints ⋮ Strong mixed-integer programming formulations for trained neural networks ⋮ Speeding up Polyhedral Analysis by Identifying Common Constraints ⋮ Two mixed integer programming formulations arising in manufacturing management ⋮ 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 ⋮ A cutting-plane approach to mixed 0-1 stochastic integer programs ⋮ Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results ⋮ Worst-case analysis of clique MIPs ⋮ A decomposition method for distributionally-robust two-stage stochastic mixed-integer conic programs ⋮ Unnamed Item ⋮ A generalization of extension complexity that captures P ⋮ Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure ⋮ Between steps: intermediate relaxations between big-M and convex hull formulations ⋮ 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 ⋮ Relaxed constant positive linear dependence constraint qualification for disjunctive systems

Cites Work

This page was built for publication: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems