5
$\begingroup$

Currently, I am working on the implementation of a MILP formulation with lazy constraints for an optimization problem, and I am using the MIP Start strategy. I am generating the integer feasible solution to the MIP Start through a heuristic, the solution is feasible for all possible lazy constraints. However, whenever I pass the integer solution to the MIP Start the Cplex returns the following warning:

Warning: No solution found from 481 MIP starts.

And the Cplex begins to solve the problem without using the provided integer solution. In all MIP Start effort level, the same behavior is presented. Also, as recommended by this IBM Support webpage, I am setting the Cplex parameters:

  • Presolve reduce to 1:

    cplex.setParam(IloCplex::Param::Preprocessing::Reduce, 1);

  • Symmetry to 0.

    cplex.setParam(IloCplex::Param::Preprocessing::Symmetry, 0);

and again, the same behavior is presented. It seems that the MIP start is not accepting the provided solution. But I do not know why. I would like to know if anyone already experienced this. For more information, I am using the programming language C++ with Cplex studio 12.10 and Concert technology.

UPDATE 1: The approached optimization problem is a variant of the VRP, and the MILP formulation is very similar to the VRP Vehicle flow formulation. And regarding the feasible solution, it is composed of one customer per route.

Thank you.

$\endgroup$
  • 1
    $\begingroup$ Could you add more information about the constraints being added to the model and the MIP start solution passed to CPLEX? $\endgroup$ – YukiJ Feb 11 at 13:01
  • $\begingroup$ Sure, I added an update to the question. Thank you. $\endgroup$ – Matheus Diógenes Andrade Feb 11 at 13:23
  • 3
    $\begingroup$ Are you supplying a full solution, or only values for some variables? If you fix all the variables at their starting values (by setting their upper and lower bounds) and try to solve the model, does CPLEX declare it infeasible? $\endgroup$ – prubin Feb 11 at 21:36
  • $\begingroup$ @prubin, Yes the solution is feasible and complete, and I checked it using the strategy recommended by you in this question: or.stackexchange.com/questions/3418/… $\endgroup$ – Matheus Diógenes Andrade Feb 13 at 10:16
3
$\begingroup$

Assuming that your solution is indeed feasible and that your lazy constraints are correctly coded, the most likely explanation is that the order of your variables is inconsistent between your heuristic and CPLEX's input.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank for the answer, but what are you trying to say is that there is some error in the piece of code that 'translates' the heuristic solution to a CPLEX's input? $\endgroup$ – Matheus Diógenes Andrade Feb 13 at 10:23
  • 1
    $\begingroup$ Yes, that would be my best guess, a mismatch in the order/number/names of variables. $\endgroup$ – Nikos Kazazakis Feb 13 at 14:04
  • $\begingroup$ You were right, please check the question's answer to see in detail. $\endgroup$ – Matheus Diógenes Andrade Feb 14 at 11:48
2
$\begingroup$

Have you tried to disable all the presolve?

I don't remember which version it stoped, but in some early 12. versions of cplex there was a bug that did not disable some presolve function that allowed the solver to remove some constraints/variables it found unnecessary. Sometimes this could lead to infeasibility, or suboptimal solutions.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. Well, I followed the recommendations presented on this web page (ibm.com/support/pages/node/416477), where is recommended to set the presolve reduce to 1 and symmetry to 0. But I will check the other presolvers as well. $\endgroup$ – Matheus Diógenes Andrade Feb 13 at 10:28
2
$\begingroup$

After hours of internet research and coding debugging, I could finally solve the problem. The problem was on the way that I passed the solution to the Cplex MIP Start. Below follows an example of how I was passing the solution to the Cplex MIP Start, where x_var is a matrix of variables, x_start_val is a matrix of values, and cplex is an object of class IloCplex:

for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j) 
        cplex.addMIPStart(x_var[i][j], x_start_val[i][j]);

However, after carefully reading the documentation of the function addMIPStart from the class IloCplex in this IBM Support Webpage. I found the following information:

There is no method to create a MIP start from a multidimensional array of variables. In order to create a MIP start from a multidimensional array of variables, you first must copy all those variables into a flat array.

Therefore, to pass the solution in x_start_val to the MIP Start, I would need to change the previous code:

IloNumVarArray startVar(env);
IloNumArray startVal(env);
for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j) {
             startVar.add(x_var[i][j]);
             startVal.add(x_start_val[i][j]);
    }
cplex.addMIPStart(startVar, startVal);
startVal.end();
startVar.end();

Thank you, everyone, for all the comments and all the help.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.