No solution found from n MIP starts

Question

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.

Answer 1

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();

Answer 2

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.

Answer 3

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.