heur_dps.h File Reference

Detailed Description

dynamic partition search

Author

Katrin Halbig

The dynamic partition search (DPS) is a construction heuristic which additionally needs a user decomposition with linking constraints only.

This heuristic splits the problem into several sub-SCIPs according to the given decomposition. Thereby the linking constraints with their right-hand and left-hand sides are also split. DPS searches for a partition of the sides on the blocks so that a feasible solution is obtained. For each block the parts of the original linking constraints are extended by slack variables. Moreover, the objective function is replaced by the sum of these additional variables weighted by penalty parameters lambda. If all blocks have an optimal solution of zero, the algorithm terminates with a feasible solution for the main problem. Otherwise, the partition and the penalty parameters are updated, and the sub-SCIPs are solved again.

A detailed description can be found in K. Halbig, A. Göß and D. Weninger (2023). Exploiting user-supplied Decompositions inside Heuristics. https://optimization-online.org/?p=23386

Definition in file heur_dps.h.

#include "scip/def.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeHeurDps (SCIP *scip)