Closed BYS543 closed 3 years ago
If the second-stage is LP, you should not need any special strategies for L-shaped to work, in theory. However, integer problems are hard and could take a long time to solve (if even possible) using the best solvers available, depending on the model. Can you solve the deterministic equivalent of your problem in reasonable time?
I guess it will be difficult and take much time if I solve the whole MILP model directly due to large number of scenes, so I try to use the two stage model to decompose it. I just solved it again and found that it could converge,the result is as follows,
L-Shaped Gap Time: 0:00:08 (3 iterations)
Objective: 54614.396999999975
Gap: 7.19410508489006e-15
Number of cuts: 30
Iterations: 3
However, I think the objective function value is a little small, because I have used mean value of random variable to solve the whole MILP model, and find the objective function value is 78856.92.
This is the solving process,which is provided by Gurobi
┌ Warning: First-stage has binary/integer decisions and no `IntegerStrategy` has been set. Procedure will fail if second-stage has binary/integer variables. Otherwise, the master_optimizer must be integer-capable.
└ @ StochasticPrograms.LShaped C:\Users\Lenovo\.julia\packages\StochasticPrograms\Jl6sf\src\solvers\structured\lshaped\integer\ignore_integers.jl:13
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x6bd63496
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.05s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
3 1.05565366e+05 -1.22392929e+04 1.07e+01 1.82e-14 3.25e+01 0s
Barrier performed 3 iterations in 0.07 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.08 seconds
Optimal objective 1.071756636e+05
User-callback calls 85, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x5f491523
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.05s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
Barrier performed 2 iterations in 0.07 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.08 seconds
Optimal objective 1.071756636e+05
User-callback calls 82, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x5bab75a4
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.06s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
Barrier performed 2 iterations in 0.09 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.09 seconds
Optimal objective 1.071756636e+05
User-callback calls 82, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x5f4415ca
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.07s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
3 1.05565366e+05 -1.22392929e+04 1.07e+01 1.82e-14 3.25e+01 0s
4 1.03715353e+05 3.27156658e+04 4.66e+00 9.33e-15 1.46e+01 0s
Barrier performed 4 iterations in 0.10 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.10 seconds
Optimal objective 1.071756636e+05
User-callback calls 86, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x8f362a44
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.04s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
Barrier performed 2 iterations in 0.06 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.07 seconds
Optimal objective 1.071756636e+05
User-callback calls 82, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x5534fdb0
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.05s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
3 1.05565366e+05 -1.22392929e+04 1.07e+01 1.82e-14 3.25e+01 0s
Barrier performed 3 iterations in 0.08 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.08 seconds
Optimal objective 1.071756636e+05
User-callback calls 87, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x89d8482c
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.21s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
3 1.05565366e+05 -1.22392929e+04 1.07e+01 1.82e-14 3.25e+01 0s
4 1.03715353e+05 3.27156658e+04 4.66e+00 9.33e-15 1.46e+01 0s
Barrier performed 4 iterations in 0.25 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.25 seconds
Optimal objective 1.071756636e+05
User-callback calls 91, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0xf87359da
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.06s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
3 1.05565366e+05 -1.22392929e+04 1.07e+01 1.82e-14 3.25e+01 0s
Barrier performed 3 iterations in 0.08 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.09 seconds
Optimal objective 1.071756636e+05
User-callback calls 85, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0xee99446b
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.05s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
3 1.05565366e+05 -1.22392929e+04 1.07e+01 1.82e-14 3.25e+01 0s
Barrier performed 3 iterations in 0.07 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.08 seconds
Optimal objective 1.071756636e+05
User-callback calls 85, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Model fingerprint: 0x43afae65
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [8e-05, 6e+03]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 21362 rows and 8527 columns
Presolve time: 0.05s
Presolved: 2480 rows, 5332 columns, 11823 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.244e+04
Factor NZ : 3.117e+04 (roughly 3 MBytes of memory)
Factor Ops : 4.536e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 8.77300661e+05 -2.00324663e+05 9.25e+02 8.88e-16 2.43e+03 0s
1 2.26825299e+05 -1.97321906e+05 1.60e+02 1.37e+00 4.37e+02 0s
2 1.28485592e+05 -1.14567812e+05 4.58e+01 1.33e-14 1.28e+02 0s
3 1.05565366e+05 -1.22392929e+04 1.07e+01 1.82e-14 3.25e+01 0s
Barrier performed 3 iterations in 0.08 seconds
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1361 iterations and 0.08 seconds
Optimal objective 1.071756636e+05
User-callback calls 88, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 7771 rows, 3270 columns and 18584 nonzeros
Model fingerprint: 0x5c416497
Variable types: 1130 continuous, 2140 integer (2140 binary)
Coefficient statistics:
Matrix range [3e-02, 9e+02]
Objective range [1e+00, 2e+02]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 1e+04]
Presolve removed 4653 rows and 2054 columns
Presolve time: 0.18s
Presolved: 3118 rows, 1216 columns, 7966 nonzeros
Variable types: 310 continuous, 906 integer (899 binary)
Found heuristic solution: objective -18540.75000
Found heuristic solution: objective -30192.51600
Root relaxation: objective -3.150193e+04, 854 iterations, 0.01 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
H 0 0 -31501.92600 -31501.926 0.00% - 0s
0 0 -31501.926 0 113 -31501.926 -31501.926 0.00% - 0s
Explored 0 nodes (854 simplex iterations) in 0.38 seconds
Thread count was 8 (of 8 available processors)
Solution count 3: -31501.9 -30192.5 -18540.8
No other solutions better than -31501.9
Optimal solution found (tolerance 1.00e-04)
Best objective -3.150192600000e+04, best bound -3.150192600000e+04, gap 0.0000%
User-callback calls 202, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.12 seconds
Optimal objective 1.176255800e+05
User-callback calls 2732, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.14 seconds
Optimal objective 1.176255800e+05
User-callback calls 2729, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.13 seconds
Optimal objective 1.176255800e+05
User-callback calls 2729, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.12 seconds
Optimal objective 1.176255800e+05
User-callback calls 2733, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.12 seconds
Optimal objective 1.176255800e+05
User-callback calls 2729, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.14 seconds
Optimal objective 1.176255800e+05
User-callback calls 2734, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.14 seconds
Optimal objective 1.176255800e+05
User-callback calls 2738, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.13 seconds
Optimal objective 1.176255800e+05
User-callback calls 2732, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.14 seconds
Optimal objective 1.176255800e+05
User-callback calls 2732, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
2608 1.1762558e+05 0.000000e+00 0.000000e+00 0s
Solved in 2608 iterations and 0.14 seconds
Optimal objective 1.176255800e+05
User-callback calls 2735, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 7781 rows, 3270 columns and 20604 nonzeros
Model fingerprint: 0xa79863bb
Variable types: 1130 continuous, 2140 integer (2140 binary)
Coefficient statistics:
Matrix range [3e-02, 9e+02]
Objective range [1e+00, 2e+02]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 1e+04]
MIP start from previous solve produced solution with objective 81983.3 (0.01s)
Loaded MIP start from previous solve with objective 81983.3
Presolve removed 4584 rows and 1983 columns
Presolve time: 0.15s
Presolved: 3197 rows, 1287 columns, 8188 nonzeros
Found heuristic solution: objective 67574.150000
Variable types: 310 continuous, 977 integer (970 binary)
Root relaxation: objective 5.219103e+04, 1080 iterations, 0.01 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
H 0 0 52191.030000 52191.0300 0.00% - 0s
0 0 52191.0300 0 79 52191.0300 52191.0300 0.00% - 0s
Explored 0 nodes (1080 simplex iterations) in 0.19 seconds
Thread count was 8 (of 8 available processors)
Solution count 3: 52191 67574.2 81983.3
Optimal solution found (tolerance 1.00e-04)
Best objective 5.219103000000e+04, best bound 5.219103000000e+04, gap 0.0000%
User-callback calls 406, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.14 seconds
Optimal objective 9.025668700e+04
User-callback calls 4012, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.12 seconds
Optimal objective 9.025668700e+04
User-callback calls 4009, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.17 seconds
Optimal objective 9.025668700e+04
User-callback calls 4009, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.15 seconds
Optimal objective 9.025668700e+04
User-callback calls 4013, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.15 seconds
Optimal objective 9.025668700e+04
User-callback calls 4009, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.14 seconds
Optimal objective 9.025668700e+04
User-callback calls 4014, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.16 seconds
Optimal objective 9.025668700e+04
User-callback calls 4018, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.14 seconds
Optimal objective 9.025668700e+04
User-callback calls 4012, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.14 seconds
Optimal objective 9.025668700e+04
User-callback calls 4012, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 23842 rows, 11780 columns and 62766 nonzeros
Coefficient statistics:
Matrix range [1e-02, 2e+03]
Objective range [8e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [7e-18, 6e+03]
Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 0s
1241 9.0256687e+04 0.000000e+00 0.000000e+00 0s
Solved in 1241 iterations and 0.19 seconds
Optimal objective 9.025668700e+04
User-callback calls 4015, time in user-callback 0.00 sec
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 7791 rows, 3270 columns and 22754 nonzeros
Model fingerprint: 0xb2167a38
Variable types: 1130 continuous, 2140 integer (2140 binary)
Coefficient statistics:
Matrix range [3e-02, 9e+02]
Objective range [1e+00, 2e+02]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 1e+04]
MIP start from previous solve produced solution with objective 54614.4 (0.03s)
Loaded MIP start from previous solve with objective 54614.4
Presolve removed 7783 rows and 3257 columns
Presolve time: 0.13s
Presolved: 8 rows, 13 columns, 25 nonzeros
Variable types: 13 continuous, 0 integer (0 binary)
Explored 0 nodes (0 simplex iterations) in 0.16 seconds
Thread count was 8 (of 8 available processors)
Solution count 1: 54614.4
Optimal solution found (tolerance 1.00e-04)
Best objective 5.461439700000e+04, best bound 5.461439700000e+04, gap 0.0000%
User-callback calls 591, time in user-callback 0.00 sec
You could perhaps experiment a bit with fewer scenarios at first, to get a better sense of behavior, and check if L-shaped results match the DEP etc.
Integer constraints are difficult, and I currently only offer some experimental extensions for L-shaped. If your first-stage only has binary variables, you could try set_optimizer_attribute(sp, IntegerStrategy(), CombinatorialCuts()
, otherwise I do not have many suggestions.
Since you have access to Gurobi you could also try the ProgressiveHedging.Optimizer
, probably with set_optimizer_attribute(sp, Penalizer(), Adaptive()
, as another decomposition approach. It is not necessarily more efficient since the subproblems will be MIQP, but worth to try.
Thank you very much for this valuable reply. I am trying to reduce my scenarios. By the way, does Gurobi support the decomposition methods now ? Some time ago, I have asked if Gurobi supports the decomposition methods,like Benders? The answer is no(maybe not support Benders)
I am not aware of it at least. I believe CPLEX has a Benders implementation.
Okay. Just now I made a mistake and lead to the iteration process premature convergence. In fact, there is no convergence tendency of iteration and sometimes even large fluctuations of my subproblem objective function value as I said at the top of the discussion. Because my subproblem is infeasible sometimes, so I relaxed some constraints and introduced penalty to my subproblem objective function, does it influence the convergence of the whole L-shaped iteration? And a small problem...(if I do not set the termination conditions(e.g. maximum iteration times), the iteration process will continue until the proper gap is reached?)
The convergence behavior is problem-dependent so I really cannot say. I again suggest that you first consider smaller instances and see if you can solve them in finite time at least, and otherwise reconsider your model.
Yes, there are currently no user-defined stopping rules for L-shaped such as max_iterations, so you have to ctrl-c to stop earlier. I will look into adding custom termination rules like I have in QuasiGradient.Optimizer
at some point.
ok, so when I try to change the optimizer from LShaped.Optimizer to ProgressiveHedging.Optimizer, why it tells me the following error:
LoadError: The optimizer StochasticPrograms.ProgressiveHedging.Optimizer has no loaded structure. Consider
load_structure!``
I do not support replacing the underlying structure, so you can not always just switch out the optimizer. You need to re-instantiate the problem with the progressive-hedging optimizer from the get go. The error messages could be improved here probably.
Well, I have cleared the model and re-instantiate the problem using sto=instantiate(model,[S1,S2,S3,S4,S5,S6,S7,S8,S9,S10],optimizer=ProgressiveHedging.Optimizer);
However, it has the same error,
ERROR: LoadError: The optimizer StochasticPrograms.ProgressiveHedging.Optimizer has no loaded structure. Consider
load_structure!``
Ah, I see. The progressive-hedging solver does not have a master optimizer, only a subproblem optimizer (It decomposes completely into subproblems). This is definitely not captured correctly in the error, I will fix that. Just do not set a MasterOptimizer when using progressive-hedging.
So I set
sto=instantiate(model,[S1,S2,S3,S4,S5,S6,S7,S8,S9,S10],optimizer=ProgressiveHedging.Optimizer);
optimize!(sto)
instead of
sto=instantiate(model,[S1,S2,S3,S4,S5,S6,S7,S8,S9,S10],optimizer=ProgressiveHedging.Optimizer);
set_optimizer_attribute(sto,MasterOptimizer(),Gurobi.Optimizer);
optimize!(sto)
why it still has the same error?
You still need to set a subproblem optimizer: set_optimizer_attribute(sto, SubProblemOptimizer(), Gurobi.Optimizer)
.
All right, I forget to tell that when I set the solver of subproblem,
sto=instantiate(model,[S1,S2,S3,S4,S5,S6,S7,S8,S9,S10],optimizer=ProgressiveHedging.Optimizer);
set_optimizer_attribute(sto,SubproblemOptimizer(),Gurobi.Optimizer);
optimize!(sto)
it has a strange error,
LoadError: UndefVarError: SubproblemOptimizer not defined
so I just delete it
It is a typo, SubProblemOptimizer
instead of SubproblemOptimizer
.
thank you very much for these valuable replies, Martin. I have used the processivehedging method. What is the convergence criterion? Can I set the gap(e.g. 1%) of Gurobi for every scenario-dependence subproblems to stop?
You can modify both the PrimalTolerance
and the DualTolerance
of the algorithm. The printouts during the procedure should indicate how they evolve. The purpose of the Adaptive
penalizer is to acquire a good balance between primal and dual progress, but you might have to tune its parameters.
You can also set the tolerance of each subproblem solve directly through Gurobi using RawSubProblemOptimizerParameter
just like you would in JuMP with RawParameter
. I think
MOI.set(opt, RawSubProblemOptimizerParameter("BarConvTol"), 1e-2)
is what you want, but check the Gurobi docs to be sure.
Sorry, since its integer it is more likely
MOI.set(opt, RawSubProblemOptimizerParameter("MIPGap"), 1e-2)
you are looking for.
You could also try any of the regularized L-shaped methods:
set_optimizer_attribute(sp, Regularizer(), RegularizedDecomposition())
set_optimizer_attribute(sp, Regularizer(), TrustRegion())
set_optimizer_attribute(sp, Regularizer(), LevelSet())
Again, parameter tuning might be required.
I have tried to adjust my master problem. And solve it with set_optimizer_attribute(sto,IntegerStrategy(), CombinatorialCuts())
;However, it tells me my subproblem infeasible. I have one solution method,which is to introduce the relaxed variable into the infeasible constraints. Is there better methods to deal with subproblem infeasibility?
┌ Warning: Stochastic program is not second-stage feasible at the current decision. Rerun procedure with feasibility_strategy = FeasibilityCuts to use feasibility cuts.
└ @ StochasticPrograms.LShaped C:\Users\Lenovo\.julia\packages\StochasticPrograms\Jl6sf\src\solvers\structured\lshaped\execution\common.jl:92
L-Shaped Gap Time: 0:00:07 (2 iterations)
Objective: Inf
Early termination: INFEASIBLE
Number of cuts: 10
Iterations: 2
set_optimizer_attribute(sto, FeasibilityStrategy(), FeasibilityCuts()
to enable feasibility cuts (the warning is apparently slightly outdated, will fix).
I find if I use set_optimizer_attribute(sto, FeasibilityStrategy(), FeasibilityCuts())
, it will be still infeasible after many iterations, but the model can be solved as feasibility if I deal with all scenarios together. Whether it can be judged L-shaped method is not suitable for solving this kind of problem?
L-Shaped Gap Time: 4:17:47 (731 iterations)
Objective: Inf
Early termination: INTERRUPTED
Number of cuts: 7310
Iterations: 731
It can take a long time to locate the feasibility set using cuts, but this is another highly problem-dependent aspect. Converting to penalty functions is a good method for finding the most difficult infeasibilities. You can also consider crash starting and hope that you start and stay in the feasible set. I cannot say what solver algorithms would be most suitable, or if you should reconsider aspects of your model, you will just have to experiment. If you can solve the deterministic equivalent in reasonable time with Gurobi, it could be the best option.
Hi, Martin I have used StochasticPrograms to solve my model, However,there is a warning:
the first stage of my model is an MILP model,the second stage of my model is a LP model,I use LShaped.Optimizer to do it, I find there is no convergence tendency of iteration and sometimes even large fluctuations of my subproblem objective function value, is it related to the MILP master problem. As my best knowledge, there is some difference between the L shaped method and the integer L-shaped method, if I use Lshaped.Optimizer, which method the optimizer use? Thanks a lot!