Hi,
I am modeling a problem in such a way that I have two gaps: a required gap (gap1) and a desired gap (gap2), gap2<gap1. So, what I want to do is the following:
i) Set a number N of nodes to be explored and a desired gap gap2.
ii) After (i), check the gap and if it is lower than gap 1 then finish the process; otherwise, explore another N nodes (with the gap set to gap2), and so on.
I presume that I can handle the issue though independent MIP processes, but thus the branch and bound (B&B) three would not be saved and another root process (usually expensive) would be performed each process. Do you have any idea how I can do that?
After (i), you can run the solver again. It will be provided the last feasible solution (if any known by then). Most MIP solvers support warm start, so it won’t spend time looking again. However, if the most effort was spent in improving the dual bound, that will be repeated.
Thanks Gleb,
It is good to know that an ideal solution can be performed in C++ or Python. Additionally, please can you explain to me this part: “However, if the most effort was spent in improving the dual bound, that will be repeated”.
In addition to the complete documentation of AMPLS at the link that Gleb has given, you can see an example – an application to create a specially designed stopping rule – in our talk on New Connections to the AMPL Modeling Language: Spreadsheets and Callbacks. The relevant section begins at slide 19. There’s also a video of the presentation, with the section on callbacks beginning at about 5:20.
The target gap that you set is the gap between the primal and dual bounds. Primal bound is your best solution objective. Dual bound is the most optimistic estimate of the best possible value and it’s the minimal (for minimization problems) LP relaxation value of a branching node.
To improve dual bound, the only way is to branch. After warmstart, the solver may produce better branching due to a primal solution available, but also may not. Thus, for problems where the main difficulty is to improve dual bound to prove optimality, you’d have to wait the same time. But in this case you might already have a good solution.
For the case of difficult primal solutions, warmstart sometimes allows the solver to quickly find even better solutions. Thus, if not using callbacks, the following heuristic seems reasonable: warmstart the solver several times, possibly with different solver parameters. If the solution does not improve, you might have a good one.