Solving Large-Scale Zero-One Linear Programming Problems
From MaRDI portal
Publication:3696859
DOI10.1287/OPRE.31.5.803zbMath0576.90065OpenAlexW2167539320MaRDI QIDQ3696859
Harlan P. Crowder, Manfred W. Padberg, Ellis L. Johnson
Publication date: 1983
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.31.5.803
branch-and-boundcutting planespreprocessingrational datalarge-scale zero-one linear programmingsparse constraint matrices
Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Boolean programming (90C09)
Related Items (only showing first 100 items - show all)
Valid inequalities for mixed 0-1 programs ⋮ Implicit cover inequalities ⋮ An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem ⋮ Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts ⋮ Partial cover and complete cover inequalities ⋮ A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron ⋮ Knapsack polytopes: a survey ⋮ Exact methods for the knapsack problem and its generalizations ⋮ On the complexity of sequentially lifting cover inequalities for the knapsack polytope ⋮ Solving \(0/1\) integer programs with enumeration cutting planes ⋮ Representability in mixed integer programming. I: Characterization results ⋮ Supernode processing of mixed-integer models ⋮ Global minimization of indefinite quadratic problems ⋮ Adding activities to the dual instead of cuts to the primal problem ⋮ Lifting inequalities: a framework for generating strong cuts for nonlinear programs ⋮ Coefficient strengthening: a tool for reformulating mixed-integer programs ⋮ Some branch and bound techniques for nonlinear optimization ⋮ S3 sets. An extension of the Beale-Tomlin special ordered sets ⋮ On separating cover inequalities for the multidimensional knapsack problem ⋮ Exploiting nested inequalities and surrogate constraints ⋮ Binary integer programs with two variables per inequality ⋮ A polynomial-time solution to Papadimitriou and Steiglitz's ``traps ⋮ Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs ⋮ Some properties of cliques in 0-1 mixed integer programs ⋮ A binary integer linear program with multi-criteria and multi-constraint levels ⋮ Strong formulations for mixed integer programming: A survey ⋮ Facets and lifting procedures for the set covering polytope ⋮ \(O(n \log n)\) procedures for tightening cover inequalities ⋮ Binary accelerated particle swarm algorithm (BAPSA) for discrete optimization problems ⋮ The piecewise linear optimization polytope: new inequalities and intersection with semi-continuous constraints ⋮ Lifting, tilting and fractional programming revisited ⋮ Progress with single-item lot-sizing ⋮ On the relative strength of split, triangle and quadrilateral cuts ⋮ A branch and cut algorithm for resource-constrained project scheduling problem subject to nonrenewable resources with pre-scheduled procurement ⋮ Solving mixed integer programming production planning problems with setups by shadow price information. ⋮ Progress in presolving for mixed integer programming ⋮ A computational comparison of several models for the exact solution of the capacity and distance constrained plant location problem ⋮ Complexity evaluation of benchmark instances for the \(p\)-median problem ⋮ The generalized assignment problem: Valid inequalities and facets ⋮ Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing ⋮ Facet defining inequalities for the dichotomous knapsack problem ⋮ Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds ⋮ A production planning problem in FMS ⋮ Generating cuts in integer programming with families of special ordered sets ⋮ A note on the knapsack problem with special ordered sets ⋮ Second-order cover inequalities ⋮ Box-constrained quadratic programs with fixed charge variables ⋮ Branch-and-cut for complementarity-constrained optimization ⋮ Finding minimum cost directed trees with demands and capacities ⋮ Lifting cover inequalities for the precedence-constrained knapsack problem ⋮ Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities ⋮ Generalized coefficient strengthening cuts for mixed integer programming ⋮ A characterization of knapsacks with the max-flow--min-cut property ⋮ On tightening cover induced inequalities ⋮ The complexity of lifted inequalities for the knapsack problem ⋮ The convex hull of two core capacitated network design problems ⋮ Recoverable robust knapsacks: the discrete scenario case ⋮ Progress in computational mixed integer programming -- a look back from the other side of the tipping point ⋮ Some of my favorite integer programming applications at IBM ⋮ My experiences as a student and researcher in OR during the 1960's and 70's ⋮ Hooked on IP ⋮ Broadening the integer programming audience, the LINDO perspective ⋮ IP over 40+ years at IBM scientific centers and marketing ⋮ Polyhedral results for the precedence-constrained knapsack problem ⋮ Cutting planes in integer and mixed integer programming ⋮ On the exact separation of mixed integer knapsack cuts ⋮ Cutting plane algorithms for \(0-1\) programming based on cardinality cuts ⋮ Parametric-objective integer programming using knapsack facets and Gomory cutting planes ⋮ A computational comparison of Gomory and knapsack cuts ⋮ Multi-step methods for choosing the best set of variables in regression analysis ⋮ SCIP: solving constraint integer programs ⋮ Valid inequalities and facets of the capacitated plant location problem ⋮ Bidimensional packing by bilinear programming ⋮ Solving multiple scenarios in a combinatorial auction ⋮ Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing ⋮ Large-scale 0-1 linear programming on distributed workstations ⋮ QUAD01: A data-structured implementation of Hansen's quadratic zero-one programming algorithm ⋮ Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems ⋮ Optimizing nuclear power plant refueling with mixed-integer programming ⋮ Cutting planes for integer programs with general integer variables ⋮ Cutting planes for mixed-integer knapsack polyhedra ⋮ A procedure for optimizing tactical response in oil spill clean up operations ⋮ Different transformations for solving non-convex trim-loss problems by MINLP ⋮ Solving the generalised assignment problem using polyhedral results ⋮ Cost optimal allocation of rail passenger lines ⋮ The complexity of cover inequality separation ⋮ Order selection on a single machine with high set-up costs ⋮ A note on solving large p-median problems ⋮ Location problems ⋮ A technique for speeding up the solution of the Lagrangean dual ⋮ Achievement test construction using 0-1 linear programming ⋮ A facet generation and relaxation technique applied to an assignment problem with side constraints ⋮ Generating random points (or vectors) controlling the percentage of them that are extreme in their convex (or positive) hull ⋮ Cover and pack inequalities for (mixed) integer programming ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects ⋮ Logic-based modeling and solution of nonlinear discrete/continuous optimization problems ⋮ A conditional logic approach for strengthening mixed 0-1 linear programs ⋮ Integer-programming software systems ⋮ Logical processing for integer programming ⋮ Airline crew scheduling: state-of-the-art
This page was built for publication: Solving Large-Scale Zero-One Linear Programming Problems
