Path Based Mixed Integer Programming¶
The callback functionality in the path based mixed integer programming (path MIP) algorithm offers various callback support.
Kick-start the solution process by adding initial paths. Best case is to provide a feasible solution but even partial solutions will most likely help to regain feasibility faster. Adding a large set of columns is preferable, again to aid general convergence of the algorithm.
Plug-in your user defined heuristic to find good solutions. Possible exploit the current fractional solution.
Solution Feasibility Check¶
For all solution that the algorithm deem feasible the user is allowed a check to verify the potential solution against any additional business rules not part of the model.
Add cutting planes with respect to edge and variables.
Hook in and provide a set of user defined path, e.g., with using a user defined meta-heuristic approach. Fallback to the internal dynamic programming algorithm or bypass it entirely when adding your own specialized path algorithm.
Mixed Integer Programming¶
To be implemented.
Callback functionality inside the dynamic programming (DP) algorithm is especially useful to handle custom resources constraints in a graph.
Usually a lot of calls to the extend and dominate labels are expected. Technically this involves invoking a python method from C++ and return the result. It is expensive and can degrade performance
For performance reasons callbacks in the DP algorithm is disabled by default. Enable by setting the parameter
On using the
Resource values can be looked up and modified in the callback. They are accessed by name. The cost is accessed with the name
cost and unnamed resources are named
index is the sequence number they were added by (zero-indexed), i.e., first resources is named
r_0 by default.
Adding a custom resource reserves a
double as a state element in a label. Use the name of the resource to look it up in the callback methods.
Set the initial state of a label.
Calculate the extension of a label and modify resource values.
Feasibility Quick Rejection
All non-custom resources are extended and evaluated for infeasibility in index order with cost first. If any resource fails the feasibility test the label is discarded and the callback is not invoked.
Calculate dominance criteria between two labels
Dominance Quick Rejection
All non-custom resources are checked for dominance in index order with cost first. If any check fails the dominance check fails, the other labels is kept and the callback is not invoked.
Infeasiblility and Artificial Costs¶
When using the callback in the dynamic programming algorithm from the path MIP algorithm the cost may have artificial values. This is due to the path MIP algorithm being infeasible and trying to regain feasibility by adding artificial variables and subsequently pricing them out of the basis. While doing this the costs are artificial when accessed in the callback function.
Usually this is not an issue. However, for advanced use cases where the label cost is modified through the callback one should check if the costs are artificial using