Linear Programming When There is No Feasible Solution

Iwan Munro


Supervised by Richard Booth; Moderated by Jose Camacho Collados

Many real-life industrial problems can be expressed as linear programs (LPs) (sometimes with huge numbers of decision variables and constraints). It is usually assumed that there is at least one feasible solution, but sometimes due to manual error in formulating the problem there might be no feasible solution. In this case what is needed is some way to automatically pinpoint these errors (e.g. finding some minimal set of infeasible constraints) so the industrial partner can correct them, or even some way to automatically correct the errors themselves.

This project will look at some ways to pinpoint errors and possibly repair LPs that have no feasible solutions. Methods may be implemented on real benchmark LPs, using eg python libraries or dedicated software such as Gurobi.

Initial Plan (03/02/2020) [Zip Archive]

Final Report (15/05/2020) [Zip Archive]

Publication Form