Description

This model solves the Cardinality Constraint Quadratic Knapsack Problem
(kQKP) using a SDP convexification methods.

The convexification method requires the solution of a semidefinite
program.

Large Model of Type : RMIQCP

Category : GAMS Model library

Main file : kqkpsdp.gms   includes :  50_25.inc

$title SDP Convexifications of the Cardinality Constraint Quadratic Knapsack Problem (KQKPSDP,SEQ=355)

$onText
This model solves the Cardinality Constraint Quadratic Knapsack Problem
(kQKP) using a SDP convexification methods.

The convexification method requires the solution of a semidefinite
program.


Plateau M.C., Reformulations quadratiques convexes pour la
programmation quadratique en variables 0-1. PhD thesis,
Conservatoire National des Arts et Metiers, CEDRIC, 2006.

Guignard, M., Extension to Plateau Convexification Method for
Nonconvex Quadratic 0-1 Programs. Tech. rep., The Wharton School, 2008.

Keywords: relaxed mixed integer quadratic constraint programming, quadratic
          knapsack problem, confexification methods, semidefinite programming
$offText

$onEchoV > kQKP.awk
/^$/ {}  # do nothing for empty lines
!/^$/ {
    if (1==startweight) {
        printf("\nParameter w(i) weigths /\n");
        for (i=1; i<=n; i++) printf("n%d %d\n",i,$i);
        printf("$offDelim\n/\n");
        startweight = 0;
    }
    if (1==startprofit) {
        printf("Table p(i,i) profits \n$onDelim\n");
        for (i=0; i<=n; i++) printf("n%d ",i);
        printf("\n"); startprofit = 2; i=1;
    }
    if (2==startprofit) {
        printf("n%d %s\n",i,$0);
        if (n==i)
            startprofit = 0;
        else
            i++;
    }
    if ($2 == "#n:") {
        n = $1;
        printf("$setGlobal n %d\nset i /n1*n%d/;\n", n, n);
    }
    if ($2 == "#capacity")
        printf("scalar cap capacity /%d/;\n", $1);
    if ($2 == "#k:")
        printf("scalar ncard cardinality /%d/;\n", $1);
    if ($1 == "#Profits:") startprofit = 1;
    if ($1 == "#Weights:") startweight = 1;
}
$offEcho
$if not set instance $set instance 50_25
$call awk -f kQKP.awk %instance%.inc > kQKP%instance%.gms
$ifE errorLevel<>0 $abort problems with awk

Set i 'knapsack items', dummy / z /;

Alias (i,j);

Parameter
   p(i,j) 'profits of item pairs'
   w(i)   'weigths of items'
   cap    'capacity of knapsack'
   ncard  'cardinality of knapsack';

$offListing
$include kQKP%instance%.gms
$onListing

$onText
Setup of SDP problem to get u and v

max sum((i,j), p(i,j)*X(i,j)
s.t. -ncard*x(i) + sum(j, X(i,j)) =e= 0   for all i  (SDP1)
     X(i,i) = x(i)                                   (SDP2)
     sum(i, x(i))      =e= ncard                     (SDP3)
     sum(i, w(i)*x(i)) =l= cap                       (SDP4)
     z                 =e= 1                         (SDP5)

     (X   x)
     (x^t z) is PSD
$offText

Set n 'SDP variables' / 1*%n%, 0 /;
Set ni(n) / 1*%n% /;
Alias(ni, nj);

Set map(ni,i);
map(ni,i)$(ord(ni)=ord(i)) = yes;

Variables
   Xx(n,n)   'PSDMATRIX (X x; x^t z)'
   sdpobjvar
;

Parameter
  sdpp(n,n)  'p(i,j) but indexed over ni and symmetric'
  sdpw(n)    'w(i) but indexed over ni'
;
sdpp(ni,nj) = sum((i,j)$(map(ni,i) and map(nj,j)), p(i,j));
sdpp(ni,nj)$(ord(ni)<ord(nj)) = sdpp(nj,ni);
sdpw(ni) = sum(map(ni,i), w(i));

Equations
   sdpobj   'SDP objective function'
   sdp1(n)  '(SDP1)'
   sdp2(n)  '(SDP2)'
   sdp3     '(SDP3)'
   sdp4     '(SDP4)'
;

sdpobj.. sum((ni,nj), (sdpp(ni,nj)+eps) * Xx(ni,nj)) =E= sdpobjvar + eps*Xx('0','0');

sdp1(ni).. -ncard * (Xx(ni,'0') + Xx('0',ni))/2 + sum(nj, Xx(ni,nj) + Xx(nj,ni))/2 =E= 0;

sdp2(ni).. Xx(ni,ni) =e= (Xx(ni,'0') + Xx('0',ni))/2;

sdp3.. sum(ni, Xx('0',ni) + Xx(ni,'0'))/2 =e= ncard;

sdp4.. sum(ni, sdpw(ni) * (Xx(ni,'0') + Xx('0',ni)))/2 =L= cap;

* (SDP5)
Xx.fx('0','0') = 1;

Model sdp / sdpobj, sdp1, sdp2, sdp3, sdp4 /;
option lp = mosek;
Solve sdp max sdpobjvar using lp;

Parameter a(i), u(i);
a(i) = sum(map(ni,i),sdp1.m(ni));
u(i) = sum(map(ni,i),sdp2.m(ni));

display a, u;

* Simple MIQP model
Binary Variable x(i) 'select item in knapsack';

Variable obj 'objective';

Equation
   defobj  'profit of knapsack'
   defcobj 'profit of knapsack'
   defcap  'capacity limitation of knapsack'
   defcard 'cardinality requirement of knapsack';

defcobj.. obj =e= sum(i, p(i,i)*x(i)) + sum((i,j)$(ord(i) > ord(j)), 2*x(i)*p(i,j)*x(j))
               -  sum(i, a(i)*x(i)*(sum(j, x(j)) - ncard))
               -  sum(i, (u(i) + 0.001)*x(i)*(x(i) - 1));

defobj..  obj =e= sum(i, p(i,i)*x(i)) + sum((i,j)$(ord(i) > ord(j)), 2*x(i)*p(i,j)*x(j));

defcap..  sum(i, w(i)*x(i)) =l= cap;

defcard.. sum(i, x(i)) =e= ncard;

Model
   kQKP  /  defobj, defcap, defcard /
   ckQKP / defcobj, defcap, defcard /;

solve ckQKP max obj using rmiqcp;