Originally posted by: Eumpfenbach

I have an infeasible MIP. I want to provide some information about how to make it feasible.

First of all, I am using the Matlab API v12.2. When I solve, the model has an infeasible status. However, when I try and access cplex.Conflict there is nothing there. Matlab says there is no field cplex.Conflict.

Second, the information I would like to display is the amount of change that would have to occur to the RHS to make the model feasible for not one, but ALL the RHS values. So, keeping all the other RHS values constant, how much would the RHS for each constant have to change to make the model feasible (or if no value of the RHS will make the model feasible, then this information would be displayed). The idea is that the RHS are goals for a vehicle that interact (mpg, weight, cost, etc...) that are set too high. The user lowers the goals (or raises, depending on sign) until feasible. They might lower them all by 10%, one by 50%, etc, until feasibility is achieved. If they lower one a certain percentage and the model is still not feasible, then the information on the updated information on how much change is necessary would be presented. There is no objective. Just looking for a feasible solution.

Worst case, I could write a script to increment the RHS values for each constraint until feasibility is achieved. The model is small and can be solved very quickly. I am wondering if this or any other useful information to what I am trying to do is available anywhere in cplex when a problem is declared infeasible though.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

If I understand this correctly, it suffices to change 1 RHS to make your model feasible?

Let's assume that all constraints are <= constraints (other cases are similar).

You can do the following:

• Add a slack variable to every constraint.
• Set all slack bounds to 0.
• Set the objective to maximize the sum of the slacks.

Then you can change the lower slack bound for every constraint one after another to minus infinity. Optimize and obtain the value of the slack. Set the lower slack bound back to 0.

I hope this is not too confusing. Otherwise ask again.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

CPLEX offers the FeasOpt tool, which should do something similar to what you want.
It has different modes that you can choose:

0 = find minimum-sum relaxation
1 = find optimal minimum-sum relaxation
2 = find minimum number of relaxations
3 = find optimal relaxation with minimum number of relaxations
4 = find minimum quadratic-sum relaxation
5 = find optimal minimum quadratic-sum relaxation

This means the following:

0: You will get a solution for which the sum of all violations is minimized.
1: Same as 0, but within the different solutions that all minimize the sum of violations, pick one that then optimizes the original objective function.
2: You will get a solution that violates the smallest number of constraints (but each of them can be violated by an arbitrary amount).
3: Same as 2 plus 1.
4: You will get a solution for which the sum of all squared violations is minimized.
5: Same as 4 plus 1.

Through the programming APIs you can also specify weights for the different constraints, so that violating one constraint is considered worse than violating some other constraint. See the documentation for CPXXfeasopt() and CPXXfeasoptext() for details.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I didn't think this through totally. I was thinking that if the problem was infeasible, I could get the change in RHS necessary to make it feasible. If it is infeasible, I don't get a solution, though, so this makes no sense. I might try writing a script that iteratively increases the RHS and solves until a feasible solution can be found.

I have implemented a formulation with slack variables that shows how much slack each constraint has if feasible, with an objective to minimize the slack/rhs (to scale them appropriately).

I still can't access cplex.Conflict when the model is declared infeasible in Matlab to access the conflict refiner. It tells me there is no .Conflict field. The documentation says otherwise.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If you just solve the model and get an infeasibility status, then of course there is no solution. But then you can call feasopt to find a vector that is "as feasible as possible", with this term being being defined by the feasopt mode, see above.

Calling feasopt (in mode 0) is essentially the same as your approach of adding explicit slack variables that allow to violate the constraint and then to minimize the sum of slacks.

I do not know how to access the conflict refiner from MATLAB. John?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

Sure, you can use both conflict refiner and feasopt in MATLAB:

For conflict refine:

%build you model by Cplex class, then call 

this method cplex.refineConflict();

For feasopt:

cplex.feasOpt(preflhs, prefrhs, preflb, prefub);   Syntax:   cplex.feasOpt(preflhs, prefrhs, preflb, prefub)   Examples: If one parameter is empty, set it to [].   prefrhs=[]; cplex.feasOpt(preflhs, prefrhs, preflb, prefub)   Parameters: preflhs         Double column vector - The length must be at least equal to the number of rows in the problem. An empty vector may be specified 

if no range values are allowed to be relaxed or none are present in the active problem. When not empty, the vector specifies the preference values that determine the cost of relaxing each range. prefrhs     Double column vector - The length must be at least equal to the number of rows in the problem. An empty vector may be specified 

if no rhs values are are allowed to be relaxed. When not empty, the vector specifies the preference values that determine the cost of relaxing each constraint. preflb                 Double column vector - The length must be at least equal to the number of columns in the problem. An empty vector may be passed 

if no lower bound of any variable is allowed to be relaxed. When not empty, the vector specifies the preference values that determine the cost of relaxing each lower bound. prefub            Double column vector - The length must be at least equal to the number of columns in the problem. An empty vector may be passed 

if no upper bound of any variable is allowed to be relaxed. When not empty, the vector specifies the preference values that determine the cost of relaxing each upper bound.

John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Is it possible to specify certain constraints to not be relaxed in Feasopt? I don't want any bounds relaxed so I pass an empty vector. This seems to work fine. For the constraints, I want something like prefrhs = 1;1;1;1;1;Inf, (ie, relax the first 5 constraints equally but do not relax the 6th constraint). This does not seem to be working, though.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

For now I just turned my objective into a penalty function. It's not too bad because there is only 1 constraint I don't want relaxed and it is an equality constraint. Could be a pain to do this for other problems though.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

In order to avoid relaxation of a constraint you need to specify a non-positive value and not infinity. See also the reference documentation for function CPXfeasopt() which has details about how the preferences are interpreted.
#CPLEXOptimizers
#DecisionOptimization