Originally posted by: Washout

Hi all,

My code first solves a model, then adds some constraints, modifies the objective function and then resolves using the best (incumbent) solution from the original solve as a starting solution for the resolve. Is there a way to use all (still feasible) solutions from the original solve as solutions in the modified model? I understand why it pickes the incumbent solution, or solution with the lowest objective function value from the original model, but once I put in the changes to the objective function and add extra constraints it would be useful to still have those other solutions as they may help provide a better solution to the modified model. At the moment it simply picks the best available solution based on the original objective function and uses that as a starting solution.

Cheers
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Washout wrote:
> Hi all,
>
> My code first solves a model, then adds some constraints, modifies the objective function and then resolves using the best (incumbent) solution from the original solve as a starting solution for the resolve. Is there a way to use all (still feasible) solutions from the original solve as solutions in the modified model? I understand why it pickes the incumbent solution, or solution with the lowest objective function value from the original model, but once I put in the changes to the objective function and add extra constraints it would be useful to still have those other solutions as they may help provide a better solution to the modified model. At the moment it simply picks the best available solution based on the original objective function and uses that as a starting solution.
>
> Cheers

Does your code explicitly pass the incumbent solution back as a MIP start?
If so, I suggest you skip that step. CPLEX will automatically keep the solutions
it accumulated during the optimization as possible MIP starts for any subsequent
optimization following problem modifications. For example, here's a run where
CPLEX initially finds 8 solutions and saves them all, as you can see from the
second to last line of output:

---

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

• 0+ 0 6450.0000 527 ---

0 0 560.0000 521 6450.0000 560.0000 527 91.32%
0 0 560.0000 292 6450.0000 Cuts: 155 707 91.32%
0 0 560.0000 366 6450.0000 Cuts: 644 1087 91.32%

• 0+ 0 5762.0000 560.0000 1329 90.28%

0 0 560.0000 267 5762.0000 Cuts: 352 1329 90.28%
0 0 560.0000 294 5762.0000 Cuts: 644 1719 90.28%
0 2 560.0000 213 5762.0000 560.0000 1719 90.28%
Elapsed real time = 0.79 sec. (tree size = 0.01 MB, solutions = 2)

• 109+ 109 2716.0000 560.0000 3897 79.38%

109 111 560.0000 210 2716.0000 560.0000 3897 79.38%

• 128+ 128 2676.0000 560.0000 4125 79.07%
• 141+ 141 2654.0000 560.0000 4225 78.90%
• 142+ 142 2598.0000 560.0000 4226 78.44%
• 143+ 143 2584.0000 560.0000 4227 78.33%
• 180+ 180 2580.0000 560.0000 4699 78.29%

328 329 560.0000 222 2580.0000 560.0000 6558 78.29%
559 560 970.0000 150 2580.0000 560.0000 8989 78.29%
...

Solution pool: 8 solutions saved.

MIP - Node limit exceeded, integer feasible: Objective = 2.5800000000e+03

---

Now, let's add a constraint on the objective that makes all 8 solutions
infeasible, then reoptimize from where we left off.
CPLEX> d pr con obj
Minimize
obj: Y_STAR + 0 Z13 + 0 Z29
CPLEX> add
Enter new constraints and bounds :
Y_STAR <= 2550
end
Problem addition successful.
The previous best solution had objective 2580. Now when we reoptimize,
CPLEX prints a message indicating that it considered all 8 previously
available solutions:

---

CPLEX> mip
Warning: No solution found from 8 MIP starts.
Retaining values of one MIP start for possible repair.
Tried aggregator 1 time.
MIP Presolve eliminated 1 rows and 2 columns.
MIP Presolve modified 6336 coefficients.
Reduced MIP has 2178 rows, 1154 columns, and 10626 nonzeros.
Reduced MIP has 1087 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing fixed 0 vars, tightened 4 bounds.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.01 sec.
Probing time = 0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.01 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 560.0000 486 560.0000 503
0 0 560.0000 306 Cuts: 171 678
0 0 560.0000 344 Cuts: 566 1013
0 0 560.0000 235 Cuts: 597 1235
0 0 560.0000 294 Cuts: 644 1546

• 0+ 0 2546.0000 560.0000 1546 78.00%
• 0+ 0 2492.0000 560.0000 1546 77.53%

---

So, I think CPLEX will do what you want. As far as adjusting how many solutions
CPLEX stores in the solution pool, the default is 20. You can adjust that by
altering the populate limit parameter. So, you can accumulate solutions in one
optimization, modify the model, then restart the optimization, and CPLEX will try
to use the best feasible solution available. Of course, if you add constraints,
you run the risk that you make all previously found solutions infeasible. Note
also that even changing the objective without adding can actually cause CPLEX to reject some solutions accumulated from the previous run. This can happen because
CPLEX's presolve may fix variables based on the objective coefficient values
(i.e. an optimality based presolve reduction rather than the more typical
feasibility based reduction). See the technotes at
http://www-01.ibm.com/support/docview.wss?uid=swg21400105 and
http://www-01.ibm.com/support/docview.wss?uid=swg21399996 for more
details.
solutions that
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Washout wrote:
> Hi all,
>
> My code first solves a model, then adds some constraints, modifies the objective function and then resolves using the best (incumbent) solution from the original solve as a starting solution for the resolve. Is there a way to use all (still feasible) solutions from the original solve as solutions in the modified model? I understand why it pickes the incumbent solution, or solution with the lowest objective function value from the original model, but once I put in the changes to the objective function and add extra constraints it would be useful to still have those other solutions as they may help provide a better solution to the modified model. At the moment it simply picks the best available solution based on the original objective function and uses that as a starting solution.
>
> Cheers

Does your code explicitly pass the incumbent solution back as a MIP start?
If so, I suggest you skip that step. CPLEX will automatically keep the solutions
it accumulated during the optimization as possible MIP starts for any subsequent
optimization following problem modifications. For example, here's a run where
CPLEX initially finds 8 solutions and saves them all, as you can see from the
second to last line of output:

---

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

• 0+ 0 6450.0000 527 ---

0 0 560.0000 521 6450.0000 560.0000 527 91.32%
0 0 560.0000 292 6450.0000 Cuts: 155 707 91.32%
0 0 560.0000 366 6450.0000 Cuts: 644 1087 91.32%

• 0+ 0 5762.0000 560.0000 1329 90.28%

0 0 560.0000 267 5762.0000 Cuts: 352 1329 90.28%
0 0 560.0000 294 5762.0000 Cuts: 644 1719 90.28%
0 2 560.0000 213 5762.0000 560.0000 1719 90.28%
Elapsed real time = 0.79 sec. (tree size = 0.01 MB, solutions = 2)

• 109+ 109 2716.0000 560.0000 3897 79.38%

109 111 560.0000 210 2716.0000 560.0000 3897 79.38%

• 128+ 128 2676.0000 560.0000 4125 79.07%
• 141+ 141 2654.0000 560.0000 4225 78.90%
• 142+ 142 2598.0000 560.0000 4226 78.44%
• 143+ 143 2584.0000 560.0000 4227 78.33%
• 180+ 180 2580.0000 560.0000 4699 78.29%

328 329 560.0000 222 2580.0000 560.0000 6558 78.29%
559 560 970.0000 150 2580.0000 560.0000 8989 78.29%
...

Solution pool: 8 solutions saved.

MIP - Node limit exceeded, integer feasible: Objective = 2.5800000000e+03

---

Now, let's add a constraint on the objective that makes all 8 solutions
infeasible, then reoptimize from where we left off.
CPLEX> d pr con obj
Minimize
obj: Y_STAR + 0 Z13 + 0 Z29
CPLEX> add
Enter new constraints and bounds :
Y_STAR <= 2550
end
Problem addition successful.
The previous best solution had objective 2580. Now when we reoptimize,
CPLEX prints a message indicating that it considered all 8 previously
available solutions:

---

CPLEX> mip
Warning: No solution found from 8 MIP starts.
Retaining values of one MIP start for possible repair.
Tried aggregator 1 time.
MIP Presolve eliminated 1 rows and 2 columns.
MIP Presolve modified 6336 coefficients.
Reduced MIP has 2178 rows, 1154 columns, and 10626 nonzeros.
Reduced MIP has 1087 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing fixed 0 vars, tightened 4 bounds.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.01 sec.
Probing time = 0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.01 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 560.0000 486 560.0000 503
0 0 560.0000 306 Cuts: 171 678
0 0 560.0000 344 Cuts: 566 1013
0 0 560.0000 235 Cuts: 597 1235
0 0 560.0000 294 Cuts: 644 1546

• 0+ 0 2546.0000 560.0000 1546 78.00%
• 0+ 0 2492.0000 560.0000 1546 77.53%

---

So, I think CPLEX will do what you want. As far as adjusting how many solutions
CPLEX stores in the solution pool, the default is 20. You can adjust that by
altering the populate limit parameter. So, you can accumulate solutions in one
optimization, modify the model, then restart the optimization, and CPLEX will try
to use the best feasible solution available. Of course, if you add constraints,
you run the risk that you make all previously found solutions infeasible. Note
also that even changing the objective without adding can actually cause CPLEX to reject some solutions accumulated from the previous run. This can happen because
CPLEX's presolve may fix variables based on the objective coefficient values
(i.e. an optimality based presolve reduction rather than the more typical
feasibility based reduction). See the technotes at
http://www-01.ibm.com/support/docview.wss?uid=swg21400105 and
http://www-01.ibm.com/support/docview.wss?uid=swg21399996 for more
details.
solutions that
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Washout

Hi Ed,

Thanks for your reply. Yes I have changed the solution pool size to accomodate more solutions when I use the populate() method rather than solve(). I understand that by modifying the objective function and adding constraints that I can render previously feasible solutions infeasible. I also resolve the model whilst the model is still in memory, so I don't need to formally load in the MIPStarts from file (though I do save the MIPStarts as part of my results data set). My issue is where there is multiple solutions that are still feasible in the modified model from the original solution pool, is there a way I can add them all to the solution pool for the modified model. Currently it simply picks the best (feasible) solution and so starts solving the modified model with just this solution in the solution pool.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Washout wrote:
> Hi Ed,
>
> Thanks for your reply. Yes I have changed the solution pool size to accomodate
> more solutions when I use the populate() method rather than solve(). I
> understand that by modifying the objective function and adding constraints that
> I can render previously feasible solutions infeasible. I also resolve the model
> whilst the model is still in memory, so I don't need to formally load in the
> MIPStarts from file (though I do save the MIPStarts as part of my results data
> set). My issue is where there is multiple solutions that are still feasible in
> the modified model from the original solution pool, is there a way I can add
> them all to the solution pool for the modified model. Currently it simply
> picks the best (feasible) solution and so starts solving the modified model
> with just this solution in the solution pool.
I don't see that. Consider the output below from the run
I just tried. We first run for 1000 nodes, accumulating 8 solutions
in the pool. We then add a constraint that retains feasibility for
only 5 of those 8 solutions. We then restart the optimization from that
point with a solution limit of 2. The optimization starts with the
best solution from the 5 feasible ones from the previous run; that counts as
one. It then stops after the next feasible solution, and we see a total
of 6 solution in the pool. So, I think CPLEX is doing what you wanted it
to do. If it was just using one solution in the pool, we would see two solutions
in the pool after the second optimization, not 6.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

• 0+ 0 6450.0000 527 ---

0 0 560.0000 521 6450.0000 560.0000 527 91.32%
0 0 560.0000 292 6450.0000 Cuts: 155 707 91.32%
0 0 560.0000 366 6450.0000 Cuts: 644 1087 91.32%

• 0+ 0 5762.0000 560.0000 1329 90.28%

0 0 560.0000 267 5762.0000 Cuts: 352 1329 90.28%
0 0 560.0000 294 5762.0000 Cuts: 644 1719 90.28%
0 2 560.0000 213 5762.0000 560.0000 1719 90.28%
Elapsed real time = 0.78 sec. (tree size = 0.01 MB, solutions = 2)

• 109+ 109 2716.0000 560.0000 3897 79.38%

109 111 560.0000 210 2716.0000 560.0000 3897 79.38%

• 128+ 128 2676.0000 560.0000 4125 79.07%
• 141+ 141 2654.0000 560.0000 4225 78.90%
• 142+ 142 2598.0000 560.0000 4226 78.44%
• 143+ 143 2584.0000 560.0000 4227 78.33%
• 180+ 180 2580.0000 560.0000 4699 78.29%

328 329 560.0000 222 2580.0000 560.0000 6558 78.29%
559 560 970.0000 150 2580.0000 560.0000 8989 78.29%

Implied bound cuts applied: 84
Flow cuts applied: 36
Mixed integer rounding cuts applied: 48
Gomory fractional cuts applied: 2

Root node processing (before b&c):
Real time = 0.76
Parallel b&c, 4 threads:
Real time = 1.13
Sync time (average) = 0.00
Wait time (average) = 0.00

Total (root+branch&cut) = 1.89 sec.

Solution pool: 8 solutions saved.

MIP - Node limit exceeded, integer feasible: Objective = 2.5800000000e+03
Current MIP best bound = 5.6000000000e+02 (gap = 2020, 78.29%)
Solution time = 2.02 sec. Iterations = 12441 Nodes = 1004 (998)
Deterministic time = 1339.92 ticks (663.43 ticks/sec)

CPLEX> d pr con obj
Minimize
obj: Y_STAR + 0 Z13 + 0 Z29
CPLEX> add
Enter new constraints and bounds :
Y_STAR <= 2700
end
Problem addition successful.
CPLEX> s mip lim sol 2
New value for mixed integer solutions limit: 2
CPLEX> mip
1 of 8 MIP starts provided solutions.
MIP start 'm1' defined initial solution with objective 2580.0000.
Tried aggregator 1 time.
MIP Presolve eliminated 1 rows and 2 columns.
MIP Presolve modified 6336 coefficients.
Reduced MIP has 2178 rows, 1154 columns, and 10626 nonzeros.
Reduced MIP has 1087 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing fixed 0 vars, tightened 4 bounds.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.01 sec.
Probing time = 0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.01 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

• 0+ 0 2580.0000 496 ---

0 0 560.0000 482 2580.0000 560.0000 496 78.29%
0 0 560.0000 267 2580.0000 Cuts: 156 656 78.29%
0 0 560.0000 351 2580.0000 Cuts: 644 1025 78.29%
0 0 560.0000 273 2580.0000 Cuts: 502 1239 78.29%
0 0 560.0000 273 2580.0000 Cuts: 644 1571 78.29%

• 0+ 0 2564.0000 560.0000 1571 78.16%

Implied bound cuts applied: 5
Flow cuts applied: 32
Mixed integer rounding cuts applied: 37
Gomory fractional cuts applied: 4

Root node processing (before b&c):
Real time = 0.79
Parallel b&c, 4 threads:
Real time = 0.00
Sync time (average) = 0.00
Wait time (average) = 0.00

Total (root+branch&cut) = 0.79 sec.

Solution pool: 6 solutions saved.

MIP - Solution limit exceeded, integer feasible: Objective = 2.5640000000e+03
Current MIP best bound = 5.6000000000e+02 (gap = 2004, 78.16%)
Solution time = 0.81 sec. Iterations = 1571 Nodes = 0 (1)
Deterministic time = 533.59 ticks (659.81 ticks/sec)
Isn't this the behavior you seek? If you are getting something different,
can you post some CPLEX output analogous to what we see above that illustrates
a model where the solution pool in the second run consists only of the feasible
solution from the first run plus any other solutions found during the second
run?
#CPLEXOptimizers
#DecisionOptimization