Here's a "MILP local search" approach to improve the 1102 solution to 1207 quickly by calling the solver in a loop. The idea is to fix the orientations for all but a small subset of the stations and optimize over the resulting neighborhood of the currently best integer feasible solution. Subsets of size 2 performed the best here, but I left the code for subsets of size 1 or 3 commented out for reference. The DO UNTIL loop ends when the current solution is locally optimal in the sense that changing only two stations cannot improve the solution.
num bestObj;
bestObj = _OBJ_;
num improved;
fix Chi;
num numSubsets init 0;
set SUBSETS = 1..numSubsets;
set <str> STATIONS_s {SUBSETS};
/*for {c in STATIONS} do;*/
/* numSubsets = numSubsets + 1;*/
/* STATIONS_s[numSubsets] = {c};*/
/*end;*/
for {c1 in STATIONS, c2 in STATIONS diff {c1}: c1 < c2} do;
numSubsets = numSubsets + 1;
STATIONS_s[numSubsets] = {c1,c2};
end;
/*for {c1 in STATIONS, c2 in STATIONS diff {c1}, c3 in STATIONS diff {c1,c2}: c1 < c2 < c3} do;*/
/* numSubsets = numSubsets + 1;*/
/* STATIONS_s[numSubsets] = {c1,c2,c3};*/
/*end;*/
do until (improved = 0);
improved = 0;
for {s in SUBSETS} do;
put STATIONS_s[s]=;
for {c in STATIONS_s[s], <a,e> in orientations} unfix Chi[c,a,e];
solve with milp / primalin;
if bestObj < _OBJ_ then do;
bestObj = _OBJ_;
improved = 1;
end;
fix Chi;
end;
end;
unfix Chi;
If you want, you can then call the solver again with PRIMALIN to solve the original problem with no fixed variables. After running for a long time, the solver did not improve BestInteger but improved BestBound to 1254, so 1207 is within 4% of optimal and might actually be optimal.
... View more
