The feasopt algorithm

This section provides a short overview of the feasopt algorithm provided by CPLEX®.

The CPLEX feasopt algorithm takes as input a CPLEX model and a list of constraints and penalties within the model. It then tries to solve the model in two phases:

1. When you call feasopt, each constraint that has the form:

   lower-bound <= expr <= upper-bound

   is rewritten in the form:

   lower-bound <= expr + x+ - x- <= upper-bound

   where x+ and x- are both positive decision variables.

   CPLEX then attempts to solve the problem with these additional slack variables and with

   minimize the sum of a*x+ + b*x-

   as the objective (a and b are the penalties).

   At the end of this phase, CPLEX has (if possible) a feasible solution of the problem that minimizes the "violation penalty".

2. CPLEX puts a max constraint on the sum of slack variables equal to the value of the objective at the end of the previous phase.

   It then reruns the solve with the real objective of the problem.

In short, feasopt allows CPLEX to solve a problem that is objectively infeasible or may be infeasible by first trying to relax the constraints as little as possible to make the problem feasible, and then trying to optimize the objective of the problem.