5
$\begingroup$

I have an optimization problem that looks something like this:

Maximize[{1+x+3*y,0<=x<=1 && x+2*y<=4},{x,y}]

Now, I want to use Linear Programming to solve this problem, assuming this is more efficient.

Unfortunately, Linear Programming has a different interface, looking something like this:

1 - LinearProgramming[{-1, -3}, {{1, 2}}, {{4, -1}}, {{0, 
 1}, {-Infinity, Infinity}}].{-1, -3}

By hand, I do the following main steps for this translation:

  • Determine constraints and translate this to bounds
  • Extract constant offset of objective function (in this case, the offset is 1)
  • Translate maximization problem into a minimization problem

Does Mathematica provide support to automate this transformation? In order words, what is the simplest way to do this transformation (automatically)?


A partial solution:

I think that if I would know how to do the following transitions, I could solve my problem:

x+4*y-z      -> {1,4,-1}
x+2*y<=z     -> {1,2,-1}
x+2*y+10<=4  -> -6

These transitions correspond to extracting factors before variables and to collecting constants.

$\endgroup$
  • 1
    $\begingroup$ "Translate maximization problem into a minimization problem" -at least this part is easy: maximization of an objective function is the same as minimizing the negation of the same objective function. $\endgroup$ – J. M. is in limbo Sep 26 '17 at 15:50
  • 2
    $\begingroup$ For the coefficients, a modification of Normal[CoefficientArrays[{x + 4*y - z == 0, x + 2*y == z}, {x, y, z}]] ought to be useful. $\endgroup$ – J. M. is in limbo Sep 26 '17 at 16:39
  • 4
    $\begingroup$ This does not give the transformed problem, but you could use the internal function TryLinearProgramming which provides an interface similar to Minimize: -Optimization`LinearProgramming`TryLinearProgramming[ Null, -(1 + x + 3*y), {0 <= x <= 1, x + 2*y <= 4}, {x, y}][[1, 1]]. $\endgroup$ – tom Sep 26 '17 at 17:46
  • 1
    $\begingroup$ @Peter I'll write something up in a few hours, although I'm hoping someone will actually write a function that can transform the arguments of Maximize. $\endgroup$ – tom Sep 27 '17 at 8:08
3
$\begingroup$

Although this unfortunately does not provide one with the actual transformation of the arguments to Maximize/Minimize, one work-around could be to use the internal function TryLinearProgramming. This function handles arguments similar to Minimize:

Optimization`LinearProgramming`TryLinearProgramming[
  Null, 
  -(1 + x + 3*y), 
  {0 <= x <= 1, x + 2*y <= 4}, 
  {x, y}
]

(*{{-7, {x -> 0, y -> 2}}}*)

TryLinearProgramming is called from e.g. Optimization`NonlinearInteriorPoint, see GeneralUtilities`PrintDefinitions[Optimization`NonlinearInteriorPoint], from which we can learn how to use it. Looking in particular at GeneralUtilities`PrintDefinitions[Optimization`NonlinearInteriorPointDump`NonlinearInteriorPointCore], we note that TryLinearProgramming has (at least) five arguments: caller (a symbol to which generated messages are attached), f (the function that is optimized), consin (the constraints), varsin (the variables), and prec (the precision of the output, which is an optional argument that defaults to Infinity). Options[Optimization`LinearProgramming`TryLinearProgramming] and Options[LinearProgramming] are identical, and some experimentation teaches us that these options can be supplied in a list as an optional sixth argument.

The output of TryLinearProgramming is a list res whose length should not exceed one (I haven't figured out what kind of input would actually produce longer lists), and res[[1]] can be either the solution to the linear program in the same form as produced by Maximize/Minimize, or a failure reason that is handled by Optimization`NonlinearInteriorPointDump`checkReasonForFailure. Putting everything together, we can write a new function MinimizeLP which acts as an interface to TryLinearProgramming:

MinimizeLP::usage = StringReplace[StringJoin[StringRiffle[StringSplit[Minimize::usage, "\n"][[{3, 5}]], "\n"]], "Minimize" -> "MinimizeLP"];

MinimizeLP::infea = "No solution can be found that satisfies the constraints.";
MinimizeLP::elem = "The constraints, `1`, contain element type constraints that are not supported.";
MinimizeLP::error = "TryLinearProgramming failed.";
MinimizeLP::malf = "The constraints, `1`, are malformed. This may be, for example, because the constraints do not form equalities or inequalities.";
MinimizeLP::nlin = "Either the constraints, `2`, or the objective function, `1`, contain nonlinear terms.";
MinimizeLP::uneq = "The constraints, `1`, contain unequal type constraints that are not supported.";

Options[MinimizeLP] = Options[LinearProgramming];

MinimizeLP[{f_, cons_}, vars_List, dom_: Reals, opts : OptionsPattern[]] := Module[
  {prec = Infinity, res},

  res = Optimization`LinearProgramming`TryLinearProgramming[
    LinearProgramming, f, cons, vars, prec, FilterRules[{opts}, LinearProgramming]
  ];

  If[Length[res] > 1, Message[MinimizeLP::error]; Return[$Failed]];

  res = First[res];

  res = If[

     ListQ[res],

     res,

     Switch[First[res],

       "CouldNotHandleUnequalConstraints",
       Message[MinimizeLP::uneq, cons];
       $Failed,

       "CouldNotHandleElementConstraints",
       Message[MinimizeLP::elem, cons];
       $Failed,

       "MalformedConstraints",
       Message[MinimizeLP::malf, cons];
       $Failed,

       "NotLinear",
       Message[MinimizeLP::nlin, f, cons];
       $Failed,

       "NotReal",
       Message[MinimizeLP::nreal, f, cons];
       $Failed,

       "NoFeasiblePoints",
       Message[MinimizeLP::infea];
       $Failed,

       _,
       Message[MinimizeLP::error];
       $Failed

     ]

   ];

   res /; res =!= $Failed

 ];

Additional definitions should be added to copy the behavior of Minimize for other argument patterns.

The maximization problem posed in the question can then be solved following the comment by J.M. as follows:

MapAt[Minus, MinimizeLP[{-(1 + x + 3*y), 0 <= x <= 1 && x + 2*y <= 4}, {x, y}], 1]

(*{7, {x -> 0, y -> 2}}*)

A MaximizeLP function can easily be created by incorporating these two negations in MinimizeLP.

Finally I suppose TryLinearProgramming also allows integer linear programming, but I'm not sure how to invoke this. Note that TryLinearProgramming is an undocumented function, so the usual caveats apply.

$\endgroup$
3
$\begingroup$

If you use FindMaximum instead of Maximize, then you can force FindMaximum to use LinearProgramming with the Method option:

FindMaximum[{1+x+3*y, 0<=x<=1 && x+2*y<=4}, {x,y}, Method->"LinearProgramming"]

{7., {x -> 0., y -> 2.}}

$\endgroup$
  • 1
    $\begingroup$ Nice! Can this approach be used to obtain arbitrary-precision results like in Maximize and LinearProgramming? (I'm not sure if this is a requirement for the op.) $\endgroup$ – tom Sep 27 '17 at 14:51
  • 1
    $\begingroup$ @tom, for arbitrary precision, just increase WorkingPrecision as needed. For exact... not sure. $\endgroup$ – J. M. is in limbo Sep 27 '17 at 15:06
  • $\begingroup$ Thanks for the hint! Unfortunately, I am interested in exact results, so I cannot apply this. But it may be useful for others! $\endgroup$ – Peter Sep 28 '17 at 6:36
  • 2
    $\begingroup$ @Peter Maximize with Method -> "LinearProgramming" gives you exact results $\endgroup$ – Coolwater Sep 28 '17 at 7:06

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.