8 A 0-1-Quadratic Program (examp-qp01)

Run LPL Code  ,  PDF Document

Problem

The general 0-1-quadratic (convex) programming model – called 0-1-QP – contains n linear constraints and m binary variables and a quadratic convex objective function. It can be compactly formulated as follows (see [11]):

            ∑                ∑
min               xjQj,kxk +      cjxj
           j∑∈J,k∈J             j∈J
subjectto       Ai,j ⋅ xj ≥ bi                      forall i ∈ I
           j∈J

           xj ∈ {0,1}                              forall j ∈ J
           J =  {1...m }, I = {1 ...n}, m, n ≥ 0

An even more compact formulation using matrix notation for the model is :

min        x ⋅ Q ⋅ x′ + c ⋅ x
subjectto  A ⋅ x ≥ b

           x ∈ {0, 1}

Solve this problem – x are unknowns, A, b, and c are given – with n = 15 and m = 15 with the following data:

    (                                                          )
c =  16  73  39  81  68  60  90  11  33  89  71  12  24  23  47

    (                                                           )         (    )
    | 87  34  0   0   43  0   52  85  36  0   0   0   0   0   0 |         |  0 |
    | 0   0   39  0   84  0   0   88  0   0   0   0   0   0   22|         |  0 |
    || 55  63  79  0   0   0   0   71  0   0   0   0   70  0   79||         ||  0 ||
    || 0   0   0   0   0   0   0   73  0   0   0   22  0   0   0 ||         ||  0 ||
    || 0   0   0   66  0   0   34  0   0   24  0   61  0   0   64||         ||  0 ||
    || 0   0   16  19  0   0   0   0   0   0   0   0   0   0   18||         ||  0 ||
    || 15  70  61  0   0   0   0   0   0   0   0   0   0   0   0 ||         ||  0 ||
A = | 0   0   0   0   0   0   0   0   52  0   14  0   0   92  0 |     b = | 58 |
    ||                                                           ||         ||    ||
    || 0   0   0   0   0   0   0   30  0   0   98  0   19  0   0 ||         || 44 ||
    || 0   70  37  0   0   0   0   0   0   0   0   86  0   93  0 ||         ||  0 ||
    || 90  0   82  0   66  0   0   0   0   26  0   0   0   0   0 ||         ||  0 ||
    || 77  30  0   0   0   0   13  10  0   0   0   50  0   0   0 ||         ||  0 ||
    | 0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 |         |  0 |
    |( 0   72  0   0   0   79  0   0   0   0   0   11  90  0   0 |)         |(  0 |)
      0   0   0   0   0   32  55  0   23  0   0   0   0   0   36            119

          (                                                     )
diag(Q) =  7  5  5  6   17  19  6  8  16  19  12  5  13  17   18

The data given above specify the following explicit linear program:

min        7x1x1 +  5x2x2 + 5x3x3 + 6x4x4 + 17x5x5 +  19x6x6
                +6x7x7 +  8x8x8 + 16x9x9 + 19x10x10 + 12x11x11
                +5x   x  + 13x   x  + 17x   x  + 18x   x
                    12 12      13 13      14 14      15 15
                +16x1 +  73x2 + 39x3 + 81x4 + 68x5 + 60x6 +  90x7 + 11x8
                +33x9 +  89x10 + 71x11 + 12x12 + 24x13 + 23x14 + 47x15
subjectto  87x1 + 34x2 +  43x5 + 52x7 + 85x8 + 36x9 ≥  0
           39x3 + 84x5 +  88x8 + 22x15 ≥ 0

           55x1 + 63x2 +  79x3 + 71x8 + 70x13 + 79x15 ≥ 0
           73x8 + 22x12 ≥  0
           66x4 + 34x7 +  24x10 + 61x12 + 64x15 ≥ 0
           16x3 + 19x4 +  18x15 ≥ 0
           15x1 + 70x2 +  61x3 ≥ 0

           52x9 + 14x11 + 92x14 ≥  58
           30x8 + 98x11 + 19x13 ≥  44
           70x2 + 37x3 +  86x12 + 93x14 ≥ 0
           90x1 + 82x3 +  66x5 + 26x10 ≥ 0
           77x  + 30x  +  13x  + 10x  + 50x   ≥ 0
               1      2      7      8      12
           72x2 + 79x6 +  11x12 + 90x13 ≥ 0
           32x6 + 55x7 +  23x9 + 36x15 ≥ 119
           xj ∈ {0,1 }   forall j ∈ {1 ...15}

Modeling Steps

A 0-1-quadratic program (0-1-QP) is a mathematical model that consists of a number (n 0) of linear inequalities in a number (m 0) of binary variables. Furthermore, it defines an quadratic convex objective function that is to be minimized or maximized. The 0-1-QP model has many applications in quantitative decision making. The formulation of the model in LPL modeling language is straightforward and the notation is close to the mathematical notation using indices: First we define the two sets i and j. Then we declare and assign the data as parameters A, c, b, and a semidefinite positive (SDP) matrix Q. The variable vector x is declared, and finally the constraints R and the minimizing objective function obj.

Note that the data matrices A, b, c, and Q are generated using LPL’s own random generator. (To generate each time the same data, the code can also use the function SetRandomSeed(a) where a is an integer.) Note that the unique difference within this model and the QP model (see examp-qp) consists of the word binary in declaration of the variables.


Listing 6: The Complete Model implemented in LPL [10]
model Qp15_01 "A 0-1-Quadratic Program"; 
  set i := [1..15];  j,k := [1..15]; 
  parameter A{i,j}:= Trunc(if(Rnd(0,1)<.25,Rnd(10,100))); 
            c{j}  := Trunc(Rnd(10,100)); 
            b{i}  := Trunc(if(Rnd(0,1)<.15,Rnd(0,120))); 
            Q{j,k}:= Trunc(if(j=k, Rnd(5,20))); //SDP 
  binary variable  x{j}; 
  constraint R{i} : sum{j} A*x >= b; 
  minimize obj    : sum{j} c*x + sum{j,k} x[j]*Q*x[k]; 
  Writep(obj,x); 
end

Solution

The model has the following solution:

    (                                          )
x =  0  0  0  0  0  1  1  1  0  0 0  0  1  1  1

The optimal value of the objective function is:

obj = 336

Further Comments

Interesting applications for the iQP model come from portfolio theory. Especially, if we want to limit the number of assets in a portfolio we must use 0-1 variables. An applications come from clustering problems. An example is bill035.