masterplugins.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
34 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 #define USEHEURS 1
36 #define USESEPA 0
37 #define USEPROP 1
38 
39 #include "masterplugins.h"
40 
41 #include "scip/cons_and.h"
42 #include "scip/cons_bounddisjunction.h"
43 #include "scip/cons_conjunction.h"
44 #include "scip/cons_integral.h"
45 #include "scip/cons_knapsack.h"
46 #include "scip/cons_linear.h"
47 #include "scip/cons_logicor.h"
48 #include "scip/cons_or.h"
49 #include "scip/cons_setppc.h"
50 #include "scip/cons_varbound.h"
51 #include "scip/cons_xor.h"
52 
53 #if USEHEURS
54 #include "scip/heur_actconsdiving.h"
55 #include "scip/heur_clique.h"
56 #include "scip/heur_coefdiving.h"
57 #include "scip/heur_crossover.h"
58 #include "scip/heur_dins.h"
59 #include "scip/heur_dualval.h"
60 #include "scip/heur_feaspump.h"
61 #include "scip/heur_fixandinfer.h"
62 #include "scip/heur_fracdiving.h"
63 #include "scip/heur_guideddiving.h"
64 #include "scip/heur_intdiving.h"
65 #include "scip/heur_intshifting.h"
66 #include "scip/heur_linesearchdiving.h"
67 #include "scip/heur_localbranching.h"
68 #include "scip/heur_mutation.h"
69 #include "scip/heur_objpscostdiving.h"
70 #include "scip/heur_octane.h"
71 #include "scip/heur_oneopt.h"
72 #include "scip/heur_proximity.h"
73 #include "scip/heur_pscostdiving.h"
74 #include "scip/heur_randrounding.h"
75 #include "scip/heur_rens.h"
76 #include "scip/heur_rins.h"
77 #include "scip/heur_rootsoldiving.h"
78 #include "scip/heur_rounding.h"
79 #include "scip/heur_shiftandpropagate.h"
80 #include "scip/heur_shifting.h"
81 #include "scip/heur_simplerounding.h"
82 #include "scip/heur_twoopt.h"
83 #include "scip/heur_vbounds.h"
84 #include "scip/heur_veclendiving.h"
85 #include "scip/heur_zeroobj.h"
86 #include "scip/heur_zirounding.h"
87 #endif
88 
89 #include "scip/presol_implics.h"
90 #include "scip/presol_inttobinary.h"
91 #include "presol_roundbound.h"
92 #include "scip/presol_boundshift.h"
93 
94 #if USEPROP
95 #include "scip/prop_dualfix.h"
96 #include "scip/prop_genvbounds.h"
97 #include "scip/prop_probing.h"
98 #include "scip/prop_pseudoobj.h"
99 #include "scip/prop_rootredcost.h"
100 #include "scip/prop_redcost.h"
101 #include "scip/prop_vbounds.h"
102 #endif
103 
104 #if USESEPA
105 #include "scip/sepa_clique.h"
106 #include "scip/sepa_cmir.h"
107 #include "scip/sepa_flowcover.h"
108 #include "scip/sepa_gomory.h"
109 #include "scip/sepa_impliedbounds.h"
110 #include "scip/sepa_intobj.h"
111 #include "scip/sepa_mcf.h"
112 #include "scip/sepa_oddcycle.h"
113 #include "scip/sepa_strongcg.h"
114 #endif
115 
116 /* Jonas' stuff */
117 #include "sepa_basis.h"
118 
119 #include "scip/reader_cip.h"
120 #include "scip/reader_lp.h"
121 #include "scip/scipshell.h"
122 
123 /* GCG specific stuff */
124 #include "pricer_gcg.h"
125 #include "nodesel_master.h"
126 #include "cons_masterbranch.h"
127 #include "cons_integralorig.h"
128 #include "sepa_master.h"
129 #include "branch_ryanfoster.h"
130 #include "branch_orig.h"
131 #include "branch_relpsprob.h"
132 #include "branch_generic.h"
133 #include "scip/debug.h"
134 #include "dialog_master.h"
135 #include "disp_master.h"
136 #include "solver_knapsack.h"
137 #include "solver_mip.h"
138 #include "event_bestsol.h"
139 #include "event_relaxsol.h"
140 #include "event_solvingstats.h"
141 #include "event_display.h"
142 
143 /* Christian's heuristics */
144 #include "heur_greedycolsel.h"
145 #include "heur_masterdiving.h"
146 #include "heur_mastercoefdiving.h"
147 #include "heur_masterfracdiving.h"
148 #include "heur_masterlinesdiving.h"
149 #include "heur_mastervecldiving.h"
150 #include "heur_relaxcolsel.h"
151 #include "heur_restmaster.h"
152 #include "heur_setcover.h"
153 
154 #ifdef WITH_CLIQUER
155 #include "solver_cliquer.h"
156 #endif
157 
158 #ifdef WITH_CPLEXSOLVER
159 #include "solver_cplex.h"
160 #endif
161 
162 #include "scip/table_default.h"
163 
166  SCIP* scip
167  )
168 {
169  SCIP_CALL( SCIPincludeConshdlrLinear(scip) ); /* linear must be first due to constraint upgrading */
170  SCIP_CALL( SCIPincludeConshdlrAnd(scip) );
171  SCIP_CALL( SCIPincludeConshdlrBounddisjunction(scip) );
172  SCIP_CALL( SCIPincludeConshdlrConjunction(scip) );
173  SCIP_CALL( SCIPincludeConshdlrIntegral(scip) );
174  SCIP_CALL( SCIPincludeConshdlrKnapsack(scip) );
175  SCIP_CALL( SCIPincludeConshdlrLogicor(scip) );
176  SCIP_CALL( SCIPincludeConshdlrOr(scip) );
177  SCIP_CALL( SCIPincludeConshdlrSetppc(scip) );
178  SCIP_CALL( SCIPincludeConshdlrVarbound(scip) );
179  SCIP_CALL( SCIPincludeConshdlrXor(scip) );
180 
181  SCIP_CALL( SCIPincludeReaderCip(scip) );
182  SCIP_CALL( SCIPincludeReaderLp(scip) );
183 
184  SCIP_CALL( SCIPincludePresolBoundshift(scip) );
185  SCIP_CALL( SCIPincludePresolImplics(scip) );
186  SCIP_CALL( SCIPincludePresolInttobinary(scip) );
187  SCIP_CALL( SCIPincludePresolRoundbound(scip) );
188 
189 #if USEPROP
190  SCIP_CALL( SCIPincludePropDualfix(scip) );
191  SCIP_CALL( SCIPincludePropGenvbounds(scip) );
192  SCIP_CALL( SCIPincludePropProbing(scip) );
193  SCIP_CALL( SCIPincludePropPseudoobj(scip) );
194  SCIP_CALL( SCIPincludePropRootredcost(scip) );
195  SCIP_CALL( SCIPincludePropRedcost(scip) );
196  SCIP_CALL( SCIPincludePropVbounds(scip) );
197 #endif
198 
199  SCIP_CALL( SCIPincludeNodeselMaster(scip) );
200  SCIP_CALL( SCIPincludeConshdlrIntegralOrig(scip) );
201  SCIP_CALL( SCIPincludeBranchruleRyanfoster(scip) );
202  SCIP_CALL( SCIPincludeBranchruleOrig(scip) );
203  SCIP_CALL( SCIPincludeBranchruleRelpsprob(scip) );
204  SCIP_CALL( SCIPincludeBranchruleGeneric(scip) );
205 
206 #if USEHEURS
207  SCIP_CALL( SCIPincludeHeurActconsdiving(scip) );
208  SCIP_CALL( SCIPincludeHeurClique(scip) );
209  SCIP_CALL( SCIPincludeHeurCoefdiving(scip) );
210  SCIP_CALL( SCIPincludeHeurCrossover(scip) );
211  SCIP_CALL( SCIPincludeHeurDins(scip) );
212  SCIP_CALL( SCIPincludeHeurDualval(scip) );
213  SCIP_CALL( SCIPincludeHeurFeaspump(scip) );
214  SCIP_CALL( SCIPincludeHeurFixandinfer(scip) );
215  SCIP_CALL( SCIPincludeHeurFracdiving(scip) );
216  SCIP_CALL( SCIPincludeHeurGuideddiving(scip) );
217  SCIP_CALL( SCIPincludeHeurIntdiving(scip) );
218  SCIP_CALL( SCIPincludeHeurIntshifting(scip) );
219  SCIP_CALL( SCIPincludeHeurLinesearchdiving(scip) );
220  SCIP_CALL( SCIPincludeHeurLocalbranching(scip) );
221  SCIP_CALL( SCIPincludeHeurMutation(scip) );
222  SCIP_CALL( SCIPincludeHeurObjpscostdiving(scip) );
223  SCIP_CALL( SCIPincludeHeurOctane(scip) );
224  SCIP_CALL( SCIPincludeHeurOneopt(scip) );
225  SCIP_CALL( SCIPincludeHeurProximity(scip) );
226  SCIP_CALL( SCIPincludeHeurPscostdiving(scip) );
227  SCIP_CALL( SCIPincludeHeurRandrounding(scip) );
228  SCIP_CALL( SCIPincludeHeurRens(scip) );
229  SCIP_CALL( SCIPincludeHeurRins(scip) );
230  SCIP_CALL( SCIPincludeHeurRootsoldiving(scip) );
231  SCIP_CALL( SCIPincludeHeurRounding(scip) );
232  SCIP_CALL( SCIPincludeHeurShiftandpropagate(scip) );
233  SCIP_CALL( SCIPincludeHeurShifting(scip) );
234  SCIP_CALL( SCIPincludeHeurTwoopt(scip) );
235  SCIP_CALL( SCIPincludeHeurVbounds(scip) );
236  SCIP_CALL( SCIPincludeHeurVeclendiving(scip) );
237  SCIP_CALL( SCIPincludeHeurZeroobj(scip) );
238  SCIP_CALL( SCIPincludeHeurZirounding(scip) );
239 
240  SCIP_CALL( SCIPincludeHeurSimplerounding(scip) );
241 
242  /* Christian's heuristics */
243  SCIP_CALL( SCIPincludeHeurGreedycolsel(scip) );
244  SCIP_CALL( SCIPincludeEventHdlrMasterdiving(scip) );
245  SCIP_CALL( GCGincludeHeurMastercoefdiving(scip) );
246  SCIP_CALL( GCGincludeHeurMasterfracdiving(scip) );
247  SCIP_CALL( GCGincludeHeurMasterlinesdiving(scip) );
248  SCIP_CALL( GCGincludeHeurMastervecldiving(scip) );
249  SCIP_CALL( SCIPincludeHeurRelaxcolsel(scip) );
250  SCIP_CALL( SCIPincludeHeurRestmaster(scip) );
251  SCIP_CALL( SCIPincludeHeurSetcover(scip) );
252 #endif
253 
254 #if USESEPA
255  SCIP_CALL( SCIPincludeSepaClique(scip) );
256  SCIP_CALL( SCIPincludeSepaCmir(scip) );
257  SCIP_CALL( SCIPincludeSepaFlowcover(scip) );
258  SCIP_CALL( SCIPincludeSepaGomory(scip) );
259  SCIP_CALL( SCIPincludeSepaImpliedbounds(scip) );
260  SCIP_CALL( SCIPincludeSepaIntobj(scip) );
261  SCIP_CALL( SCIPincludeSepaMcf(scip) );
262  SCIP_CALL( SCIPincludeSepaOddcycle(scip) );
263  SCIP_CALL( SCIPincludeSepaRedcost(scip) );
264  SCIP_CALL( SCIPincludeSepaStrongcg(scip) );
265  SCIP_CALL( SCIPincludeSepaZerohalf(scip) );
266 #endif
267  SCIP_CALL( SCIPincludeSepaMaster(scip) );
268  SCIP_CALL( SCIPincludeDialogMaster(scip) );
269  SCIP_CALL( SCIPincludeDispMaster(scip) );
270  SCIP_CALL( SCIPdebugIncludeProp(scip) ); /*lint !e506 !e774*/
271  SCIP_CALL( SCIPincludeTableDefault(scip) );
272 
273  /* Jonas' stuff */
274  SCIP_CALL( SCIPincludeSepaBasis(scip) );
275 
276  SCIP_CALL( GCGincludeSolverKnapsack(scip) );
277  SCIP_CALL( GCGincludeSolverMip(scip) );
278 
279 #ifdef WITH_CLIQUER
280  SCIP_CALL( GCGincludeSolverCliquer(scip) );
281 #endif
282 
283 #ifdef WITH_CPLEXSOLVER
284  SCIP_CALL( GCGincludeSolverCplex(scip) );
285 #endif
286 
287  /* include masterbranch constraint handler */
288  SCIP_CALL( SCIPincludeConshdlrMasterbranch(scip) );
289 
290  SCIP_CALL( SCIPincludeEventHdlrBestsol(scip) );
291  SCIP_CALL( SCIPincludeEventHdlrRelaxsol(scip) );
292  SCIP_CALL( SCIPincludeEventHdlrSolvingstats(scip) );
293  SCIP_CALL( SCIPincludeEventHdlrDisplay(scip) );
294 
295  return SCIP_OKAY;
296 }
set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)
eventhandler to update the relaxation solution in the original problem when the master LP has been so...
master display columns
SCIP_RETCODE SCIPincludeBranchruleRelpsprob(SCIP *scip)
branching rule for original problem in GCG
SCIP_RETCODE SCIPincludeHeurSetcover(SCIP *scip)
SCIP_RETCODE GCGincludeSolverCliquer(SCIP *scip)
SCIP plugins for generic column generation.
master LP diving heuristic that chooses fixings w.r.t. the matrix coefficients
SCIP_RETCODE SCIPincludeDialogMaster(SCIP *scip)
Definition: dialog_master.c:73
SCIP_RETCODE SCIPincludeDispMaster(SCIP *scip)
Definition: disp_master.c:89
SCIP_RETCODE SCIPincludeEventHdlrSolvingstats(SCIP *scip)
eventhdlr to disable the master display after the root node
constraint handler for the integrality constraint
SCIP_RETCODE SCIPincludeHeurRestmaster(SCIP *scip)
master separator
SCIP_RETCODE SCIPincludeEventHdlrDisplay(SCIP *scip)
Definition: event_display.c:82
SCIP_RETCODE SCIPincludeNodeselMaster(SCIP *scip)
SCIP_RETCODE GCGincludeSolverKnapsack(SCIP *scip)
SCIP_RETCODE GCGincludeSolverCplex(SCIP *scip)
eventhdlr for writing various types of information during the solving process
relaxation based column selection primal heuristic
master LP diving heuristic that chooses fixings w.r.t. the fractionalities
SCIP_RETCODE GCGincludeSolverMip(SCIP *scip)
Definition: solver_mip.c:676
user interface dialog for master problem
basis separator
SCIP_RETCODE SCIPincludeEventHdlrMasterdiving(SCIP *scip)
Node selector for coordination of master and original formulation.
cplex solver for pricing problems
master LP diving heuristic that rounds variables with long column vectors
SCIP_RETCODE SCIPincludeConshdlrIntegralOrig(SCIP *scip)
greedy column selection primal heuristic
SCIP_RETCODE SCIPincludeSepaMaster(SCIP *scip)
Definition: sepa_master.c:367
SCIP_RETCODE SCIPincludeEventHdlrBestsol(SCIP *scip)
GCG variable pricer.
Restricted Master Heuristic.
eventhdlr to record the best primal bound for each heuristic
SCIP_RETCODE SCIPincludeHeurRelaxcolsel(SCIP *scip)
SCIP_RETCODE GCGincludeHeurMastercoefdiving(SCIP *scip)
SCIP_RETCODE GCGincludeHeurMastervecldiving(SCIP *scip)
branching rule based on vanderbeck's generic branching scheme
branching rule for original problem in GCG implementing the Ryan and Foster branching scheme ...
constraint handler for storing the branching decisions at each node of the tree
SCIP_RETCODE SCIPincludePresolRoundbound(SCIP *scip)
heuristic solver for pricing problems that solves independent set problems with cliquer ...
SCIP_RETCODE SCIPincludeBranchruleRyanfoster(SCIP *scip)
master LP diving heuristic that fixes variables with a large difference to their root solution ...
knapsack solver for pricing problems
SCIP_RETCODE GCGincludeHeurMasterlinesdiving(SCIP *scip)
mip solver for pricing problems
SCIP_RETCODE SCIPincludeHeurGreedycolsel(SCIP *scip)
SCIP_RETCODE SCIPincludeBranchruleOrig(SCIP *scip)
Definition: branch_orig.c:903
reliable pseudo costs branching rule
SCIP_RETCODE SCIPincludeBranchruleGeneric(SCIP *scip)
SCIP_RETCODE SCIPincludeEventHdlrRelaxsol(SCIP *scip)
primal heuristic interface for LP diving heuristics on the master variables
SCIP_RETCODE SCIPincludeSepaBasis(SCIP *scip)
Definition: sepa_basis.c:1507
SCIP_RETCODE SCIPincludeConshdlrMasterbranch(SCIP *scip)
roundbound presolver: round fractional bounds on integer variables
SCIP_RETCODE GCGincludeHeurMasterfracdiving(SCIP *scip)
SCIP_RETCODE GCGincludeMasterPlugins(SCIP *scip)