CPXXfeasopt and CPXfeasopt

The routine CPXXfeasopt/CPXfeasopt computes a minimum-cost relaxation of the righthand side values of constraints or bounds on variables in order to make an infeasible problem feasible.

int CPXXfeasopt( CPXCENVptr env, CPXLPptr lp, double const * rhs, double const * rng, double const * lb, double const * ub )

int CPXfeasopt( CPXCENVptr env, CPXLPptr lp, double const * rhs, double const * rng, double const * lb, double const * ub )

Description

The routine CPXXfeasopt/CPXfeasopt computes a minimum-cost relaxation of the righthand side values of constraints or bounds on variables in order to make an infeasible problem feasible. The routine also computes a relaxed solution vector that can be queried with CPXXsolution and CPXsolution, CPXXgetcolinfeas and CPXgetcolinfeas for columns, CPXXgetrowinfeas and CPXgetrowinfeas for rows, CPXXgetsosinfeas and CPXgetsosinfeas for special ordered sets.

If CPXXfeasopt/CPXfeasopt finds a feasible solution, it returns the solution and the corresponding objective in terms of the original model.

Tip:

If you call CPXXgetobjval and CPXgetobjval after phase one of CPXXfeasopt/CPXfeasopt, it accesses the total infeasibility computed (not necessarily a feasible objective).

This routine supports several options for the metric used to determine what constitutes a minimum-cost relaxation. These options are specified by the parameter that controls the mode of FeasOpt (CPXPARAM_Feasopt_Mode) which can take the following values:

CPX_FEASOPT_MIN_SUM 0
CPX_FEASOPT_OPT_SUM 1
CPX_FEASOPT_MIN_INF 2
CPX_FEASOPT_OPT_INF 3
CPX_FEASOPT_MIN_QUAD 4
CPX_FEASOPT_OPT_QUAD 5

It can minimize the weighted sum of the penalties for relaxations (denoted by SUM).
It can minimize the weighted number of relaxed bounds and constraints (denoted by INF).
It can minimize the weighted sum of the squared penalties of the relaxations (denoted by QUAD).

This routine can also optionally perform a secondary optimization (denoted by OPT in the name of the option), where it optimizes the original objective function over all possible relaxations for which the relaxation metric does not exceed the amount computed in the first phase. These options are specified by the parameter that controls the mode of FeasOpt (CPXPARAM_Feasopt_Mode). Thus, for example, the value CPX_FEASOPT_MIN_SUM denotes that CPXXfeasopt/CPXfeasopt should find a relaxation that minimizes the weighted sum of relaxations. Similarly, the value CPX_FEASOPT_OPT_INF specifies that CPXXfeasopt/CPXfeasopt should find a solution that optimizes the original objective function, choosing from among all possible relaxations that minimize the number of relaxed constraints and bounds.

If you use INF mode, the resulting feasopt problems will be MIPs even if your problem is continuous. Similarly, if you use QUAD mode, the feasopt problems will become quadratic even if your original problem is linear. This change in problem type can result in higher than expected solve times.

The user can specify preferences associated with relaxing a bound or righthand side value through input values of the rhs, rng, lb, and ub arguments. The input value denotes the user's willingness to relax a constraint or bound. More precisely, the reciprocal of the specified preference is used to weight the relaxation of that constraint or bound. For example, consider a preference of p on a constraint that is relaxed by 2 units. The penalty of this relaxation will be 1/p when minimizing the weighted number of infeasibilities; the penalty will be 2/p when minimizing the weighted sum of infeasibilities; and the penalty will be 4/p when minimizing the weighted sum of the squares of the infeasibilities. The user may specify a preference less than or equal to 0 (zero), which denotes that the corresponding constraint or bound must not be relaxed.

To determine whether CPXXfeasopt/CPXfeasopt found relaxed values to make the problem feasible, call the routine CPXXsolninfo and CPXsolninfo for continuous problems or CPXXgetstat and CPXgetstat for any problem type. CPXXsolninfo/CPXsolninfo will return a value of CPX_NO_SOLN for the argument solntype_p if CPXXfeasopt/CPXfeasopt could not find a feasible relaxation. Otherwise, it will return one of the following, depending on the value of the parameter that controls the mode of FeasOpt (CPXPARAM_Feasopt_Mode):

CPX_STAT_FEASIBLE_RELAXED_SUM
CPX_STAT_OPTIMAL_RELAXED_SUM
CPX_STAT_FEASIBLE_RELAXED_INF
CPX_STAT_OPTIMAL_RELAXED_INF
CPX_STAT_FEASIBLE_RELAXED_QUAD
CPX_STAT_OPTIMAL_RELAXED_QUAD

For a MIP problem, the routine CPXXgetstat and CPXgetstat will return a value of CPXMIP_INFEASIBLE or CPX_STAT_INFEASIBLE if it could not find a feasible relaxation. Otherwise, it will return one of the following, depending on the value of the parameter that controls the mode of FeasOpt (CPXPARAM_Feasopt_Mode):

CPXMIP_FEASIBLE_RELAXED_SUM
CPXMIP_OPTIMAL_RELAXED_SUM
CPXMIP_FEASIBLE_RELAXED_INF
CPXMIP_OPTIMAL_RELAXED_INF
CPXMIP_FEASIBLE_RELAXED_QUAD
CPXMIP_OPTIMAL_RELAXED_QUAD

The routine CPXXfeasopt/CPXfeasopt accepts all problem types. However, it does not allow you to relax convex quadratic constraints nor indicator constraints; use the routine CPXXfeasoptext and CPXfeasoptext.

These four parameters do not influence this routine.

upper cutoff CPXPARAM_MIP_Tolerances_UpperCutoff
lower cutoff CPXPARAM_MIP_Tolerances_LowerCutoff
upper objective value limit CPXPARAM_Simplex_Limits_UpperObj
lower objective value limit CPXPARAM_Simplex_Limits_LowerObj

If you want to study infeasibilities introduced by those parameters, consider adding an objective function constraint to your model to enforce their effect before you invoke this routine.

Warning:

For efficiency reasons this function temporarily modifies your problem to account for the relaxations. In certain corner cases, such as out of memory situations, CPLEX may fail to restore your problem to its original state. In such a case, CPLEX clears your problem, and the lp argument will refer to an empty object. The only valid operation on this object is then for you to call CPXXfreeprob and CPXfreeprob.

Arguments

env: A pointer to the CPLEX environment as returned by CPXXopenCPLEX/CPXopenCPLEX.
lp: A pointer to a CPLEX problem object as returned by CPXXcreateprob/CPXcreateprob.
rhs: An array of doubles of length at least equal to the number of rows in the problem. NULL may be specified if no rhs values are allowed to be relaxed. When not NULL, the array specifies the preference values that determine the cost of relaxing each constraint.
rng: An array of doubles of length at least equal to the number of rows in the problem. NULL may be specified if no range values are allowed to be relaxed or none are present in the active problem. When not NULL, the array specifies the preference values that determine the cost of relaxing each range.
lb: An array of doubles of length at least equal to the number of columns in the problem. NULL may be passed if no lower bound of any variable is allowed to be relaxed. When not NULL, the array specifies the preference values that determine the cost of relaxing each lower bound.
ub: An array of doubles of length at least equal to the number of columns in the problem. NULL may be passed if no upper bound of any variable is allowed to be relaxed. When not NULL, the array specifies the preference values that determine the cost of relaxing each upper bound.

Return

The routine returns 0 (zero) if successful and nonzero if an error occurs.

Example


status = CPXfeasopt (env, lp, rhs, rng, lb, ub);