Decision Optimization

 View Only
  • 1.  Is my LP problem really infeasible?

    Posted Tue December 07, 2021 09:59 AM
    Hi everyone,

    I have a question concerning the feasability of a binary LP problem with constant (zero) objective function that arises from a complex combinatorial tiling problem. The LP problem has 1,372,296 binary variables and 7733 constraints. 

    I first tried running this LP problem on my Mac Pro using CPLEX ver 12.8. After a minute CPLEX came back with the message

    MIP - Integer Infeasible
    Current MIP best bound is infinite

    Now I had reason to question whether this LP problem was in fact infeasible. I had created similar LP problems for smaller tiling problems and solved them and I knew that the bigger problem has multiple solutions. So I next tried to run my LP problem in CPLEX ver 20.1. (on a MacBook Pro) and it has been 'hanging' at node zero for over 2 days.

    So based on this behaviour do people think my problem really is infeasible, in which case I need to look for a bug in the setup of the LP file, or should I just be patient and wait for CPLEX to hopefully run to conclusion?

    Thank you for any advice you can give.

    Marcus Garvie.

    ------------------------------
    Marcus Garvie
    ------------------------------


  • 2.  RE: Is my LP problem really infeasible?

    Posted Tue December 07, 2021 11:00 AM
    What you may try is to run the feasopt to produce a solution, then provide this solution to the main problem to see if it is accepted.
    If it is accepted, it may be either that CPLEX has a bug or that it encountered a challenging numeric.

    As for the 20.1 node zero, you may try to switch rinsheur off (set mip strategy rinsheur -1), disable all cuts (set mip cut all -1) to see if you overcome it?

    Is the data check reader complaining about numerics? 


    ------------------------------
    Vincent Beraudier
    ------------------------------



  • 3.  RE: Is my LP problem really infeasible?

    Posted Tue December 07, 2021 11:15 AM
    Hi Vincent,

    thank you for your reply! Unfortunately my knowledge of CPLEX is very elementary (I am a mathematician). I know some basic shell commands for reading, running, and saving files, but not much beyond that. To try what you suggest for CPLEX ver 12.8 I would need the specific shell commands. I can try your commands in the CPLEX ver 20.1 case. I don't see any complaints about numerics. I do know that this LP problem is very challenging. It's an LP formulation of the Eternity puzzle !! I have copied the currently available output for the CPLEX ver 20.1 case below (it's still running).

    Thank you,

    Marcus Garvie.

    CPLEX> read /Users/mgarvie/LPfiles/subregion6.lp
    Problem '/Users/mgarvie/LPfiles/subregion6.lp' read.
    Read time = 9.37 sec. (706.70 ticks)
    CPLEX> optimize
    Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    Tried aggregator 1 time.
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    MIP Presolve eliminated 388 rows and 97704 columns.
    MIP Presolve modified 692209 coefficients.
    Reduced MIP has 7229 rows, 1274592 columns, and 46970412 nonzeros.
    Reduced MIP has 1274592 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 29.94 sec. (30231.16 ticks)
    Tried aggregator 1 time.
    Presolve has eliminated 0 rows and 0 columns...
    Detecting symmetries...
    Reduced MIP has 7229 rows, 1274592 columns, and 46970412 nonzeros.
    Reduced MIP has 1274592 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 32.85 sec. (33910.51 ticks)
    Elapsed time = 39.49 sec. (10000.47 ticks) for 3% of probing (2100 vars fixed)
    Elapsed time = 66.95 sec. (20000.59 ticks) for 5% of probing (2509 vars fixed)
    Elapsed time = 92.66 sec. (30001.02 ticks) for 8% of probing (11613 vars fixed)
    Elapsed time = 117.65 sec. (40002.23 ticks) for 10% of probing (11625 vars fixed)
    Probing fixed 12260 vars, tightened 0 bounds.
    Probing time = 139.31 sec. (48282.56 ticks)
    Clique table members: 1281871.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 8 threads.
    Root relaxation solution time = 7080.18 sec. (3296628.30 ticks)
            Nodes                                         Cuts/
       Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
          0     0        0.0000  4911                      0.0000      601         
          0     0        0.0000  1962                    Cuts: 84   972014 


    ------------------------------
    Marcus Garvie
    ------------------------------



  • 4.  RE: Is my LP problem really infeasible?

    Posted Wed December 08, 2021 03:47 AM
    Here are the commands I would test on a model with unexpected behavior as you describe:

    # check if cplex detects bad numerics
    ./cplex -c "set read datacheck 2" "read subregion6.lp" opt

    # ease the solve by increasing simplex tolerances feasibility
    ./cplex -c "set simplex tolerances feasibility 1e-05" "read subregion6.lp" opt

    # switch presolve off.
    ./cplex -c "set preprocessing presolve n" "read subregion6.lp" opt

    # emphasize precision, will slow down cplex a lot but will add extrem numeric care.

    ./cplex -c "set emphasis numerical y" "read subregion6.lp" opt


    # check if a relaxed solution is accepted?
    # feasopt + write solution + reread all and opt
    # look for 1 of 1 MIP starts provided solutions.
    # or MIP start 'incumbent' defined initial solution with objective in the log
    ./cplex -c "read subregion6.lp" "feasopt all" "write subregion6-relax.sol" "y" "read subregion6.lp" "read subregion6-relax.sol" opt


    # try to get a faster root node processing with 20.1
    ./cplex -c "read subregion6.lp" "set mip cut all -1" "set mip strategy rinsheur -1" opt ​

    ------------------------------
    Vincent Beraudier
    ------------------------------



  • 5.  RE: Is my LP problem really infeasible?

    Posted Thu December 09, 2021 10:27 AM
    Hi Vincent,
    I implemented some of the commands you suggested yesterday (both versions of CPLEX are still running on separate machines). With regard to the ones for CPLEX ver 12.8 I'm not seeing any improvement or error messages regarding "bad numerics" (see below). With regard to CPLEX ver 20.1I am seeing a little bit more 'movement' (see below), but not much. My guess is because this is such a hard combinatorial problem (in the NP-complete class) that CPLEX is struggling for that reason alone. I would welcome any other insights or strategies.
    Thank you,
    Marcus Garvie.
    Log for CPLEX ver 12.8:
    CPLEX> set read datacheck 2
    New value for indicator to check data consistency: 2
    CPLEX> read /Users/mgarvie/LPfiles/subregion6.lp
    Problem '/Users/mgarvie/LPfiles/subregion6.lp' read.
    Read time = 9.99 sec. (712.26 ticks)
    CPLEX> opt
    CPXPARAM_Read_DataCheck                          2
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    Tried aggregator 1 time.
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    MIP Presolve eliminated 388 rows and 97704 columns.
    MIP Presolve modified 692209 coefficients.
    Reduced MIP has 7229 rows, 1274592 columns, and 46970412 nonzeros.
    Reduced MIP has 1274592 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 25.05 sec. (30080.49 ticks)

    Root node processing (before b&c):
      Real time             =   62.93 sec. (66018.96 ticks)
    Parallel b&c, 12 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) =   62.93 sec. (66018.96 ticks)
     
    MIP - Integer infeasible.
    Current MIP best bound is infinite.
    Solution time =   65.90 sec.  Iterations = 0  Nodes = 0 (1)
    Deterministic time = 66022.89 ticks  (1001.80 ticks/sec)

    CPLEX> set simplex tolerances feasibility 1e-05
    New value for feasibility tolerance: 1e-05
    CPLEX> read /Users/mgarvie/LPfiles/subregion6.lp
    Problem '/Users/mgarvie/LPfiles/subregion6.lp' read.
    Read time = 9.59 sec. (712.26 ticks)
    CPLEX> opt
    CPXPARAM_Simplex_Tolerances_Feasibility          1.0000000000000001e-05
    CPXPARAM_Read_DataCheck                          2
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    Tried aggregator 1 time.
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    MIP Presolve eliminated 388 rows and 97704 columns.
    MIP Presolve modified 692209 coefficients.
    Reduced MIP has 7229 rows, 1274592 columns, and 46970412 nonzeros.
    Reduced MIP has 1274592 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 25.02 sec. (30080.49 ticks)

    Root node processing (before b&c):
      Real time             =   62.82 sec. (66018.97 ticks)
    Parallel b&c, 12 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) =   62.82 sec. (66018.97 ticks)

    MIP - Integer infeasible.
    Current MIP best bound is infinite.
    Solution time =   65.68 sec.  Iterations = 0  Nodes = 0 (1)
    Deterministic time = 66022.89 ticks  (1005.25 ticks/sec)

    CPLEX> set preprocessing presolve n
    New value for presolve indicator: no
    CPLEX> read /Users/mgarvie/LPfiles/subregion6.lp
    Problem '/Users/mgarvie/LPfiles/subregion6.lp' read.
    Read time = 9.57 sec. (712.26 ticks)
    CPLEX> opt
    CPXPARAM_Simplex_Tolerances_Feasibility          1.0000000000000001e-05
    CPXPARAM_Preprocessing_Presolve                  0
    CPXPARAM_Read_DataCheck                          2
    Clique table members: 7733.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 12 threads.
    Root relaxation solution time = 1515.73 sec. (1660570.59 ticks)

            Nodes                                         Cuts/
       Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

          0     0        0.0000  4268                      0.0000        0         
    Log for CPLEX ver 20.1:
    CPLEX> read /Users/mgarvie/LPfiles/subregion6.lp
    Problem '/Users/mgarvie/LPfiles/subregion6.lp' read.
    Read time = 8.89 sec. (706.70 ticks)
    CPLEX> set mip cut all -1
    New value for type of BQP cut generation (only applies to non-convex models solved to global optimality): -1
    New value for type of clique cut generation: -1
    New value for type of cover cut generation: -1
    New value for type of disjunctive cut generation: -1
    New value for type of flow cover cut generation: -1
    New value for type of Gomory fractional cut generation: -1
    New value for type of GUB cover cut generation: -1
    New value for type of implied bound cut generation: -1
    New value for type of Lift and Project cut generation: -1
    New value for type of local implied bound cut generation: -1
    New value for type of MCF cut generation: -1
    New value for type of mixed integer rounding cut generation: -1
    New value for type of flow path cut generation: -1
    New value for type of RLT cut generation (only applies to non-convex models solved to global optimality): -1
    New value for type of zero-half cut generation: -1
    CPLEX> set mip strategy rinsheur -1
    New value for frequency to apply RINS heuristic: -1
    CPLEX> opt
    Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
    CPXPARAM_MIP_Cuts_Cliques                        -1
    CPXPARAM_MIP_Cuts_Covers                         -1
    CPXPARAM_MIP_Cuts_FlowCovers                     -1
    CPXPARAM_MIP_Cuts_Implied                        -1
    CPXPARAM_MIP_Cuts_GUBCovers                      -1
    CPXPARAM_MIP_Cuts_Gomory                         -1
    CPXPARAM_MIP_Cuts_PathCut                        -1
    CPXPARAM_MIP_Cuts_MIRCut                         -1
    CPXPARAM_MIP_Cuts_Disjunctive                    -1
    CPXPARAM_MIP_Cuts_ZeroHalfCut                    -1
    CPXPARAM_MIP_Cuts_MCFCut                         -1
    CPXPARAM_MIP_Cuts_LiftProj                       -1
    CPXPARAM_MIP_Cuts_LocalImplied                   -1
    CPXPARAM_MIP_Cuts_BQP                            -1
    CPXPARAM_MIP_Cuts_RLT                            -1
    CPXPARAM_MIP_Strategy_RINSHeur                   -1
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    Tried aggregator 1 time.
    Presolve has eliminated 388 rows and 97704 columns...
    Presolve has improved bounds 97704 times...
    MIP Presolve eliminated 388 rows and 97704 columns.
    MIP Presolve modified 692209 coefficients.
    Reduced MIP has 7229 rows, 1274592 columns, and 46970412 nonzeros.
    Reduced MIP has 1274592 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 27.66 sec. (30231.16 ticks)
    Tried aggregator 1 time.
    Presolve has eliminated 0 rows and 0 columns...
    Detecting symmetries...
    Reduced MIP has 7229 rows, 1274592 columns, and 46970412 nonzeros.
    Reduced MIP has 1274592 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 33.92 sec. (33910.51 ticks)
    Elapsed time = 38.74 sec. (10000.47 ticks) for 3% of probing (2100 vars fixed)
    Elapsed time = 66.26 sec. (20000.59 ticks) for 5% of probing (2509 vars fixed)
    Elapsed time = 91.86 sec. (30001.02 ticks) for 8% of probing (11613 vars fixed)
    Elapsed time = 116.78 sec. (40002.23 ticks) for 10% of probing (11625 vars fixed)
    Probing fixed 12260 vars, tightened 0 bounds.
    Probing time = 138.49 sec. (48282.56 ticks)
    Clique table members: 1281871.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 8 threads.
    Root relaxation solution time = 7086.34 sec. (3296628.30 ticks)

            Nodes                                         Cuts/
       Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

          0     0        0.0000  4911                      0.0000      601         
    Heuristic still looking.
    Heuristic still looking.
    Heuristic still looking.
    Heuristic still looking.
          0     2        0.0000  1693                      0.0000   830262         
    Elapsed time = 58959.99 sec. (30377279.41 ticks, tree = 0.02 MB, solutions = 0)


    ------------------------------
    Marcus Garvie
    ------------------------------



  • 6.  RE: Is my LP problem really infeasible?

    Posted Fri December 10, 2021 10:47 AM
    Finally past node zero (see below):

            Nodes                                         Cuts/
       Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
          0     0        0.0000  4911                      0.0000      601         
    Heuristic still looking.
    Heuristic still looking.
    Heuristic still looking.
    Heuristic still looking.
          0     2        0.0000  1693                      0.0000   830262         
    Elapsed time = 58959.99 sec. (30377279.41 ticks, tree = 0.02 MB, solutions = 0)
          2     3        0.0000  4501                      0.0000  1588948


    ------------------------------
    Marcus Garvie
    ------------------------------