Problem with the initialization step in a decomposition technique
enhany75
I am coding an hybrid algorithm mixes outer approximation and
decomposition techniques to solve a nonlinear problem. the algorithm
runs so fine for a small size problem but for medium size one I have a
problem with the initialization step. This step solves a linearized
version of the nonlinear model but it gives me this error
initial_problem.result = failure
If i take this linearized version in a separate file to be solved
alone, it sounds good.
Could you please help
enhany75
appears because I break the run. the problem is that the solver stuck
in solving this initialization problem. I am wondering why, because it
is solvable in about 1 sec if it is tried separately.
Robert Fourer
If the solver is behaving differently when tried separately and when tried
as part of the hybrid algorithm, then there must be some difference between
the problems that it is receiving from AMPL in the two situations. I would
set "option show_stats 1;" to be sure that the problems aren't obviously of
different sizes, and I would check that the initial values of the variables
are not different. But it is hard to say with any certainty what the
difficulty might be, given only the brief description that you have
provided. Can you post an example of the files you are using for the hybrid
algorithm, along with a more detailed description of what goes wrong when
you run them?
Bob Fourer
4...@ampl.com
enhany75
objective and variables values.
here is the output of the decomposition method after about 30 min run
for a bigger size problem:
Presolve eliminates 0 constraints and 13318 variables.
Adjusted problem:
34152 variables:
17359 binary variables
16793 linear variables
53619 constraints, all linear; 172115 nonzeros
1 linear objective; 34152 nonzeros.
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
srun: interrupt (one more within 1 sec to abort)
srun: task0: running
<BREAK> (cplex)
CPLEX solution status 13 with fixed integers:
aborted in phase II
initial_problem.result = failure
Presolve eliminates 0 constraints and 47469 variables.
Adjusted problem:
1 variable, all nonlinear
16807 constraints, all linear; 16807 nonzeros
1 nonlinear objective; 1 nonzero.
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
_solve_time = 0.03499500000000921
T_cut [*] :=
1 0.05
;
sub_objective = 28280.001989516993
Presolve eliminates 0 constraints and 30677 variables.
Adjusted problem:
16794 variables, all linear
33600 constraints, all linear; 33601 nonzeros
1 linear objective; 16794 nonzeros.
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
subject to optimality_cut[1]:
534000*T + Alpha >= 53400;
Alpha = 0
msoln = 1
Presolve eliminates 0 constraints and 30678 variables.
Adjusted problem:
16794 variables, all linear
33600 constraints, all linear; 33601 nonzeros
1 linear objective; 16794 nonzeros.
bender_upper_bound = 1882.6318805340982
bender_lower_bound = 1369.8269895170597
Presolve eliminates 0 constraints and 30112 variables.
Adjusted problem:
17360 variables:
17359 binary variables
1 linear variable
36813 constraints, all linear; 121725 nonzeros
1 linear objective; 17360 nonzeros.
And here is the code of this decomposition method;
model oa_benY.mod;
data inventory8.txt;
param sub_objective;
param m;
param bender_upper_bound;
param bender_lower_bound;
option show_stats 1;
option solver_msg 0;
option presolve 0;
option eexit -500;
option display_precision 0;
suffix up OUT;
suffix down OUT;
problem initial_problem: T, Xjiq, Xkiq, Yjiqbl, Ykiqbl, Zjiqbl,
Zkiqbl,
assignment_t2_1, assignment_t2_2, assignment_t1_1,
assignment_t1_2,t2_cycle_feasibiliy, t1_cycle_feasibiliy,
linearization_1,linearization_3, linearization_5,
linearization_6,linearization_7,linearization_9, linearization_11,
linearization_12, holding_cost;
problem bender_master_problem: Xjiq, Xkiq, Yjiqbl,Ykiqbl, Beta,
assignment_t2_1,
assignment_t2_2,assignment_t1_1, assignment_t1_2,
linearization_1,linearization_3,linearization_5, linearization_6,
linearization_11, linearization_12, bender_cut, bender_master_cost;
problem bender_sub_problem: T, Zjiqbl,Zkiqbl,Alpha,
t2_cycle_feasibiliy,t1_cycle_feasibiliy, linearization_7,
linearization_9,
optimality_cut,Yjiqbl_values, Ykiqbl_values, bender_sub_cost;
problem sub_problem: T, t2_cycle_feasibiliy, t1_cycle_feasibiliy,
linearization_7, linearization_9, total_cost;
solve initial_problem;
display initial_problem.result;
display T;
display holding_cost;
display Xjiq;
display Xkiq;
display Yjiqbl;
display Ykiqbl;
display Zjiqbl;
display Zkiqbl;
repeat {
solve sub_problem;
display _solve_time;
let nsoln:= nsoln + 1;
let T_cut[nsoln]:= T;
display T_cut;
let sub_objective := total_cost;
display sub_objective;
## bender iteration ##
repeat {
for {j in t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj
[j]:b <> i and
l<> q} {let Yjiqbl_value[j,i,q,b,l] := Yjiqbl[j,i,q,b,l];}
for {k in t2, i in prodk[k],q in seqk[k], b in prodk[k], l in seqk
[k]:b <> i and
l<> q} {let Ykiqbl_value[k,i,q,b,l] := Ykiqbl[k,i,q,b,l];}
solve bender_sub_problem;
expand optimality_cut;
display Alpha;
let msoln:= msoln +1;
display msoln;
for {j in t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj
[j]:b <> i and
l<> q} {let Yjiqbln[j,i,q,b,l,msoln] := Yjiqbl[j,i,q,b,l];}
for {k in t2, i in prodk[k],q in seqk[k], b in prodk[k], l in seqk
[k]:b <> i and
l<> q} {let Ykiqbln[k,i,q,b,l,msoln] := Ykiqbl[k,i,q,b,l];}
for {j in t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj
[j]:b <> i and
l<> q} {let Gama[j,i,q,b,l,msoln]:= Yjiqbl_values[j,i,q,b,l].dual;}
for {k in t2, i in prodk[k],q in seqk[k], b in prodk[k], l in seqk
[k]:b <> i and
l<> q} {let Eta[k,i,q,b,l,msoln]:= Ykiqbl_values[k,i,q,b,l].dual;}
let bender_sub_obj[msoln]:= bender_sub_cost;
let bender_lower_bound := bender_master_cost;
let bender_upper_bound := bender_sub_cost + sum{k in t2, i in prodk
[k], q in
prodk[k]} ((HRki[k,i]+ HFki[k,i]) * m1* m2* (Dki[k,i]^2) * 0.5 / Pki
[k,i] + HRki
[k,i] * Dki[k,i]*Ski[k,i])* Xkiq[k,i,q]
+ sum{k in t2, i in prodk[k],q in seqk[k], b in prodk[k], l in seqk
[k]:b <> i and
l< q} HRki[k,i]*Dki[k,i] * Ski[k,b]* Ykiqbl [k,i,q,b,l] + sum{k in t2,
i in
prodk[k],q in seqk[k], b in prodk[k], l in seqk[k]:b <> i and l< q}
HRki[k,i]
*Dki[k,i]* m1*m2*Dki[k,b]/Pki[k,b] * (.05* Ykiqbl [k,i,q,b,l])
+sum{k in t2, i in prodk[k],q in seqk[k], b in prodk[k], l in seqk
[k]:b <> i and
l> q} HFki[k,i]*Dki[k,i] * Ski[k,b]* Ykiqbl [k,i,q,b,l] + sum{k in t2,
i in
prodk[k],q in seqk[k], b in prodk[k], l in seqk[k]:b <> i and l> q}
HFki[k,i]
*Dki[k,i] * m1*m2*Dki[k,b]/Pki[k,b] * (.05* Ykiqbl [k,i,q,b,l])
+ sum{j in t1, i in prodj[j], q in prodj[j]} ((HRji[j,i]+ HFji[j,i]) *
m1* (Dji
[j,i]^2) * 0.5 / Pji[j,i] + HRji[j,i] * Dji[j,i]*Sji[j,i])* Xjiq
[j,i,q]
+ sum{j in t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj
[j]:b <> i and
l< q} HRji[j,i]*Dji[j,i] * Sji[j,b]* Yjiqbl [j,i,q,b,l] + sum{j in t1,
i in
prodj[j],q in seqj[j], b in prodj[j], l in seqj[j]:b <> i and l < q}
HRji[j,i]
*Dji[j,i]* m1*Dji[j,b]/Pji[j,b] * (.05* Yjiqbl [j,i,q,b,l])
+sum{j in t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj
[j]:b <> i and
l> q} HFji[j,i]*Dji[j,i] * Sji[j,b]* Yjiqbl [j,i,q,b,l] + sum{j in t1,
i in
prodj[j],q in seqj[j], b in prodj[j], l in seqj[j]:b <> i and l> q}
HFji[j,i]
*Dji[j,i] * m1*Dji[j,b]/Pji[j,b] * (.05* Yjiqbl [j,i,q,b,l]);
display bender_upper_bound;
display bender_lower_bound;
if (bender_upper_bound - bender_lower_bound) < 0.005 and
(bender_upper_bound -
bender_lower_bound) > -0.005 then break;
solve bender_master_problem;
display Beta;
}
###
display _solve_time;
let msoln:= 0;
display T;
display T;
display Xjiq;
display Xkiq;
display total_cost;
if (bender_master_cost - total_cost) > -0.1 and (total_cost -
bender_master_cost) < 0.1 then break;
}
display _total_solve_time;
Robert Fourer
The first problem that you solve (the initialization step) involves a rather
large mixed-integer program, so I can imagine that it might be hard for
CPLEX. To get a better idea what is going on, insert the following command
with the other "option" statements toward the beginning of the decomposition
script:
option cplex_options 'mipdisplay 2 mipinterval 1000 time 3600';
This should result in a long log of information about the initialization,
progress, and results of CPLEX's branch-and-bound procedure, which may
enable me to give some advice about solving the problem. The "time"
directive insures that CPLEX will stop after an hour even if its best
solution so far has not been proven optimal.
>
> You received this message because you are subscribed to the Google Groups
> "AMPL Modeling Language" group.
> To post to this group, send email to am...@googlegroups.com.
> To unsubscribe from this group, send email to
> ampl+uns...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/ampl?hl=en.
>
enhany75
min,
thanks a lot for ur help
MIP Presolve eliminated 18822 rows and 18817 columns.
MIP Presolve modified 75264 coefficients.
Reduced MIP has 40416 rows, 19200 columns, and 116352 nonzeros.
Clique table members: 21600.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 10.00 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node
ItCnt Gap
0 0 19487.2752 3409 19487.2752
14772
* 0+ 0 23038.1724 19487.2752
14772 15.41%
0 0 19604.4137 3434 23038.1724 Cuts: 281
18399 14.90%
0 0 19605.6067 3505 23038.1724 Cuts: 116
19911 14.90%
0 0 19610.8576 3520 23038.1724 Cuts: 202
22230 14.88%
* 0+ 0 23002.6469 19610.8576
22230 14.75%
0 0 19610.8576 3512 23002.6469 Cuts: 184
23865 14.75%
0 0 19650.3290 3725 23002.6469 Cuts: 191
27038 14.57%
0 0 19721.9728 3679 23002.6469 Cuts: 136
30427 14.26%
* 0+ 0 22960.4065 19721.9728
30427 14.10%
0 0 19806.7353 3622 22960.4065 Cuts: 103
34059 13.74%
0 0 19852.9347 3660 22960.4065 Cuts: 122
38340 13.53%
* 0+ 0 22886.8147 19852.9347
38340 13.26%
0 0 19871.5945 3629 22886.8147 Cuts: 124
40864 13.17%
0 0 19879.5913 3563 22886.8147 Cuts: 119
42879 13.14%
0 0 19892.1634 3660 22886.8147 Cuts: 91
45932 13.08%
0 0 19914.4297 3765 22886.8147 Cuts: 122
48836 12.99%
* 0+ 0 22803.2731 19914.4297
48836 12.67%
0 0 19928.8093 3699 22803.2731 Cuts: 105
51585 12.61%
0 0 19943.0820 3756 22803.2731 Cuts: 75
54811 12.54%
0 0 19948.3964 3614 22803.2731 Cuts: 83
57744 12.52%
0 0 19951.3769 3785 22803.2731 Cuts: 102
59546 12.51%
0 0 19951.8425 3889 22803.2731 Cuts: 74
60970 12.50%
* 0+ 0 22727.7298 19951.8425
60970 12.21%
0 2 19951.8425 3889 22727.7298 19951.8425
60970 12.21%
Elapsed time = 114.83 sec. (tree size = 0.00 MB)
* 80+ 80 22712.3163 19956.6610
103498 12.13%
* 100+ 100 22707.1941 19956.6610
111540 12.11%
* 340+ 340 22693.2441 19956.6610
195471 12.06%
* 500+ 326 22629.2131 20563.9877
382119 9.13%
* 540+ 238 22568.8512 20565.9857
422344 8.87%
Clique cuts applied: 804
Zero-half cuts applied: 463
Gomory fractional cuts applied: 28
initial_problem.result = limit
T = 1.569614069369809
holding_cost = 22568.85121224676
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
_solve_time = 0.03399500000003286
T_cut [*] :=
1 1.569614069369809
;
sub_objective = 22997.619030485163
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
subject to optimality_cut[1]:
273.168*T + Alpha >= 857.536;
msoln = 1
bender_upper_bound = 22997.6190304872
bender_lower_bound = 6204.333696848739
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
MIP start values provide initial solution with objective 22997.6190.
MIP Presolve eliminated 1 rows and 1 columns.
MIP Presolve modified 37632 coefficients.
Reduced MIP has 40416 rows, 19200 columns, and 116352 nonzeros.
Clique table members: 21600.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 7.55 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node
ItCnt Gap
0 0 21994.6363 3213 22997.6190 21994.6363
14144 4.36%
0 0 22022.6715 3601 22997.6190 Cuts: 296
17698 4.24%
0 0 22022.8046 3761 22997.6190 Cuts: 137
19372 4.24%
0 0 22022.8046 3706 22997.6190 Cuts: 135
21192 4.24%
0 0 22022.8046 3695 22997.6190 Cuts: 160
22993 4.24%
0 0 22024.6966 3562 22997.6190 Cuts: 148
25476 4.23%
0 0 22028.7365 3773 22997.6190 Cuts: 196
28093 4.21%
0 0 22034.6645 3617 22997.6190 Cuts: 89
30575 4.19%
0 0 22038.8655 3853 22997.6190 Cuts: 131
32554 4.17%
0 0 22041.7912 3705 22997.6190 Cuts: 92
34975 4.16%
0 0 22045.7560 3804 22997.6190 Cuts: 114
37355 4.14%
0 0 22052.2790 3880 22997.6190 Cuts: 110
39983 4.11%
0 0 22057.9379 3901 22997.6190 Cuts: 88
42426 4.09%
0 0 22062.3532 3613 22997.6190 Cuts: 98
45259 4.07%
0 0 22064.5258 3719 22997.6190 Cuts: 121
47306 4.06%
Heuristic still looking.
0 2 22064.5258 3719 22997.6190 22064.5258
47306 4.06%
Elapsed time = 89.24 sec. (tree size = 0.00 MB)
* 100+ 100 22981.6722 22074.0829
102454 3.95%
* 240+ 240 22967.3250 22074.0829
163194 3.89%
* 280+ 280 22954.5423 22074.0829
173559 3.84%
srun: interrupt (one more within 1 sec to abort)
srun: task0: running
<BREAK> (cplex)
Clique cuts applied: 676
Zero-half cuts applied: 468
Gomory fractional cuts applied: 5
CPLEX solution status 13 with fixed integers:
aborted in phase II
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
subject to optimality_cut[1]:
273.168*T + Alpha >= 857.536;
msoln = 2
bender_upper_bound = 23024.08842997425
bender_lower_bound = 22954.542312711754
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
MIP start values provide initial solution with objective 23024.0884.
MIP Presolve eliminated 2 rows and 1 columns.
MIP Presolve modified 37632 coefficients.
Reduced MIP has 40416 rows, 19200 columns, and 116352 nonzeros.
Clique table members: 21600.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Terminated
srun: error: n20: task0: Exited with exit code 15
> ...
>
> read more »
Robert Fourer
Based on your output, it seems likely that CPLEX is simply unable to solve
your problems to optimality within the time that you are willing to wait.
The last log line shows a gap between the best lower bound and the best
upper bound found so far of 8.87% in the first hard problem and 3.84% in the
second. CPLEX will not stop and claim success until this gap is only a
fraction of a percent.
It is taking a lot longer to process the nodes than I had guessed, though.
To get more log lines and a better idea of how close the search is getting
to optimal, I suggest using
option cplex_options 'mipdisplay 2 mipinterval 100 clocktype 2 timelimit
3600';
This is also supposed to cause CPLEX to measure time in elapsed seconds
rather than CPU seconds.
Bob Fourer
4...@ampl.com
> > > l> t2,
> > > i in
> > > prodk[k],q in seqk[k], b in prodk[k], l in seqk[k]:b <> i and l> q}
> > > HFki[k,i] *Dki[k,i] * m1*m2*Dki[k,b]/Pki[k,b] * (.05* Ykiqbl
> > > [k,i,q,b,l])
> > > + sum{j in t1, i in prodj[j], q in prodj[j]} ((HRji[j,i]+ HFji[j,i])
> > > + *
> > > m1* (Dji
> > > [j,i]^2) * 0.5 / Pji[j,i] + HRji[j,i] * Dji[j,i]*Sji[j,i])* Xjiq
> > > [j,i,q]
> > > + sum{j in t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj
> > > [j]:b <> i and
> > > l< q} HRji[j,i]*Dji[j,i] * Sji[j,b]* Yjiqbl [j,i,q,b,l] + sum{j in
> > > t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj[j]:b <> i
> > > and l < q} HRji[j,i]
> > > *Dji[j,i]* m1*Dji[j,b]/Pji[j,b] * (.05* Yjiqbl [j,i,q,b,l])
> > > +sum{j in t1, i in prodj[j],q in seqj[j], b in prodj[j], l in seqj
> > > [j]:b <> i and
> > > l> q} HFji[j,i]*Dji[j,i] * Sji[j,b]* Yjiqbl [j,i,q,b,l] + sum{j in
> > > l> t1,
enhany75
option cplex_options 'mipdisplay 2 mipinterval 100 clocktype 2
timelimit
3600';
Could you plesase tell me where is the difficulty of this problem.
If it is not possible to reach an optimal solution for this
internalization problem, I would accept a good feasible one because
the problem is resolved again through decomposition. So, how can I get
a good feasible solution.
Thanks a lot
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
MIP Presolve eliminated 19206 rows and 19201 columns.
MIP Presolve modified 76032 coefficients.
Reduced MIP has 40416 rows, 19200 columns, and 116352 nonzeros.
Clique table members: 21600.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 6.24 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node
ItCnt Gap
0 0 20301.6317 3335 20301.6317
12035
* 0+ 0 23937.1055 20301.6317
12035 15.19%
0 0 20419.4139 3510 23937.1055 Cuts: 288
16324 14.70%
* 0+ 0 23656.5259 20419.4139
16324 13.68%
0 0 20419.4139 3654 23656.5259 Cuts: 121
17653 13.68%
0 0 20419.7940 3359 23656.5259 Cuts: 128
19097 13.68%
0 0 20421.8118 3539 23656.5259 Cuts: 184
21582 13.67%
0 0 20421.8118 3400 23656.5259 Cuts: 140
23150 13.67%
* 0+ 0 23639.2992 20421.8118
23150 13.61%
0 0 20430.4598 3358 23639.2992 Cuts: 155
25548 13.57%
0 0 20462.5584 3475 23639.2992 Cuts: 169
28068 13.44%
0 0 20503.5420 3465 23639.2992 Cuts: 86
31392 13.27%
0 0 20517.2287 3580 23639.2992 Cuts: 88
34968 13.21%
0 0 20548.9422 3563 23639.2992 Cuts: 107
37487 13.07%
0 0 20565.7977 3559 23639.2992 Cuts: 97
41248 13.00%
0 0 20578.6408 3654 23639.2992 Cuts: 136
43296 12.95%
0 0 20590.6240 3576 23639.2992 Cuts: 80
45643 12.90%
0 0 20608.0132 3683 23639.2992 Cuts: 87
47992 12.82%
0 0 20630.9498 3617 23639.2992 Cuts: 79
51434 12.73%
0 0 20644.1850 3647 23639.2992 Cuts: 103
53589 12.67%
0 0 20662.1349 3898 23639.2992 Cuts: 81
56172 12.59%
0 0 20681.2665 3472 23639.2992 Cuts: 78
59961 12.51%
0 0 20696.2515 3733 23639.2992 Cuts: 142
62946 12.45%
0 0 20716.3710 3664 23639.2992 Cuts: 80
65717 12.36%
0 0 20718.2679 3734 23639.2992 Cuts: 70
67879 12.36%
* 0+ 0 23556.3842 20718.2679
67879 12.05%
0 2 20718.2679 3734 23556.3842 20718.2679
67879 12.05%
Elapsed real time = 139.46 sec. (tree size = 0.00 MB)
* 10+ 10 23534.3334 20744.0160
73252 11.86%
* 30+ 30 23504.4466 20744.0160
86892 11.74%
100 102 21519.8914 2875 23504.4466 20744.0160
119161 11.74%
200 202 22096.2691 2176 23504.4466 20744.0160
167687 11.74%
300 300 22724.6083 1181 23504.4466 20744.0160
197578 11.74%
400 400 23099.5857 896 23504.4466 20744.0160
206663 11.74%
* 484+ 318 23396.0095 21405.4503
470138 8.51%
500 324 21448.1813 3383 23396.0095 21407.2952
483171 8.50%
600 359 21847.9570 2602 23396.0095 21407.2952
520122 8.50%
700 386 infeasible 23396.0095 21407.2952
541697 8.50%
Clique cuts applied: 863
Zero-half cuts applied: 506
Gomory fractional cuts applied: 36
initial_problem.result = limit
T = 1.569614069369809
holding_cost = 23396.009482132413
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
_solve_time = 0.03599400000008046
T_cut [*] :=
1 1.569614069369809
;
sub_objective = 23824.777300370824
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
subject to optimality_cut[1]:
273.168*T + Alpha >= 857.536;
msoln = 1
bender_upper_bound = 23824.777300370813
bender_lower_bound = 4863.089243929741
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
MIP start values provide initial solution with objective 23824.7773.
MIP Presolve eliminated 1 rows and 1 columns.
MIP Presolve modified 37632 coefficients.
Reduced MIP has 40416 rows, 19200 columns, and 116352 nonzeros.
Clique table members: 21600.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 13.12 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node
ItCnt Gap
0 0 22804.8586 3438 23824.7773 22804.8586
15034 4.28%
0 0 22836.5204 3314 23824.7773 Cuts: 278
18323 4.15%
0 0 22836.5204 3329 23824.7773 Cuts: 105
19913 4.15%
0 0 22836.5204 3357 23824.7773 Cuts: 157
21716 4.15%
* 0+ 0 23785.4815 22836.5204
21716 3.99%
0 2 22836.5204 3357 23785.4815 22836.5204
21716 3.99%
Elapsed real time = 54.01 sec. (tree size = 0.00 MB)
100 102 23141.2401 2505 23785.4815 22849.5582
73750 3.93%
200 202 23370.5845 1798 23785.4815 22849.5582
115792 3.93%
300 298 23556.2224 1249 23785.4815 22849.5582
127127 3.93%
400 392 23082.9475 2462 23785.4815 22856.5359
151427 3.91%
srun: interrupt (one more within 1 sec to abort)
srun: task0: running
<BREAK> (cplex)
Clique cuts applied: 136
Zero-half cuts applied: 141
Gomory fractional cuts applied: 5
CPLEX solution status 13 with fixed integers:
aborted in phase II
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
subject to optimality_cut[1]:
273.168*T + Alpha >= 857.536;
msoln = 2
bender_upper_bound = 23896.207292310242
bender_lower_bound = 23785.481520515543
ILOG CPLEX 11.000, licensed to "concordia university-montreal,
canada", options: e m b q use=30 MaintenanceEnd=20120930
MIP start values provide initial solution with objective 23896.2073.
MIP Presolve eliminated 2 rows and 1 columns.
MIP Presolve modified 37632 coefficients.
Reduced MIP has 40416 rows, 19200 columns, and 116352 nonzeros.
Clique table members: 21600.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Terminated
> ...
>
> read more »
Robert Fourer
It appears that you are only running CPLEX's branch-and-bound procedure for
several hundred nodes, and this is not enough to complete the search and
declare optimality. CPLEX may be able to reach optimality if you let it run
longer. On the other hand, you can instruct CPLEX to stop prematurely and
to return the best feasible solution that it has found so far, using a
directive such as timelimit or mipgap; see the discussion on pages 70-72 of
www.ampl.com/BOOKLETS/amplcplex110userguide.pdf. In fact I would expect
that CPLEX did return a feasible solution at the end of your run.
Also I just realized that you are setting "option solver_msg 0;" which is
suppressing some useful output. Until you have everything working I would
remove or comment out this statement. At the end of the CPLEX run you
should then see a statement that says that a feasible solution has been
found and that reports the objective value for that solution and the total
number of nodes searched.
CPLEX has to solve at each node an LP derived from the MIP problem. The
difficulty with your first problem is partly that these LPs are large and
take some work to solve, and partly that these LPs do not give an especially
tight lower bound on the optimal solution; the gap between the best lower
bound and the best feasible solution when your run stopped was still 8.5%.
With some study of integer programming and the branch-and-bound procedure,
it is sometimes possible to tighten the formulation and choose non-default
options from the user guide which will speed up the search; but this may be
more trouble than it's worth if it is not so important to get a provably
optimal solution anyway.
Beyond that I cannot say much, though if you want to send me your files I
will try to run them and see if I can reproduce the difficulty.
Bob Fourer
4...@ampl.com