bchmknap.gms

	[ Home \| Support \| Sales \| Solvers \| Documentation \| Model Library \| Search \| Contact Us ]

bchmknap.gms : Multi knapsack problem using BCH Facility

This multiknapsack problem illustrates the use of user supplied cutting planes
in the GAMS BCH (branch-and-cut-and-heuristic) facility. Please note, that cover
cuts used in this example, are already implemented in modern MIP solvers.

Example taken from the OR-Library
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html
first example in mknap1.

References:

Petersen, C C, Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Science 13 (9) (1967), 736-750.
Linderoth, J, IE418 Lecture Notes - Lecture #19, 2003. Lehigh University, http://www.lehigh.edu/~jtl3/teaching/ie418/lecture19.pdf
Beasley, J E, OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society 41 (11) (1990), 1069-1072.

Small Model of Type: MIP Includes: bchcover.inc

$Title Multi knapsack problem using BCH Facility (BCHMKNAP,SEQ=289) $ontext This multiknapsack problem illustrates the use of user supplied cutting planes in the GAMS BCH (branch-and-cut-and-heuristic) facility. Please note, that cover cuts used in this example, are already implemented in modern MIP solvers. Example taken from the OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html first example in mknap1. Beasley, J E, OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society 41 (11) (1990), 1069-1072. Petersen, C C, Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Science 13 (9) (1967), 736-750. Linderoth, J, IE418 Lecture Notes - Lecture #19, 2003. Lehigh University, http://www.lehigh.edu/~jtl3/teaching/ie418/lecture19.pdf $offtext set j columns /c1*c6/ i rows /r1*r10/ Parameters obj(j) / c1 100, c2 600, c3 1200, c4 2400, c5 500, c6 2000 / rhs(i) / r1 80, r2 96, r3 20, r4 36, r5 44, r6 48, r7 10, r8 18, r9 22, r10 24 /; Table a(i,j) c1 c2 c3 c4 c5 c6 r1 8 12 13 64 22 41 r2 8 12 13 75 22 41 r3 3 6 4 18 6 4 r4 5 10 8 32 6 12 r5 5 13 8 42 6 20 r6 5 13 8 48 6 20 r7 8 r8 3 4 8 r9 3 2 4 8 4 r10 3 2 4 8 8 4 Binary variables x(j) Positive variables slack(i) Variable z; Equations mk(i), defobj; defobj.. z =e= sum(j, obj(j)*x(j)); mk(i).. sum(j, a(i,j)*x(j)) + slack(i) =e= rhs(i); model m /all/; * Export base data execute_unload 'mkdata', j, i, a, rhs; $ifi %system.mip% == cplex $goto cont $ifi %system.mip% == coincbc $goto cont $abort 'BCH Facility not available for MIP solver %system.mip%.' $label cont m.optfile = 1; m.optcr = 0; * We activate the user supplied cut generator and turn all advanced CPLEX options off $onecho > cplex.opt usercutcall bchcover.inc mip=cplex cuts no preind 0 heurfreq -1 mipinterval 1 $offecho $onecho > coincbc.opt usercutcall bchcover.inc mip=coincbc cuts off preprocess off heuristics off $offecho solve m max z using mip;