Alternate Optimal Solutions

Sometimes when an optimization model is formulated the model yields a lot of alternate optimal solutions meaning that for the same value of the objective function the model yields multiple value of the non basic or decision variables.

Alternate optimal solutions occur mainly due to some portion of the polyhedron being parallel to the objective function. In such cases all points along the segment of the portion that is parallel to the obj function will be affine transforms and would yield the same value of the obj function.

In a practical situation the implications of this would be that when one is trying to solve a problem of say trying to calculate the maximum profit given the effort to manufacture 10 different products and the total constraint on available labour in the plant. Supposing the problem has 10 decision variables and two constraints. Due to degeneracy explained above it may yield an optimal solution of maximum profit of USD 10000 for multiple combinations of the product mix required to be manufactured in the factory.

In such cases it is very difficult to figure out which production mix to choose as the optimal criterion as there are actually multiple values. The parallel portion of the either the edge of the polyhedron or the hyperplane that connects two planes of an n dimensional polyhedron can be disturbed slightly by tweaking the constraints a little bit.

The constraints in the linear programming model form the boundaries of the polyhedron or the hyper plane of the polyhedron. But just modifying the constraint say from 4*X + 5 * Y < 5 to 4*X + 5 * Y < 5.1 would result in altering the feasible region just little bit, but would cease to produce alternate optimal solutions.

In the same context we can also discuss what forms a feasible convex set and why linear programming problems require the set of constraints to be a convex. The optimal solution to a linear programming formulation is found out by traversing the set of constraints from vertex to vertex. So why does an optimal solution not fall somewhere on an edge that connects two vertices, but only on the vertex?. This is because the feasible set can be visualized as the boundary enforced by constraints. The constraints in a linear programming model would result in a polyhedron /polytope. When this is convex it means that any point connecting the two vertexes does not lie inside and so the extreme solution of the objective function will be necessarily found on the vertex.

Leave a Reply