Thursday, August 9, 2018

The best way to debug infeasible models

Well, there is no universally best way. But one approach I like to suggest is: use (or construct) a known feasible solution and fix decision variables. This approach is not often mentioned. Most algorithm suppliers say: just use IIS [1]. In my opinion (and based on experience), fixing is often more reliable: it will pin-point infeasible constraints. In addition, fixing is conceptually much simpler than looking at IIS output. The results of fixing does not require much explanation. Sometimes lo-tech is better than hi-tech [2].

Example: a transportation problem


Let's use a simple transportation problem as an example: \[\bbox[lightcyan,10px,border:3px solid darkblue]{\begin{align}\min&\sum_{i,j} c_{i,j} x_{i,j}\\ & \sum_i x_{i,j} \ge d_j& \forall j&\text{  (demand)}\\ & \sum_j x_{i,j} \le s_i& \forall i&\text{  (supply)}\\  &x_{i,j} \ge 0\end{align}}\]
The data looks like:


----     45 PARAMETER c  transport cost

             new-york     chicago      topeka

seattle         0.225       0.153       0.162
san-diego       0.225       0.162       0.126


----     45 PARAMETER d  demand at market j

new-york 325.000,    chicago  300.000,    topeka   275.000


----     45 PARAMETER s  capacity of plant i

seattle   350.000,    san-diego 600.000

When we deal with infeasibilities, we can ignore the objective: this will never have a role. So in the data above, we don't need to worry about parameter \(c\).

A feasible solution is easily constructed:

Feasible solution
Let's create a bug: assume somehow \(s_i\) arrived incorrectly at 80% of the current values. I.e.


---     70 PARAMETER s  capacity of plant i

seattle   280.000,    san-diego 480.000

The model is now infeasible. The reason is the total supply is too small to meet total demand.

The GAMS equation listing will show the individual equations (before solving):


---- demand  =G=  satisfy demand at market j

demand(new-york)..  x(seattle,new-york) + x(san-diego,new-york) =G= 325 ; (LHS = 0, INFES = 325 ****)
     
demand(chicago)..  x(seattle,chicago) + x(san-diego,chicago) =G= 300 ; (LHS = 0, INFES = 300 ****)
     
demand(topeka)..  x(seattle,topeka) + x(san-diego,topeka) =G= 275 ; (LHS = 0, INFES = 275 ****)
     

---- supply  =L=  observe supply limit at plant i

supply(seattle)..  x(seattle,new-york) + x(seattle,chicago) + x(seattle,topeka) =L= 280 ; (LHS = 0)
     
supply(san-diego)..  x(san-diego,new-york) + x(san-diego,chicago) + x(san-diego,topeka) =L= 480 ; (LHS = 0)

This is a useful listing to look at. The initial values for the variables are zero here, so the demand equations are infeasible at the initial point. The supply constraints are feasible at the initial point. It is noted that the variables are always feasible with respect to their bounds. GAMS makes sure the variable levels are always within their bounds at this initial point.

One good way to prevent even to pass the model on to the solver is to add a data check:
abort$(sum(i,s(i)) < sum(j,d(j)) - 0.01) "Supply too small for demand";
Let's see what solvers do with this infeasible model. I'll try three different approaches:

  • Solve as is, and see how different solver report a solution for this infeasible model. We'll see there is little uniformity.
  • Run with IIS (Irreducible Infeasible Set). This is often advised as good tool to inspect and diagnose infeasibilities. I am usually less successful when using this approach.
  • Fix decision variables to a known feasible solution, and see what is reported. This is often my preferred approach.

Solve and look at the solution


The best solution will minimize the sum of the infeasibilities (this sum is 140) and properly mark the infeasible rows and columns. Let's see how the solver do on this.

Cplex



---- EQU demand  satisfy demand at market j

                LOWER          LEVEL          UPPER         MARGINAL

new-york       325.0000       325.0000        +INF            0.2250      
chicago        300.0000       300.0000        +INF            0.1530      
topeka         275.0000       275.0000        +INF            0.1260      

---- EQU supply  observe supply limit at plant i

                 LOWER          LEVEL          UPPER         MARGINAL

seattle          -INF          280.0000       280.0000         EPS         
san-diego        -INF          620.0000       480.0000          .     INFES

---- VAR x  shipment quantities in cases

                          LOWER          LEVEL          UPPER         MARGINAL

seattle  .new-york          .           -20.0000        +INF             .     INFES
seattle  .chicago           .           300.0000        +INF             .          
seattle  .topeka            .              .            +INF            0.0360      
san-diego.new-york          .           345.0000        +INF             .          
san-diego.chicago           .              .            +INF            0.0090      
san-diego.topeka            .           275.0000        +INF             .          

**** REPORT SUMMARY :        0     NONOPT
                             2 INFEASIBLE (INFES)
                    SUM        160.0000
                    MAX        140.0000
                    MEAN        80.0000
                             0  UNBOUNDED

We see there are two reported infeasibilities. One of them is an infeasible variable. Interestingly, this is not the solution with the minimum phase 1 objective (i.e. minimum sum of infeasibilities). Here we have a total infeasibility of 160 while the optimal phase 1 objective is 140.

MINOS, CONOPT


A proper minimum phase 1 solution with a total infeasibility of 140 is reported by MINOS and Conopt:


---- EQU demand  satisfy demand at market j

                LOWER          LEVEL          UPPER         MARGINAL

new-york       325.0000       325.0000        +INF            0.0039      
chicago        300.0000       300.0000        +INF            0.0039      
topeka         275.0000       135.0000        +INF            0.0039 INFES

---- EQU supply  observe supply limit at plant i

                 LOWER          LEVEL          UPPER         MARGINAL

seattle          -INF          280.0000       280.0000        -0.0039      
san-diego        -INF          480.0000       480.0000        -0.0039      

---- VAR x  shipment quantities in cases

                          LOWER          LEVEL          UPPER         MARGINAL

seattle  .new-york          .              .            +INF            EPS         
seattle  .chicago           .           145.0000        +INF             .          
seattle  .topeka            .           135.0000        +INF             .          
san-diego.new-york          .           325.0000        +INF             .          
san-diego.chicago           .           155.0000        +INF             .          
san-diego.topeka            .              .            +INF            EPS         


**** REPORT SUMMARY :        0     NONOPT
                             1 INFEASIBLE (INFES)
                    SUM        140.0000
                    MAX        140.0000
                    MEAN       140.0000
                             0  UNBOUNDED
                             0     ERRORS

In both cases the solver distributes infeasibilities in a way that is unrelated to the original problem: we see a demand equation is marked  (while both supply equations are the real culprit here).

Gurobi


---- EQU demand  satisfy demand at market j

                LOWER          LEVEL          UPPER         MARGINAL

new-york       325.0000          .            +INF           -1.0000      
chicago        300.0000          .            +INF           -1.0000      
topeka         275.0000          .            +INF           -1.0000      

---- EQU supply  observe supply limit at plant i

                 LOWER          LEVEL          UPPER         MARGINAL

seattle          -INF             .           280.0000         1.0000      
san-diego        -INF             .           480.0000         1.0000      

---- VAR x  shipment quantities in cases

                          LOWER          LEVEL          UPPER         MARGINAL

seattle  .new-york          .              .            +INF             .          
seattle  .chicago           .              .            +INF             .          
seattle  .topeka            .              .            +INF             .          
san-diego.new-york          .              .            +INF             .          
san-diego.chicago           .              .            +INF             .          
san-diego.topeka            .              .            +INF             .          


**** REPORT SUMMARY :        0     NONOPT
                             0 INFEASIBLE
                             0  UNBOUNDED

This is just a bogus solution: all levels are zero. Infeasibilities are not properly marked. The number and sum of infeasibilities is also wrong.

The conclusion must be: many solvers do not do a good job of returning a proper phase 1 solution that minimizes the sum of the infeasibilities. I always find this somewhat disappointing. I like to know what the minimum sum of infeasibilities is: the size can give a clue about the source of the infeasibilities.

IIS: Irreducable Infeasible Set


Many modern solvers have a facility to use an  IIS (Irreducable Infeasible Set) algorithm [3] to return groups of equations such that when one equation is removed thit set of equations becomes feasible.

Here is the IIS reported by Gurobi:


LP status(3): Model was proven to be infeasible.
Computing IIS...
An IIS is a set equations and variables (ie a submodel) which is
infeasible but becomes feasible if any one equation or variable bound
is dropped.

A problem may contain several independent IISs but only one will be
found per run.
Number of equations in the IIS: 5
demand(new-york) > 325
demand(chicago) > 300
demand(topeka) > 275
supply(seattle) < 280
supply(san-diego) < 480
Number of variables in the IIS: 0

Cplex gives the same thing:

Minimal conflict found.

A conflict is a set equations and variables (ie a submodel) which is
infeasible but becomes feasible if any one equation or variable bound
is dropped.

A problem may contain several independent conflicts but only one will be
found per run.

Number of equations in the conflict:  5.
lower: demand(new-york) > 325
lower: demand(chicago) > 300
lower: demand(topeka) > 275
upper: supply(seattle) < 280
upper: supply(san-diego) < 480

Number of variables in the conflict:  0.


The IIS set has all constraints of the model. This actually means: if we drop any of the constraints of our model, the resulting model will be feasible. Well, that is interesting, but it does not bring me closer to the conclusion that the supply capacities are wrong.

Fixing: the best approach for this problem


The best approach is to fix the variable to our feasible solution. In GAMS, we can do this with:

table solx(i,j)
              
new-york       chicago        topeka
  
seattle       325
  
san-diego                    300            275
;
x.fx(i,j) = solx(i,j);

The equation listing tells us exactly what is wrong:


---- demand  =G=  satisfy demand at market j

demand(new-york)..  x(seattle,new-york) + x(san-diego,new-york) =G= 325 ; (LHS = 325)
     
demand(chicago)..  x(seattle,chicago) + x(san-diego,chicago) =G= 300 ; (LHS = 300)
     
demand(topeka)..  x(seattle,topeka) + x(san-diego,topeka) =G= 275 ; (LHS = 275)
     

---- supply  =L=  observe supply limit at plant i

supply(seattle)..  x(seattle,new-york) + x(seattle,chicago) + x(seattle,topeka) =L= 280 ; (LHS = 325, INFES = 45 ****)
     
supply(san-diego)..  x(san-diego,new-york) + x(san-diego,chicago) + x(san-diego,topeka) =L= 480 ;
     
      (LHS = 575, INFES = 95 ****)

The initial point with the fixed levels for the variables, yields infeasibilities for the supply equation. The solver will also pinpoint a single infeasibility in the log:

Infeasibility row 'supply(seattle)':  0 <= -45.
Only one infeasibility is reported here, This is because the presolver handled this. When a presolver finds the model is infeasible most often it can produce a good message, but it will only report one infeasibility. The infeasiblity is reported as 0 <= -45. This is a bit less clear than we want. Basically the left-hand side of the inequality x(seattle,new-york) + x(seattle,chicago) + x(seattle,topeka) \(\le\) 280 has become empty as all variables are replaced by their fixed values. The constants are moved to the right-hand side. The constraint is therefore re-interpreted as \(0 \le 280 - 325 = -45\). This is clearly infeasible.

Note:
However, the presolver can also lead to the dreaded: 
Model was proven to be either infeasible or unbounded. 
The solver puts premium on minimization of its time. One could say, the real problem a solver solves is: minimize the time spent on solving the problem. In case of this message, the problem to find out whether the model is really unbounded or infeasible is off-loaded to the user. In my opinion, the users time is more valuable, so the solver should spent a little bit of extra time to figure out if the problem is actually infeasible or unbounded.
GAMS can do a more strict test when we add the model setting holdfixed=1. This will make all fixed variables constants, just like parameters. When we do:

transport.holdfixed=1;
solve transport using lp minimizing z;

we'll see:


**** Exec Error at line 62: Equation infeasible due to rhs value

**** INFEASIBLE EQUATIONS ...

---- supply  =L=  observe supply limit at plant i

supply(seattle)..  0 =L= -45 ; (LHS = 0, INFES = 45 ****)
     
supply(san-diego)..  0 =L= -95 ; (LHS = 0, INFES = 95 ****)

In this case the model is not even passed on to the solver.

Some notes on fixing:

  • Often you don't need to fix all variables in a model. Just fixing the central variables may be enough: the other variables can be calculated from them in an unambiguous way. If you only fix a few central variables, you need to rely on the solver messages to pinpoint the infeasibility. As the initial point is not complete, we cannot rely on the GAMS equation listing.
  • Make sure you don't destroy any bounds on the variables. 
  • Bounds can play an important role in the model being infeasible.
  • This method also works when the problem is integer infeasible (but LP feasible).

An elastic formulation


If you want to protect your models against infeasibilities, it may help to formulate an elastic version. This means that you allow to violate constraints, but at a cost. In other words: convert hard constraints into soft ones. For example, a manpower constraint can be made elastic by allowing to hire temporary workers (at a higher cost).

An elastic formulation would make the problem always feasible. We can make the supply equations elastic by allowing to oversupply beyond our capacity. E.g. by outsourcing and supplying from other suppliers at a high cost. Such a formulation can look like: \[\begin{align}\min&\sum_{i,j} c_{i,j} x_{i,j} +  C_e \sum_ i e_i\\ & \sum_i x_{i,j} \ge d_j& \forall j&\text{  (demand)}\\ & \sum_j x_{i,j} \le s_i+e_i& \forall i&\text{  (supply)}\\  &x_{i,j} \ge 0, e_i \ge 0\end{align}\] Note that we only add slacks to the supply equation. This is enough to make the model always feasible. We don't need to make the demand equation also elastic. When we solve this elastic model we see:

                           LOWER          LEVEL          UPPER         MARGINAL

---- EQU cost2               .              .              .             1.0000      

  cost2  new objective: add cost extra supply

---- EQU demand  satisfy demand at market j

                LOWER          LEVEL          UPPER         MARGINAL

new-york       325.0000       325.0000        +INF          999.2250      
chicago        300.0000       300.0000        +INF          999.1530      
topeka         275.0000       275.0000        +INF          999.1260      

---- EQU supply2  allow for extra supply

                 LOWER          LEVEL          UPPER         MARGINAL

seattle          -INF          280.0000       280.0000      -999.0000      
san-diego        -INF          480.0000       480.0000      -999.0000      

---- VAR x  shipment quantities in cases

                          LOWER          LEVEL          UPPER         MARGINAL

seattle  .new-york          .           120.0000        +INF             .          
seattle  .chicago           .           300.0000        +INF             .          
seattle  .topeka            .              .            +INF            0.0360      
san-diego.new-york          .           205.0000        +INF             .          
san-diego.chicago           .              .            +INF            0.0090      
san-diego.topeka            .           275.0000        +INF             .          

---- VAR e  extra supply

                 LOWER          LEVEL          UPPER         MARGINAL

seattle            .           140.0000        +INF             .          
san-diego          .              .            +INF            EPS         

                           LOWER          LEVEL          UPPER         MARGINAL

---- VAR tc                -INF       140013.6750        +INF             .          

  tc  total cost


**** REPORT SUMMARY :        0     NONOPT
                             0 INFEASIBLE
                             0  UNBOUNDED

I used a unit cost of \(C_e=999\) for this extra supply. Observe that we added 140 units of expensive, extra supply.  Obviously this number is the same as the optimal phase 1 objective reported earlier by Minos and Conopt.

Conclusion


If you know (or can construct) a feasible point, fixing variables to this point is an extremely useful tool to find out what caused the problem to be infeasible. Of course, constructing a feasible solution is not always easy, so this method is not suited for all cases. For other models it may be surprisingly easy to generate a feasible solution. For instance, for a machine scheduling model, just order jobs by their release date on a single machine.

The GAMS output for different solvers is unfortunately difficult to interpret: some of the output is contradictory, and output is spread around in log and listing files. Solvers are not very consistent in what they report. Depending on whether the presolver or the solver itself detects infeasibilities, the reporting may be totally differently. This is all somewhat messy.

Some solvers like to report a Farkas certificate of infeasibility [4]. There are very enthusiastic proponents of this approach. I think it is fair to say that not all users are quite comfortable with this type of reporting. When a feasible solution is available, fixing, to me, still looks simpler and more accurate.

Finally I want to mention that unbounded models are easier to debug. Just put a bound on the objective, e.g.: \[\begin{align}\min\>&z \\ & z = c^Tx \\ &  z \ge -1000000\\ &Ax=b \\ & \ell \le x \le u\end{align}\] and inspect the solution to for large (negative) values.

References


  1. encountering INFEASIBLE status in Gurobi Matlab interface, https://stackoverflow.com/questions/51743892/encountering-infeasible-status-in-gurobi-matlab-interface
  2. K best solutions for an assignment problem, https://yetanothermathprogrammingconsultant.blogspot.com/2018/04/k-best-solutions-for-assignment-problem.html
  3. O. Guieu and J.W. Chinneck (1999), "Analyzing Infeasible Mixed-Integer and Integer Linear Programs", INFORMS Journal on Computing, vol. 11, no. 1, pp. 63-77.
  4. Erling D. Andersen, How to use Farkas’ lemma to say something important about infeasible linear problems, https://docs.mosek.com/whitepapers/infeas.pdf