# Speedup of reduce function?

I tried to run this $15$ variable feasibility linear programming to see what the solution looks like. Unfortunately it is taking too much time on my laptop. Is there a way to speed it up? Any tips will help.

  Reduce[{0 <= a <= 1, 0 <= b <= 1, 0 <= c <= 1, 0 <= d <= 1,
0 <= e <= 1, 0 <= f <= 1, a + b + c == d + e + f == 2,
0 <= k <= Min[a, d], 0 <= l <= Min[a, e],
0 <= m <= Min[a, f], 0 <= p <= Min[b, d],
0 <= q <= Min[b, e], 0 <= r <= Min[b, f],
0 <= s <= Min[c, d], 0 <= t <= Min[c, e],
0 <= u <= Min[c, f],
l + m + k + p + q + r + s + t + u == 4}, {a, b, c, d, e, f, k, l, m,
p, q, r, s, t, u}]

• There is a specific function LinearProgramming. – Andrew Apr 11 '18 at 8:28
• Why do you want reduce to rewrite the conditions that defines the feasible region? What's the problem with those you wrote? – Coolwater Apr 11 '18 at 9:14

The conditions of

Reduce[{
a + b + c == 2,
d + e + f == 2,
0 <= k <= Min[a, d, (a + d)/2],
0 <= l <= Min[a, e, (a + e)/2],
0 <= m <= Min[a, f, (a + f)/2],
0 <= p <= Min[b, d, (b + d)/2],
0 <= q <= Min[b, e, (b + e)/2],
0 <= r <= Min[b, f, (b + f)/2],
0 <= s <= Min[c, d, (c + d)/2],
0 <= t <= Min[c, e, (c + e)/2],
0 <= u <= Min[c, f, (c + f)/2],
l + m + k + p + q + r + s + t + u == 4}, {a, b, c, d, e, f, k, l, m, p, q, r, s, t, u}]


translate to conditions with the forms matrix.var ≥ vec, matrix.var = vec and
matrix.var ≤ vec with the following matrices and vectors

(* Greater than 0 *)
mat1 = PadLeft[IdentityMatrix[{9, 15}][[;; 9, ;; 9]], {9, 15}];
vec1 = ConstantArray[{0, 1}, 9];

(* Equal to 2 *)
mat2 = PadRight[{{1, 1, 1, 0, 0, 0}, {0, 0, 0, 1, 1, 1}}, {2, 15}];
vec2 = ConstantArray[{2, 0}, 2];

(* Equal to 4 *)
mat3 = {Join[{0, 0, 0, 0, 0, 0}, ConstantArray[1, 9]]};
vec3 = {{4, 0}};

(* Less than inequalities *)
With[{kToU = PadLeft[IdentityMatrix[{9, 15}][[;; 9, ;; 9]], {9, 15}],
aToC = PadRight[ArrayFlatten[Evaluate[DiagonalMatrix[{#, #, #}]] &[{{1}, {1}, {1}}]], {9, 15}],
def = Join[#, #, #] &[PadRight[RotateLeft[IdentityMatrix[{3, 6}], {0, 3}], {3, 15}]]},
mat4 = Join[kToU - aToC, kToU - def, kToU - (aToC + def)/2]];
vec4 = ConstantArray[{0, -1}, 27];


and the remaining inequalites are

varMinMax = PadRight[ConstantArray[{0, 1}, 6], 15, {{-∞, ∞}}];


To minimize a linear combination of the variables, evaluate this code:

LinearProgramming[RandomReal[{-2, 2}, 15],
Join[mat1, mat2, mat3, mat4],
Join[vec1, vec2, vec3, vec4],
varMinMax]

• is it quick now? Also I am not minimizing (I am doing feasibility). – Turbo Apr 11 '18 at 9:05
• How is the output to be interpreted? – Turbo Apr 11 '18 at 9:06
• Sorry could you comment where exactly are you doing inequalities? – Turbo Apr 11 '18 at 9:11
• @Turbo I construct a matrix and a vector such that matrix.vars ≥ vec are the same inequalities as those you wrote. What I call vec is actually n,2-dimensional. The second column indicates whether the LHS (mat.vars) should be less, equal of greater than the RHS (first column of vec). – Coolwater Apr 11 '18 at 9:18
• it works I am just trying to understand your code so I can generalize it. you dont use matrix.var ≥ vec in code. What does join do? some kind of implicit inequality? BTW the o/p is pretty fast. – Turbo Apr 11 '18 at 9:22