5
$\begingroup$

Consider the following:

FindMinimum[
   {t, 2x + y + 2 < t && -x - 2y + 3 < t && -3x + y < t && 2x - 3y < t},
   {t, x, y},
   Method -> "LinearProgramming"
]
(* {1.93333, {t -> 1.93333, x -> -0.4, y -> 0.733333}} *)

Using the syntax of the LinearProgramming function would be much more concise when there are many inequalities. How do we convert the above to the syntax needed for the Mathematica LinearProgramming function?

Improve this question
$\endgroup$
6
$\begingroup$

Taking your variables in the order {t, x, y}, you can rewrite your constraints as follows, which makes it easier (at least for me) to turn them into matrix form (as shown in comments for each line):

t - 2 x -   y > 2    (* {1, -2, -1} *)
t +   x + 2 y > 3    (* {1,  1,  2} *)
t + 3 x -   y > 0    (* {1,  3, -1} *)
t - 2 x + 3 y > 0    (* {1, -2,  3} *)

Then your target function $t$ is represented by coefficients {1, 0, 0} in the variables {t, x, y}, respectively.

With this, you can write:

LinearProgramming[
  {1, 0, 0},
  {{1, -2, -1},
   {1,  1,  2},
   {1,  3, -1},
   {1, -2,  3}},
  {2, 3, 0, 0}, 
  None
]

(* Out: {29/15, -(2/5), 11/15} *)

The result above is exact, because exact coefficients were provided, but of course it is numerically the same as the one reported by FindMinimum.

Improve this answer
$\endgroup$
9
$\begingroup$

LinearOptimization can accept the objective and constraints in this form

LinearOptimization[t, {2 x + y + 2 < t, -x - 2 y + 3 < t, 
                       -3 x + y < t, 2 x - 3 y < t}, {t, x, y}]

(* {t -> 29/15, x -> -(2/5), y -> 11/15} *)

 N[%]

(* {t -> 1.93333, x -> -0.4, y -> 0.733333} *)

and it can also convert them to the matrix formulation, for example

obj = LinearOptimization[t, {2 x + y + 2 < t, -x - 2 y + 3 < t, 
      -3 x + y < t, 2 x - 3 y < t}, {t, x, y}, "ObjectiveVector"]

(* {1, 0, 0} *)

{a, b} = Normal @ LinearOptimization[t, {2 x + y + 2 < t, -x - 2 y + 3 < t, 
      -3 x + y < t, 2 x - 3 y < t}, {t, x, y}, "LinearInequalityConstraints"]

(* {{{1, -2, -1}, {1, 1, 2}, {1, 3, -1}, {1, -2, 3}}, {-2, -3, 0, 0}} *)

Of course it is possible to feed these into LinearOptimization:

 LinearOptimization[obj, {a, b}]

 (* {29/15, -(2/5), 11/15} *)

or into LinearProgramming:

 LinearProgramming[obj, a, -b, None]

 (* {29/15, -(2/5), 11/15} *)

but in general LinearOptimization is the more modern and flexible function.

Improve this answer
$\endgroup$
1
$\begingroup$

A proper meaningful insight can be gained by graphical representation of the problem:

With[{t = 1.9333}, 
 Show[RegionPlot[
   2 x + y + 2 < t && -x - 2 y + 3 < t && -3 x + y < t && 
    2 x - 3 y < t, {x, -4, 4}, {y, -4, 4}], 
  Plot[t - 2 x - 2, {x, -4, 4}, PlotStyle -> Orange], 
  Plot[ (-t - x + 3)/2, {x, -4, 4}, PlotStyle -> Blue], 
  Plot[ t + 3 x, {x, -4, 4}, PlotStyle -> Gray], 
  Plot[ (-t + 2 x)/3, {x, -4, 4}, PlotStyle -> Pink]]]

graphical solution

This is not so satisfying. One constraint is obsolete and may be removed without affecting the solution.

So the problem is equivalent to determine the crossing of the three other boundaries given. Then the enclosed area of the three lines bounded area is zero.

The problem posed here fulfills the conditions named in the Mathematica documentation tutorial Linear Programming. It can be solved therefore both with FindMinimum and LinearProgramming.

Since the pink-colored boundary is irrelevant the problem reduces to 

FindMinimum[{t, 
  2 x + y + 2 < t && -x - 2 y + 3 < t && -3 x + y < t}, {t, x, y}, 
 Method -> "LinearProgramming"]

this can be formulated equivalent in

LinearProgramming[{1, 0, 0}, {{1, -2, -1}, {1, 1, 2}, {1, 3, -1}}, {2,
   3, 0}, None]

The graphic representation saves time and effort.

(* Out: {29/15, -(2/5), 11/15} *)

If the t-value is altered in the RegionPlot a real region appears for t>29/15 and an error is posed for smaller values. The solution is a point in the case of the three value solution. It is a region for bigger values. So this give insight into the solution of the linear programming problem. With this point, a region emerges in which real solutions exist. This is the smallest set of solutions all other included infinite many points, a region.

That is the solution to the linear programming problem here, not the point alone.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ I do not see how this addresses the question that was raised in the original post. $\endgroup$
    – Daniel Lichtblau
    Apr 16 '20 at 23:39
  • $\begingroup$ This addresses real certain this very passage: " much more concise when there are many inequalities". Since it does not make concise calculations whether some of the many conditions, boundary restrictions are of use, important or redundant or impossible to be fulfilled. The posed problem has a solution only for three of the linear conditions. It poses critiques a hint on how to optimize Mathematica for meaningful, concise numerical answers, results. Of course, this is no probe. It poses a receipt on how to avoid the problems that fall through the numerical methods of 'LinearProgramming'. $\endgroup$
    – Steffen Jaeschke
    Apr 20 '20 at 17:39
  • $\begingroup$ It is restricted to two and three dimensions and requires human intervention. In practice LPs can have superfluous constraints, and, depending on application, attempting to remove them might or might not be a good use of program run time. But this would need to be done in an automated manner for large problems. In any case I am fairly certain the question was how to use LinearProgramming with its more concise (than NMinimize and FindMinimum) notation, not how to graphically detect superfluous inequalities. $\endgroup$
    – Daniel Lichtblau
    Apr 20 '20 at 22:57

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.