17
$\begingroup$

Sometimes, when solving mathematical optimization models (especially MIPs), they may be infeasible. Is there any comprehensive method to deal with the infeasibility conditions? (especially in complex models)

$\endgroup$
  • 5
    $\begingroup$ Maybe you should clarify: is the problem really infeasible (so you want a good solution as close as possible to feasibility, as in many practical cases), or the model is buggy and you want to correct it? In both cases, adding penalties through slack variables can help. $\endgroup$ – Matteo Fischetti Aug 9 at 5:20
  • 1
    $\begingroup$ @Matteo Fischetti, Kevin Dalmeijer, Dipayan Banerjee, EhsanK, Geoffrey Brent, Oguz Toragay, Many thanks for all the useful answers. Please, let me know how we could figure out the causes of the infeasibility before solving the model? Is there any way? $\endgroup$ – A.Omidi Aug 10 at 4:25
  • $\begingroup$ Without specific problem knowledge, I think the most practical way to detect infeasibility is to just start solving the model. Why are you interested in a different way? $\endgroup$ – Kevin Dalmeijer Aug 12 at 8:21
17
$\begingroup$

Adding slack variables (with high penalty in the objective function) converts hard constraint into soft ones, and can also be useful to locate the source of infeasibility. This approach can be very useful for feasible problems for which finding a heuristic feasible solution is hard/very time consuming.

$\endgroup$
  • 1
    $\begingroup$ I would like to add a word of warning. If choose a HUGE penalty instead of reasonable you easily creates numerical problems. This is very common issue I think all solve guys/girls have seen. $\endgroup$ – ErlingMOSEK Aug 15 at 11:30
15
$\begingroup$

CPLEX offers the conflict refiner for this purpose:

A conflict is a set of mutually contradictory constraints and bounds within a model. Given an infeasible model, IBM ILOG CPLEX can identify conflicting constraints and bounds within it. CPLEX refines an infeasible model by examining elements that can be removed from the conflict to arrive at a minimal conflict. A conflict smaller than the full model may make it easier for the user to analyze the source of infeasibilities in the original model.

Taken from the CPLEX documentation.

$\endgroup$
14
$\begingroup$

Some methods I've used - most of these have already been discussed in other answers, but I wanted to elaborate a little on these. Ordered roughly in the order that I would try to apply these, which is of course influenced by the kind of problems that I work on.

1. Confirm specification of constraints by testing against a "known feasible" solution (as mentioned by @EhsanK).

In my own experience, and in almost every OR project I've heard about from other practitioners, it's very unusual that clients will be able to specify the rules perfectly on their first attempt. It's just a very difficult thing to do, especially for people who aren't familiar with OR programming. Sometimes you'll find that rules presented as hard constraints are actually soft constraints, or have exceptions that haven't been included in the specs.

If your client is able to provide an example of what they consider to be a satisfactory solution, testing it against your understanding of the rules is a very effective way to discover misunderstandings and mis-specifications.

As well as being pretty straightforward to code (assuming that your client can provide an example of a feasible solution), this approach is often easy to communicate to clients. If I produce an IIS and discover that the problem lies somewhere in this set of $500$ constraints, that will be very hard for clients to interpret. If I can say "hi, this example solution that you gave me breaks this rule that you said I needed to include, what gives?" that's a lot easier for the client to understand and address.

2. Build up the model one rule at a time and test as often as possible.

This is a good idea in almost any area of programming. The faster you detect new bugs, the easier it is to figure out the causes.

3. Eyeball infeasibility diagnostics and look for obvious matches in inputs.

I mostly work via AMPL. When it detects infeasibility in presolve, it will usually give information on the size of that infeasibility - "upper bound $-67$, lower bound $0$" sort of thing. Quite often I can find the cause of the infeasibility by scanning the inputs for values that match the size of that gap; for instance, I might have a value that has been constrained to be non-positive but also to be equal to $67$.

This is by no means a foolproof approach, but it's quick and easy to do, so I'll often give it a try before going to more systematic methods.

4. Ersatz/manual IIS methods

Experiment with switching off constraints selectively and attempting solves, to figure out which rules are incompatible with one another. Again, this is not as systematic as using proper IIS methods, but it's often easier to do/interpret, and it can be used with solvers that don't have IIS capability.

5. Automated IIS methods (as mentioned by @dxb and @KevinDalmeijer).

Some solvers have the capability to automatically identify a set of conflicting constraints. This is a useful capability but I tend to de-prioritise it because much of my experience has been with problems where the IIS's tend to be large and tedious to interpret, so I like to try other methods first. YMMV.

When I do use this approach, if I have a large IIS, I try to look for commonalities between the constraints - for instance, if my variables are indexed $i,j,k$ and the IIS constraints have different values for $i$ and $k$ but all have the same $j$-value, that's probably where I want to look first.

Note: some products can get in the way of IIS methods. For instance, when I use Gurobi via AMPL, it's possible that AMPL presolve will detect an infeasibility before it ever passes the problem to Gurobi. In this case, I can't use Gurobi's IIS capability because Gurobi never sees the problem. The solution here is to switch off presolve.

6. Slack methods (as mentioned by @MatteoFischetti).

One thing I'd add to Matteo's advice is that the shape of the penalty function will affect the information that you get from this approach.

Suppose I have a system of constraints like:

\begin{align}C_1&: x \le 5\\C_2&: y \le 5\\C_3&: x+y \ge 13\\&\cdots\end{align}

If my penalty function is linear, then most likely the solution I get will only use slack from one of these three constraints, e.g. $x=8$, $y=5$. Looking at the results, I can then see that $C_1$ is involved in the infeasibility, but I can't easily tell what else is involved.

If my penalty function is quadratic, OTOH, then I will usually get a solution that uses slack from all constraints involved in the infeasibility. In this case, if I weight all three slack variables equally - and if I switch off the non-penalty components of the objective function - I will get the solution $x=6$, $y=6$, which violates each of the constraints by exactly 1. This makes it much easier to see all the constraints involved in the infeasibility by scanning the slack values. It can even help to identify and distinguish multiple groups of incompatible constraints in a single run - e.g. if I have three constraints that end up with a slack value of $1.33333$ and two others that end up with slack of $2.5$, these probably form two separate groups of incompatible constraints, something that I can't identify from an IIS method without multiple runs.

Obviously this requires that you have a solver that can handle quadratic objectives, or alternately that you construct a piecewise linear approximation to a quadratic penalty function.

This can be quite a nice method; I only put it below the others because it's a little bit more work to program.

$\endgroup$
11
$\begingroup$

On top of getting IIS from the solver and using slack variables (as suggested by other answers), one more thing that you can do for debugging purposes is to fix your variables to a known feasible solution and see what is reported from your model. Doing that, you can figure out what has happened to make the problem infeasible.

For example, assume you have $x_1 +x_2 = 10$ constraint and a known feasible solution is $x_1 = 6, x_2 = 2$, you can see the infeasibility and the constraint that throws the infeasibility.

$\endgroup$
  • 2
    $\begingroup$ This is one of the best ways. I did it too. $\endgroup$ – A.Omidi Aug 10 at 4:27
10
$\begingroup$

Related to @Kevin Dalmeijer's answer, Gurobi offers Irreducible Inconsistent Subsystem functionality via Model.computeIIS():

Compute an Irreducible Inconsistent Subsystem (IIS). An IIS is a subset of the constraints and variable bounds with the following properties:

  • the subsystem represented by the IIS is infeasible, and

  • if any of the constraints or bounds of the IIS is removed, the subsystem becomes feasible.

Note that an infeasible model may have multiple IISs. The one returned by Gurobi is not necessarily the one with minimum cardinality; there may exist others with fewer constraints or bounds.

$\endgroup$
4
$\begingroup$

Here is a good (but a little bit old) paper1 discussing the algorithmic approaches to identify and manage the infeasibility situation in MIPs and IPs.


Reference

[1] Guieu, Olivier, and John W. Chinneck. "Analyzing infeasible mixed-integer and integer linear programs." INFORMS Journal on Computing 11.1 (1999): 63-77.

$\endgroup$

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.