Primal-Dual Infeasible After Successful Solves

[Rob Zittlau]

Can anyone help interpret the message below from CPLEX?

The problem (linear, continuous) is run through three consecutive optimizations. After the first and second optimizations, certain variables are fixed. The first two optimizations are feasible, so I am expecting the third to be feasible, as well. However, I get this message on the third solve.

Any insight appreciated.

Regards,

Rob

Presolve eliminates 8018757 constraints and 6519752 variables.
Adjusted problem:
20427112 variables, all linear
13365972 constraints, all linear; 62323580 nonzeros
    10988949 equality constraints
    2377023 inequality constraints
1 linear objective; 22344 nonzeros.

CPLEX 12.6.3.0: iisfind=1
bardisplay=1
barobjrange=1e20
baralg=1
barcorr=-1
bargrowth=1e+12
barstart=1
crossover=0
ordering=3
LP Presolve eliminated 9460824 rows and 14886932 columns.
Reduced LP has 1947091 rows, 3582123 columns, and 17677645 nonzeros.
Parallel mode: using up to 32 threads for barrier.
Number of nonzeros in lower triangle of A*A' = 40174658
Total time for nested dissection ordering = 14.25 sec. (9884.22 ticks)
Summary statistics for Cholesky factor:
  Threads                   = 32
  Rows in Factor            = 1947091
  Integer space required    = 14724230
  Total non-zeros in factor = 113549957
  Total FP ops to factor    = 18861992015
 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf Inf Ratio
   0  8.1725045e+010  1.8772672e+014 1.63e+010 1.13e+008 3.80e+009 1.00e+000
   1  8.0958368e+010  1.8626841e+014 1.62e+010 1.12e+008 3.77e+009 1.10e-004
   2  7.9691020e+010  1.8132153e+014 1.59e+010 1.11e+008 3.67e+009 2.53e-005
   3  7.2101569e+010  1.6972749e+014 1.44e+010 1.00e+008 3.44e+009 9.16e-006
   4  6.4340360e+010  1.4652127e+014 1.29e+010 8.95e+007 2.97e+009 4.19e-006
   5  5.8330690e+010  1.3863912e+014 1.17e+010 8.14e+007 2.81e+009 2.97e-006
   6  5.6227211e+010  1.3502811e+014 1.13e+010 7.87e+007 2.74e+009 2.52e-006
   7  5.4349684e+010  1.3182822e+014 1.10e+010 7.62e+007 2.67e+009 2.25e-006
   8  5.2866926e+010  1.2887017e+014 1.07e+010 7.42e+007 2.61e+009 2.05e-006
   9  5.2004905e+010  1.2711599e+014 1.05e+010 7.31e+007 2.58e+009 1.97e-006
  10  5.1538346e+010  1.2624401e+014 1.04e+010 7.25e+007 2.56e+009 1.66e-006
  11  5.1088860e+010  1.2536985e+014 1.04e+010 7.20e+007 2.54e+009 1.43e-006
  12  5.0679135e+010  1.2455853e+014 1.03e+010 7.15e+007 2.53e+009 1.27e-006
  13  5.0296858e+010  1.2378408e+014 1.02e+010 7.10e+007 2.51e+009 1.13e-006
  14  4.9933785e+010  1.2306288e+014 1.02e+010 7.06e+007 2.50e+009 1.03e-006
  15  4.9602503e+010  1.2239741e+014 1.01e+010 7.02e+007 2.48e+009 9.46e-007
  16  4.9296875e+010  1.2177149e+014 1.01e+010 6.98e+007 2.47e+009 8.72e-007
  17  4.9017852e+010  1.2119164e+014 1.00e+010 6.95e+007 2.46e+009 8.07e-007
  18  4.8755415e+010  1.2065983e+014 9.96e+009 6.92e+007 2.45e+009 7.47e-007
  19  4.8561203e+010  1.2024727e+014 9.93e+009 6.89e+007 2.44e+009 6.96e-007
  20  4.8441672e+010  1.1999972e+014 9.91e+009 6.88e+007 2.43e+009 6.60e-007
  21  4.8367544e+010  1.1985398e+014 9.90e+009 6.87e+007 2.43e+009 6.33e-007
  22  4.8306443e+010  1.1974452e+014 9.89e+009 6.87e+007 2.43e+009 6.07e-007
  23  4.8264245e+010  1.1967671e+014 9.89e+009 6.86e+007 2.43e+009 5.84e-007
  24  4.8235625e+010  1.1963165e+014 9.88e+009 6.86e+007 2.43e+009 5.63e-007
  25  4.8212947e+010  1.1960428e+014 9.88e+009 6.86e+007 2.43e+009 5.46e-007
  26  4.8197246e+010  1.1958416e+014 9.88e+009 6.86e+007 2.43e+009 5.34e-007
  27  4.8185253e+010  1.1956939e+014 9.88e+009 6.86e+007 2.42e+009 5.27e-007
  28  4.8173821e+010  1.1955440e+014 9.88e+009 6.86e+007 2.42e+009 5.20e-007
  29  4.8162639e+010  1.1953862e+014 9.88e+009 6.86e+007 2.42e+009 5.14e-007
  30  4.8151271e+010  1.1952151e+014 9.87e+009 6.86e+007 2.42e+009 5.09e-007
  31  4.8139635e+010  1.1950349e+014 9.87e+009 6.85e+007 2.42e+009 5.03e-007
  32  4.8127146e+010  1.1948458e+014 9.87e+009 6.85e+007 2.42e+009 4.98e-007
  33  4.8114472e+010  1.1946460e+014 9.87e+009 6.85e+007 2.42e+009 4.93e-007
  34  4.8101638e+010  1.1944320e+014 9.87e+009 6.85e+007 2.42e+009 4.87e-007
  35  4.8088252e+010  1.1942014e+014 9.87e+009 6.85e+007 2.42e+009 4.82e-007
  36  4.8074670e+010  1.1939567e+014 9.86e+009 6.85e+007 2.42e+009 4.76e-007
  37  4.8061754e+010  1.1937026e+014 9.86e+009 6.85e+007 2.42e+009 4.71e-007
  38  4.8048238e+010  1.1934331e+014 9.86e+009 6.85e+007 2.42e+009 4.65e-007
  39  4.8034104e+010  1.1931614e+014 9.86e+009 6.84e+007 2.42e+009 4.60e-007
  40  4.8018479e+010  1.1928823e+014 9.86e+009 6.84e+007 2.42e+009 4.54e-007
  41  4.8001920e+010  1.1925853e+014 9.85e+009 6.84e+007 2.42e+009 4.49e-007
  42  4.7984743e+010  1.1922578e+014 9.85e+009 6.84e+007 2.42e+009 4.43e-007
  43  4.7966480e+010  1.1919063e+014 9.85e+009 6.84e+007 2.42e+009 4.37e-007
  44  4.7948909e+010  1.1915264e+014 9.85e+009 6.84e+007 2.42e+009 4.31e-007
  45  4.7930238e+010  1.1911206e+014 9.84e+009 6.83e+007 2.42e+009 4.25e-007
  46  4.7910314e+010  1.1906308e+014 9.84e+009 6.83e+007 2.41e+009 4.19e-007
  47  4.7888656e+010  1.1900944e+014 9.84e+009 6.83e+007 2.41e+009 4.12e-007
  48  4.7863138e+010  1.1895040e+014 9.83e+009 6.83e+007 2.41e+009 4.06e-007
  49  4.7831256e+010  1.1888030e+014 9.83e+009 6.82e+007 2.41e+009 4.00e-007
  50  4.7793550e+010  1.1879102e+014 9.82e+009 6.82e+007 2.41e+009 3.94e-007
CPLEX 12.6.3.0: best solution found, primal-dual infeasible; objective 47793549600
50 barrier iterations
Return 1719 from CPXgetconflict.
No basis.

Third solve:          4.616666666666666    minutes          207    infeasible 

[AMPL Google Group]

This result is consistent with there being no feasible solution.

In general, fixing a variable is like adding a special constraint, so it can make a problem infeasible. Can you provide some additional information about your situation?

• What AMPL statements are you using to fix the variables?
• How are you deciding what values to fix the variables at?
• How do you know that the resulting problem will remain feasible?

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

{#HS:1922021117-110575#}

Third solve: 4.616666666666666 minutes 207 infeasible --
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/f19e4cb2-4bfe-486e-8aed-5b01e55c871dn%40googlegroups.com.

[Rob Zittlau]

Hi Robert,

Thanks for your response.

After the first and second optimization, I am using "fix" statements to fix certain variables at the values found in the previous optimization (is there a better way to do this?). I then change the objective function and re-run the optimization, so I thought the previous solution would still be feasible, if nothing else.

Rob

[AMPL Google Group]

There are two forms of the fix command:

• fix variable-name; or fix {indexing} variable-name; fixes variables at their current values.
• fix variable-name := value; or fix {indexing} variable-name := value; fixes variables at the given values.

Which are you using? If you are using the first form, then (if you have not changed the values of any variables since the last solve) your problem should remain feasible. But in any case, as a test, you can use the following commands just before solving, to display the greatest infeasibility of any variable with respect to its bounds, and the greatest infeasibility in any constraint:

display min {i in 1.._ncons} _con[i].slack;
display min {j in 1.._nvars} _var[j].slack;

If these are 0 or just very slightly negative (not worse than -1e-6) then you can consider the problem to still have a feasible solution after fixing the variables. But otherwise, some change may have made the constraints infeasible.

You may also want to try a newer version of CPLEX, since 12.6.3 was released over 6 years ago. The latest version that we distribute is available from our download portal.

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

{#HS:1922021117-110575#}

On Thu, Jun 16, 2022 at 9:09 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hi Robert,

Thanks for your response.

After the first and second optimization, I am using "fix" statements to fix certain variables at the values found in the previous optimization (is there a better way to do this?). I then change the objective function and re-run the optimization, so I thought the previous solution would still be feasible, if nothing else.

Rob

On Wed, Jun 15, 2022 at 9:41 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

This result is consistent with there being no feasible solution.

In general, fixing a variable is like adding a special constraint, so it can make a problem infeasible. Can you provide some additional information about your situation?

• What AMPL statements are you using to fix the variables?
• How are you deciding what values to fix the variables at?
• How do you know that the resulting problem will remain feasible?

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