A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems

DOI10.1016/0166-218X(92)00190-WzbMath0819.90064OpenAlexW2076535438MaRDI QIDQ1329799

Publication date: 5 September 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)00190-w

zbMATH Keywords

disjunctive programming tight relaxations convex hull of feasible solutions convex hull representations facetial inequalities mixed-integer zero-one programming

Mathematics Subject Classification ID

Mixed integer programming (90C11) Boolean programming (90C09)

Related Items

Efficient separation of RLT cuts for implicit and explicit bilinear products, Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem, Tight lower bounds for the traveling salesman problem with draft limits, Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, An LP-based characterization of solvable QAP instances with chess-board and graded structures, A theoretical and computational study of green vehicle routing problems, Semidefinite relaxations for partitioning, assignment and ordering problems, Semidefinite relaxations for partitioning, assignment and ordering problems, A localization and reformulation discrete programming approach for the rectilinear distance location-allocation problem, Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, Matrix Relaxations in Combinatorial Optimization, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, A global optimization algorithm for reliable network design, Optimization models for a single-plant district cooling system, The quadratic three-dimensional assignment problem: exact and approximate solution methods, Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs, Surrogate-RLT cuts for zero-one integer programs, Theoretical challenges towards cutting-plane selection, Strategic bidding in price coupled regions, Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles, A two-level location-allocation problem in designing local access fiber optic networks, Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations, Two-stage stochastic hierarchical multiple risk problems: Models and algorithms, Lower bounds and exact algorithms for the quadratic minimum spanning tree problem, Configuration of airspace sectors for balancing air traffic controller workload, Unnamed Item, Composite-variable modeling for service parts logistics, Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering, A level-2 reformulation-linearization technique bound for the quadratic assignment problem, Tighter representations for set partitioning problems, The Maximum k-Colorable Subgraph Problem and Related Problems, Distributionally Robust Optimization Under a Decision-Dependent Ambiguity Set with Applications to Machine Scheduling and Humanitarian Logistics, Enhanced Models for a Mixed Arrival-Departure Aircraft Sequencing Problem, Manifold relaxations for integer programming, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, An efficient linearization technique for mixed 0-1 polynomial problem, Stochastic and risk management models and solution algorithm for natural gas transmission network expansion and LNG terminal location planning, Product assortment and space allocation strategies to attract loyal and non-loyal customers, The coastal seaspace patrol sector design and allocation problem, On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon, Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs, Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems, Knapsack problem with probability constraints, Robust multicriteria risk-averse stochastic programming models, Domain reduction techniques for global NLP and MINLP optimization, A penalized nonlinear ADMM algorithm applied to the multi-constrained traffic assignment problem, Foundation-penalty cuts for mixed-integer programs., A Benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture, A decomposition approach for solving a broadcast domination network design problem, A decomposition approach to the two-stage stochastic unit commitment problem, A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, The mixing-MIR set with divisible capacities, Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques, Extended formulations for convex envelopes, Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations, Exact solution of emerging quadratic assignment problems, The Steiner tree problem with delays: a compact formulation and reduction procedures, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, Two new reformulation convexification based hierarchies for 0-1 MIPs, Two-Stage Stochastic Mixed-Integer Programs: Algorithms and Insights, Convex hull representation of the deterministic bipartite network interdiction problem, A study of general and security Stackelberg game formulations, Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs, BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS, RLT: A unified approach for discrete and continuous nonconvex optimization, RLT insights into lift-and-project closures, Smoothing and Regularization for Mixed-Integer Second-Order Cone Programming with Applications in Portfolio Optimization, Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique, Unnamed Item, Partial convexification cuts for 0--1 mixed-integer programs, A polyhedral study of the generalized vertex packing problem, A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints, Strong multi-commodity flow formulations for the asymmetric traveling salesman problem, Multi-period maintenance scheduling of tree networks with minimum flow disruption, The Cutting Plane Method is Polynomial for Perfect Matchings, An algorithm for the generalized quadratic assignment problem, Complementary column generation and bounding approaches for set partitioning formulations, A new approximation algorithm for unrelated parallel machine scheduling with release dates, Reformulations in Mathematical Programming: Definitions and Systematics, Tightening concise linear reformulations of 0-1 cubic programs, A novel modeling approach for express package carrier planning, A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem, Convex hull representations of special monomials of binary variables, Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem, A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions, Enumeration approach for linear complementarity problems based on a reformulation-linearization technique, An optimal data-splitting algorithm for aircraft sequencing on a single runway, Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem, Allocating nodes to hubs for minimizing the hubs processing resources: A case study, Cuts for mixed 0-1 conic programming, New modeling approaches for the design of local access transport area networks, A global optimization RLT-based approach for solving the hard clustering problem, Linear programming insights into solvable cases of the quadratic assignment problem, Combinatorial optimization: current successes and directions for the future, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Logic cuts for processing networks with fixed charges, Univariate parameterization for global optimization of mixed-integer polynomial problems, A global optimization RLT-based approach for solving the fuzzy clustering problem, Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods, Depth-optimized convexity cuts, Mixed integer linear programming in process scheduling: modeling, algorithms, and applications, A conditional logic approach for strengthening mixed 0-1 linear programs, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems, Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints

Cites Work