Solution methods for MaxFS

[ Home | People | Papers | Software | Instances | Links ]

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 $ A{\bf x}
\geq {\bf b}$ with $ A \in \mathbb{R}^{m \times n}$ and $ {\bf b} \in \mathbb{R}^m$, as well as a starting point $ {\bf x}_0\in\mathbb{R}^n$, such a method generates a sequence $ \bigl({\bf x}_i\bigr)_\mathbb{N}\subset\mathbb{R}^n$ of approximate solutions. [more...]
This page is maintained by Pietro Belotti.