kqkpsdp.gms : SDP Convexifications of the Cardinality constraint Quadratic Knapsack Problem

Description

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

The convexification method requires the solution of a semidefinite
program. The communication with the SDP solver is done through ASCII
files.
```

Small Model of Type : RMIQCP

Category : GAMS Model library

Main file : kqkpsdp.gms   includes :  runcsdp.inc  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 confexification methods.

The convexification method requires the solution of a semidefinite
program. The communication with the SDP solver is done through ASCII
files.

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)

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

CSDP gets the problem in SDPA format:

(D)    max tr(F0*Y)
st  tr(Fi*Y) = ci           i = 1,2,...,m
Y >= 0
\$offText

Set
n          / z,#i /
m          / k1*k%n%, i1*i%n%, ncard, cap, zdef /
mk(m)      / k1*k%n% /
mi(m)      / i1*i%n% /
mkmap(m,i) / #mk:#i  /
mimap(m,i) / #mi:#i  /;

Parameter
c(m)     'rhs'
F(m,*,*) 'constraint matrix'
F0(*,*)  'objective term'
mLE(m)   'SDP constraints with =l='
xvec(m)  'dual solution';

F0(i,j)\$(ord(i) > ord(j)) = p(i,j);
F0('z',i)                 = p(i,i)/2;

* SDP1
F(mk,'z',i)\$mkmap(mk,i) = -ncard;
F(mk,i,j)\$mkmap(mk,i)   =  1 + 1\$sameas(i,j);
c(mk)                   =  0;

* SDP2
F(mi,'z',i)\$mimap(mi,i) = -1.0;
F(mi,i,i)\$mimap(mi,i)   =  2;
c(mi)                   =  0;

* SDP3
F('ncard','z',i) = 1.0;
c('ncard')       = 2*ncard;

* SDP4
F('cap','z',i) = w(i);
c('cap')       = 2*cap;
mLE('cap')     = yes;

* SDP5
F('zdef','z','z') = 1;
c('zdef')         = 1;

execute_unload 'csdpin.gdx' n, m, mLE, c, F, F0;
execute 'gams runcsdp.inc lo=%gams.lo% --strict=1';
abort\$errorLevel 'Problems running RunCSDP. Check listing file for details.';

Parameter a(i), u(i);
a(i) = sum(mkmap(mk,i), xvec(mk));
u(i) = sum(mimap(mi,i), xvec(mi));

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, 2*a(i)*x(i)*(sum(j, x(j)) - ncard))
-  sum(i, 2*(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;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170