1
$\begingroup$

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}]
$\endgroup$
  • 2
    $\begingroup$ There is a specific function LinearProgramming. $\endgroup$ – Andrew Apr 11 '18 at 8:28
  • 1
    $\begingroup$ Why do you want reduce to rewrite the conditions that defines the feasible region? What's the problem with those you wrote? $\endgroup$ – Coolwater Apr 11 '18 at 9:14
2
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ is it quick now? Also I am not minimizing (I am doing feasibility). $\endgroup$ – Turbo Apr 11 '18 at 9:05
  • $\begingroup$ How is the output to be interpreted? $\endgroup$ – Turbo Apr 11 '18 at 9:06
  • $\begingroup$ Sorry could you comment where exactly are you doing inequalities? $\endgroup$ – Turbo Apr 11 '18 at 9:11
  • $\begingroup$ @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). $\endgroup$ – Coolwater Apr 11 '18 at 9:18
  • $\begingroup$ 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. $\endgroup$ – Turbo Apr 11 '18 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.