Skip to main content
Computational Science

Return to Answer

added 35 characters in body
Source Link
Brian Borchers
Brian Borchers
  • 19k
  • 1
  • 40
  • 70

For debugging purposes, it's helpful to identify small subsets of infeasible constraints in an LP formulation- an Irreducible Infeasible Subset (IIS) is a subset of the constraints that are infeasible and such that removing any constraint from the IIS results in a feasible set of constraints. This is doable in polynomial time and fairly fast in practice, but it is not the same as finding a maximum feasible subsystem.

This problem of finding a maximum subset of feasible constraints in an infeasible LP is NP-Hard. See

Amaldi, Edoardo, Marc E. Pfetsch, and Leslie E. Trotter Jr. "On the maximum feasible subsystem problem, IISs and IIS-hypergraphs." Mathematical Programming 95, no. 3 (2003): 533-554.

For debugging purposes, it's helpful to identify small subsets of infeasible constraints in an LP formulation- an Irreducible Infeasible Subset (IIS) is a subset of the constraints that are infeasible and such that removing any constraint from the IIS results in a feasible set of constraints. This is doable in practice, but it is not the same as finding a maximum feasible subsystem.

This problem of finding a maximum subset of feasible constraints in an infeasible LP is NP-Hard. See

Amaldi, Edoardo, Marc E. Pfetsch, and Leslie E. Trotter Jr. "On the maximum feasible subsystem problem, IISs and IIS-hypergraphs." Mathematical Programming 95, no. 3 (2003): 533-554.

For debugging purposes, it's helpful to identify small subsets of infeasible constraints in an LP formulation- an Irreducible Infeasible Subset (IIS) is a subset of the constraints that are infeasible and such that removing any constraint from the IIS results in a feasible set of constraints. This is doable in polynomial time and fairly fast in practice, but it is not the same as finding a maximum feasible subsystem.

This problem of finding a maximum subset of feasible constraints in an infeasible LP is NP-Hard. See

Amaldi, Edoardo, Marc E. Pfetsch, and Leslie E. Trotter Jr. "On the maximum feasible subsystem problem, IISs and IIS-hypergraphs." Mathematical Programming 95, no. 3 (2003): 533-554.

Source Link
Brian Borchers
Brian Borchers
  • 19k
  • 1
  • 40
  • 70

For debugging purposes, it's helpful to identify small subsets of infeasible constraints in an LP formulation- an Irreducible Infeasible Subset (IIS) is a subset of the constraints that are infeasible and such that removing any constraint from the IIS results in a feasible set of constraints. This is doable in practice, but it is not the same as finding a maximum feasible subsystem.

This problem of finding a maximum subset of feasible constraints in an infeasible LP is NP-Hard. See

Amaldi, Edoardo, Marc E. Pfetsch, and Leslie E. Trotter Jr. "On the maximum feasible subsystem problem, IISs and IIS-hypergraphs." Mathematical Programming 95, no. 3 (2003): 533-554.