# Linear programming with many variables and parameters

I am trying to reconstruct the answer that is given in this report. (page 153 in Appendix B; Section B.2.1). They are given variables, parameters, constraints, and the objective function to minimize.

Summary of the problem:

Minimize: q01 + q11 + q21 + q31 - q02 - q12 - q22 - q32
Variables: {q00 , q01 , q02 , q03 , q10 , q11 , q12 , q13 ,
q20 , q21 , q22 , q23 , q30, q31 , q32 , q33}
Parameters: {p000 , p010 , p100 , p110 , p001 , p011 , p101 , p111}
Constraints:
1) all q's nonnegative
2) [sum all q's] == 1
3) p000 == q00 + q01 + q10 + q11
4) p010 == q20 + q22 + q30 + q32
5) p100 == q02 + q03 + q12 + q13
6) p110 == q21 + q23 + q31 + q33
7) p001 == q00 + q01 + q20 + q21
8) p011 == q10 + q12 + q30 + q32
9) p101 == q02 + q03 + q22 + q23
10) p111 == q11 + q13 + q31 + q33


Their output is given on page 155 as the maximum of a set of eight linear functions of the parameters:

 Minimum of Objective Function is the Maximum of:
p111 + p000 - 1
p110 + p001 - 1
-p011 - p101
-p010 - p100
p110 - p111 - p101 - p010 - p100
p111 - p110 - p100 - p011 - p101
p001 - p011 - p101 - p010 - p000
p000 - p010 - p100 - p011 - p001


When trying to reproduce it in Mathematica 8.0, first tried simple test case of using parameters

LinearProgramming[{1, 1}, {{1, 2}}, {a}]


which gave an error, but using Minimize does give a full answer

Minimize[x + y, x + 2*y >= a && x >= 0 && y >= 0, {x, y}]


I then rephrased the original problem in terms of Minimize function and even after running overnight it was still thinking:

Minimize[q01 + q11 + q21 + q31 - q02 - q12 - q22 - q32,
q00 + q01 + q02 + q03 + q10 + q11 + q12 + q13 + q20 + q21 + q22 +
q23 + q30 + q31 + q32 + q33 == 1 &&
q00 >= 0 && q01 >= 0 &&
q02 >= 0 && q03 >= 0 && q10 >= 0 && q11 >= 0 && q12 >= 0 &&
q13 >= 0 && q20 >= 0 && q21 >= 0 && q22 >= 0 && q23 >= 0 &&
q30 >= 0 && q31 >= 0 && q32 >= 0 && q33 >= 0 &&
p000 == q00 + q01 + q10 + q11 && p010 == q20 + q22 + q30 + q32 &&
p100 == q02 + q03 + q12 + q13 && p110 == q21 + q23 + q31 + q33 &&
p001 == q00 + q01 + q20 + q21 && p011 == q10 + q12 + q30 + q32 &&
p101 == q02 + q03 + q22 + q23 &&
p111 == q11 + q13 + q31 + q33, {q00, q01, q02, q03, q10, q11, q12,
q13, q20, q21, q22, q23, q30, q31, q32, q33}]


Is there a way for Mathematica (8.0) to reproduce their results? Have a feeling I'm either missing a function that would answer it, or not inputting some restriction or assumption which Mathematica needs. Thank you!

### EDIT

I tried the suggestion of @Anon:

Minimize[{f, constraints}, {q00, q02, ...}]


Minimize[f, constraints, {q00, q01, ...}]


hoping that was the answer. It still was thinking overnight, with no answer produced. Is Minimize the correct function to use for this problem?

(Originally posted in StackOverflow, first response recommended posting the question here)

-
The syntax is Minimize[{f,constraints},{q00,q02...}] and it looks like you wrote Minimize[f,constraint,{q00,q01...}]. –  Pickett Jul 28 '13 at 14:59
@Anon Thanks for the correction. However, when I tried that procedure it still did not produce an answer, even after thinking overnight. –  sheppa28 Jul 29 '13 at 11:40
I'm not much good with these things but I'd like to help if I can. Could you provide an example smaller than the main one but larger than Minimize[x + y, x + 2*y >= a && x >= 0 && y >= 0, {x, y}] that can be solved by Minimize? –  Mr.Wizard Jul 29 '13 at 11:55
@sheppa28 If one removes all constraints but the first, q00 + q01 + q02 + q03 + q10 + q11 + q12 + q13 + q20 + q21 + q22 + q23 + q30 + q31 + q32 + q33 == 1, Minimize quickly returns "The minimum is not attained at any point satisfying the given constraints." Piling on more constraints isn't helping I suppose, maybe it's taking so long because there are lots of combinations to try and no correct answer. (IDK any about this, I just put this to you for consideration.) –  Pickett Jul 29 '13 at 13:10
Note the problem is not solvable for "arbitrary" parameters, for one thing all p must obviously be > 0. Its likely getting bogged down generating massive lists of conditional results for different p cases. Adding all pxx>=0 to the system might help.. –  george2079 Jul 30 '13 at 19:54

LinearProgramming will work but you need the values for the parameters as it is not a symbolic algorithm.

Constructing the parameters for LinearProgramming will give:

c = Flatten@{{1, 0, -1, 0}, {0, 1, -1, 0}, {0, 1, -1, 0}, {0, 1, -1, 0}};


This corresponds to the minimisation problem. I use the matrix form and then flatten to assist with translating. The left-hand side of the constraints in the same order as you have present will give:

m =
{
ConstantArray[1, 16],
Flatten@{{1, 1, 0, 0}, {1, 1, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}},
Flatten@{{0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {1, 0, 1, 0}},
Flatten@{{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}},
Flatten@{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 1, 0, 1}, {0, 1, 0, 1}},
Flatten@{{1, 1, 0, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}},
Flatten@{{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}},
Flatten@{{0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 1, 1}, {0, 0, 0, 0}},
Flatten@{{0, 0, 0, 0}, {0, 1, 0, 1}, {0, 0, 0, 0}, {0, 1, 0, 1}}
};


The right-hand side of the constraints is where you need values for the algorithm to compute. I've chosen some values that will work for all but the first constraint. I hand to change the first constraint from == 1 to >= 1 to demonstrate that it works. You need the actual values from the constraints to get the intended result since LinearProgramming is not a symbolic algorithm.

p000 = 0.9; p010 = 0.8; p100 = 0.7; p110 = 0.6;
p001 = 0.5; p011 = 0.6; p101 = 0.8; p111 = 0.9;
b = {{1, 1}, {p000, 0}, {p010, 0}, {p100, 0}, {p110, 0},
{p001, 0}, {p011, 0}, {p101, 0}, {p111, 0}};


This will solve but as I don't have the actual values to the parameters and had to change the first constraint from == to >= the result vector sums to 3 instead of 1.

LinearProgramming[c, m, b]
(* {0., 0.3, 0.7, 0., 0., 0.6, 0., 0., 0.2, 0.2, 0., 0.1, 0., 0., 0.6, 0.3} *)
Total[%]
(* 3 *)


This returns immediately; no overnight wait. I suspect that if you get the actual parameter values (and change the first constraint back to == by changing the {1,1} to {1,0} in b) that it would solve equally as fast.

Hope this helps

-

Removing the >= 0 constrains solves the problem

q00 >= 0 && q01 >= 0 &&
q02 >= 0 && q03 >= 0 && q10 >= 0 && q11 >= 0 && q12 >= 0 &&
q13 >= 0 && q20 >= 0 && q21 >= 0 && q22 >= 0 && q23 >= 0 &&
q30 >= 0 && q31 >= 0 && q32 >= 0 && q33 >= 0 &&


-

Minimize[{q01 + q11 + q21 + q31 - q02 - q12 - q22 - q32,

q00 + q01 + q02 + q03 + q10 + q11 + q12 + q13 + q20 + q21 + q22 +
q23 + q30 + q31 + q32 + q33 == 1 &&
p000 - q00 - q01 - q10 - q11 == 0 &&
p010 - q20 - q22 - q30 - q32 == 0 &&
p100 - q02 - q03 - q12 - q13 == 0 &&
p110 - q21 - q23 - q31 - q33 == 0 &&
p001 - q00 - q01 - q20 - q21 == 0 &&
p011 - q10 - q12 - q30 - q32 == 0 &&
p101 - q02 - q03 - q22 - q23 == 0 &&
p111 - q11 - q13 - q31 - q33 == 0
},
{q00, q01, q02, q03, q10, q11, q12, q13, q20, q21, q22, q23, q30, q31, q32, q33}]


results in

-
Removing the >= constraints does solve the run-time problem, but the answers do not match. Is there a way to reconstruct their answer? (Given above in original question under "Minimum of Objective Function is the Maximum of:") On a side note, when all the p's are specified numerically Mathematica does give the correct numerical answer, along with what the q's equal. I am trying to reproduce the parametric solution given in the original paper. –  sheppa28 Jul 29 '13 at 16:48