Infeasible without conflict

[Ádám Sleisz]

Hello,

I have a numerical issue that I find very elusive and frustrating.

I have a large MIP with many binaries and bigM constraints. (As far as I know, bigM values are as small as possible.) AMPL/CPLEX declares the problem to be infeasible. Yet when I fix a few critical binaries, the solver finds the corresponding solution easily. When I search for conflicts without fixing anything (and no presolve), it says there are no conflicts. But it still remains infeasible. The log:

CPLEX 20.1.0.0: presolve=0

iisfind=1

Problem is feasible; no conflict available.

CPLEX 20.1.0.0: integer infeasible.
315936 MIP simplex iterations
0 branch-and-bound nodes
Surprise values mc = 0, nc = 0 from CPXrefineconflict.
Return 1719 from CPXgetconflict.
No basis.

Unfortunately, I cannot share the problem itself because it is confidential. (At least not right away.) But maybe I can ask this question in general: are there any other options to find the cause of infeasibility in cases like this? I displayed the slacks of the fixed solution but the largest negative is -9.095e-13... Any suggestion would be appreciated.

Regards,

Ádám

[AMPL Google Group]

Can you run again with mipdisplay=2 added to your cplex_options string? This will cause a long CPLEX log listing to appear; copy and paste the entire listing into your reply. The CPLEX log listing often contains useful information that suggests what is happening or what should be tried next.

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

{#HS:1639997862-106412#}

--
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/fa593383-ad75-4f81-ac82-1a7839cbee96n%40googlegroups.com.

[Ádám Sleisz]

This is the extended log:

CPLEX 20.1.0.0: presolve=0

iisfind=1

mipdisplay=2

Clique table members: 72078.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 165.89 sec. (135866.75 ticks)



        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap



      0     0    infeasible                                     315936         



Root node processing (before b&c):

  Real time             =  166.09 sec. (135951.98 ticks)

Parallel b&c, 8 threads:

  Real time             =    0.00 sec. (0.00 ticks)

  Sync time (average)   =    0.00 sec.

  Wait time (average)   =    0.00 sec.

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

Total (root+branch&cut) =  166.09 sec. (135951.98 ticks)

Problem is feasible; no conflict available.

CPLEX 20.1.0.0: integer infeasible.
315936 MIP simplex iterations
0 branch-and-bound nodes
Surprise values mc = 0, nc = 0 from CPXrefineconflict.
Return 1719 from CPXgetconflict.
No basis.

[AMPL Google Group]

It appears that CPLEX's simplex algorithm determines that the problem's root (continuous) relaxation has no feasible solution. But then the conflict refiner does not detect any infeasible constraints. However CPLEX considers a solution to be "feasible" if the maximum amount of infeasibility is less than some small tolerance, and this can occasionally lead to inconsistent results. Here are a few more tests to try, to shed light on the current situation:

1. Increase the feasibility tolerance for this problem, by adding feasibility=1e-5 to your cplex_options string. Report whether the feasibility issues are still seen.
2. Set "option relax_integrality 1;" so that CPLEX solves only the continuous relaxation. Report whether it finds the problem to be feasible or whether it computes an IIS.
3. Set "option show_stats 2;" to get more information about AMPL's presolve phase. Report any message like "Setting . . . could change presolve results."
4. Set "option presolve 0;" to avoid any side-effects of AMPL's presolve phase. Report whether the feasibility issues are still seen.

In my experience, it's important to take care that the tests are run independently. The safest way to do this is to start an entirely new AMPL session for each test.

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

{#HS:1639997862-106412#}

On Thu, Sep 23, 2021 at 9:44 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Can you run again with mipdisplay=2 added to your cplex_options string? This will cause a long CPLEX log listing to appear; copy and paste the entire listing into your reply. The CPLEX log listing often contains useful information that suggests what is happening or what should be tried next.

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

[Ádám Sleisz]

Thank you for the suggestions. I will progress backwards.

4. As a result of my earlier debug attemps, the AMPL presolve was already switched off along with the CPLEX presolve.

3. If I switch it on and specify 'show_stats 2', then the log in log3.txt is created. The presolve stats are not particularly interesting to me but the CPLEX log is slightly different from the original. I don't know what "cutoff" means in this context (without an incumbent solution and user cutoffs).

2. The continuous relaxation is feasible. (AMPL presolve is off again.) Log:

CPLEX 20.1.0.0: presolve=0

mipdisplay=2

iisfind=1

timelimit=3600

CPLEX 20.1.0.0: optimal solution; objective 53824381.08
70 separable QP barrier iterations
No basis.

1. The problem remains infeasible with the enlarged tolerance (see log1.txt). I tried with 'feasibility=1e-3' and the result is essentially the same. ( AMPL presolve is off in this test, too.)

[AMPL Google Group]

It appears that CPLEX finds a feasible solution with some fractional variables after only a few simplex iterations. But then after many more iterations (but no branching) it determines that no integer feasible solutions exist. The only way I can see that integer infeasibility could be determined in this situation is that in the course of adding cuts at the root node, the problem becomes infeasible.

What happens if you set cutpass = -1 in cplex_options? If the error is the same, then at least we will know that it is not related to cut processing. In any case, please post the log.

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

{#HS:1639997862-106412#}

On Mon, Sep 27, 2021 at 1:45 AM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Thank you for the suggestions. I will progress backwards.

4. As a result of my earlier debug attemps, the AMPL presolve was already switched off along with the CPLEX presolve.

3. If I switch it on and specify 'show_stats 2', then the log in log3.txt is created. The presolve stats are not particularly interesting to me but the CPLEX log is slightly different from the original. I don't know what "cutoff" means in this context (without an incumbent solution and user cutoffs).

2. The continuous relaxation is feasible. (AMPL presolve is off again.) Log:

CPLEX 20.1.0.0: presolve=0

mipdisplay=2

iisfind=1

timelimit=3600

CPLEX 20.1.0.0: optimal solution; objective 53824381.08
70 separable QP barrier iterations
No basis.

1. The problem remains infeasible with the enlarged tolerance (see log1.txt). I tried with 'feasibility=1e-3' and the result is essentially the same. ( AMPL presolve is off in this test, too.)

On Fri, Sep 24, 2021 at 4:59 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

It appears that CPLEX's simplex algorithm determines that the problem's root (continuous) relaxation has no feasible solution. But then the conflict refiner does not detect any infeasible constraints. However CPLEX considers a solution to be "feasible" if the maximum amount of infeasibility is less than some small tolerance, and this can occasionally lead to inconsistent results. Here are a few more tests to try, to shed light on the current situation:

1. Increase the feasibility tolerance for this problem, by adding feasibility=1e-5 to your cplex_options string. Report whether the feasibility issues are still seen.
2. Set "option relax_integrality 1;" so that CPLEX solves only the continuous relaxation. Report whether it finds the problem to be feasible or whether it computes an IIS.
3. Set "option show_stats 2;" to get more information about AMPL's presolve phase. Report any message like "Setting . . . could change presolve results."
4. Set "option presolve 0;" to avoid any side-effects of AMPL's presolve phase. Report whether the feasibility issues are still seen.

In my experience, it's important to take care that the tests are run independently. The safest way to do this is to start an entirely new AMPL session for each test.

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

[Ádám Sleisz]

I have completed this test with and without AMPL presolve. The number "clique table members" is much smaller, otherwise I do not see meaningful differences.

[AMPL Google Group]

Looking back at your earlier tests, the only case where I see cuts reported is in "log1.txt", which has these options:

presolve=0
mipdisplay=2
iisfind=1
feasibility=1e-5

In the log for this case there are many reported cuts,

Clique cuts applied: 24
Cover cuts applied: 323
Implied bound cuts applied: 379
Flow cuts applied: 320
Mixed integer rounding cuts applied: 2326
Gomory fractional cuts applied: 63

and applying them is reported to require over 9000 simplex iterations. Can you reproduce this case, and then run it again with cutpass=-1 added to the options? Also, try running it again with cutsfactor=0 (a different way to suppress cuts) added instead.

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

{#HS:1639997862-106412#}

On Wed, Sep 29, 2021 at 2:55 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

I have completed this test with and without AMPL presolve. The number "clique table members" is much smaller, otherwise I do not see meaningful differences.

On Mon, Sep 27, 2021 at 8:00 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

It appears that CPLEX finds a feasible solution with some fractional variables after only a few simplex iterations. But then after many more iterations (but no branching) it determines that no integer feasible solutions exist. The only way I can see that integer infeasibility could be determined in this situation is that in the course of adding cuts at the root node, the problem becomes infeasible.

What happens if you set cutpass = -1 in cplex_options? If the error is the same, then at least we will know that it is not related to cut processing. In any case, please post the log.

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

[Ádám Sleisz]

In these cases, "infeasible" appears in the logs instead of "cutoff".

I had to introduce a time limit because the conflict search is very long in the cutpass=-1 version. Of course, it is not really meaningful this way... It is running now without the time limit for more than 12 hours.

[Ádám Sleisz]

I had to abort the cutpass=-1 test after 2 days.

[AMPL Google Group]

With feasibility=1e-5 and cutpass=-1, finally CPLEX's conflict refiner correctly treats the problem as infeasible and starts to search for an irreducible infeasible subset of the constraints. However, finding such a subset requires solving a whole series of optimization problems, and for a difficult MIP, that can take much longer than you want to wait -- as you have seen in this case.

Actually, CPLEX has several algorithms that can be used in finding an infeasible subset. You can choose one by setting conflictalg in cplex_options (while keeping iisfind=1). So here are some more tests to try.

• Set conflictalg=6 without feasibility=1e-5 and cutpass=-1.
• Set conflictalg=6 and feasibility=1e-5 (but without cutpass=-1).
• Set conflictalg=1 or conflictalg=2 or conflictalg=5, together with feasibility=1e-5 and cutpass=-1. These settings do not guarantee an irreducible infeasible subset, but they may be much faster to find some infeasible subset.

Also, when your run terminates due to a time limit (such as in feas_cutpass_iis.txt), see whether CPLEX returns the best infeasible subset it has found so far. You can do this with

display {i in 1.._ncons: _con[i].iis <> "non"} (_conname[i],_con[i].iis) >iis.txt;
display {j in 1.._nvars: _var[j].iis <> "non"} (_varname[j],_var[j].iis) >iis.txt;

If CPLEX does return an infeasible subset, it will be listed in the file iis.txt.

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

{#HS:1639997862-106412#}

On Mon, Oct 4, 2021 at 1:22 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

I had to abort the cutpass=-1 test after 2 days.

On Sat, Oct 2, 2021 at 7:54 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

In these cases, "infeasible" appears in the logs instead of "cutoff".

I had to introduce a time limit because the conflict search is very long in the cutpass=-1 version. Of course, it is not really meaningful this way... It is running now without the time limit for more than 12 hours.

On Wed, Sep 29, 2021 at 5:43 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Looking back at your earlier tests, the only case where I see cuts reported is in "log1.txt", which has these options:

presolve=0
mipdisplay=2
iisfind=1
feasibility=1e-5

In the log for this case there are many reported cuts,

Clique cuts applied: 24
Cover cuts applied: 323
Implied bound cuts applied: 379
Flow cuts applied: 320
Mixed integer rounding cuts applied: 2326
Gomory fractional cuts applied: 63

and applying them is reported to require over 9000 simplex iterations. Can you reproduce this case, and then run it again with cutpass=-1 added to the options? Also, try running it again with cutsfactor=0 (a different way to suppress cuts) added instead.

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