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
------------------------------
#DecisionOptimization