0
$\begingroup$

I believe this is a linear programming question that basically boils down to correctly formulating a feasible regions constraints from OR statements between other feasible regions.

My direct question relates to the following 3 feasible regions. I believe I have the feasible region already constructed properly but my question is whether there is a way to combine them.

F.R. 1 -

0 < X1 < 11,

0 < X2 < 6

OR

F.R. 2 -

0 < X1 < 6,

0 < X2 < 11

OR

F.R. 3 -

X1 < 11,

X2 < 11

X2 >= -X1 + 17

Geometrically this is a rectangular feasible region with a infeasible triangular region inside.

Again, want to know what would be the best way to formulate the constraints together on into one feasible region, if possible, without using ORs or is this not possible?

Thanks.

$\endgroup$
  • $\begingroup$ No. Editing Now. $\endgroup$ – eccadena Nov 3 '19 at 19:43
  • $\begingroup$ Done. Thank you @EricTowers $\endgroup$ – eccadena Nov 3 '19 at 19:45
0
$\begingroup$

Linear programming expects to get a convex feasible region, so there's no way to do this with a single LP.

A better way to do what you want to do: optimize on the interior of your excluded triangle, obtaining $x_1$ as the optimal point. Then use $x_1$ as the initial point for optimization inside the allowed rectangle together with the constraint that the objective must be $\geq$ the value of the objective at $x_1$. (This additional constraint prevents any motion back into the excluded triangle and means you can drop/ignore all of the excluded triangle constraints.)

A picture might help.

Mathematica graphics

Suppose the feasible optimum is in (on the boundary of, but I'm not going to type that every time) the green region. Then $x_1$ is on the green boundary of the triangle and the second stage will take it to the feasible optimum. Similarly if the optimum is in the orange or blue regions -- the first stage will give $x_1$ on the boundary between the feasible region and the infeasible triangle and the second stage will take the optimum through that region to the global optimum.

This sort of thing can be generalized to several interior exclusions: when the next step in the simplex algorithm would take one into an excluded region, switch to solving in that region until the next pivot would take you out of that region, then return to the external region. Note that every time you find a better optimum, you can add a new constraint "new points at least as good as this point" and drop all now redundant constraints.

$\endgroup$
  • $\begingroup$ Interesting. Thank you for your response. $\endgroup$ – eccadena Nov 3 '19 at 19:48
  • $\begingroup$ What about usage of binary relationships (If... then or either/or) and functionally adding another variable to y with some large number M such that the constraint is satisfied? I have formulated past problems with this notation but that was when we were imposing and either/or on constraints for one feasible region. I am unsure, again, if this is possible between three FRs. Thanks! $\endgroup$ – eccadena Nov 3 '19 at 23:13
  • $\begingroup$ @eccadena : This would seem to require as a first step, decomposition of a nonconvex polyhedron into a collection of disjoint convex polyhedra. Then you would have a subsystem of variables for determining which member of the collection the current simplex step is in as well as a bunch of constraints for each of member of the collection that are useless when you are not in their hull, but which has to be updated for simplex steps. It sounds like burning much time and memory during the LP solver. (continued...) $\endgroup$ – Eric Towers Nov 3 '19 at 23:39
  • $\begingroup$ @eccadena : Also, exact convex decomposition is a somewhat difficult problem. Even in 2d and 3d. Even available code to do this is troublesome. It appears to me that much less time or memory is wasted by optimizing in each exclusion, picking the optimal of those points, using the "better than the starting point constraint", then LP solving in the convex hull + that constraint. $\endgroup$ – Eric Towers Nov 3 '19 at 23:44

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.