Page 1 of 1

Issue about fix and dive heuristic

Posted: Fri Sep 17, 2021 1:05 pm
by abb.omidi

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:

Code: Select all

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. Please, see the attached file.

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?
I can elaborate more on the model if it would be necessary.
The solver/model status are:

Code: Select all

Version identifier: | 2021-04-07 | 3a818710c 
CPXPARAM_Advance 0 
CPXPARAM_Threads 1 
CPXPARAM_TimeLimit 300 
CPXPARAM_MIP_Tolerances_AbsMIPGap 0 
CPXPARAM_MIP_Tolerances_MIPGap 0 Tried aggregator 1 time. 
LP Presolve elim[attachment=0]results.txt[/attachment]inated 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