Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
From MaRDI portal
The authors consider a 0-1 programming problem with two types of variables, selection variables and bounding ones. The first variables describe the content of the problem and the second ones describe resource restrictions. The authors propose two heuristic methods for reducing the values of the bounding variables which is not permitted in previously known methods. The two methods are based on a solution of a special subset sum problem.
Recommendations
- Heuristics and reduction methods for multiple constraints 0-1 linear programming problems
- On tightening 0-1 programs based on extensions of pure 0-1 knapsack and subset-sum problems
- Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
- Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
- Linear programming for the \(0-1\) quadratic knapsack problem
Cites work
- A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
- Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
- New Procedures For Preprocessing 0–1 Models With Knapsack-Like Constraints And Conjunctive And/Or Disjunctive Variable Upper Bounds
- S3 sets. An extension of the Beale-Tomlin special ordered sets
- Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
- Solving Large-Scale Zero-One Linear Programming Problems
Cited in
(15)- Heuristics and reduction methods for multiple constraints 0-1 linear programming problems
- On tightening cover induced inequalities
- On tightening 0-1 programs based on extensions of pure 0-1 knapsack and subset-sum problems
- Reducing the number of variables in integer and linear programming problems
- Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts
- Supernode processing of mixed-integer models
- Efficient reformulation for 0-1 programs -- methods and computational results
- Covering linear programming with violations
- New Procedures For Preprocessing 0–1 Models With Knapsack-Like Constraints And Conjunctive And/Or Disjunctive Variable Upper Bounds
- Some of my favorite integer programming applications at IBM
- scientific article; zbMATH DE number 4185395 (Why is no real title available?)
- On some extended mixed integer optimization models of the Eisenberg–Noe model in systemic risk management
- The multidimensional 0-1 knapsack problem -- bounds and computational aspects
- A conditional logic approach for strengthening mixed 0-1 linear programs
- Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
This page was built for publication: Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q914548)
