Canonical Cuts on the Unit Hypercube

DOI10.1137/0123007zbMath0237.52004OpenAlexW2049741107MaRDI QIDQ5647555

Publication date: 1972

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0123007

Mathematics Subject Classification ID

Inequalities and extremum problems involving convexity in convex geometry (52A40) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Polytopes and polyhedra (52Bxx)

Related Items (74)

Natural gas production network infrastructure development under uncertainty ⋮ Petroleum supply planning: reformulations and a novel decomposition algorithm ⋮ Implicit cover inequalities ⋮ Pump scheduling in drinking water distribution networks with an LP/NLP-based branch and bound ⋮ A cross-decomposition scheme with integrated primal-dual multi-cuts for two-stage stochastic programming investment planning problems ⋮ Optimizing single-terminal dispatch of large volume trips to trucks ⋮ Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Reliability, covering and balanced matrices ⋮ New convergent heuristics for 0-1 mixed integer programming ⋮ Finding all global optima of engineering design problems with discrete signomial terms ⋮ New formulations and solution approaches for the latency location routing problem ⋮ A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks ⋮ Finding multiple solutions to general integer linear programs ⋮ Bilevel Knapsack with Interdiction Constraints ⋮ Alternative solution algorithm for winner determination problem with quantity discount of transportation service procurement ⋮ Representations of Boolean functions by systems of linear inequalities ⋮ A direct dual method for the mixed plant location problem with some side constraints ⋮ Template-Based Minor Embedding for Adiabatic Quantum Optimization ⋮ Polynomial size IP formulations of knapsack may require exponentially large coefficients ⋮ Nonlinear 0–1 programming: II. Dominance relations and algorithms ⋮ A storm of feasibility pumps for nonconvex MINLP ⋮ An outer-approximation algorithm for a class of mixed-integer nonlinear programs ⋮ Minimum cost delivery of multi-item orders in e-commerce logistics ⋮ Decomposition strategy for the stochastic pooling problem ⋮ On interval-subgradient and no-good cuts ⋮ Polytopes associated with symmetry handling ⋮ Spherical cuts for integer programming problems ⋮ Logic-based Benders decomposition for wildfire suppression ⋮ Combining optimisation and simulation using logic-based Benders decomposition ⋮ Multi-period distribution networks with purchase commitment contracts ⋮ Packing, partitioning, and covering symresacks ⋮ Sequence independent lifting for mixed knapsack problems with GUB constraints ⋮ On the 2-Club Polytope of Graphs ⋮ Identifying the most important set of weights when modelling bad outputs with the weak disposability approach ⋮ Fairness over time in dynamic resource allocation with an application in healthcare ⋮ Inequalities and Target Objectives for Metaheuristic Search – Part I: Mixed Binary Optimization ⋮ Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation ⋮ A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem ⋮ The Weighted Set Covering Game: A Vaccine Pricing Model for Pediatric Immunization ⋮ Integer programming and convex analysis: Intersection cuts from outer polars ⋮ A review of deterministic optimization methods in engineering and management ⋮ Finding multiple optimal solutions of signomial discrete programming problems with free variables ⋮ Faces for a linear inequality in 0–1 variables ⋮ Facet of regular 0–1 polytopes ⋮ A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation ⋮ Solving the traveling salesman problem with interdiction and fortification ⋮ Enriching Solutions to Combinatorial Problems via Solution Engineering ⋮ Facets of the knapsack polytope ⋮ Location-allocation models for traffic police patrol vehicles on an interurban network ⋮ A lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures ⋮ Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs ⋮ The precedence constrained knapsack problem: separating maximally violated inequalities ⋮ A characterization of knapsacks with the max-flow--min-cut property ⋮ Parametric mixed-integer 0-1 linear programming: The general case for a single parameter ⋮ Water distribution networks design under uncertainty ⋮ Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem ⋮ Rounding-based heuristics for nonconvex MINLPS ⋮ Improved convergent heuristics for the 0-1 multidimensional knapsack problem ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ On defining sets of vertices of the hypercube by linear inequalities ⋮ Lifting the facets of zero–one polytopes ⋮ Integer programming formulation of combinatorial optimization problems ⋮ Almost integral polyhedra related to certain combinatorial optimization problems ⋮ A note on characterizing canonical cuts using geometry ⋮ HMS: a hybrid multi-start algorithm for solving binary linear programs ⋮ Zero-one programming with many variables and few constraints ⋮ The convex hull of a linear congruence relation in zero-one variables ⋮ An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope. ⋮ Improving the performance of DICOPT in convex MINLP problems using a feasibility pump ⋮ Sphere coverings of the hypercube with incomparable centers ⋮ Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope ⋮ An alternative efficient representation for the project portfolio selection problem ⋮ Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem ⋮ A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems

This page was built for publication: Canonical Cuts on the Unit Hypercube