Sub-optimal termination for barrier method optimization without crossover
713 views
Skip to first unread message
Andre Voigt
Feb 10, 2014, 9:18:19 AM2/10/14
to gur...@googlegroups.com
I am trying to solve a linear program (MPS file is attached) in Gurobi 5.0 (through gurobi_cl under Ubuntu 12.04) using the barrier method, with crossover set to 0. It is readily solved with the simplex method or with Crossover=2, as shown in the two first examples below. However, with Method=2 and Crossover=0, Gurobi is unable to find a satisfactory optimal solution (shown in third example). Are there any parameters I could pass to Gurobi in order to allow it to find a more optimal solution (and is there a way for me to figure out why Gurobi terminates on the sub-optimal solution)? The program is solved fast (less than a second), so there is quite a lot of leeway in terms of execution time.
----------------------------------------------------------------------------------------------------------
$ gurobi_cl Method=0 Crossover=0 BarHomogeneous=1 iNJMPS.mps
Set parameter Method to value 0
Set parameter Crossover to value 0
Set parameter BarHomogeneous to value 1
Gurobi Optimizer version 5.0.0 build 9993 (linux64)
Copyright (c) 2012, Gurobi Optimization, Inc.
Read MPS format model from file iNJMPS.mps
Reading time = 0.00 seconds
GENERIC: 838 rows, 1049 columns, 4880 nonzeros
Optimize a model with 838 rows, 1049 columns and 4880 nonzeros
Presolve removed 642 rows and 689 columns
Presolve time: 0.00s
Presolved: 196 rows, 360 columns, 2068 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 6.492191e+04 2.257109e+08 0s
401 -5.2199349e-02 0.000000e+00 0.000000e+00 0s
Solved in 401 iterations and 0.01 seconds
Optimal objective -5.219934930e-02
----------------------------------------------------------------------------------------------------------
$ gurobi_cl Method=2 Crossover=-1 BarHomogeneous=1 iNJMPS.mps
Set parameter Method to value 2
Set parameter Crossover to value -1
Set parameter BarHomogeneous to value 1
Gurobi Optimizer version 5.0.0 build 9993 (linux64)
Copyright (c) 2012, Gurobi Optimization, Inc.
Read MPS format model from file iNJMPS.mps
Reading time = 0.00 seconds
GENERIC: 838 rows, 1049 columns, 4880 nonzeros
Optimize a model with 838 rows, 1049 columns and 4880 nonzeros
Presolve removed 643 rows and 689 columns
Presolve time: 0.00s
Presolved: 195 rows, 360 columns, 2065 nonzeros
Ordering time: 0.00s
Barrier statistics:
Dense cols : 1
AA' NZ : 2.257e+03
Factor NZ : 5.234e+03
Factor Ops : 1.705e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -1.75363194e+04 -6.88409586e+04 5.76e+04 5.18e-02 4.91e+02 0s
1 -3.65320843e+03 -3.75812065e+04 1.14e+04 1.72e-14 1.07e+02 0s
2 -8.28688357e+02 -8.75581782e+03 2.79e+03 4.34e-14 2.03e+01 0s
3 -8.23243355e+01 -1.45738021e+03 5.07e+02 2.43e-14 3.33e+00 0s
4 -7.25757304e+01 -6.76035625e+02 4.35e+02 5.50e-14 2.24e+00 0s
5 -1.89211383e+01 -3.11758811e+02 1.26e+02 1.89e-14 8.40e-01 0s
6 -1.06534124e+01 -2.09835937e+02 7.32e+01 3.15e-15 5.50e-01 0s
7 -5.93512248e+00 -1.08251749e+02 4.08e+01 8.86e-15 2.89e-01 0s
8 -3.92940035e-01 -3.39563272e+00 2.65e+00 1.11e-14 1.31e-02 0s
9 -1.09583790e-01 -7.73335542e-01 7.08e-01 1.59e-13 2.56e-03 0s
10 -3.90418040e-02 -1.37642841e-01 2.27e-01 9.02e-13 4.85e-04 0s
11 -8.75446987e-02 -1.08889107e-01 1.19e-01 7.57e-13 2.20e-04 0s
12 -5.27417617e-02 -7.03428690e-02 7.99e-03 9.04e-13 3.48e-05 0s
13 -5.24205634e-02 -6.77493506e-02 4.68e-03 8.32e-13 2.72e-05 0s
14 -5.23448080e-02 -5.31651240e-02 1.01e-03 1.24e-11 2.38e-06 0s
15 -5.22497377e-02 -5.23039838e-02 2.90e-04 1.03e-11 4.34e-07 0s
16 -5.22473889e-02 -5.23007203e-02 4.70e-04 2.54e-12 4.20e-07 0s
17 -5.22062332e-02 -5.22071783e-02 2.99e-05 6.31e-11 2.38e-08 0s
18 -5.22062387e-02 -5.22071940e-02 2.69e-05 6.31e-11 2.34e-08 0s
19 -5.22062381e-02 -5.22071925e-02 3.29e-05 6.31e-11 2.32e-08 0s
20 -5.22062364e-02 -5.22071880e-02 7.85e-05 6.31e-11 2.30e-08 0s
21 -5.22062350e-02 -5.22072495e-02 7.86e-05 6.33e-11 2.31e-08 0s
22 -5.22062339e-02 -5.22072466e-02 7.84e-05 6.35e-11 2.31e-08 0s
23 -5.22062364e-02 -5.22076913e-02 7.89e-05 6.41e-11 2.32e-08 0s
24 -5.22062368e-02 -5.22336735e-02 7.89e-05 1.16e-08 2.37e-08 0s
25 -5.22062354e-02 -5.22016346e-02 7.86e-05 3.11e-08 1.34e-08 0s
26 -5.22062354e-02 -5.21619174e-02 7.89e-05 3.44e-09 1.62e-08 0s
27 -5.22062357e-02 -5.21663011e-02 2.43e-04 3.51e-08 1.93e-08 0s
28 -5.22062319e-02 -5.22748649e-02 3.35e-04 4.13e-08 3.79e-08 0s
29 -5.22062314e-02 -5.22125560e-02 1.66e-04 5.34e-09 3.48e-08 0s
30 -5.22062399e-02 -5.22105514e-02 8.27e-05 5.33e-09 3.76e-08 0s
31 -5.22062367e-02 -5.22084207e-02 8.08e-05 5.14e-09 3.72e-08 0s
32 -5.22062363e-02 -5.22085708e-02 8.10e-05 5.14e-09 3.73e-08 0s
33 -5.22062360e-02 -5.22085585e-02 8.80e-05 5.14e-09 3.94e-08 0s
34 -5.22062352e-02 -5.22088675e-02 8.79e-05 5.14e-09 3.96e-08 0s
35 -5.22062397e-02 -5.22094242e-02 8.80e-05 5.14e-09 4.64e-08 0s
36 -5.22062382e-02 -5.22153134e-02 8.80e-05 7.86e-10 4.68e-08 0s
37 -5.22063425e-02 -5.22773891e-02 2.30e-04 7.82e-10 7.44e-08 0s
38 -5.22063419e-02 -5.22783546e-02 1.99e-04 2.00e-10 7.48e-08 0s
39 -5.22060311e-02 -5.22780130e-02 3.26e-04 1.67e-09 7.66e-08 0s
40 -5.22060301e-02 -5.22809184e-02 3.74e-04 5.54e-10 7.69e-08 0s
41 -5.22060263e-02 -5.22802849e-02 2.11e-04 5.55e-10 3.74e-08 0s
42 -5.22058355e-02 -5.22125367e-02 2.02e-04 2.80e-09 3.45e-08 0s
43 -5.22058326e-02 -5.22108218e-02 2.23e-04 2.69e-09 3.42e-08 0s
44 -5.22058337e-02 -5.23574093e-02 1.95e-04 4.16e-08 2.09e-08 0s
45 -5.22058424e-02 -5.22838421e-02 7.14e-04 1.73e-09 2.15e-08 0s
46 -5.22063018e-02 -5.23256677e-02 1.18e-02 2.34e-09 2.24e-08 0s
47 -5.22059267e-02 -5.22553712e-02 1.18e-02 5.43e-09 2.15e-08 0s
48 -5.22081277e-02 -5.93329884e-02 1.19e-02 1.69e-08 2.76e-08 0s
49 -5.22071537e-02 -5.32551143e-02 1.21e-02 6.29e-08 1.48e-08 0s
50 -5.22244753e-02 -5.55504375e-02 4.17e-02 6.28e-08 2.18e-08 0s
51 -5.23886307e-02 -5.47024195e-02 2.56e-02 4.13e-08 1.14e-08 0s
52 -5.23883858e-02 -5.23250146e-02 1.59e-02 1.30e-08 1.05e-08 0s
53 -5.23894864e-02 -5.23368201e-02 1.62e-02 2.33e-08 1.11e-08 0s
54 -5.23897239e-02 -5.23371086e-02 3.06e-02 2.33e-08 1.10e-08 0s
Barrier performed 54 iterations in 0.05 seconds
Sub-optimal termination - objective -5.22062387e-02
Crossover log...
39 DPushes remaining with DInf 0.0000000e+00 0s
0 DPushes remaining with DInf 2.3747670e-13 0s
136 PPushes remaining with PInf 2.5918403e-05 0s
0 PPushes remaining with PInf 0.0000000e+00 0s
Push phase complete: Pinf 0.0000000e+00, Dinf 2.3747670e-13 0s
Iteration Objective Primal Inf. Dual Inf. Time
177 -5.2199203e-02 0.000000e+00 5.838837e-02 0s
179 -5.2199203e-02 0.000000e+00 0.000000e+00 0s
Solved in 179 iterations and 0.05 seconds
Optimal objective -5.219920280e-02
----------------------------------------------------------------------------------------------------------
$ gurobi_cl Method=2 Crossover=0 BarHomogeneous=1 iNJMPS.mps
Set parameter Method to value 2
Set parameter Crossover to value 0
Set parameter BarHomogeneous to value 1
Gurobi Optimizer version 5.0.0 build 9993 (linux64)
Copyright (c) 2012, Gurobi Optimization, Inc.
Read MPS format model from file iNJMPS.mps
Reading time = 0.00 seconds
GENERIC: 838 rows, 1049 columns, 4880 nonzeros
Optimize a model with 838 rows, 1049 columns and 4880 nonzeros
Presolve removed 643 rows and 689 columns
Presolve time: 0.00s
Presolved: 195 rows, 360 columns, 2065 nonzeros
Ordering time: 0.00s
Barrier statistics:
Dense cols : 1
AA' NZ : 2.257e+03
Factor NZ : 5.234e+03
Factor Ops : 1.705e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -1.75038461e+04 -6.89200612e+04 5.75e+04 5.18e-02 4.90e+02 0s
1 -3.64806319e+03 -3.75794560e+04 1.14e+04 1.85e-15 1.07e+02 0s
2 -8.28179766e+02 -8.73586084e+03 2.80e+03 8.80e-15 2.02e+01 0s
3 -8.17785675e+01 -1.45062269e+03 5.05e+02 2.83e-15 3.32e+00 0s
4 -5.81604801e+01 -3.67169408e+02 4.01e+02 1.81e-14 1.75e+00 0s
5 -1.25876625e+01 -1.47762167e+02 9.00e+01 5.65e-15 5.03e-01 0s
6 -9.19489836e+00 -1.40279150e+02 6.58e+01 5.63e-15 4.05e-01 0s
7 -2.97146556e-01 -8.27225609e+00 2.09e+00 1.64e-14 1.72e-02 0s
8 -8.64565156e-02 -1.28298554e+00 6.00e-01 4.89e-14 3.04e-03 0s
9 -2.05695550e-02 -2.54827746e-01 1.33e-01 6.70e-13 5.41e-04 0s
10 -1.62464426e-02 -1.52060115e-01 5.17e-03 4.56e-13 1.92e-04 0s
11 -4.57602369e-02 -7.28747702e-02 8.04e-04 8.15e-14 3.79e-05 0s
12 -5.02903085e-02 -5.63606257e-02 2.49e-04 6.50e-13 8.58e-06 0s
13 -5.02872315e-02 -5.63575370e-02 2.49e-04 7.02e-13 8.56e-06 0s
14 -5.02872315e-02 -5.63574818e-02 2.49e-04 7.03e-13 8.56e-06 0s
15 -5.02873072e-02 -5.67932712e-02 2.49e-04 2.64e-12 8.82e-06 0s
16 -5.03449469e-02 -5.67579197e-02 2.42e-04 6.63e-13 8.68e-06 0s
17 -5.04301334e-02 -5.26740992e-02 8.21e-04 2.67e-11 3.27e-06 0s
18 -5.04267079e-02 -5.26743434e-02 1.18e-01 2.68e-11 3.28e-06 0s
19 -5.04267265e-02 -5.26743404e-02 1.17e-01 2.68e-11 3.28e-06 0s
20 -5.04290348e-02 -5.26742404e-02 1.84e-01 4.23e-12 3.27e-06 0s
21 -5.04897181e-02 -5.26686650e-02 1.78e-01 5.17e-12 3.11e-06 0s
22 -5.04889109e-02 -5.26696404e-02 1.77e-01 5.33e-12 3.12e-06 0s
23 -5.08693263e-02 -5.25471614e-02 1.42e-01 1.13e-10 2.22e-06 0s
24 -5.08696954e-02 -5.25549197e-02 1.39e-01 4.42e-13 2.23e-06 0s
25 -5.20147094e-02 -5.24494109e-02 3.76e-02 3.04e-10 3.85e-07 0s
26 -5.20147152e-02 -5.24709018e-02 3.76e-02 1.85e-10 4.00e-07 0s
27 -5.20147281e-02 -5.24709093e-02 3.92e-02 1.86e-10 4.00e-07 0s
28 -5.20150509e-02 -5.24708967e-02 5.72e-02 1.79e-10 3.99e-07 0s
29 -5.20150308e-02 -5.24708879e-02 5.72e-02 1.79e-10 3.99e-07 0s
30 -5.20431444e-02 -5.22159847e-02 8.66e-01 2.36e-10 2.32e-07 0s
31 -5.20431559e-02 -5.22175139e-02 8.66e-01 2.36e-10 2.31e-07 0s
32 -5.20431566e-02 -5.22177374e-02 8.66e-01 2.37e-10 2.73e-07 0s
33 -5.20193937e-02 -5.22167460e-02 8.39e-01 2.45e-10 2.51e-07 0s
34 -5.20194032e-02 -5.22178741e-02 8.39e-01 2.45e-10 2.52e-07 0s
35 -5.20035428e-02 -5.22166611e-02 1.03e+00 2.47e-10 2.51e-07 0s
36 -5.20036048e-02 -5.22173693e-02 1.03e+00 2.48e-10 2.52e-07 0s
37 -5.19997540e-02 -5.22171144e-02 9.96e-01 2.48e-10 2.64e-07 0s
38 -5.20001973e-02 -5.22170071e-02 9.60e-01 2.38e-10 2.59e-07 0s
39 -5.20003897e-02 -5.22179183e-02 9.60e-01 2.37e-10 2.61e-07 0s
40 -5.20008568e-02 -5.22208202e-02 9.59e-01 2.38e-10 2.74e-07 0s
41 -5.20034363e-02 -5.22365811e-02 9.73e-01 5.19e-10 3.18e-07 0s
42 -5.20030446e-02 -5.22437990e-02 9.79e-01 8.24e-11 3.24e-07 0s
43 -5.19986382e-02 -5.22440395e-02 9.76e-01 8.24e-11 3.60e-07 0s
44 -5.20008104e-02 -5.24386986e-02 9.79e-01 4.09e-10 1.56e-06 0s
45 -5.20316153e-02 -5.27230448e-02 1.12e+00 1.18e-09 3.45e-06 0s
46 -5.20427787e-02 -5.22979303e-02 9.89e-01 4.42e-09 2.08e-06 0s
47 -5.20434463e-02 -5.22813337e-02 9.84e-01 2.35e-09 1.89e-06 0s
48 -5.20432000e-02 -5.22792218e-02 1.02e+00 2.35e-09 1.88e-06 0s
49 -5.23109212e-02 -5.23709378e-02 4.05e-01 1.23e-09 9.65e-07 0s
50 -5.23093787e-02 -5.22413540e-02 5.57e-01 2.34e-09 7.51e-07 0s
51 -5.23147689e-02 -5.28211706e-02 5.41e-01 2.58e-09 6.95e-07 0s
Barrier performed 51 iterations in 0.04 seconds
Sub-optimal termination - objective -5.02903085e-02
----------------------------------------------------------------------------------------------------------
$ gurobi_cl Method=0 Crossover=0 BarHomogeneous=1 iNJMPS.mps
Set parameter Method to value 0
Set parameter Crossover to value 0
Set parameter BarHomogeneous to value 1
Gurobi Optimizer version 5.0.0 build 9993 (linux64)
Copyright (c) 2012, Gurobi Optimization, Inc.
Read MPS format model from file iNJMPS.mps
Reading time = 0.00 seconds
GENERIC: 838 rows, 1049 columns, 4880 nonzeros
Optimize a model with 838 rows, 1049 columns and 4880 nonzeros
Presolve removed 642 rows and 689 columns
Presolve time: 0.00s
Presolved: 196 rows, 360 columns, 2068 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 6.492191e+04 2.257109e+08 0s
401 -5.2199349e-02 0.000000e+00 0.000000e+00 0s
Solved in 401 iterations and 0.01 seconds
Optimal objective -5.219934930e-02
----------------------------------------------------------------------------------------------------------
$ gurobi_cl Method=2 Crossover=-1 BarHomogeneous=1 iNJMPS.mps
Set parameter Method to value 2
Set parameter Crossover to value -1
Set parameter BarHomogeneous to value 1
Gurobi Optimizer version 5.0.0 build 9993 (linux64)
Copyright (c) 2012, Gurobi Optimization, Inc.
Read MPS format model from file iNJMPS.mps
Reading time = 0.00 seconds
GENERIC: 838 rows, 1049 columns, 4880 nonzeros
Optimize a model with 838 rows, 1049 columns and 4880 nonzeros
Presolve removed 643 rows and 689 columns
Presolve time: 0.00s
Presolved: 195 rows, 360 columns, 2065 nonzeros
Ordering time: 0.00s
Barrier statistics:
Dense cols : 1
AA' NZ : 2.257e+03
Factor NZ : 5.234e+03
Factor Ops : 1.705e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -1.75363194e+04 -6.88409586e+04 5.76e+04 5.18e-02 4.91e+02 0s
1 -3.65320843e+03 -3.75812065e+04 1.14e+04 1.72e-14 1.07e+02 0s
2 -8.28688357e+02 -8.75581782e+03 2.79e+03 4.34e-14 2.03e+01 0s
3 -8.23243355e+01 -1.45738021e+03 5.07e+02 2.43e-14 3.33e+00 0s
4 -7.25757304e+01 -6.76035625e+02 4.35e+02 5.50e-14 2.24e+00 0s
5 -1.89211383e+01 -3.11758811e+02 1.26e+02 1.89e-14 8.40e-01 0s
6 -1.06534124e+01 -2.09835937e+02 7.32e+01 3.15e-15 5.50e-01 0s
7 -5.93512248e+00 -1.08251749e+02 4.08e+01 8.86e-15 2.89e-01 0s
8 -3.92940035e-01 -3.39563272e+00 2.65e+00 1.11e-14 1.31e-02 0s
9 -1.09583790e-01 -7.73335542e-01 7.08e-01 1.59e-13 2.56e-03 0s
10 -3.90418040e-02 -1.37642841e-01 2.27e-01 9.02e-13 4.85e-04 0s
11 -8.75446987e-02 -1.08889107e-01 1.19e-01 7.57e-13 2.20e-04 0s
12 -5.27417617e-02 -7.03428690e-02 7.99e-03 9.04e-13 3.48e-05 0s
13 -5.24205634e-02 -6.77493506e-02 4.68e-03 8.32e-13 2.72e-05 0s
14 -5.23448080e-02 -5.31651240e-02 1.01e-03 1.24e-11 2.38e-06 0s
15 -5.22497377e-02 -5.23039838e-02 2.90e-04 1.03e-11 4.34e-07 0s
16 -5.22473889e-02 -5.23007203e-02 4.70e-04 2.54e-12 4.20e-07 0s
17 -5.22062332e-02 -5.22071783e-02 2.99e-05 6.31e-11 2.38e-08 0s
18 -5.22062387e-02 -5.22071940e-02 2.69e-05 6.31e-11 2.34e-08 0s
19 -5.22062381e-02 -5.22071925e-02 3.29e-05 6.31e-11 2.32e-08 0s
20 -5.22062364e-02 -5.22071880e-02 7.85e-05 6.31e-11 2.30e-08 0s
21 -5.22062350e-02 -5.22072495e-02 7.86e-05 6.33e-11 2.31e-08 0s
22 -5.22062339e-02 -5.22072466e-02 7.84e-05 6.35e-11 2.31e-08 0s
23 -5.22062364e-02 -5.22076913e-02 7.89e-05 6.41e-11 2.32e-08 0s
24 -5.22062368e-02 -5.22336735e-02 7.89e-05 1.16e-08 2.37e-08 0s
25 -5.22062354e-02 -5.22016346e-02 7.86e-05 3.11e-08 1.34e-08 0s
26 -5.22062354e-02 -5.21619174e-02 7.89e-05 3.44e-09 1.62e-08 0s
27 -5.22062357e-02 -5.21663011e-02 2.43e-04 3.51e-08 1.93e-08 0s
28 -5.22062319e-02 -5.22748649e-02 3.35e-04 4.13e-08 3.79e-08 0s
29 -5.22062314e-02 -5.22125560e-02 1.66e-04 5.34e-09 3.48e-08 0s
30 -5.22062399e-02 -5.22105514e-02 8.27e-05 5.33e-09 3.76e-08 0s
31 -5.22062367e-02 -5.22084207e-02 8.08e-05 5.14e-09 3.72e-08 0s
32 -5.22062363e-02 -5.22085708e-02 8.10e-05 5.14e-09 3.73e-08 0s
33 -5.22062360e-02 -5.22085585e-02 8.80e-05 5.14e-09 3.94e-08 0s
34 -5.22062352e-02 -5.22088675e-02 8.79e-05 5.14e-09 3.96e-08 0s
35 -5.22062397e-02 -5.22094242e-02 8.80e-05 5.14e-09 4.64e-08 0s
36 -5.22062382e-02 -5.22153134e-02 8.80e-05 7.86e-10 4.68e-08 0s
37 -5.22063425e-02 -5.22773891e-02 2.30e-04 7.82e-10 7.44e-08 0s
38 -5.22063419e-02 -5.22783546e-02 1.99e-04 2.00e-10 7.48e-08 0s
39 -5.22060311e-02 -5.22780130e-02 3.26e-04 1.67e-09 7.66e-08 0s
40 -5.22060301e-02 -5.22809184e-02 3.74e-04 5.54e-10 7.69e-08 0s
41 -5.22060263e-02 -5.22802849e-02 2.11e-04 5.55e-10 3.74e-08 0s
42 -5.22058355e-02 -5.22125367e-02 2.02e-04 2.80e-09 3.45e-08 0s
43 -5.22058326e-02 -5.22108218e-02 2.23e-04 2.69e-09 3.42e-08 0s
44 -5.22058337e-02 -5.23574093e-02 1.95e-04 4.16e-08 2.09e-08 0s
45 -5.22058424e-02 -5.22838421e-02 7.14e-04 1.73e-09 2.15e-08 0s
46 -5.22063018e-02 -5.23256677e-02 1.18e-02 2.34e-09 2.24e-08 0s
47 -5.22059267e-02 -5.22553712e-02 1.18e-02 5.43e-09 2.15e-08 0s
48 -5.22081277e-02 -5.93329884e-02 1.19e-02 1.69e-08 2.76e-08 0s
49 -5.22071537e-02 -5.32551143e-02 1.21e-02 6.29e-08 1.48e-08 0s
50 -5.22244753e-02 -5.55504375e-02 4.17e-02 6.28e-08 2.18e-08 0s
51 -5.23886307e-02 -5.47024195e-02 2.56e-02 4.13e-08 1.14e-08 0s
52 -5.23883858e-02 -5.23250146e-02 1.59e-02 1.30e-08 1.05e-08 0s
53 -5.23894864e-02 -5.23368201e-02 1.62e-02 2.33e-08 1.11e-08 0s
54 -5.23897239e-02 -5.23371086e-02 3.06e-02 2.33e-08 1.10e-08 0s
Barrier performed 54 iterations in 0.05 seconds
Sub-optimal termination - objective -5.22062387e-02
Crossover log...
39 DPushes remaining with DInf 0.0000000e+00 0s
0 DPushes remaining with DInf 2.3747670e-13 0s
136 PPushes remaining with PInf 2.5918403e-05 0s
0 PPushes remaining with PInf 0.0000000e+00 0s
Push phase complete: Pinf 0.0000000e+00, Dinf 2.3747670e-13 0s
Iteration Objective Primal Inf. Dual Inf. Time
177 -5.2199203e-02 0.000000e+00 5.838837e-02 0s
179 -5.2199203e-02 0.000000e+00 0.000000e+00 0s
Solved in 179 iterations and 0.05 seconds
Optimal objective -5.219920280e-02
----------------------------------------------------------------------------------------------------------
$ gurobi_cl Method=2 Crossover=0 BarHomogeneous=1 iNJMPS.mps
Set parameter Method to value 2
Set parameter Crossover to value 0
Set parameter BarHomogeneous to value 1
Gurobi Optimizer version 5.0.0 build 9993 (linux64)
Copyright (c) 2012, Gurobi Optimization, Inc.
Read MPS format model from file iNJMPS.mps
Reading time = 0.00 seconds
GENERIC: 838 rows, 1049 columns, 4880 nonzeros
Optimize a model with 838 rows, 1049 columns and 4880 nonzeros
Presolve removed 643 rows and 689 columns
Presolve time: 0.00s
Presolved: 195 rows, 360 columns, 2065 nonzeros
Ordering time: 0.00s
Barrier statistics:
Dense cols : 1
AA' NZ : 2.257e+03
Factor NZ : 5.234e+03
Factor Ops : 1.705e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -1.75038461e+04 -6.89200612e+04 5.75e+04 5.18e-02 4.90e+02 0s
1 -3.64806319e+03 -3.75794560e+04 1.14e+04 1.85e-15 1.07e+02 0s
2 -8.28179766e+02 -8.73586084e+03 2.80e+03 8.80e-15 2.02e+01 0s
3 -8.17785675e+01 -1.45062269e+03 5.05e+02 2.83e-15 3.32e+00 0s
4 -5.81604801e+01 -3.67169408e+02 4.01e+02 1.81e-14 1.75e+00 0s
5 -1.25876625e+01 -1.47762167e+02 9.00e+01 5.65e-15 5.03e-01 0s
6 -9.19489836e+00 -1.40279150e+02 6.58e+01 5.63e-15 4.05e-01 0s
7 -2.97146556e-01 -8.27225609e+00 2.09e+00 1.64e-14 1.72e-02 0s
8 -8.64565156e-02 -1.28298554e+00 6.00e-01 4.89e-14 3.04e-03 0s
9 -2.05695550e-02 -2.54827746e-01 1.33e-01 6.70e-13 5.41e-04 0s
10 -1.62464426e-02 -1.52060115e-01 5.17e-03 4.56e-13 1.92e-04 0s
11 -4.57602369e-02 -7.28747702e-02 8.04e-04 8.15e-14 3.79e-05 0s
12 -5.02903085e-02 -5.63606257e-02 2.49e-04 6.50e-13 8.58e-06 0s
13 -5.02872315e-02 -5.63575370e-02 2.49e-04 7.02e-13 8.56e-06 0s
14 -5.02872315e-02 -5.63574818e-02 2.49e-04 7.03e-13 8.56e-06 0s
15 -5.02873072e-02 -5.67932712e-02 2.49e-04 2.64e-12 8.82e-06 0s
16 -5.03449469e-02 -5.67579197e-02 2.42e-04 6.63e-13 8.68e-06 0s
17 -5.04301334e-02 -5.26740992e-02 8.21e-04 2.67e-11 3.27e-06 0s
18 -5.04267079e-02 -5.26743434e-02 1.18e-01 2.68e-11 3.28e-06 0s
19 -5.04267265e-02 -5.26743404e-02 1.17e-01 2.68e-11 3.28e-06 0s
20 -5.04290348e-02 -5.26742404e-02 1.84e-01 4.23e-12 3.27e-06 0s
21 -5.04897181e-02 -5.26686650e-02 1.78e-01 5.17e-12 3.11e-06 0s
22 -5.04889109e-02 -5.26696404e-02 1.77e-01 5.33e-12 3.12e-06 0s
23 -5.08693263e-02 -5.25471614e-02 1.42e-01 1.13e-10 2.22e-06 0s
24 -5.08696954e-02 -5.25549197e-02 1.39e-01 4.42e-13 2.23e-06 0s
25 -5.20147094e-02 -5.24494109e-02 3.76e-02 3.04e-10 3.85e-07 0s
26 -5.20147152e-02 -5.24709018e-02 3.76e-02 1.85e-10 4.00e-07 0s
27 -5.20147281e-02 -5.24709093e-02 3.92e-02 1.86e-10 4.00e-07 0s
28 -5.20150509e-02 -5.24708967e-02 5.72e-02 1.79e-10 3.99e-07 0s
29 -5.20150308e-02 -5.24708879e-02 5.72e-02 1.79e-10 3.99e-07 0s
30 -5.20431444e-02 -5.22159847e-02 8.66e-01 2.36e-10 2.32e-07 0s
31 -5.20431559e-02 -5.22175139e-02 8.66e-01 2.36e-10 2.31e-07 0s
32 -5.20431566e-02 -5.22177374e-02 8.66e-01 2.37e-10 2.73e-07 0s
33 -5.20193937e-02 -5.22167460e-02 8.39e-01 2.45e-10 2.51e-07 0s
34 -5.20194032e-02 -5.22178741e-02 8.39e-01 2.45e-10 2.52e-07 0s
35 -5.20035428e-02 -5.22166611e-02 1.03e+00 2.47e-10 2.51e-07 0s
36 -5.20036048e-02 -5.22173693e-02 1.03e+00 2.48e-10 2.52e-07 0s
37 -5.19997540e-02 -5.22171144e-02 9.96e-01 2.48e-10 2.64e-07 0s
38 -5.20001973e-02 -5.22170071e-02 9.60e-01 2.38e-10 2.59e-07 0s
39 -5.20003897e-02 -5.22179183e-02 9.60e-01 2.37e-10 2.61e-07 0s
40 -5.20008568e-02 -5.22208202e-02 9.59e-01 2.38e-10 2.74e-07 0s
41 -5.20034363e-02 -5.22365811e-02 9.73e-01 5.19e-10 3.18e-07 0s
42 -5.20030446e-02 -5.22437990e-02 9.79e-01 8.24e-11 3.24e-07 0s
43 -5.19986382e-02 -5.22440395e-02 9.76e-01 8.24e-11 3.60e-07 0s
44 -5.20008104e-02 -5.24386986e-02 9.79e-01 4.09e-10 1.56e-06 0s
45 -5.20316153e-02 -5.27230448e-02 1.12e+00 1.18e-09 3.45e-06 0s
46 -5.20427787e-02 -5.22979303e-02 9.89e-01 4.42e-09 2.08e-06 0s
47 -5.20434463e-02 -5.22813337e-02 9.84e-01 2.35e-09 1.89e-06 0s
48 -5.20432000e-02 -5.22792218e-02 1.02e+00 2.35e-09 1.88e-06 0s
49 -5.23109212e-02 -5.23709378e-02 4.05e-01 1.23e-09 9.65e-07 0s
50 -5.23093787e-02 -5.22413540e-02 5.57e-01 2.34e-09 7.51e-07 0s
51 -5.23147689e-02 -5.28211706e-02 5.41e-01 2.58e-09 6.95e-07 0s
Barrier performed 51 iterations in 0.04 seconds
Sub-optimal termination - objective -5.02903085e-02
Jakob Sch.
Feb 11, 2014, 5:46:21 AM2/11/14
to gur...@googlegroups.com
Hi Andre,
I do not get what you are trying to achieve here? Clearly the simplex method solves your problem faster. Is there a special reason why you use the barrier method?
To the crossover: The barrier works with a slightly different problem than the original, therefore at the end of the solving process there has to be some extra work done to get the values for the original problem. If you set Crossover to 0, you forbid gurobi to do this and therefore it reports a sub-optimal solution.
See also the manual:
Best regards,
Jakob
I do not get what you are trying to achieve here? Clearly the simplex method solves your problem faster. Is there a special reason why you use the barrier method?
To the crossover: The barrier works with a slightly different problem than the original, therefore at the end of the solving process there has to be some extra work done to get the values for the original problem. If you set Crossover to 0, you forbid gurobi to do this and therefore it reports a sub-optimal solution.
See also the manual:
Use value 0 to disable crossover; this setting returns the interior solution computed by barrier. (http://www.gurobi.com/documentation/5.6/reference-manual/crossover#parameter:Crossover)
Best regards,
Jakob
Jakob Sch.
Feb 11, 2014, 10:02:08 AM2/11/14
to gur...@googlegroups.com
Hi Andre,
As a follow up, I took a look at your problem. It seems that your coefficients are very badly scaled. Especially there seem to be some set to 1E-6 which is dangerously near 0. I would strongly advise you to consider some rescaling of your constraints. Furthermore, it is now more obvious why the barrier solver struggles as this algorithm is more affected by the numerics of your model than the simplex (that is somewhat more stable since it works with the underlying combinatorial structure of the problem).
Best regards,
Jakob
As a follow up, I took a look at your problem. It seems that your coefficients are very badly scaled. Especially there seem to be some set to 1E-6 which is dangerously near 0. I would strongly advise you to consider some rescaling of your constraints. Furthermore, it is now more obvious why the barrier solver struggles as this algorithm is more affected by the numerics of your model than the simplex (that is somewhat more stable since it works with the underlying combinatorial structure of the problem).
Best regards,
Jakob
Andre Voigt
Feb 12, 2014, 5:22:16 AM2/12/14
to gur...@googlegroups.com
Hi,
thanks for the reply. The reason why I want to use the barrier method is not because I require higher speed, but because the solution space for the LP problem corresponds to a possible set of biochemical fluxes - and I want to avoid having the reported optimal solutions at the corners of the solution space. Ideally, we're looking for a point somewhere in the interior of the optimal solution plane (which is a more plausible case, from a biological point of view). I figured that the barrier method would be suitable for this, as we don't need a strictly optimal solution - being reasonably close to a point on the interior of the optimal solution region is good enough (and I was hoping it would be possible to get a bit closer than 96% of the simplex optimum).
If I understand crossover correctly, if crossover is enabled, the final reported solution is a corner of the solution space, right? If so, crossover should be disabled for the same reason I'm avoiding simplex in the first place.
On the subject of rescaling, would Gurobi be more capable of handling the problem if I simply multiply each constraint by the same (large) constant, so the smaller constraints are further from 0? If that solves the issue, it's a fairly straightforward fix.
Thanks for the help,
André
thanks for the reply. The reason why I want to use the barrier method is not because I require higher speed, but because the solution space for the LP problem corresponds to a possible set of biochemical fluxes - and I want to avoid having the reported optimal solutions at the corners of the solution space. Ideally, we're looking for a point somewhere in the interior of the optimal solution plane (which is a more plausible case, from a biological point of view). I figured that the barrier method would be suitable for this, as we don't need a strictly optimal solution - being reasonably close to a point on the interior of the optimal solution region is good enough (and I was hoping it would be possible to get a bit closer than 96% of the simplex optimum).
If I understand crossover correctly, if crossover is enabled, the final reported solution is a corner of the solution space, right? If so, crossover should be disabled for the same reason I'm avoiding simplex in the first place.
On the subject of rescaling, would Gurobi be more capable of handling the problem if I simply multiply each constraint by the same (large) constant, so the smaller constraints are further from 0? If that solves the issue, it's a fairly straightforward fix.
Thanks for the help,
André
Andre Voigt
Feb 12, 2014, 7:14:46 AM2/12/14
to gur...@googlegroups.com
I attempted rescaling the constraints (multiplying them all by a factor of 10^6). In this case, Gurobi works just fine with interior point and no crossover (obviously, the optimal value of the objective function is also multiplied by 10^6). I suppose it isn't the cleanest fix, but it's not too hard to adapt to it. That being said, it would still be more elegant to just send different parameters to Gurobi (so it would work on 'smaller resolutions') - do you have any idea which parameters would be relevant?
Thanks again,
André
Thanks again,
André
Jakob Sch.
Feb 12, 2014, 3:15:27 PM2/12/14
to gur...@googlegroups.com
Hi André,
You could try to use the parameter NumericFocus and set it to a higher number (Default is 0, max is 3) - see http://www.gurobi.com/documentation/5.5/reference-manual/node859#parameter:NumericFocus
I guess adding additional constraints to enforce a solution "more in the interior" of the solution plane is not an option?
Best regards,
Jakob
You could try to use the parameter NumericFocus and set it to a higher number (Default is 0, max is 3) - see http://www.gurobi.com/documentation/5.5/reference-manual/node859#parameter:NumericFocus
I guess adding additional constraints to enforce a solution "more in the interior" of the solution plane is not an option?
Best regards,
Jakob
Reply all
Reply to author
Forward
0 new messages