A note on the solution of group knapsack problems
The paper is concerned with the following problem: \[ \hbox{Minimize}\quad\sum^ n_{i=1} c_ ix_ i\quad (c_ i>0, x_ i\geq 0)\quad\hbox{s.t.}\quad \sum^ n_{i=1} g_{ij}x_ i\equiv g_{0j}(\varepsilon_ j)\quad\hbox{for}\quad 1\leq j\leq r, \] where \(g_{ij}\), \(g_{0j}\), \(\varepsilon_ j\) are integers with \((g_{01},\dots,g_{0r})\neq(0,\dots,0)\). The paper gives an approximation algorithm, which is an improvement of Shapiro's. The fundamental idea is that the problem can be reformalized as a shortest path problem. Some numerical tests are also included.
- A note on two problems in connexion with graphs
- Computational experience with a group theoretic integer programming algorithm
- Generation of all integer points for given sets of linear inequalities
- scientific article; zbMATH DE number 3763671 (Why is no real title available?)
- scientific article; zbMATH DE number 3791939 (Why is no real title available?)
- Integer Linear Programming: A Study in Computational Efficiency
- Some polyhedra related to combinatorial problems
- The nicholson principle in discrete dynamic optimization
- Über die irrednziblen punkte des eckenpolyeders
- A relation between the knapsack and group knapsack problems
- STRUCTURE OF OPTIMAL SOLUTIONS OF A KNAPSACK PROBLEM SUBJECT TO A GIVEN TOTAL NUMBER OF VARIABLES USED
- Minmax linear knapsack problem with grouped variables and gub
- The Complexity of Knapsack in Graph Groups
- scientific article; zbMATH DE number 7139161 (Why is no real title available?)
- Test sets of the knapsack problem and simultaneous Diophantine approximation
This page was built for publication: A note on the solution of group knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3979526)