Approximate and exact merging of knapsack constraints with cover inequalities

DOI10.1080/02331934.2020.1719492zbMath1460.90113OpenAlexW3109104499MaRDI QIDQ5151546

Fabio Vitor, Todd Easton

Publication date: 19 February 2021

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331934.2020.1719492

zbMATH Keywords

integer programmingcutting planesknapsack constraintscover inequalitiesinequality merging

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Dynamic programming (90C39)

Uses Software

• CPLEX
• OR-Library

Cites Work

• Unnamed Item
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
• An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics
• Partially ordered knapsack and applications to scheduling
• Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
• A multi-level search strategy for the 0-1 multidimensional knapsack problem
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms
• Solving a mixed-integer multiobjective bond portfolio model involving logical conditions
• A genetic algorithm for the multidimensional knapsack problem
• A decision support system for a real vehicle routing problem.
• On the facets of the mixed-integer knapsack polyhedron
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• A fuzzy DEA and knapsack formulation integrated model for project selection
• Improved results on the 0--1 multidimensional knapsack problem
• Mixed integer programming approaches to treatment planning for brachytherapy -- application to permanent prostate implants
• Integer programming applied to intensity-modulated radiation therapy treatment planning
• Sequence independent lifting in mixed integer programming
• Production and inventory management under multiple resource constraints
• Very large-scale neighborhood search for the \(K\)-constraint multiple knapsack problem
• Some polyhedra related to combinatorial problems
• Edmonds polytopes and a hierarchy of combinatorial problems
• Simple lifted cover inequalities and hard knapsack problems
• Merging valid inequalities over the multiple knapsack polyhedron
• Two row mixed-integer cuts via lifting
• The multiobjective multidimensional knapsack problem: a survey and a new approach
• The Multidimensional Knapsack Problem: Structure and Algorithms
• Easily Computable Facets of the Knapsack Polytope
• Outline of an algorithm for integer solutions to linear programs
• An Automatic Method of Solving Discrete Programming Problems
• On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems
• A global optimization approach for solving three-dimensional open dimension rectangular packing problems
• A Knapsack Secretary Problem with Applications
• Lifting the facets of zero–one polytopes
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• Valid Inequalities and Superadditivity for 0–1 Integer Programs
• Disjunctive Programming
• Dependent-chance integer programming applied to capital budgeting
• Reducibility among Combinatorial Problems
• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• Sequential-Merge Facets for Two-Dimensional Group Problems

This page was built for publication: Approximate and exact merging of knapsack constraints with cover inequalities