5
$\begingroup$

Is it possible/likely for a mixed integer linear solver (CBC in my case) to incorrectly state that a problem is infeasible when in fact it is actually feasible?

Are there properties of the model that could exacerbate this? For example, large numbers.

I'm asking because I'm solving a number of very similar models and some of them are being flagged as infeasible when I don't think they are.

$\endgroup$
7
$\begingroup$

It is quite likely that this happens. Numerical difficulties (large and small numbers or a large range of numbers in the problem) can cause this, they can lead to the simplex algorithm failing to identify the feasibility of a node (often even the root node) correctly. If it is the root node before adding cuts that is infeasible, it can help to run IIS (I am not sure that is available for CBC/CLP).

Sometimes presolve or cuts can lead to a problem being marked infeasible although it is not. If turning off presolver or cuts results in any solution being found this is typically a good indicator that the problem is indeed feasible and the default result is wrong (due to a bug somewhere or numerical issues).

All that said, feasibility in a MILP solver is always "within tolerance". Sometimes a problem can only be made feasible by slightly violating integrality, bounds or constraints. Then things get tricky. Feasible or infeasible is not always an easy decision.

$\endgroup$
2
$\begingroup$

Yes, solvers can sometimes render infeasibility even when you expect feasible solutions to exist. This is despite dependent on the nature of the problem is in general expected to be encountered not very often. There are a couple of likely reasons when this can happen:

  1. Numerical Issue. The solver was not able to bring the solution inside the feasible region within tolerances.
  2. Bad Starting Point. Your starting point is not carefully chosen and the solver terminates within an infeasible solution regime.
$\endgroup$
2
$\begingroup$

We observed the same problem when working with CPLEX. During Presolve, CPLEX somehow identifies the problem as infeasible. We couldn't figure out the actual reason, but it was the same problem (except some model parameters) we solve on daily basis.

What was interesting is that disabling Presolve resolved the issue for that particular case and CPLEX could solve the problem.

$\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.