Originally posted by: JochemT

Hello,

I am working with JAVA and CPLEX to solve a VRP and PDP problem in which I stop cplex after finding two feasible solutions and proceed in local searches for better feasible solutions. When a solution is found, these values are added to the original cplex, with the addMIPStart function, while using IloCplex.MIPStartEffort.Repair. Unfortunately, cplex occasionally uses one of the feasible solutions as new found upperbound. I have checked the solutions found in the local searchers multiple times and they are feasible, I have also checked this by adding them as constraints to the original model.

Therefore, I am stuck in using my local searches as MIPStarts for the original problem. I have constructed the MIPStart in the following matter and is only used when a new and improved feasible solution is found:

startVar = new IloNumVar[2*n*n*CD*K+2*CD+n*CD*K];
startVal = new double[2*n*n*CD*K+2*CD+n*CD*K];

int h=0;
for (int i : V) {
    for (int j : V) {
        for (int k = 0; k < K; k++) {
            for (int d : C_1) {
                startVar[h] = x[i][j][d][k];
                startVal[h] = valx[i][j][d][k];
                h++;
            }
        }
    }
}
//int h_2 = ((n*n*CD*K)/2)-1;
for (int i : V) {
    for (int j : V) {
        for (int k = 0; k < K; k++) {
            for (int d : C_1) {
                startVar[h] = alpha[i][j][d][k];
                startVal[h] = valalpha[i][j][d][k];
                h++;
            }
        }
    }
}

for (int i : V) {
    for (int k = 0; k < K; k++) {
        for (int d : C_1) {
            startVar[h] = v[i][d][k];
            startVal[h] = valv[i][d][k];
            h++;
        }
    }
}

for(int i:C_1) {
    for (int j : C_1) {
        //if (i != j) {
        startVar[h] = omega[i][j];
        startVal[h] = valomega[i][j];
        h++;
        //}
    }
}

cplexstart.addMIPStart(startVar, startVal, IloCplex.MIPStartEffort.Repair);

So what can I do to improve the code such that is used the MIPStarts that are found? Furthermore, the MIPStarts seem to work on the localsearch properly but not on the original/main cplex solve.

Kind regards,

Jochem

I suggest to analyze this with the interactive optimizer:

• Export your model as SAV file using IloCplex.exportModel()
• Export the MIP starts using IloCplex.writeMIPStarts()
• In the interactive optimizer load the models and the MIP starts
• optimize and see if MIP starts are still rejected
• If they are use the command 'conflict 1' to run the conflict refiner on the first MIP start
• Use 'disp conf all' to display the conflict found in the previous step

Could it be that your MIP starts are feasible but for some reason have an objective value that is worse than the current incumbent?

Originally posted by: JochemT

Hello Daniel,

So we have saved the model and mipstarts and used the interactive optimizer to load the model and mipstarts.

Below you can find the way we have stored and the way we tested to find the problem with the wrong objective value as starting point. Upfront of this code, all the searches were completed and improved feasible solutions are added as mipstarts.

System.
out.println(
"--- CONTINUE CPLEX SOLVE ---");

oldvalue = 
objvalue;


cplex.writeMIPStarts(
"start.mst");SolveModel(
cplex, valx, 
valalpha, 
valomega, x, alpha, omega);


objvalue = 
cplex.getObjValue();
InitialSolution(
cplex, valx, 
valalpha, 
valomega, valv, x, alpha, omega, v);


newvalue = 
cplex.getObjValue();


if (
newvalue > 
oldvalue) {
    System.
out.println(
"Houston, Houston Help me!!");
    
cplex.exportModel(
"main.lp");
    
cplex.end();

}

The optimizer indicated that 16 out of the 17 mipstarts are feasible and that there are no conflicts.

Furthermore, is the following printed during a normal cplex.solve (not in the optimizer),

 Objective function Value = 928.5999999999999
--- CONTINUE CPLEX SOLVE ---
CPXPARAM_Threads                                 1
CPXPARAM_MIP_Limits_Solutions                    2
2 of 17 MIP starts provided solutions.
MIP start 'obj1438.1999999999998' defined initial solution with objective 1438.2000.

It can be seen that 15 MIP starts do not give a solution, where they are a solution during the local searches and in the optimizer.

Therefore, the problem cannot be found yet.

This is not necessarily unexpected.

If a MIP start provides a solution that is worse than the current best known solution then this is also considered as "not providing a solution".

You can test your mipstarts one by one by loading model and mip start file and then using the 'change delete mipstart' command to delete all starts that you do not want to test.

Originally posted by: JochemT

I understand that the MIPstart takes the best feasible solution that is available. Yet it does not takes this value as new upper bound in the restart of branching. Illustrated in the following print:

 Objective function Value = 928.5999999999999
--- CONTINUE CPLEX SOLVE ---
CPXPARAM_Threads                                 1
CPXPARAM_MIP_Limits_Solutions                    2
2 of 17 MIP starts provided solutions.
MIP start 'obj1438.1999999999998' defined initial solution with objective 1438.2000.

I have tested the mipstart and also the mipstart with the objective value of 928.5999 in the interactive optimizer and the solutions provided are feasible. So in the print above, the mipstart ' obj928.5999' should be defined as initial solution, which it does not do.

Originally posted by: JochemT

Hi Daniel,

Is it possible that you have a look at my problem? Since it is really weird that the interactive optimizer is able to use the mipstart. But when it is used within java, it does not use the best found mipstarts.

- Jochem

Yes, sure. Please send a code as small as possible to daniel(dot)junglas(at)de(dot)ibm(dot)com.

I think we resolved this in private communication. The problem is that you have a large number of MIP starts but a rather tight solution limit. CPLEX starts processing your MIP starts and finds feasible solutions from all. However, it quickly hits the solution limit and thus stops without even looking at the remaining MIP starts. This is expected behavior since with a solution limit you ask CPLEX to stop as soon as that many solutions were found.

Potential remedies are:

1. Don't use a solution limit
2. Inject MIP starts in decreasing order of quality (best solution first)
3. If you want to stick with solution limits then keep a list of MIP starts and repeatedly do the following:
   1. Inject all MIP starts from the list
   2. solve()
   3. If the solve() returned with a status of "solution limit hit" and the current incumbent is worse than the best MIP start then remove all starts from the list that are worse than the current incumbent and go to 1.