27
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 ...
11
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 ...
- 28.2k
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 ...
- 3,267
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 ...
- 261
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:
...
- 28.2k
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 ...
- 28.2k
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 ...
- 1,384
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 <...
- 1,538
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 ...
- 3,267
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 ...
- 5,796
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 ...
- 36.4k
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,...
- 959
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 ...
- 321
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 ...
- 2,418
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 ...
- 303
Only top scored, non community-wiki answers of a minimum length are eligible