Those tricky booleans...
150 views
Skip to first unread message
mathieu...@gmail.com
Nov 20, 2015, 10:59:49 AM11/20/15
to AMPL Modeling Language
Good morning everyone,
I have been using AMPL with Xpress for a few months, happily solving MIQCQP problems with up to ~20.000 variables (among which only less than 10 integer ones) and ~30.000 constraints. For the present problem though, I use a smaller test case with around 350 variables and 700 constraints.
I am trying to add a sort of "de/re-activation" functionality to my model. Therefore, say x is a (continuous) variable and xMin, xMax are parameters, I wish to replace a constraint
xMin <= x <= xMax
with the following linear one:
b*xMin <= x <= b* xMax
where b is a new binary variable.
If b starts at 1, all seems to work fine: it ends up at 1 or 0 as expected according to my test cases.
However, if b=0 at the starting point, xpress tells me the problem is infeasible, while I know it's not (a solution exists if b=1). And it gets better: on a case where both b=0 and b=1 are feasible, the solution says b=0 even though b=1 is considerably better (again this does not happen if b=1 at the starting point).
Any help to start the investigation would be much appreciated!
Note: I am not allowed to post my files here (yet). Here is a log, however. I'm particularly skeptical about that "global search complete" bit, as it would mean the proper solution was examined and wrongly deemed infeasible...
Have a good day,
Mathieu
Presolve eliminates 734 constraints and 179 variables.
Substitution eliminates 282 variables.
Adjusted problem:
365 variables:
1 binary variable
227 nonlinear variables
137 linear variables
702 constraints; 2383 nonzeros
214 nonlinear constraints
488 linear constraints
72 equality constraints
630 inequality constraints
1 linear objective; 180 nonzeros.
Presolve eliminates 509 constraints and 215 variables.
Substitution eliminates 282 variables.
Adjusted problem:
329 variables:
1 binary variable
191 nonlinear variables
137 linear variables
518 constraints; 1678 nonzeros
48 nonlinear constraints
470 linear constraints
72 equality constraints
446 inequality constraints
1 linear objective; 179 nonzeros.
XPRESS 27.01: miptol=0.0001
miprelstop=0.0001
mipabsstop=0.0001
feastol=1e-06
optimalitytol=0.0001
defaultalg=2
outlev=1
Reading Problem \s6dc.
Problem Statistics
518 ( 0 spare) rows
330 ( 0 spare) structural columns
1488 ( 0 spare) non-zero elements
143 quadratic elements in 48 quadratic constraints
Global Statistics
1 entities 0 sets 0 set members
Minimizing MIQCQP \s6dc.
Original problem has:
518 rows 330 cols 1488 elements 1 globals
48 qrows 143 qrowelem
Converted 47 second order cones to standard form
Presolved problem has:
450 rows 413 cols 1267 elements 0 globals
1 qrows 143 qrowelem 47 cones 141 celems
Its Obj Value S Ninf Nneg Sum Dual Inf Time
0 74.783847 D 109 0 .000000 0
0 -502.132891 D 154 0 .000000 0
Barrier cache sizes : L1=32K L2=30720K
Using AVX support
Cores per CPU (CORESPERCPU): 24
Barrier starts, with L2 cache 1280K
Matrix ordering - Dense cols.: 188 NZ(L): 5679 Flops: 48022
Its P.inf D.inf U.inf Primal obj. Dual obj. Compl.
0 1.91e+002 9.88e+002 2.50e+000 -2.0815178e+003 -5.4468645e+002 1.0e+003
1 9.77e+001 5.04e+002 1.28e+000 -1.0868614e+003 -3.0300051e+002 6.7e+002
2 4.56e+001 2.35e+002 5.95e-001 -5.0492024e+002 -1.3937972e+002 4.0e+002
3 2.64e+001 1.36e+002 3.45e-001 -2.9437318e+002 -8.2594097e+001 2.7e+002
4 1.37e+001 7.08e+001 1.79e-001 -1.5437467e+002 -4.4330600e+001 1.7e+002
5 5.46e+000 2.82e+001 7.13e-002 -6.1789561e+001 -1.7995837e+001 7.4e+001
6 4.53e+000 2.34e+001 5.92e-002 -5.1148826e+001 -1.4831402e+001 6.2e+001
7 3.50e+000 1.81e+001 4.57e-002 -3.9515800e+001 -1.1454878e+001 4.8e+001
8 2.86e+000 1.48e+001 3.74e-002 -3.2370275e+001 -9.4308187e+000 3.7e+001
9 2.76e+000 1.42e+001 3.60e-002 -3.0917284e+001 -8.7926119e+000 2.9e+001
10 2.14e+000 1.11e+001 2.80e-002 -3.0316323e+001 -8.0355371e+000 2.0e+001
11 1.17e+000 6.06e+000 1.53e-002 -2.8111021e+001 -6.0417595e+000 1.1e+001
12 6.58e-001 3.40e+000 8.60e-003 -2.5028154e+001 -3.0635028e+000 6.3e+000
13 3.84e-001 1.98e+000 5.02e-003 -2.1598611e+001 2.8092686e-001 3.7e+000
14 2.18e-001 1.12e+000 2.84e-003 -1.8929642e+001 2.8945195e+000 2.2e+000
15 1.13e-001 5.83e-001 1.47e-003 -1.7996642e+001 3.9486674e+000 1.1e+000
16 5.57e-002 2.88e-001 7.28e-004 -1.7807318e+001 4.5765369e+000 5.6e-001
17 2.73e-002 1.41e-001 3.56e-004 -1.7772064e+001 5.5748929e+000 2.8e-001
18 1.33e-002 1.07e-001 1.74e-004 -1.7764396e+001 7.5693620e+000 1.3e-001
19 6.50e-003 1.07e-001 8.50e-005 -1.7762159e+001 1.1644203e+001 6.6e-002
20 3.18e-003 1.06e-001 4.15e-005 -1.7761121e+001 1.9986062e+001 3.2e-002
21 1.55e-003 1.06e-001 2.03e-005 -1.7760609e+001 3.7067561e+001 1.6e-002
22 7.57e-004 1.06e-001 9.89e-006 -1.7760309e+001 7.2047279e+001 7.7e-003
23 3.70e-004 1.06e-001 4.83e-006 -1.7760119e+001 1.4367987e+002 3.7e-003
24 1.81e-004 1.06e-001 2.36e-006 -1.7759998e+001 2.9037194e+002 1.8e-003
25 8.82e-005 1.06e-001 1.15e-006 -1.7759922e+001 5.9077406e+002 8.9e-004
26 4.31e-005 1.06e-001 5.63e-007 -1.7759876e+001 1.2059512e+003 4.4e-004
27 2.10e-005 1.06e-001 2.75e-007 -1.7759853e+001 2.4657414e+003 2.1e-004
28 1.03e-005 1.06e-001 1.34e-007 -1.7759842e+001 5.0456024e+003 1.0e-004
29 5.01e-006 1.06e-001 6.55e-008 -1.7759837e+001 1.0328770e+004 5.1e-005
30 2.45e-006 1.06e-001 3.20e-008 -1.7759834e+001 2.1147901e+004 2.5e-005
31 1.20e-006 1.06e-001 1.56e-008 -1.7759833e+001 4.3303846e+004 1.2e-005
32 5.84e-007 1.06e-001 7.63e-009 -1.7759832e+001 8.8675879e+004 5.9e-006
33 2.85e-007 1.06e-001 3.72e-009 -1.7759832e+001 1.8159096e+005 2.9e-006
34 1.39e-007 1.06e-001 1.82e-009 -1.7759832e+001 3.7186698e+005 1.4e-006
35 6.80e-008 1.06e-001 8.88e-010 -1.7759831e+001 7.6152363e+005 6.9e-007
36 3.32e-008 1.06e-001 4.34e-010 -1.7759831e+001 1.5594816e+006 3.4e-007
37 1.62e-008 1.06e-001 2.12e-010 -1.7759831e+001 3.1935790e+006 1.6e-007
Barrier method finished in 0 seconds
Problem is infeasible after 37 iterations
0 -392.332146 D 119 0 .000000 0
0 -502.132891 D 130 0 .000000 0
Barrier cache sizes : L1=32K L2=30720K
Using AVX support
Cores per CPU (CORESPERCPU): 24
Barrier starts, with L2 cache 1280K
Matrix ordering - Dense cols.: 188 NZ(L): 5679 Flops: 48022
Its P.inf D.inf U.inf Primal obj. Dual obj. Compl.
0 1.91e+002 9.88e+002 2.50e+000 -2.0815178e+003 -5.4468645e+002 1.0e+003
1 9.77e+001 5.04e+002 1.28e+000 -1.0868614e+003 -3.0300051e+002 6.7e+002
2 4.56e+001 2.35e+002 5.95e-001 -5.0492024e+002 -1.3937972e+002 4.0e+002
3 2.64e+001 1.36e+002 3.45e-001 -2.9437318e+002 -8.2594097e+001 2.7e+002
4 1.37e+001 7.08e+001 1.79e-001 -1.5437467e+002 -4.4330600e+001 1.7e+002
5 5.46e+000 2.82e+001 7.13e-002 -6.1789561e+001 -1.7995837e+001 7.4e+001
6 4.53e+000 2.34e+001 5.92e-002 -5.1148826e+001 -1.4831402e+001 6.2e+001
7 3.50e+000 1.81e+001 4.57e-002 -3.9515800e+001 -1.1454878e+001 4.8e+001
8 2.86e+000 1.48e+001 3.74e-002 -3.2370275e+001 -9.4308187e+000 3.7e+001
9 2.76e+000 1.42e+001 3.60e-002 -3.0917284e+001 -8.7926119e+000 2.9e+001
10 2.14e+000 1.11e+001 2.80e-002 -3.0316323e+001 -8.0355371e+000 2.0e+001
11 1.17e+000 6.06e+000 1.53e-002 -2.8111021e+001 -6.0417596e+000 1.1e+001
12 6.58e-001 3.40e+000 8.60e-003 -2.5028154e+001 -3.0635028e+000 6.3e+000
13 3.84e-001 1.98e+000 5.02e-003 -2.1598611e+001 2.8092685e-001 3.7e+000
14 2.18e-001 1.12e+000 2.84e-003 -1.8929642e+001 2.8945195e+000 2.2e+000
15 1.13e-001 5.83e-001 1.47e-003 -1.7996642e+001 3.9486674e+000 1.1e+000
16 5.57e-002 2.88e-001 7.28e-004 -1.7807318e+001 4.5765369e+000 5.6e-001
17 2.73e-002 1.41e-001 3.56e-004 -1.7772064e+001 5.5748929e+000 2.8e-001
18 1.33e-002 1.07e-001 1.74e-004 -1.7764396e+001 7.5693620e+000 1.3e-001
19 6.50e-003 1.07e-001 8.50e-005 -1.7762159e+001 1.1644203e+001 6.6e-002
20 3.18e-003 1.06e-001 4.15e-005 -1.7761121e+001 1.9986062e+001 3.2e-002
21 1.55e-003 1.06e-001 2.03e-005 -1.7760609e+001 3.7067561e+001 1.6e-002
22 7.57e-004 1.06e-001 9.89e-006 -1.7760309e+001 7.2047279e+001 7.7e-003
23 3.70e-004 1.06e-001 4.83e-006 -1.7760119e+001 1.4367987e+002 3.7e-003
24 1.81e-004 1.06e-001 2.36e-006 -1.7759998e+001 2.9037194e+002 1.8e-003
25 8.82e-005 1.06e-001 1.15e-006 -1.7759922e+001 5.9077406e+002 8.9e-004
26 4.31e-005 1.06e-001 5.63e-007 -1.7759876e+001 1.2059512e+003 4.4e-004
27 2.10e-005 1.06e-001 2.75e-007 -1.7759853e+001 2.4657413e+003 2.1e-004
28 1.03e-005 1.06e-001 1.34e-007 -1.7759842e+001 5.0456023e+003 1.0e-004
29 5.01e-006 1.06e-001 6.55e-008 -1.7759837e+001 1.0328769e+004 5.1e-005
30 2.45e-006 1.06e-001 3.20e-008 -1.7759834e+001 2.1147897e+004 2.5e-005
31 1.20e-006 1.06e-001 1.56e-008 -1.7759833e+001 4.3303841e+004 1.2e-005
32 5.84e-007 1.06e-001 7.63e-009 -1.7759832e+001 8.8675858e+004 5.9e-006
33 2.85e-007 1.06e-001 3.72e-009 -1.7759832e+001 1.8159091e+005 2.9e-006
34 1.39e-007 1.06e-001 1.82e-009 -1.7759832e+001 3.7186691e+005 1.4e-006
35 6.80e-008 1.06e-001 8.88e-010 -1.7759831e+001 7.6152338e+005 6.9e-007
36 3.32e-008 1.06e-001 4.34e-010 -1.7759831e+001 1.5594810e+006 3.4e-007
37 1.62e-008 1.06e-001 2.12e-010 -1.7759831e+001 3.1935777e+006 1.6e-007
Barrier method finished in 0 seconds
Problem is infeasible after 37 iterations
*** Solution loaded **** Time: 0 Obj: 1.00000E+40
Will try to keep branch and bound tree memory usage below 110.0Gb
Barrier cache sizes : L1=32K L2=30720K
Using AVX support
Cores per CPU (CORESPERCPU): 24
Barrier starts, using up to 48 threads, 24 cores
Number of threads is reduced to 32 due to memory limitations
Matrix ordering - Dense cols.: 188 NZ(L): 5679 Flops: 48022
Its P.inf D.inf U.inf Primal obj. Dual obj. Compl.
0 1.91e+002 9.88e+002 2.50e+000 -2.0815178e+003 -5.4385752e+002 1.0e+003
1 9.78e+001 5.05e+002 1.28e+000 -1.0879567e+003 -3.0282132e+002 6.6e+002
2 4.56e+001 2.35e+002 5.95e-001 -5.0493666e+002 -1.3925681e+002 3.9e+002
3 2.64e+001 1.36e+002 3.45e-001 -2.9438099e+002 -8.2505305e+001 2.7e+002
4 1.33e+001 6.87e+001 1.74e-001 -1.4979005e+002 -4.3021796e+001 1.6e+002
5 5.22e+000 2.70e+001 6.82e-002 -5.9154300e+001 -1.7232662e+001 7.0e+001
6 4.26e+000 2.20e+001 5.57e-002 -4.8166313e+001 -1.3960798e+001 5.8e+001
7 3.36e+000 1.73e+001 4.39e-002 -3.7932308e+001 -1.0991569e+001 4.6e+001
8 2.83e+000 1.46e+001 3.69e-002 -3.2021468e+001 -9.3438205e+000 3.6e+001
9 2.77e+000 1.43e+001 3.62e-002 -3.1075855e+001 -8.8627020e+000 2.9e+001
10 2.17e+000 1.12e+001 2.84e-002 -3.0466549e+001 -8.1388686e+000 2.0e+001
11 1.19e+000 6.16e+000 1.56e-002 -2.8359795e+001 -6.2146075e+000 1.1e+001
12 6.67e-001 3.45e+000 8.72e-003 -2.5280157e+001 -3.2605586e+000 6.3e+000
13 3.90e-001 2.01e+000 5.09e-003 -2.1856786e+001 8.1946175e-002 3.7e+000
14 2.22e-001 1.14e+000 2.90e-003 -1.9105222e+001 2.7740849e+000 2.2e+000
15 1.15e-001 5.95e-001 1.51e-003 -1.8102882e+001 3.8832925e+000 1.1e+000
16 5.70e-002 2.94e-001 7.44e-004 -1.7899086e+001 4.5080571e+000 5.7e-001
17 2.79e-002 1.44e-001 3.64e-004 -1.7861361e+001 5.4773787e+000 2.8e-001
18 1.36e-002 1.09e-001 1.78e-004 -1.7853228e+001 7.4086974e+000 1.4e-001
19 6.65e-003 1.09e-001 8.69e-005 -1.7850878e+001 1.1353563e+001 6.6e-002
20 3.25e-003 1.09e-001 4.24e-005 -1.7849794e+001 1.9429172e+001 3.2e-002
21 1.59e-003 1.09e-001 2.07e-005 -1.7849263e+001 3.5965385e+001 1.6e-002
22 7.74e-004 1.09e-001 1.01e-005 -1.7848953e+001 6.9828419e+001 7.7e-003
23 3.78e-004 1.09e-001 4.94e-006 -1.7848758e+001 1.3917421e+002 3.8e-003
24 1.85e-004 1.09e-001 2.41e-006 -1.7848633e+001 2.8118323e+002 1.8e-003
25 9.02e-005 1.09e-001 1.18e-006 -1.7848554e+001 5.7199517e+002 9.0e-004
26 4.40e-005 1.09e-001 5.75e-007 -1.7848506e+001 1.1675330e+003 4.4e-004
27 2.15e-005 1.09e-001 2.81e-007 -1.7848483e+001 2.3871049e+003 2.1e-004
28 1.05e-005 1.09e-001 1.37e-007 -1.7848471e+001 4.8846047e+003 1.0e-004
29 5.13e-006 1.09e-001 6.70e-008 -1.7848466e+001 9.9991088e+003 5.1e-005
30 2.50e-006 1.09e-001 3.27e-008 -1.7848463e+001 2.0472840e+004 2.5e-005
31 1.22e-006 1.09e-001 1.60e-008 -1.7848462e+001 4.1921458e+004 1.2e-005
32 5.97e-007 1.09e-001 7.80e-009 -1.7848461e+001 8.5844998e+004 5.9e-006
33 2.92e-007 1.09e-001 3.81e-009 -1.7848461e+001 1.7579377e+005 2.9e-006
34 1.42e-007 1.09e-001 1.86e-009 -1.7848461e+001 3.5999527e+005 1.4e-006
35 6.95e-008 1.09e-001 9.08e-010 -1.7848461e+001 7.3721202e+005 6.9e-007
36 3.39e-008 1.09e-001 4.43e-010 -1.7848460e+001 1.5096951e+006 3.4e-007
37 1.66e-008 1.09e-001 2.17e-010 -1.7848460e+001 3.0916235e+006 1.7e-007
Barrier method finished in 0 seconds
Problem is infeasible after 37 iterations
Problem is infeasible
*** Search completed *** Time: 0 Nodes: 0
Problem is integer infeasible
Number of integer feasible solutions found is 0
Best bound is 1.00000E+40
Uncrunching matrix
?429 Error: No basis is available
XPRESS 27.01: Global search complete - infeasible (no integer solution found)
Best bound determined so far 1e+40
0 branch and bound nodes
No basis.
47 cones detected.
Robert Fourer
Nov 20, 2015, 7:59:58 PM11/20/15
to am...@googlegroups.com
In the Xpress log, it appears that infeasibility is being detected when solving the continuous relaxation of your problem, which is something that should not be sensitive to any proposed starting points.
What AMPL statement are you using to "start b at 0"? The results are consistent with b being fixed at zero instead of being given a starting value of 0. (However you do say that when b is given a starting value of 1, it is not fixed at 1 and sometimes comes out 0 in the optimal solution.)
Can you show logs of two runs, one with b having starting value 0 and one with b having starting value 1, but otherwise with everything the same? That might suggest why the starting value is making a difference.
Bob Fourer
am...@googlegroups.com
=======
What AMPL statement are you using to "start b at 0"? The results are consistent with b being fixed at zero instead of being given a starting value of 0. (However you do say that when b is given a starting value of 1, it is not fixed at 1 and sometimes comes out 0 in the optimal solution.)
Can you show logs of two runs, one with b having starting value 0 and one with b having starting value 1, but otherwise with everything the same? That might suggest why the starting value is making a difference.
Bob Fourer
am...@googlegroups.com
=======
muzt...@gmail.com
Nov 23, 2015, 11:02:15 AM11/23/15
to AMPL Modeling Language, 4...@ampl.com
Good morning Bob,
Many thanks for answering.
I agree with your observation that the starting point shouldn't explain the infeasibility... Thus my call for help ;-).
The line initialising the variable is this one (where bON is the "b" I was referring to earlier, and where InitConfigG is given in a .dat file for every member of the set GENERATORS):
var bON {j in GENERATORS} binary, :=InitConfigG[j];
(Through other parameters, all bON but one are fixed to their initial value.)
I join two logs, with either bON = 0 or bON = 1 at the starting point. I ran them a few seconds ago, and that is the only change between both runs.
I also join a .sol file, where a search on "bON['GENB23']" confirms that bON seems correctly defined.
Thanks again for you time,
Mathieu
Many thanks for answering.
I agree with your observation that the starting point shouldn't explain the infeasibility... Thus my call for help ;-).
The line initialising the variable is this one (where bON is the "b" I was referring to earlier, and where InitConfigG is given in a .dat file for every member of the set GENERATORS):
var bON {j in GENERATORS} binary, :=InitConfigG[j];
(Through other parameters, all bON but one are fixed to their initial value.)
I join two logs, with either bON = 0 or bON = 1 at the starting point. I ran them a few seconds ago, and that is the only change between both runs.
I also join a .sol file, where a search on "bON['GENB23']" confirms that bON seems correctly defined.
Thanks again for you time,
Mathieu
Robert Fourer
Nov 24, 2015, 1:28:33 PM11/24/15
to am...@googlegroups.com
The starting point does not make any difference to the problem that is sent to the solver, but the logs suggest that the problems in StartAtZero and StartAtOne are slightly different. In particular:
StartAtZero:
Presolve eliminates 512 constraints and 215 variables.
Substitution eliminates 282 variables.
...
611 constraints; 2020 nonzeros
StartAtOne:
Presolve eliminates 510 constraints and 213 variables.
Substitution eliminates 284 variables.
...
611 constraints; 2022 nonzeros
To look into this further, I suggest adding the command "expand >StartAtZero.out;" just before "solve;" in the first run, and then changing this to "expand >StartAtOne.out;" for the second run, to create two files that show explicitly the constraints that AMPL is generating at the time that the solve is done. Then you can use a file comparison utility to look for differences.
If the two files are the same, then use "solexpand" instead of "expand" to compare the constraints that AMPL is generating for the solver, after the presolve reductions are made; this will reflect, in particular, any differences due to variables being fixed.
You might also learn more about any differences by generating files like your "Case23.sol" for both cases, and comparing them to look for any differences other than in the initial value of bON['GENB23'].
Bob Fourer
am...@googlegroups.com
=======
StartAtZero:
Presolve eliminates 512 constraints and 215 variables.
Substitution eliminates 282 variables.
...
611 constraints; 2020 nonzeros
StartAtOne:
Presolve eliminates 510 constraints and 213 variables.
Substitution eliminates 284 variables.
...
611 constraints; 2022 nonzeros
To look into this further, I suggest adding the command "expand >StartAtZero.out;" just before "solve;" in the first run, and then changing this to "expand >StartAtOne.out;" for the second run, to create two files that show explicitly the constraints that AMPL is generating at the time that the solve is done. Then you can use a file comparison utility to look for differences.
If the two files are the same, then use "solexpand" instead of "expand" to compare the constraints that AMPL is generating for the solver, after the presolve reductions are made; this will reflect, in particular, any differences due to variables being fixed.
You might also learn more about any differences by generating files like your "Case23.sol" for both cases, and comparing them to look for any differences other than in the initial value of bON['GENB23'].
Bob Fourer
am...@googlegroups.com
=======
muzt...@gmail.com
Nov 26, 2015, 3:23:05 PM11/26/15
to AMPL Modeling Language, 4...@ampl.com
Dear Robert,
Problem solved, you pointed me towards the solution ;-) .
A word of explanation, in case you're curious about it:
I am developing a tool for solving some class of optimal power flow problems (it's a very common problem in the energy world, and everybody tries to solve bigger/more comprehensive cases). At the beginning, we didn't intend to support generators (i.e. power plants) (de)activation. Each of them was either on or off in the case of interest, and that was it.
In the constraints stating that all the power going into a node of the network has to come out or be consumed, we initially had a (constant) flag on each generator, and its (constant) production would only be considered if the generator was on. The idea then was that the production would become a variable if and when needed. I completely forgot about that flag when I adapted the model to support generator deactivation. It turns out this flag was responsible for some variables to be dropped during presolve when a generator was initially declared off.
Once again, thank you very much for your time and help.
Happy thanksgiving if you're over there,
Mathieu
Reply all
Reply to author
Forward
0 new messages