Scippy

SCIP

Solving Constraint Integer Programs

pricer_coloring.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file pricer_coloring.h
17  * @brief variable pricer for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements the pricer for the coloring algorithm.
21  *
22  * It computes maximal stable sets in the current graph whose corresponding variables can improve
23  * the current LP solution. This is done by computing a maximum weighted stable set in the current
24  * graph with dual-variables of the node constraints as weights. A variable can improve the
25  * solution, if the weight of the corresponding stable set is larger than 1, since it then has
26  * negative reduced costs, which are given by (1 - weight of the set).
27  *
28  * The pricer first tries to compute such a stable set using a a greedy-method. If it fails, the tclique-algorithm is
29  * used on the complementary graph. This is a branch-and-bound based algorithm for maximal cliques,
30  * included in SCIP. In this case, not only the best solution is added to the LP, but also all other
31  * stable sets found during the branch-and-bound process that could improve the current LP solution
32  * are added, limited to a maximal number that can be changed by a parameter.
33  */
34 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 
37 #ifndef __SCIP_PRICER_COLORING__
38 #define __SCIP_PRICER_COLORING__
39 
40 #include "probdata_coloring.h"
41 
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45 
46 /** creates the healthcare variable pricer and includes it in SCIP */
48  SCIP* scip /**< SCIP data structure */
49  );
50 
51 /** sets the way, the pricer handles variables with negative reduced costs found during the tclique-algorithm
52  if onlybest is true, only the best n variables are added to the lp, while onlybest = false means, that
53  the first n variables with negative reduced costs are added
54  Here, n is the value set by setNVarsCreatedPerRound */
56  SCIP* scip, /**< SCIP data structure */
57  SCIP_Bool onlybest /**< true, if only the best vars should be used */
58  );
59 
60 
61 /* sets, whether the pricing should use the greedy-method */
63  SCIP* scip, /**< SCIP data structure */
64  SCIP_Bool usegreedy /**< true, if the greedy should be used */
65  );
66 
67 
68 /* sets whether the pricing should use the tclique-method for finding new variables */
70  SCIP* scip, /**< SCIP data structure */
71  SCIP_Bool usetclique /**< true, if the tclique-algorithm should be used */
72  );
73 
74 
75 /* sets the number of variables that the pricer is allowed to create in one round of pricing */
77  SCIP* scip, /**< SCIP data structure */
78  int nvars /**< maximal number of variables that should be created in one round */
79  );
80 
81 #ifdef __cplusplus
82 }
83 #endif
84 
85 #endif
problem data for vertex coloring algorithm
void COLORpricerUseTclique(SCIP *scip, SCIP_Bool usetclique)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void COLORpricerUseGreedy(SCIP *scip, SCIP_Bool usegreedy)
void COLORpricerSetNVarsCreatedPerRound(SCIP *scip, int nvars)
#define SCIP_Bool
Definition: def.h:84
void COLORpricerUseOnlyBestStableSets(SCIP *scip, SCIP_Bool onlybest)
SCIP_RETCODE SCIPincludePricerColoring(SCIP *scip)