# Tag Info

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

### 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 ...
• 33.1k
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,471
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 ...
• 13.5k

### 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 ...

### 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: ...
• 33.1k
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 ...
• 33.1k
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,414
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,703
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,471

### 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,884

### 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 ...
• 39.8k

### 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,...
• 984

### 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 ...
• 331
1 vote
Accepted

### choose constraint from IIS to build penalty function

I think that, when selecting constraints to relax (with penalties), you should look at the IIS from the perspective of the final decision maker. Which constraints do they think absolutely must be ...
• 39.8k
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 ...
• 39.8k
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,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 ...
• 313

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