$ontext


   Quadratic Knapsack Problem

$offtext


$include qkp.inc

alias (i,j);

parameters
  c(i)    'linear costs'
  a(i)    'capacity coefficients -- weights'
  d(i,j)  'quadratic costs'
;
c(i) = data('c',i);
a(i) = data('a',i);
d(i,j) = data(i,j);

set ij(i,j) 'upper triangular';
ij(i,j)$(ord(j)>ord(i))=yes;

binary variables
  x(i)     'main variable'
  xx(i,j)  'products x(i)*x(j). We will relax these variables'
;
variable z 'objective';

* the products can be relaxed.
xx.prior(i,j) = INF;

equations
    obj
    cap
    product1(i,j)
    product2(i,j)
    product3(i,j)
;

obj..  z =e= sum(i,c(i)*x(i))+sum(ij,d(ij)*xx(ij));
cap..  sum(i,a(i)*x(i)) =l= rhs;
product1(ij(i,j)).. xx(i,j) =l= x(i);
product2(ij(i,j)).. xx(i,j) =l= x(j);

* this one is optional:
product3(ij(i,j)).. xx(i,j) =g= x(i)+x(j)-1;

option optcr=0;
model m1 /obj,cap,product1,product2,product3/;
model m2 /obj,cap,product1,product2/;
solve m2 maximizing z using mip;

option x:0;
display x.l;