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
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, Data-driven construction of convex region surrogate models, On a Generalization of the Chvátal-Gomory Closure, Cover inequalities for robust knapsack sets-Application to the robust bandwidth packing problem, A lift-and-project cutting plane algorithm for mixed 0-1 programs, A distributed exact algorithm for the multiple resource constrained sequencing problem, The Boolean Quadric Polytope, A branch-and-price-and-cut approach for sustainable crop rotation planning, Reliability, covering and balanced matrices, Separation algorithms for 0-1 knapsack polytopes, An algorithm for solving fixed-charge problems using surrogate constraints, Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints, A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, Global minimization of large-scale constrained concave quadratic problems by separable programming, Theoretical challenges towards cutting-plane selection, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, Strategies for LP-based solving a general class of scheduling problems, Local cuts for mixed-integer programming, An efficient integer programming model of the dynamic lot-sizing problem, The integer linear complementarity problem, Cardinality-restricted chains and antichains in partially ordered sets, Lifting the knapsack cover inequalities for the knapsack polytope, Long range planning in the process industries: A projection approach, A binary-rounding heuristic for multi-period variable-task-duration assignment problems, A comparison of two methods for solving 0-1 integer programs using a general purpose simulated annealing algorithm, Covering Linear Programming with Violations, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, A cut-and-solve based algorithm for the single-source capacitated facility location problem, Polytopes associated with symmetry handling, A cut-and-branch algorithm for the quadratic knapsack problem, Computational study of a branching algorithm for the maximum \(k\)-cut problem, The affine hull of the schedule polytope for servicing identical requests by parallel devices, A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems, Sequence independent lifting of cover inequalities, The bus sightseeing problem, Computer programs for non‐linear programming, Lifting for the integer knapsack cover polyhedron, New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems, A knapsack intersection hierarchy, New classes of facets for complementarity knapsack problems, Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation, Domain reduction techniques for global NLP and MINLP optimization, LP extreme points and cuts for the fixed-charge network design problem, Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints, Foundation-penalty cuts for mixed-integer programs., On facet-inducing inequalities for combinatorial polytopes, Linear complementarity problems solvable by integer programming, Two-row and two-column mixed-integer presolve using hashing-based pairing methods, Preprocessing and cutting for multiple allocation hub location problems., Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes, Valid integer polytope (VIP) penalties for branch-and-bound enumeration, Generalized cover facet inequalities for the generalized assignment problem, Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON, A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, Generalized Chvátal-Gomory closures for integer programs with bounds on variables, Classical cuts for mixed-integer programming and branch-and-cut, Stronger formulations of mixed integer linear programs: an example, Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints, Management of design activities in a concurrent engineering environment, Branch and cut methods for network optimization, A strong cutting plane algorithm for the robotic assembly line balancing problem, Partial convexification cuts for 0--1 mixed-integer programs, A polyhedral study of nonconvex quadratic programs with box constraints, Strong IP formulations need large coefficients, Lifting, superadditivity, mixed integer rounding and single node flow sets revisited, Benders decomposition: solving binary master problems by enumeration, Optimization algorithms for the disjunctively constrained knapsack problem, The strength of multi-row aggregation cuts for sign-pattern integer programs, On lifted cover inequalities: a new lifting procedure with unusual properties, Efficient reformulation for 0-1 programs -- methods and computational results, Deterministic network interdiction, Generalizing 0-1 conflict hypergraphs and mixed conflict graphs: mixed conflict hypergraphs in discrete optimization, \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, Using cutting planes in an interactive reference point approach for multiobjective integer linear programming problems, An Event-Driven Algorithm for Agents on the Web, A branch and bound method for stochastic integer problems under probabilistic constraints, A Branch-and-Cut Approach for the Minimum-Energy Broadcasting Problem in Wireless Networks, Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs, On identifying dominant cliques., Presolve Reductions in Mixed Integer Programming, Cutting-plane proofs in polynomial space, On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in 0-1 mixed integer programs, Multi-cover inequalities for totally-ordered multiple knapsack sets, Future paths for integer programming and links to artificial intelligence, Facets and algorithms for capacitated lot sizing, Gomory cuts revisited, ``Facet separation with one linear program, New SOCP relaxation and branching rule for bipartite bilinear programs, Valid inequalities for a class of assembly system problems, The aggregation closure is polyhedral for packing and covering integer programs, A study of integer programming formulations for scheduling problems, Evolution and state-of-the-art in integer programming, A production and maintenance planning model for the process industry, Solving large-scale mixed-integer programs with fixed charge variables, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, On the exact separation of cover inequalities of maximum-depth, On a generalization of the Chvátal-Gomory closure
