Description
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.
Small Model of Type : MIP
Category : GAMS Model library
Main file : bchmknap.gms 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 - Integer Programming Lecture Notes - Lecture #15, 2005.
University of Wisconsin-Madison,
http://homepages.cae.wisc.edu/~linderot/classes/ie418/lecture15.pdf
Keywords: mixed integer linear programming, knapsack problem, branch and cut
and heuristic facility
$offText
Set
j 'columns' / c1*c6 /
i 'rows' / r1*r10 /;
Parameter
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 Variable x(j);
Positive Variable slack(i);
Variable z;
Equation 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;
$ifThenI %system.mip% == cplex $set solver cplex
$else
$abort 'BCH Facility not available for MIP solver %system.mip%.'
$endIf
m.optFile = 1;
m.optCr = 0;
* We activate the user supplied cut generator and turn all advanced CPLEX options off
$onEcho > %solver%.opt
userCutCall bchcover.inc mip = %solver%
cuts no
preInd 0
heurFreq -1
mipInterval 1
$offEcho
solve m max z using mip;