28 votes
Accepted

Is the Irreducible Infeasible Subset (IIS) of an LP unique?

The irreducible infeasible subsystem (IIS) for an infeasible linear program (LP) is a minimal subset of constraints that has no feasible solution, i.e., an inconsistent set of constraints for which ...
Aleksandr Kazachkov's user avatar
12 votes

Is it possible to identify all possible Irreducible Infeasible Sets (IIS) for an infeasible Integer Linear Programming problem? (ILP)?

Equivalently, you want to remove the smallest number of constraints so that the resulting problem is feasible. You can do this implicitly, without enumerating all Irreducible Infeasible Sets, by ...
RobPratt's user avatar
  • 32k
9 votes
Accepted

Computational complexity to compute an IIS

Finding a minimum-cardinality MIS for a linear program is an NP-hard problem in general, see Edoardo Amaldi, Marc E. Pfetsch, and Leslie E. Trotter Jr. On the maximum feasible subsystem problem, IISs ...
Joris Kinable's user avatar
6 votes
Accepted

Gurobipy MILP model comes infeasible yet can't compute IIS because "the model is feasible"

This model is likely on the borderline between feasibility and infeasibility. The algorithm used to determine feasibility in the solver is different than the algorithm used in IIS, and may reach a ...
Mark L. Stone's user avatar
5 votes

Is the Irreducible Infeasible Subset (IIS) of an LP unique?

An IIS is not unique. Given a system $Ax \le b$, the indices of an IIS are the supports of the vertices of the polyhedron $P=\{y: y^{\top}A=0, \; y^{\top}b \le -1, \; y \ge 0\}$. This is the ...
Hamed Rahimian's user avatar
5 votes

Is there any automatic way to spot contradictory constraints in linear programming?

Shameless plug: I recently gave a webinar on diagnosing infeasibility. Here's what your example looks like in SAS: ...
RobPratt's user avatar
  • 32k
4 votes
Accepted

Minimal infeasible constraint set

In the optimization community, this is called an irreducible infeasible set (IIS), and many solvers support this functionality. The "irreducible" part means that the set is minimal in the ...
RobPratt's user avatar
  • 32k
4 votes
Accepted

How to know which constraint in CP-SAT did not meet the feasibility gap

Not yet, see https://github.com/google/or-tools/issues/973 For debugging I would recommend you to divide your constraints into groups so you can activate/deactivate some of them to pin down the ...
Stradivari's user avatar
  • 1,414
4 votes
Accepted

Compute Irreducible Infeasible Set (IIS) in Pyomo

The Gurobi documentation states how you can compute and inspect the IIS: model.computeIIS() model.write("model.ilp") I am not certain how to call the <...
mattmilten's user avatar
  • 1,643
3 votes
Accepted

How to check infeasibility with conflict refiner (docplex mixed integer programming )?

ILOG Cplex 20.1 installation comes with a directory with examples. To use the conflict refiner, you want to consult the manual which includes a list of files that contain examples on how to use the ...
Joris Kinable's user avatar
3 votes

How to check infeasibility with conflict refiner (docplex mixed integer programming )?

As the docplex documentation says: Given an infeasible model, the conflict refiner can identify conflicting constraints and bounds within it. So, consider you ...
EhsanK's user avatar
  • 5,864
3 votes

How to see constraint violation for network flow problem

There are a number of things you can try. First, the Gurobi output says the lower limit on right-hand side values is 7e-16, rather than zero, which looks a bit suspicious to me. You might want to ...
prubin's user avatar
  • 39.1k
3 votes

How to see constraint violation for network flow problem

Below constraint of flow restriction on an arc need not be summed as it is a restriction at an arc level m.addConstrs( (flow.sum(i, j) <= capacity[i, j] for i, j in arcs), "cap") hence,...
anjikum's user avatar
  • 984
2 votes

How to see constraint violation for network flow problem

The first thing to check: in order for a network flow model to be feasible, the sum of supplies and demands over all nodes must be zero. If you know that test passes, then you can start to find an ...
mjsaltzman's user avatar
1 vote

Cplex no solution but no conflict

Finding a conflict in CPLEX is a two step process. First you have to instruct CPLEX to "refine" the conflict; then you have to ask it for the results (the constraints and variable bounds ...
prubin's user avatar
  • 39.1k
1 vote

How to solve infeasible cplex model in GAMS?

I've not worked with the GAMS/Matlab interface, but iis is a CPLEX option and not a GAMS option. So when you're in GAMS, you just need to put it in a cplex option file (i.e., cplex.opt that is by ...
Ehsan's user avatar
  • 2,463
1 vote
Accepted

How to see constraint violation for network flow problem

Similar to the comment by @prubin I would recommend to create a small scale test problem by providing some simpler csv that you know are feasible. Then you can validate your model. With a valid model ...
Andreas's user avatar
  • 313

Only top scored, non community-wiki answers of a minimum length are eligible