Possibly unbounded problem, buy why?

[Ellen Fowler]

Can anyone interpret the message below from CPLEX for me?

The primal is a minimization problem. Up until iteration #25 the primary and dual objective values seem to be converging nicely, the primal from above, the dual from below. Then the dual objective value increases beyond the primal's and zooms off to infinity.

According to what I intended to formulate: The variables in the objective function have lower and upper bounds. If they were all at their lower bounds (0) the objective value would also be 0 but the solution would be infeasible. If they were all at their upper bounds, the objective value would be about 9.8 million and the solution would be sub-sub-optimal.

Any thoughts?

Thank you,

Ellen Fowler

LP Presolve eliminated 7557005 rows and 11720856 columns.

Reduced LP has 1867746 rows, 3101083 columns, and 15474850 nonzeros.

Parallel mode: using up to 12 threads for barrier.

Number of nonzeros in lower triangle of A*A' = 35241057

Elapsed ordering time = 8.38 sec. (10000.01 ticks)

Total time for nested dissection ordering = 11.59 sec. (15158.17 ticks)

Summary statistics for Cholesky factor:

  Threads                   = 12

  Rows in Factor            = 1867746

  Integer space required    = 12655908

  Total non-zeros in factor = 144134914

  Total FP ops to factor    = 30456259014

 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf Inf Ratio

   0  3.7846900e+011 -6.8778703e+012 7.63e+013 5.49e+012 5.02e+006 1.00e+000

   1  2.7731957e+011 -5.6297093e+012 5.46e+013 3.93e+012 4.11e+006 1.33e-005

   2  7.1218857e+010 -2.3091796e+012 1.17e+013 8.43e+011 1.69e+006 1.94e-006

   3  6.7527632e+010 -2.3087916e+012 1.11e+013 8.01e+011 1.69e+006 1.94e-006

   4  2.7107535e+010 -2.2718559e+012 4.86e+012 3.50e+011 1.67e+006 1.66e-006

   5  1.6623770e+010 -1.5095775e+012 2.95e+012 2.13e+011 1.11e+006 1.58e-006

   6  8.5238763e+009 -1.0038631e+012 1.49e+012 1.07e+011 7.37e+005 1.69e-006

   7  6.0592637e+009 -5.9205826e+011 1.05e+012 7.55e+010 4.34e+005 2.53e-006

   8  5.4138224e+009 -5.0099399e+011 9.35e+011 6.73e+010 3.68e+005 2.81e-006

   9  4.6107243e+009 -4.0001818e+011 7.93e+011 5.70e+010 2.94e+005 3.22e-006

  10  3.8533702e+009 -3.1400708e+011 6.59e+011 4.74e+010 2.30e+005 3.74e-006

  11  3.1208197e+009 -2.3932377e+011 5.31e+011 3.82e+010 1.76e+005 4.44e-006

  12  2.4226660e+009 -1.7412032e+011 4.10e+011 2.95e+010 1.28e+005 5.48e-006

  13  1.7419873e+009 -1.1603146e+011 2.94e+011 2.11e+010 8.52e+004 7.43e-006

  14  1.1289487e+009 -7.9705709e+010 1.90e+011 1.37e+010 5.85e+004 1.02e-005

  15  7.5265452e+008 -5.4108956e+010 1.26e+011 9.08e+009 3.97e+004 1.40e-005

  16  3.6662798e+008 -3.8847555e+010 6.13e+010 4.41e+009 2.85e+004 1.90e-005

  17  2.2271154e+008 -2.8073872e+010 3.71e+010 2.67e+009 2.06e+004 2.60e-005

  18  1.5041366e+008 -1.7178726e+010 2.50e+010 1.80e+009 1.26e+004 4.19e-005

  19  9.2576709e+007 -1.1427968e+010 1.53e+010 1.10e+009 8.39e+003 6.38e-005

  20  7.5697646e+007 -8.8660008e+009 1.24e+010 8.93e+008 6.51e+003 8.28e-005

  21  6.0176558e+007 -5.2802616e+009 9.75e+009 7.01e+008 3.88e+003 1.40e-004

  22  4.9610662e+007 -2.7913254e+009 7.93e+009 5.71e+008 2.05e+003 2.58e-004

  23  3.7059379e+007 -1.9325198e+009 5.65e+009 4.07e+008 1.42e+003 3.01e-004

  24  9.4977747e+007 -5.2053618e+009 1.52e+010 1.09e+009 3.83e+003 4.49e-005

  25  5.4332642e+007 -8.8128877e+008 7.78e+009 5.60e+008 6.55e+002 4.63e-006

  26  4.4595384e+007  8.8203439e+008 6.53e+009 4.70e+008 4.54e+002 1.27e-009

  27  4.0731810e+007  6.3931752e+012 6.03e+009 4.34e+008 4.34e+002 3.81e-013

  28  3.8603774e+007  2.3066762e+016 5.75e+009 4.13e+008 1.01e+006 1.14e-016

  29  3.7191607e+007  8.0863109e+019 5.56e+009 4.00e+008 1.88e+010 3.05e-020

  30  3.5773075e+007  3.1268739e+023 5.37e+009 3.87e+008 2.70e+014 4.69e-024

 Barrier limit on dual objective exceeded.

 Infeasible barrier solution (dependent on objective limit).

Barrier time = 96.91 sec. (94942.86 ticks)

Total time on 12 threads = 96.91 sec. (94942.86 ticks)

CPLEX 12.6.3.0: dual objective limit reached; objective 35773074.64

30 barrier iterations

No basis.

First solve:       3.85 minutes       406 limit

[AMPL Google Group]

There's a suggestion of how to interpret this log in the CPLEX page on Infeasibility Ratio in the Log File:

"If you are using one of the barrier infeasibility algorithms available in the CPLEX barrier optimizer (that is, if you have set [baralg=1 or baralg=2 in cplex_options]), then CPLEX records a column of output titled Inf Ratio, the infeasibility ratio. This ratio, always positive, is a measure of progress for that particular algorithm. In a problem with an optimal solution, you will see this ratio increase to a large number. In contrast, in a problem that is infeasible or unbounded, this ratio will decrease to a very small number. (The infeasibility ratio is not available in the standard barrier algorithm, that is, when [baralg=3 in cplex_options].)"

Since the Inf Ratio in your log decreases to 4.69e-024, your problem appears to be "infeasible or unbounded". Since the dual is a maximization in your case, and the dual objective value is going off to Infinity, it appears that the dual problem is unbounded, and hence the original primal problem is infeasible. This is consistent with the "Infeasible barrier solution" message that appears. (CPLEX's default definition of "off to infinity" is "> 1e20", which can be changed by setting option barobjrange in cplex_options.)

--
Robert Fourer
am...@googlegroups.com

{#HS:1463031841-102999#}

[Ellen Fowler]

Thanks for these thoughts, Bob.

Can you tell me how to tell it to solve the primal only? I have tried some related Cplex options before but really don't think I got it right.

If I could get the primal to be infeasible rather than the dual being unbounded, I could get some help from the IIS.

Ellen

[Ellen Fowler]

I tried adding dual to my cplex options and got the mirror image result. Either way, it indicates that my original dual is unbounded and therefore my original primal is infeasible. How then do I get an IIS (the cplex option is on) if CPLEX thinks it's dealing with unboundedness?

Ellen

[AMPL Google Group]

Hi Ellen,

As long as CPLEX knows that the primal is infeasible, it will try to find an IIS. Finding that the dual is unbounded implies that the primal is infeasible, so that is not a problem. However, when the barrier method is terminated by "Barrier limit on dual objective exceeded," CPLEX will be unable to find an IIS. You could try setting, say, baralg=1 barobjrange=1e30 (or baralg=1 barobjrange=1e30) see whether that will allow the barrier method to terminate with a normal infeasibility condition and to continue on to finding an IIS.

If the barrier method can't terminate normally with any setting of barobjrange, then you could try switching to the primal or dual simplex method, specified by primalopt or dualopt in cplex_options. (Specifying dual is different; it causes CPLEX to form and solve the dual of the given problem, by whatever method you specify.)

Barrier is a primal-dual method, so there's no way to tell it to focus on just solving the primal or the dual problem.

--
Robert Fourer
am...@googlegroups.com

{#HS:1463031841-102999#}

On Wed, Mar 24, 2021 at 9:19 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

I tried adding dual to my cplex options and got the mirror image result. Either way, it indicates that my original dual is unbounded and therefore my original primal is infeasible. How then do I get an IIS (the cplex option is on) if CPLEX thinks it's dealing with unboundedness?

Ellen

On Wed, Mar 24, 2021 at 8:40 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Thanks for these thoughts, Bob.

Can you tell me how to tell it to solve the primal only? I have tried some related Cplex options before but really don't think I got it right.

If I could get the primal to be infeasible rather than the dual being unbounded, I could get some help from the IIS.

Ellen

On Wed, Mar 24, 2021 at 8:27 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

There's a suggestion of how to interpret this log in the CPLEX page on Infeasibility Ratio in the Log File:

"If you are using one of the barrier infeasibility algorithms available in the CPLEX barrier optimizer (that is, if you have set [baralg=1 or baralg=2 in cplex_options]), then CPLEX records a column of output titled Inf Ratio, the infeasibility ratio. This ratio, always positive, is a measure of progress for that particular algorithm. In a problem with an optimal solution, you will see this ratio increase to a large number. In contrast, in a problem that is infeasible or unbounded, this ratio will decrease to a very small number. (The infeasibility ratio is not available in the standard barrier algorithm, that is, when [baralg=3 in cplex_options].)"

Since the Inf Ratio in your log decreases to 4.69e-024, your problem appears to be "infeasible or unbounded". Since the dual is a maximization in your case, and the dual objective value is going off to Infinity, it appears that the dual problem is unbounded, and hence the original primal problem is infeasible. This is consistent with the "Infeasible barrier solution" message that appears. (CPLEX's default definition of "off to infinity" is "> 1e20", which can be changed by setting option barobjrange in cplex_options.)

--
Robert Fourer
am...@googlegroups.com

[Ellen Fowler]

I added the barobjrange option although I had to go up to its maximum, 1e75, before I no longer got the "Barrier limit on dual objective exceeded" error. Here is my new output. Unfortunately I still do not have an IIS. I will try the primalopt algorithm choice as instead of the barrier.

Presolve eliminates 3592792 constraints and 2773592 variables.

Adjusted problem:

11021033 variables, all linear

7247741 constraints, all linear; 32603838 nonzeros

5945674 equality constraints

1302067 inequality constraints

1 linear objective; 373248 nonzeros.

CPLEX 12.6.3.0: lpdisplay=1

bardisplay=1

iisfind=1

barobjrange=1e75

advance=1

aggcutlim=0

agglim=5

aggregate=1

backtrack=0.999999

baralg=1

barcorr=-1

bargrowth=1e+6

barstart=1

bbinterval=15

boundstr=0

branch=0

cliques=-1

coeffreduce=1

covers=2

crash=1

crossover=0

cutpass=0

cutsfactor=4

dgradient=5

disjcuts=1

flowcuts=-1

flowpathcuts=0

fraccand=50

fraccuts=0

fracpass=128

gubcuts=2

heuristicfreq=20

impliedcuts=-1

lbheur=0

localimpliedcuts=3

mcfcuts=0

memoryemphasis=0

mipalg=4

mipcrossover=1

mipsearch=2

mipstartalg=4

mipstartstatus=1

mipstartvalue=0

mircuts=1

netfind=1

netopt=1

netpricing=0

nodefile=1

nodeselect=3

ordering=3

ordertype=2

parallelmode=-1

pgradient=0

predual=-1

prelinear=1

prepass=64

prereduce=3

prerelax=0

presolve=1

presolvenode=0

pricing=4

priorities=0

probe=-1

refactor=0

repeatpresolve=3

rinsheur=20

scale=1

singular=40

splitcuts=1

strongcand=10

strongit=0

symmetry=5

varsel=-1

zerohalfcuts=2

LP Presolve eliminated 4865887 rows and 7823707 columns.

Reduced LP has 1161853 rows, 1977325 columns, and 9549087 nonzeros.

Parallel mode: using up to 32 threads for barrier.

Number of nonzeros in lower triangle of A*A' = 20683274

Total time for nested dissection ordering = 7.36 sec. (4083.36 ticks)

Summary statistics for Cholesky factor:

  Threads                   = 32

  Rows in Factor            = 1161853

  Integer space required    = 7961537

  Total non-zeros in factor = 90469933

  Total FP ops to factor    = 19529779887

 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf Inf Ratio

   0  2.4285418e+011 -3.7716812e+012 4.63e+013 3.72e+013 6.88e+005 1.00e+000

   1  2.0088897e+011 -9.2920141e+011 9.64e+012 7.73e+012 1.94e+005 2.08e-006

   2  7.8133487e+010 -5.8440099e+011 3.14e+012 2.52e+012 1.24e+005 2.07e-006

   3  3.9881633e+010 -4.0388172e+011 1.44e+012 1.15e+012 8.59e+004 2.25e-006

   4  2.7458569e+010 -3.2347281e+011 9.45e+011 7.58e+011 6.90e+004 2.54e-006

   5  2.0416071e+010 -1.9755243e+011 6.68e+011 5.36e+011 4.24e+004 3.66e-006

   6  1.8139073e+010 -1.6458090e+011 5.84e+011 4.69e+011 3.54e+004 4.22e-006

   7  1.5360054e+010 -1.2916298e+011 4.86e+011 3.90e+011 2.79e+004 5.12e-006

   8  1.2766977e+010 -9.9945277e+010 3.98e+011 3.19e+011 2.16e+004 6.34e-006

   9  1.0248587e+010 -7.5085785e+010 3.16e+011 2.54e+011 1.63e+004 8.14e-006

  10  7.8496736e+009 -5.3843244e+010 2.43e+011 1.95e+011 1.17e+004 1.11e-005

  11  5.6044827e+009 -3.5384722e+010 1.76e+011 1.42e+011 7.63e+003 1.66e-005

  12  3.2697032e+009 -2.2540531e+010 1.09e+011 8.77e+010 4.82e+003 2.72e-005

  13  2.1341097e+009 -1.5054822e+010 7.45e+010 5.98e+010 3.20e+003 4.19e-005

  14  1.0030341e+009 -9.1903692e+009 3.82e+010 3.07e+010 1.94e+003 7.53e-005

  15  6.5799496e+008 -6.1727360e+009 2.56e+010 2.05e+010 1.30e+003 1.14e-004

  16  4.6730883e+008 -4.4807380e+009 1.84e+010 1.48e+010 9.40e+002 1.59e-004

  17  2.6134959e+008 -2.6087258e+009 1.07e+010 8.59e+009 5.45e+002 2.83e-004

  18  1.7113118e+008 -1.8241984e+009 7.34e+009 5.89e+009 3.80e+002 4.22e-004

  19  1.4000408e+008 -9.1759892e+008 6.15e+009 4.93e+009 1.89e+002 8.80e-004

  20  6.1056634e+007 -4.3542747e+008 3.27e+009 2.62e+009 8.64e+001 2.20e-003

  21  5.7673403e+007 -3.0899364e+008 2.92e+009 2.34e+009 6.29e+001 2.73e-003

  22  1.7963490e+008 -4.4733019e+008 4.99e+009 4.00e+009 1.08e+002 8.78e-004

  23  9.1381655e+008  1.6627920e+009 4.81e+009 3.86e+009 9.67e+001 1.83e-004

  24  1.6488806e+009  1.8045060e+009 2.83e+009 2.27e+009 8.34e+001 8.65e-005

  25  6.9329184e+011  9.6257942e+011 2.66e+009 2.13e+009 7.67e+001 2.09e-007

  26  5.2834648e+015  7.3392811e+015 2.77e+009 2.22e+009 9.03e+001 2.75e-011

  27  2.4951623e+019  5.5348186e+019 2.83e+009 2.27e+009 3.30e+004 5.81e-015

  28  2.7231301e+023  3.1452220e+023 3.57e+009 2.78e+009 3.82e+008 5.33e-019

  29  1.0347567e+027  2.0045556e+027 4.96e+011 2.40e+009 6.79e+011 1.40e-022

  30  7.5214141e+030  9.3375402e+030 2.47e+015 2.21e+009 1.23e+016 1.93e-026

  31  3.2726527e+034  4.1452087e+034 9.13e+018 2.15e+009 1.96e+020 4.43e-030

  32  1.8623369e+038  7.4797056e+037 6.88e+022 1.89e+009 3.12e+023 7.78e-034

  33  4.5282186e+041  4.0095425e+041 9.30e+025 1.39e+009 1.78e+027 3.20e-037

  34  3.1660757e+045  2.7031409e+045 1.24e+030 1.44e+009 7.59e+031 4.57e-041

  35  2.1454696e+049  2.5472254e+049 4.47e+033 1.39e+009 1.03e+036 6.75e-045

  36  1.5984158e+053  1.6526400e+053 5.36e+037 1.32e+009 1.23e+040 9.05e-049

  37  1.6829269e+057  1.1597099e+057 4.13e+041 1.39e+009 1.26e+044 8.60e-053

  38  1.0715328e+061  1.0715066e+061 3.52e+045 8.89e+008 7.94e+047 1.35e-056

  39  1.2986878e+065  1.2986968e+065 3.44e+049 1.08e+009 1.52e+052 1.11e-060

  40  1.3061095e+069  1.3061185e+069 3.82e+053 1.08e+009 8.33e+055 1.11e-064

  41  1.3159632e+073  1.3159723e+073 3.63e+057 1.09e+009 9.52e+059 1.10e-068

  42  1.3257734e+077  1.3257825e+077 4.18e+061 1.10e+009 1.20e+064 1.09e-072

Numerical difficulties encountered.

Barrier time = 69.88 sec. (43210.54 ticks)

Total time on 32 threads = 69.88 sec. (43210.54 ticks)

CPLEX 12.6.3.0: best solution found, primal-dual infeasible; objective 1.32577336e+77

42 barrier iterations

Return 1719 from CPXgetconflict.

No basis.

"option rel_boundtol 2.2474516028046365e-06;"

will change deduced dual values.

First solve:       2.55 minutes       207 infeasible

-------------------------------------------------------------------------

[AMPL Google Group]

This time the run again failed, though with a different error: "Numerical difficulties encountered." My tests suggest that CPLEX will not try to find an IIS unless the solver run has a successful termination.

--
Robert Fourer
am...@googlegroups.com

{#HS:1463031841-102999#}

On Wed, Mar 24, 2021 at 11:52 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Hi Ellen,

As long as CPLEX knows that the primal is infeasible, it will try to find an IIS. Finding that the dual is unbounded implies that the primal is infeasible, so that is not a problem. However, when the barrier method is terminated by "Barrier limit on dual objective exceeded," CPLEX will be unable to find an IIS. You could try setting, say, baralg=1 barobjrange=1e30 (or baralg=1 barobjrange=1e30) see whether that will allow the barrier method to terminate with a normal infeasibility condition and to continue on to finding an IIS.

If the barrier method can't terminate normally with any setting of barobjrange, then you could try switching to the primal or dual simplex method, specified by primalopt or dualopt in cplex_options. (Specifying dual is different; it causes CPLEX to form and solve the dual of the given problem, by whatever method you specify.)

Barrier is a primal-dual method, so there's no way to tell it to focus on just solving the primal or the dual problem.

--
Robert Fourer
am...@googlegroups.com