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

This routine supports several options for the metric used to determine what constitutes a minimum-cost relaxation. These options are controlled by the parameter CPX_PARAM_FEASOPTMODE 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 optimizaton (denoted by OPT), 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 controlled by the parameter CPX_PARAM_FEASOPTMODE. Thus, for example, the value CPX_FEASOPT_MIN_SUM denotes that CPXfeasopt should find a relaxation that minimizes the weighted sum of relaxations. Similarly, the value CPX_FEASOPT_OPT_INF indicates that 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.

Note that if you use INF mode, the resulting feasopt models will be MIPs even if your model is continuous. Similarly, if you use QUAD mode, the feasopt models will become quadratic even if your original model is linear. This 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 CPXfeasopt found relaxed values to make the model feasible, call the routine CPXsolninfo for continuous models or CPXgetstat for any model type. CPXsolninfo will return a value of CPX_NO_SOLN for the argument solntype_p if CPXfeasopt could not find a feasible relaxation. Otherwise, it will return one of the following, depending on the value of CPX_PARAM_FEASOPTMODE:

• 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 model, the routine CPXgetstat will return a value of CPXMIP_INFEASIBLE_RELAXED if it could not find a feasible relaxation. Otherwise, it will return one of the following, depending on the value of CPX_PARAM_FEASOPTMODE:

• 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 CPXfeasopt accepts all problem types. However, it does not allow you to relax quadratic constraints nor indicator constraints; use the routine CPXfeasoptext for that purpose.

Parameters

env

A pointer to the CPLEX environment as returned by CPXopenCPLEX.

lp

A pointer to a CPLEX problem object as returned by 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 model. 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.