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;