Decision Optimization

Issue about fix and dive heuristic

  • 1.  Issue about fix and dive heuristic

    Posted Sun August 22, 2021 09:16 AM
    Dear community team,

    I am trying to solve a scheduling problem (MILP) by using GAMS/Cplex. As the problem is not being solved in a reasonable time for the large-scale instance, I would like to use a simple heuristic namely fix and dive to achieve a feasible solution. What I have tried to do is, solving the original problem as a relaxed problem. (RMIP instead of MIP). Sorting integer variables based on whose relaxed values. (In my case, integer variables are binary and the rest are continuous). Fixing about 15% till 20% of the binary variables on the nearest value to those upper bound (equal to one) and reoptimizing the model. It seems the method works fine as the sorting list will be updated in each iteration and all of the binary variables can be assigned. The issue is that in the model, I have a constraint as follows:
    LHS <= RHS (the RHS is a pre-defined number and is equal to the capacity of the available resources)​

    Actually, I do not expect this method can solve the problem optimality but, it would be possible to achieve, at least, a feasible solution. In my case, the final solutions do not satisfy the capacity constraint. The results are shown here:

    The optimal schedule by solving the problem as MIP
    
                       begin         end
    
    2328021 .50        37.000     109.000
    2325005 .50       109.000     156.000
    2224001 .50         1.000      36.000
    2223017 .70       147.000     156.000
    2325101 .70        61.000     146.000
    2324012 .70         1.000      60.000
    22220412.120        2.000     100.000
    22241012.120      100.000     156.000
    2325002 .150a     106.000     156.000
    2322013 .150a       2.000     106.000
    23280051.150b       2.000      98.000
    2328010 .150b      99.000     156.000
    2322009 .150c      81.000      84.000
    2323206 .150c      84.000     156.000
    2323207 .150c       1.000      79.000
    2322005 .260      132.000     156.000
    2328006 .260        2.000     132.000
    2225002 .450a       1.000     156.000
    2222037 .450c       1.000     153.000
    2225001 .450b     128.000     154.000
    2222038 .450b       1.000     128.000
    
    =============================================================
    The optimal schedule by solving the problem as RMIP  
    
                       begin         end
    
    2328021 .50        48.333     120.333
    2223017 .70         1.000      10.000
    2325101 .50       160.000     245.000
    2324012 .70       160.000     219.000
    22220412.120       57.000     155.000
    22241012.120        1.000      57.000
    2325002 .150c     160.000     210.000
    2322013 .150b       1.000     105.000
    23280051.150b     160.000     256.000
    2328010 .150a     160.000     217.000
    2322009 .150a      73.000      76.000
    2323206 .150a       1.000      73.000
    2323207 .120      160.000     238.000
    2322005 .260      131.000     155.000
    2328006 .260        1.000     131.000
    2225002 .450c       1.000     156.000
    2222037 .450a       1.000     153.000
    2225001 .450b     128.000     154.000
    2222038 .450b       1.000     128.000

    As you can see, the RHS of the constraint is violated by the value of 256 while it has to be at most 160.
    I was wondering if, where I am doing wrong? and is it possible this method can produce an infeasible solution?

    The solver/model statuse are:

    Version identifier: 20.1.0.1 | 2021-04-07 | 3a818710c
    CPXPARAM_Advance                                 0
    CPXPARAM_Threads                                 1
    CPXPARAM_MIP_Display                             4
    CPXPARAM_TimeLimit                               300
    CPXPARAM_MIP_Tolerances_AbsMIPGap                0
    CPXPARAM_MIP_Tolerances_MIPGap                   0
    Tried aggregator 1 time.
    LP Presolve eliminated 1188 rows and 32647 columns.
    Aggregator did 42 substitutions.
    Reduced LP has 485 rows, 955 columns, and 37475 nonzeros.
    Presolve time = 0.11 sec. (136.93 ticks)
    Initializing dual steep norms . . .
    
    Iteration log . . .
    Iteration:     1   Dual objective     =           256.000000
    
    --- LP status (1): optimal.
    --- Cplex Time: 0.15sec (det. 182.38 ticks)
    
    
    Optimal solution found
    Objective:          256.000000


    Best regards
    Abbas



    ------------------------------
    Abbas Omidi
    ------------------------------