Facets of the knapsack polytope
From MaRDI portal
Publication:4077731
DOI10.1007/BF01580440zbMath0316.90046MaRDI QIDQ4077731
Publication date: 1975
Published in: Mathematical Programming (Search for Journal in Brave)
Related Items
Cover inequalities for robust knapsack sets-Application to the robust bandwidth packing problem, A distributed exact algorithm for the multiple resource constrained sequencing problem, Approximate Deadline-Scheduling with Precedence Constraints, Separation algorithms for 0-1 knapsack polytopes, Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints, A cutting plane method for knapsack polytope, Cascading knapsack inequalities: reformulation of a crude oil distribution problem, Improved Computational Approaches and Heuristics for Zero Forcing, Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning, Lifting the knapsack cover inequalities for the knapsack polytope, Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem, Nonlinear 0–1 programming: I. Linearization techniques, Nonlinear 0–1 programming: II. Dominance relations and algorithms, The transit time constrained fixed charge multi-commodity network design problem, Cover by disjoint cliques cuts for the knapsack problem with conflicting items, Polytopes associated with symmetry handling, A cut-and-branch algorithm for the quadratic knapsack problem, Integer programming solution approach for inventory‐production–distribution problems with direct shipments, A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems, Sequence independent lifting of cover inequalities, A note on the implications of approximate submodularity in discrete optimization, A revisited branch-and-cut algorithm for large-scale orienteering problems, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, New classes of facets for complementarity knapsack problems, Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation, A polyhedral study of the semi-continuous knapsack problem, A Noncompact Formulation for Job-Shop Scheduling Problems in Traffic Management, Faces for a linear inequality in 0–1 variables, Constraint Integer Programming: A New Approach to Integrate CP and MIP, Facets of the knapsack polytope, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, Classical cuts for mixed-integer programming and branch-and-cut, Approximate and exact merging of knapsack constraints with cover inequalities, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Polyhedral properties for the intersection of two knapsacks, Lineare Charakterisierungen von Travelling Salesman Problemen, Formulations and valid inequalities for the heterogeneous vehicle routing problem, A hybrid algorithm for the generalized assignment problem, Lifting the facets of zero–one polytopes, Lifting, superadditivity, mixed integer rounding and single node flow sets revisited, The adjacency relation on the traveling salesman polytope is NP-Complete, A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem, (1,k)-configurations and facets for packing problems, A note on characterizing canonical cuts using geometry, Lifting convex inequalities for bipartite bilinear programs, A note on the continuous mixing set, New valid inequalities for the fixed-charge and single-node flow polytopes, Idealness and 2-resistant sets, Lifting convex inequalities for bipartite bilinear programs, Polyhedral techniques in combinatorial optimization I: Theory, Valid inequalities, cutting planes and integrality of the knapsack polytope, Optimum Solution of the Closest String Problem via Rank Distance, Unnamed Item, Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty, Regular (2, 2)-systems, Parametric convex quadratic relaxation of the quadratic knapsack problem, Strong bounds for resource constrained project scheduling: preprocessing and cutting planes, Approximation algorithms for covering/packing integer programs, Some integer programs arising in the design of main frame computers, Computing low-capacity 0–1 knapsack polytopes, Implicit cover inequalities, The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design, Knapsack polytopes: a survey, On the complexity of sequentially lifting cover inequalities for the knapsack polytope, Inversion of convection-diffusion equation with discrete sources, On the mixing set with a knapsack constraint, The min-up/min-down unit commitment polytope, Lifted cover facets of the 0-1 knapsack polytope with GUB constraints, Lifting inequalities: a framework for generating strong cuts for nonlinear programs, An approach to the asymmetric multi-depot capacitated arc routing problem, An exact algorithm for the reliability redundancy allocation problem, Polyhedral analysis for concentrator location problems, Facets of the knapsack polytope derived from disjoint and overlapping index configurations, Theoretical challenges towards cutting-plane selection, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, Exploiting nested inequalities and surrogate constraints, Partial objective inequalities for the multi-item capacitated lot-sizing problem, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, On facets of knapsack equality polytopes, On the complexity of separation from the knapsack polytope, Generalized polymatroids and submodular flows, The quadratic knapsack problem -- a survey, A generalization of antiwebs to independence systems and their canonical facets, On cutting-plane proofs in combinatorial optimization, Facets and lifting procedures for the set covering polytope, Strong valid inequalities for Boolean logical pattern generation, Logic applied to integer programming and integer programming applied to logic, A cut-and-solve based algorithm for the single-source capacitated facility location problem, Sequence independent lifting for mixed knapsack problems with GUB constraints, A branch and cut algorithm for resource-constrained project scheduling problem subject to nonrenewable resources with pre-scheduled procurement, A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, 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, Bidirected and unidirected capacity installation in telecommunication networks., Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network., Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements, Second-order cover inequalities, The mixing-MIR set with divisible capacities, Branch-and-cut for complementarity-constrained optimization, A multi-stop routing problem, Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes, Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities, Adjacency of the 0-1 knapsack problem, An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits, A time indexed formulation of non-preemptive single machine scheduling problems, Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem, Supermodular covering knapsack polytope, A characterization of knapsacks with the max-flow--min-cut property, Tolerance analysis for 0-1 knapsack problems, Lifted inequalities for \(0-1\) mixed-integer bilinear covering sets, A survey of algorithms for the generalized assignment problem, On tightening cover induced inequalities, A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints, The complexity of lifted inequalities for the knapsack problem, Scheduling medical residents' training at university hospitals, Recoverable robust knapsacks: the discrete scenario case, Compressor scheduling in oil fields. Piecewise-linear formulation, valid inequalities, and computational analysis, A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints, Strong bounds with cut and column generation for class-teacher timetabling, Polyhedral results for the precedence-constrained knapsack problem, Cutting planes in integer and mixed integer programming, Maximizing a class of submodular utility functions, A new extended formulation of the generalized assignment problem and some associated valid inequalities, A branch and cut algorithm for hub location problems with single assignment, A class of facet producing graphs for vertex packing polyhedra, The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs, Strong IP formulations need large coefficients, A computational comparison of Gomory and knapsack cuts, Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem, The nucleolus and kernel for simple games or special valid inequalities for 0-1 linear integer programs, A polyhedral study on 0-1 knapsack problems with set packing constraints, SCIP: solving constraint integer programs, Optimization algorithms for the disjunctively constrained knapsack problem, On lifted cover inequalities: a new lifting procedure with unusual properties, The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers, Efficient reformulation for 0-1 programs -- methods and computational results, The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts, Deterministic network interdiction, RENS. The optimal rounding, A combinatorial optimization approach to the selection of statistical units, Resource constrained assignment problems, An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing, Multi-cover inequalities for totally-ordered multiple knapsack sets, Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope, Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds, A fast algorithm for strongly correlated knapsack problems, Refined cut selection for Benders decomposition: applied to network capacity expansion problems, The submodular knapsack polytope, Base polytopes of series-parallel posets: Linear description and optimization, Solving the generalised assignment problem using polyhedral results, A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming, The complexity of facets (and some facets of complexity), Scattered storage assignment: mathematical model and valid inequalities to optimize the intra-order item distances, A set covering reformulation of the pure fixed charge transportation problem, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Cover and pack inequalities for (mixed) integer programming, Integer-programming software systems, Light on the infinite group relaxation. I: Foundations and taxonomy
Cites Work
