Solution methods for MaxFS

Here are some of the methods used to solve MaxFS.

### Elastic programming

Heuristic based on Elastic programming (Chinneck 2001).

### Dynamic IIS generation

Partial IIS (Irreducible Infeasible Subsystem) covering formulation with dynamic IIS generation (Parker & Ryan 96)

### LP with equilibrium constraints

Formulations as LP with equilibrium constraints and concave minimization on polyhedra tackled by successive linearizations (Mangasarian et al. 94/96, Bennett et al. 97)

First branch-and-cut algorithm (Pfetsch 02/05) based on polyhedral study in Amaldi et al. 03.

### Combinatorial Benders' cuts

Combinatorial Benders' cuts (Codato & Fischetti 04).

### Feasopt (Cplex)

The Feasopt feature in Ilog Cplex: an infeasibility analysis tool that "...accepts an infeasible model and selectively relaxes the bounds and constraints, minimizing a [user defined] weighted penalty function."

### Relaxation method

It is a simple algorithmic framework for solving systems of linear inequalities, see e.g. [11,22]. At every iteration the attention is focused on reducing the violation of a single inequality. Given a feasible system with and , as well as a starting point , such a method generates a sequence of approximate solutions. [more...]