Originally posted by: SJean

Dear all,

I modelled and solved a bi-objective optimization problem, Min wf1+(1-w)f2, using CPLEX. My results for a number of problem instances show that for large value of objective weight, e.g., w>=0.5, the CPLEX time is reasonable (e.g., <10 minutes), however, as the value of obj weight decreases in the same problems e.g., <=0.5 , the CPLEX time significantly increases (e.g., >120 minutes ). Is this because the problem for small obj. weight values has fewer optimal solutions?

Thanks,
Jean
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

From the run times, I'm guessing your problem has some discrete variables. It need not be a matter of multiple optimal solutions; it could be that f1 is easy to optimize (perhaps because there is a significant drop-off from the optimal solution to runners-up, or because node bounds are inherently strong) and f2 is hard to optimize (integer-feasible solutions close to the optimum in quality, or weak bounds). As weight shifts from f1 to f2, the difficulty you would have pruning nodes when optimizing f2 alone seeps into the process.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SJean

Dear Paul:
Many thanks for your reply.
You’re absolutely correct; the model has a quiet number of discrete variables i.e., MIP with binary, integer , and semi-integer variables
It was nonlinear (multiplication of binary and non binary variables) and prior to be solved by CPLEX it has been linearized by introducing new variables and constraints. The format of the new constraints is as follows
Yij<=v * zij
Yij<= Xij
Yij>= Xij -v * (1-zij)
0<=Xij<=v

For different value of bound “v” CPLEX terminates with the following results:
Optimal solution, Integer infeasible, or fractional solution (e.g., 10 % gap).
Could you please let me know which one of the reasons you mentioned earlier is more likely causing this problem (week bound/ integer-feasible solutions close to the optimum in quality)? and any suggestion how to fix it?
Your comment is greatly appreciated in advance.
Jean
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't think it's possible to assign probabilities to the various causes, but I'm always leery of "big M" constraints because they can cause bounding problems and even numerical issues if the value of M (in your case, V) gets large. So you might start by trying to find tighter bounds (smaller -- but valid -- values for V). If you are using a single V throughout the model, you might consider a different V for each constraint.

Another possibility, if in fact V is the source of the problem, would be reformulating using combinatorial Benders cuts. Sometimes that produces significant reductions in solution time, sometimes not.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SJean

Hi Paul,

Many thanks for your help.

Cheers,
Jean
#CPLEXOptimizers
#DecisionOptimization