Decision Optimization

I'm solving a Steiner problem variant and providing a MIPStart to it. According to the logs, the solution was accepted but the runtime is worst when using the MIPStart than not using one. The solution I provide is very close to the optimal solution. What may be causing it?

Additional info:
I'm using cutsets as lazy constraints, and the following parameters are set:



------------------------------
Victor Hugo Rodrigues do Nascimento
------------------------------
#DecisionOptimization

I'm assuming here that "very close to the optimal solution" means "near-optimal objective value". There are potentially a number of things in play here. (Disclaimer: I'm not privy to IBM's trade secrets, so the following is speculation on my part.) First, a warm start can potentially alter the cuts and variable fixings that occur at the root node, possibly to the detriment of solution time. Second, if the warm start is used to generate an initial basis at the root (and I'm not sure CPLEX does this), that basis will likely be different from the one CPLEX would have generated without the warm start, and the difference might induce CPLEX to start pivoting in a way that explores less productive portions of the solution space than it otherwise would have (even allowing for the presumably earlier fathoming of chunks of the search tree thanks to the good solution). Third, the warm start may alter CPLEX's use of heuristics ... so a heuristic that previously would have gotten lucky and found the optimal solution quickly now behaves differently or is not applied at all, leaving CPLEX to take longer to find the eventual winner.

My experience with warm starting MIPs, which other people have also described, is adequately summarized by an old saying: "Some days you get the bear, and some days the bear gets you."

An alternative to a MIP start that you might like to try is to set the "uppercutoff" parameter (if minimizing; "lowercutoff" if maximizing) to the objective value of your near-optimal solution. That should allow CPLEX to fathom nodes on objective value sooner without (I think) mucking up the root node processing, heuristics etc.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Thu September 02, 2021 03:12 PM
From: Victor Hugo Rodrigues do Nascimento
Subject: Using MIPStart is making runtime worst.

I'm solving a Steiner problem variant and providing a MIPStart to it. According to the logs, the solution was accepted but the runtime is worst when using the MIPStart is worst than not using one. The solution I provide is very close to the optimal solution. What may be causing it?

Additional info:
I'm using cutsets as lazy constraints, and the following parameters are set:

cplex.setParam(IloCplex::Param::MIP::Strategy::Order, 1);

cplex.setParam(IloCplex::Param::Emphasis::MIP,IloCplex::MIPEmphasisBalanced);

cplex.setParam(IloCplex::Param::Threads, 1);

cplex.setParam(IloCplex::Param::Preprocessing::Presolve, CPX_OFF);

cplex.setParam(IloCplex::Param::MIP::Strategy::HeuristicFreq, -1);

cplex.setParam(IloCplex::Param::MIP::Strategy::RINSHeur, -1);

cplex.setParam(IloCplex::Param::MIP::Strategy::FPHeur, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::BQP, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Cliques, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Covers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Disjunctive, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::FlowCovers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Gomory, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::GUBCovers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Implied, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::LiftProj, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::LocalImplied, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::MCFCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::MIRCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::PathCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::RLT, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::ZeroHalfCut, -1);

------------------------------
Victor Hugo Rodrigues do Nascimento
------------------------------

#DecisionOptimization

Thanks for the reply, it seems that the bear got me at your second suggestion, because I've disabled all the cuts, presolve and heuristics from cplex. I've tried to set the uppercutoff  but it also didn't help. The solution is at 0.1% from the optimal value.

------------------------------
Victor Hugo Rodrigues do Nascimento
------------------------------

Original Message:
Sent: Thu September 02, 2021 04:25 PM
From: Paul Rubin
Subject: Using MIPStart is making runtime worst.

I'm assuming here that "very close to the optimal solution" means "near-optimal objective value". There are potentially a number of things in play here. (Disclaimer: I'm not privy to IBM's trade secrets, so the following is speculation on my part.) First, a warm start can potentially alter the cuts and variable fixings that occur at the root node, possibly to the detriment of solution time. Second, if the warm start is used to generate an initial basis at the root (and I'm not sure CPLEX does this), that basis will likely be different from the one CPLEX would have generated without the warm start, and the difference might induce CPLEX to start pivoting in a way that explores less productive portions of the solution space than it otherwise would have (even allowing for the presumably earlier fathoming of chunks of the search tree thanks to the good solution). Third, the warm start may alter CPLEX's use of heuristics ... so a heuristic that previously would have gotten lucky and found the optimal solution quickly now behaves differently or is not applied at all, leaving CPLEX to take longer to find the eventual winner.

My experience with warm starting MIPs, which other people have also described, is adequately summarized by an old saying: "Some days you get the bear, and some days the bear gets you."

An alternative to a MIP start that you might like to try is to set the "uppercutoff" parameter (if minimizing; "lowercutoff" if maximizing) to the objective value of your near-optimal solution. That should allow CPLEX to fathom nodes on objective value sooner without (I think) mucking up the root node processing, heuristics etc.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Thu September 02, 2021 03:12 PM
From: Victor Hugo Rodrigues do Nascimento
Subject: Using MIPStart is making runtime worst.

I'm solving a Steiner problem variant and providing a MIPStart to it. According to the logs, the solution was accepted but the runtime is worst when using the MIPStart is worst than not using one. The solution I provide is very close to the optimal solution. What may be causing it?

Additional info:
I'm using cutsets as lazy constraints, and the following parameters are set:

cplex.setParam(IloCplex::Param::MIP::Strategy::Order, 1);

cplex.setParam(IloCplex::Param::Emphasis::MIP,IloCplex::MIPEmphasisBalanced);

cplex.setParam(IloCplex::Param::Threads, 1);

cplex.setParam(IloCplex::Param::Preprocessing::Presolve, CPX_OFF);

cplex.setParam(IloCplex::Param::MIP::Strategy::HeuristicFreq, -1);

cplex.setParam(IloCplex::Param::MIP::Strategy::RINSHeur, -1);

cplex.setParam(IloCplex::Param::MIP::Strategy::FPHeur, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::BQP, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Cliques, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Covers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Disjunctive, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::FlowCovers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Gomory, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::GUBCovers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Implied, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::LiftProj, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::LocalImplied, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::MCFCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::MIRCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::PathCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::RLT, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::ZeroHalfCut, -1);

------------------------------
Victor Hugo Rodrigues do Nascimento
------------------------------

#DecisionOptimization

Are all the things turned off in your listing also turned off when you do the run without the MIP start? If not, maybe try turning off a few things (presolve comes to mind) but leaving most of the cuts and heuristics on.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Thu September 02, 2021 05:47 PM
From: Victor Hugo Rodrigues do Nascimento
Subject: Using MIPStart is making runtime worst.

Thanks for the reply, it seems that the bear got me at your second suggestion, because I've disabled all the cuts, presolve and heuristics from cplex. I've tried to set the uppercutoff  but it also didn't help. The solution is at 0.1% from the optimal value.

------------------------------
Victor Hugo Rodrigues do Nascimento

Original Message:
Sent: Thu September 02, 2021 04:25 PM
From: Paul Rubin
Subject: Using MIPStart is making runtime worst.

I'm assuming here that "very close to the optimal solution" means "near-optimal objective value". There are potentially a number of things in play here. (Disclaimer: I'm not privy to IBM's trade secrets, so the following is speculation on my part.) First, a warm start can potentially alter the cuts and variable fixings that occur at the root node, possibly to the detriment of solution time. Second, if the warm start is used to generate an initial basis at the root (and I'm not sure CPLEX does this), that basis will likely be different from the one CPLEX would have generated without the warm start, and the difference might induce CPLEX to start pivoting in a way that explores less productive portions of the solution space than it otherwise would have (even allowing for the presumably earlier fathoming of chunks of the search tree thanks to the good solution). Third, the warm start may alter CPLEX's use of heuristics ... so a heuristic that previously would have gotten lucky and found the optimal solution quickly now behaves differently or is not applied at all, leaving CPLEX to take longer to find the eventual winner.

My experience with warm starting MIPs, which other people have also described, is adequately summarized by an old saying: "Some days you get the bear, and some days the bear gets you."

An alternative to a MIP start that you might like to try is to set the "uppercutoff" parameter (if minimizing; "lowercutoff" if maximizing) to the objective value of your near-optimal solution. That should allow CPLEX to fathom nodes on objective value sooner without (I think) mucking up the root node processing, heuristics etc.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Thu September 02, 2021 03:12 PM
From: Victor Hugo Rodrigues do Nascimento
Subject: Using MIPStart is making runtime worst.

I'm solving a Steiner problem variant and providing a MIPStart to it. According to the logs, the solution was accepted but the runtime is worst when using the MIPStart is worst than not using one. The solution I provide is very close to the optimal solution. What may be causing it?

Additional info:
I'm using cutsets as lazy constraints, and the following parameters are set:

cplex.setParam(IloCplex::Param::MIP::Strategy::Order, 1);

cplex.setParam(IloCplex::Param::Emphasis::MIP,IloCplex::MIPEmphasisBalanced);

cplex.setParam(IloCplex::Param::Threads, 1);

cplex.setParam(IloCplex::Param::Preprocessing::Presolve, CPX_OFF);

cplex.setParam(IloCplex::Param::MIP::Strategy::HeuristicFreq, -1);

cplex.setParam(IloCplex::Param::MIP::Strategy::RINSHeur, -1);

cplex.setParam(IloCplex::Param::MIP::Strategy::FPHeur, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::BQP, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Cliques, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Covers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Disjunctive, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::FlowCovers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Gomory, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::GUBCovers, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::Implied, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::LiftProj, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::LocalImplied, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::MCFCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::MIRCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::PathCut, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::RLT, -1);

cplex.setParam(IloCplex::Param::MIP::Cuts::ZeroHalfCut, -1);

------------------------------
Victor Hugo Rodrigues do Nascimento
------------------------------

#DecisionOptimization