How to correctly formulate multiple constraints to multiple feasible regions into one?

Question

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.

Answer 1

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.

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.