[AMPL 24643] matheuristic algorithm

Google Group Mirror
1

Hi everyone !
I want to create an algorithm that is able to reduce the computation time compared to cplex, regarding a model which describe the aircraft landing problem. Attached are the.mod and file.run files.
The structure of the algorithm is this:

  1. It must be solved the linear relaxation of the binary variable y of the MILP;
  2. Initially choosing a small threshold epsilon=0.01;
  3. Counting of how many y variables have a value between epsilon and 1-epsilon;
  4. If the number of such variables is too high, (>1000 if want to solve the MILPs faster) then increase the epsilon threshold by 0.01 and go back to step 3, otherwise go to step 5;
  5. Fixing of all the w variables of value >= 1-epsilon to 1 and all the y of value <= epsilon to 0 and solve the MILP where the unfixed y variables are considered binary;

For small instances (e.g. 20-50 planes) everything is ok, but for large ones (100 planes and up) ampl fails to compute the objective function, even though with this algorithm we reduce the number of binary variables y , and therefore the calculation should be faster.
I would greatly appreciate your assistance and offering suggestions on this matter.
Best regards

ALP_model.mod (1.88 KB)

Matheuristic.run (1.48 KB)

2

To get help, add this command before the solve command,

option cplex_options 'mipdisplay=2';

(or, if you are already setting a cplex_options string, add mipdisplay=2 to it). Then copy all of the output that appears, and paste it into your reply. It may also help if you can attach file dat6.dat for the cases of 20 planes and 100 planes.

3

Dear Robert
As you ask me to do, i attached the output file computed 100 planes (dat10). With dat6 i obtained the optimum solution but with dat10 not. I interrupted the computation because too long for dat10 (100 planes and 2 runway).
Please received my best regards.

(Attachment output_dat10.docx is missing)

dat6.dat (4.68 KB)

dat10.dat (79.2 KB)

4

New attachment of output_dat10

output_dat10.run (31.1 KB)

5

For dat6.dat, the final mixed-integer optimization problem is very easy. AMPL’s presolve phase is able to determine the optimal values of all the y variables, before it sends the problem to the solver. After that, CPLEX only needs to solve a linear program in 63 continuous variables, which is done very quickly. (Set “option show_stats 1;” to see the size of the presolved problem.)

For dat10.dat, the final mixed-integer optimization problem is much harder. After presolve phases in AMPL and then in CPLEX, there are still 4388 binary variables (as indicated by “Reduced MIP has 4388 binaries . . .” in the log). However, it is instructive to look at the Best Integer column in the log, which shows the best feasible solution found so far. You can see that a solution with objective value 1199.32 was found in less than a minute, and no better solution was found before you stopped the run. If you let CPLEX run until it finishes, it might find a better solution. But often, finding an optimal solution takes much less time than proving optimality; it is not unusual for a solution found early in the run to be actually optimal.

Since you are implementing a heuristic anyway, it would make sense to accept the best solution that CPLEX finds after a specifiedamount of running time. When CPLEX reaches a time limit, it automatically returns to AMPL the best solution that has been found so far.

Note that if you want to specify more than one option, you should list them all in one cplex_options string. For example,

option cplex_options 'timelimit=900 mipdisplay=2';

6

Thank you so much!
I don’t understand why if I increase the value of epsilon, then increase the number of y variables to fix (also decreasing the number of binary variables of the MILP), the final value of the objective function increases excessively.
The last question is whether it is correct to use the y.relax:=1 function to restore binary variables after fixing? In this case, only variables that have not been fixed become binary, correct?

7

I’m not sure what you mean when you say that “the final value of the objective function increases excessively.” Can you explain, and give an example?

For a binary variable, the settings of .relax and fix work like this:

  • When y[i,j].relax := 1, the value of y[i,j] is allowed to be fractional (>0 and <1) in the solution that the solver returns. When y[i,j].relax := 0, the value of y[i,j] must be either 0 or 1 in the solution.
  • When the command “fix y[i,j] := 0;” is given, y[i,j] is required to equal 0 in the solution. The variable remains fixed at 0 unless you give the command “unfix y[i,j];” which allows y[i,j] to take any value allowed by the variable and constraint definitions.
    Changing .relax does not affect whether the variable is fixed. For example, if you say “fix y[i,j] := 0;” and then “y[i,j].relax := 0”, the variable is still fixed at 0.