×

A note on the solution of group knapsack problems. (English) Zbl 0743.90081

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.

MSC:

90C10 Integer programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/BF01386390 · Zbl 0092.16002 · doi:10.1007/BF01386390
[2] DOI: 10.1007/BF01585001 · Zbl 0253.90032 · doi:10.1007/BF01585001
[3] DOI: 10.1080/02331937908842547 · Zbl 0403.90087 · doi:10.1080/02331937908842547
[4] DOI: 10.1016/0024-3795(69)90017-2 · Zbl 0184.23103 · doi:10.1016/0024-3795(69)90017-2
[5] DOI: 10.1007/BF01584659 · Zbl 0256.90037 · doi:10.1007/BF01584659
[6] Haldi J., 25 integer programming test problems 43 (1964)
[7] Hu T.C., Ganzzahlige Programmierung und Netzwerkflüsse (1972)
[8] Nicholson T.A.J., Comp. J 9 pp 275– (1966)
[9] DOI: 10.1080/02331938508843027 · Zbl 0567.90076 · doi:10.1080/02331938508843027
[10] Shapiro J.F., Mathematical programming-structures and algorithms (1979) · Zbl 0502.90054
[11] Terno J., Numerische Verfahren der diskreten Optimierung (1981) · Zbl 0485.90058
[12] DOI: 10.1287/mnsc.15.9.481 · Zbl 0172.22302 · doi:10.1287/mnsc.15.9.481
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.