Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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-2021 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 
28 /**@file masterplugins.c
29  * @brief SCIP plugins for generic column generation
30  * @author Gerald Gamrath
31  * @author Martin Bergner
32  */
33 
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_indicator.h"
46 #include "scip/cons_knapsack.h"
47 #include "scip/cons_linear.h"
48 #include "scip/cons_logicor.h"
49 #include "scip/cons_or.h"
50 #include "scip/cons_setppc.h"
51 #include "scip/cons_varbound.h"
52 #include "scip/cons_xor.h"
53 
54 #if USEHEURS
55 #include "scip/heur_adaptivediving.h"
56 #include "scip/heur_actconsdiving.h"
57 #include "scip/heur_alns.h"
58 #include "scip/heur_bound.h"
59 #include "scip/heur_clique.h"
60 #include "scip/heur_coefdiving.h"
61 #include "scip/heur_completesol.h"
62 #include "scip/heur_conflictdiving.h"
63 #include "scip/heur_crossover.h"
64 #include "scip/heur_dins.h"
65 #include "scip/heur_distributiondiving.h"
66 #include "scip/heur_dps.h"
67 #include "scip/heur_dualval.h"
68 #include "scip/heur_farkasdiving.h"
69 #include "scip/heur_feaspump.h"
70 #include "scip/heur_fixandinfer.h"
71 #include "scip/heur_fracdiving.h"
72 #include "scip/heur_gins.h"
73 #include "scip/heur_guideddiving.h"
74 #include "scip/heur_indicator.h"
75 #include "scip/heur_intdiving.h"
76 #include "scip/heur_intshifting.h"
77 #include "scip/heur_linesearchdiving.h"
78 #include "scip/heur_localbranching.h"
79 #include "scip/heur_locks.h"
80 #include "scip/heur_lpface.h"
81 #include "scip/heur_mpec.h"
82 #include "scip/heur_multistart.h"
83 #include "scip/heur_mutation.h"
84 #include "scip/heur_nlpdiving.h"
85 #include "scip/heur_ofins.h"
86 #include "scip/heur_objpscostdiving.h"
87 #include "scip/heur_octane.h"
88 #include "scip/heur_oneopt.h"
89 #include "scip/heur_padm.h"
90 #include "scip/heur_proximity.h"
91 #include "scip/heur_pscostdiving.h"
92 #include "scip/heur_randrounding.h"
93 #include "scip/heur_rens.h"
94 #include "scip/heur_reoptsols.h"
95 #include "scip/heur_repair.h"
96 #include "scip/heur_rins.h"
97 #include "scip/heur_rootsoldiving.h"
98 #include "scip/heur_rounding.h"
99 #include "scip/heur_shiftandpropagate.h"
100 #include "scip/heur_shifting.h"
101 #include "scip/heur_simplerounding.h"
102 #include "scip/heur_subnlp.h"
103 #include "scip/heur_trivial.h"
104 #include "scip/heur_trivialnegation.h"
105 #include "scip/heur_trustregion.h"
106 #include "scip/heur_trysol.h"
107 #include "scip/heur_twoopt.h"
108 #include "scip/heur_undercover.h"
109 #include "scip/heur_vbounds.h"
110 #include "scip/heur_veclendiving.h"
111 #include "scip/heur_zirounding.h"
112 #include "scip/heur_zeroobj.h"
113 #endif
114 
115 #include "scip/presol_implics.h"
116 #include "scip/presol_inttobinary.h"
117 #include "presol_roundbound.h"
118 #include "scip/presol_boundshift.h"
119 
120 #if USEPROP
121 #include "scip/prop_dualfix.h"
122 #include "scip/prop_genvbounds.h"
123 #include "scip/prop_probing.h"
124 #include "scip/prop_pseudoobj.h"
125 #include "scip/prop_rootredcost.h"
126 #include "scip/prop_redcost.h"
127 #include "scip/prop_vbounds.h"
128 #endif
129 
130 #if USESEPA
131 #include "scip/sepa_clique.h"
132 #include "scip/sepa_cmir.h"
133 #include "scip/sepa_flowcover.h"
134 #include "scip/sepa_gomory.h"
135 #include "scip/sepa_impliedbounds.h"
136 #include "scip/sepa_intobj.h"
137 #include "scip/sepa_mcf.h"
138 #include "scip/sepa_oddcycle.h"
139 #include "scip/sepa_strongcg.h"
140 #endif
141 
142 /* Jonas' stuff */
143 #include "sepa_basis.h"
144 
145 #include "scip/reader_cip.h"
146 #include "scip/reader_lp.h"
147 #include "scip/scipshell.h"
148 
149 /* GCG specific stuff */
150 #include "pricer_gcg.h"
151 #include "nodesel_master.h"
152 #include "cons_masterbranch.h"
153 #include "cons_integralorig.h"
154 #include "sepa_master.h"
155 #include "branch_ryanfoster.h"
156 #include "branch_orig.h"
157 #include "branch_relpsprob.h"
158 #include "branch_generic.h"
159 #include "branch_bpstrong.h"
160 #include "scip/debug.h"
161 #include "dialog_master.h"
162 #include "disp_master.h"
163 #include "solver_knapsack.h"
164 #include "solver_mip.h"
165 #include "event_bestsol.h"
166 #include "event_relaxsol.h"
167 #include "event_solvingstats.h"
168 #include "event_display.h"
169 
170 /* Christian's heuristics */
171 #include "heur_greedycolsel.h"
172 #include "heur_masterdiving.h"
173 #include "heur_mastercoefdiving.h"
174 #include "heur_masterfracdiving.h"
175 #include "heur_masterlinesdiving.h"
176 #include "heur_mastervecldiving.h"
177 #include "heur_relaxcolsel.h"
178 #include "heur_restmaster.h"
179 #include "heur_setcover.h"
180 
181 #ifdef WITH_CLIQUER
182 #include "solver_cliquer.h"
183 #endif
184 
185 #ifdef WITH_CPLEXSOLVER
186 #include "solver_cplex.h"
187 #endif
188 
189 #include "scip/table_default.h"
190 
191 /** includes default GCG master plugins */
193  SCIP* scip /**< SCIP data structure */
194  )
195 {
196  SCIP_CALL( SCIPincludeDialogMaster(scip) );
197  SCIP_CALL( SCIPincludeConshdlrLinear(scip) ); /* linear must be first due to constraint upgrading */
198  SCIP_CALL( SCIPincludeConshdlrAnd(scip) );
199  SCIP_CALL( SCIPincludeConshdlrBounddisjunction(scip) );
200  SCIP_CALL( SCIPincludeConshdlrConjunction(scip) );
201  SCIP_CALL( SCIPincludeConshdlrIndicator(scip) );
202  SCIP_CALL( SCIPincludeConshdlrIntegral(scip) );
203  SCIP_CALL( SCIPincludeConshdlrKnapsack(scip) );
204  SCIP_CALL( SCIPincludeConshdlrLogicor(scip) );
205  SCIP_CALL( SCIPincludeConshdlrOr(scip) );
206  SCIP_CALL( SCIPincludeConshdlrSetppc(scip) );
207  SCIP_CALL( SCIPincludeConshdlrVarbound(scip) );
208  SCIP_CALL( SCIPincludeConshdlrXor(scip) );
209 
210  SCIP_CALL( SCIPincludeReaderCip(scip) );
211  SCIP_CALL( SCIPincludeReaderLp(scip) );
212 
213  SCIP_CALL( SCIPincludePresolBoundshift(scip) );
214  SCIP_CALL( SCIPincludePresolImplics(scip) );
215  SCIP_CALL( SCIPincludePresolInttobinary(scip) );
216  SCIP_CALL( SCIPincludePresolRoundbound(scip) );
217 
218 #if USEPROP
219  SCIP_CALL( SCIPincludePropDualfix(scip) );
220  SCIP_CALL( SCIPincludePropGenvbounds(scip) );
221  SCIP_CALL( SCIPincludePropProbing(scip) );
222  SCIP_CALL( SCIPincludePropPseudoobj(scip) );
223  SCIP_CALL( SCIPincludePropRootredcost(scip) );
224  SCIP_CALL( SCIPincludePropRedcost(scip) );
225  SCIP_CALL( SCIPincludePropVbounds(scip) );
226 #endif
227 
228  SCIP_CALL( SCIPincludeNodeselMaster(scip) );
229  SCIP_CALL( SCIPincludeConshdlrIntegralOrig(scip) );
230  SCIP_CALL( SCIPincludeBranchruleRyanfoster(scip) );
231  SCIP_CALL( SCIPincludeBranchruleOrig(scip) );
232  SCIP_CALL( SCIPincludeBranchruleRelpsprob(scip) );
233  SCIP_CALL( SCIPincludeBranchruleGeneric(scip) );
234  SCIP_CALL( SCIPincludeBranchruleBPStrong(scip) );
235 
236 #if USEHEURS
237  SCIP_CALL( SCIPincludeHeurActconsdiving(scip) );
238  SCIP_CALL( SCIPincludeHeurAdaptivediving(scip) );
239  SCIP_CALL( SCIPincludeHeurBound(scip) );
240  SCIP_CALL( SCIPincludeHeurClique(scip) );
241  SCIP_CALL( SCIPincludeHeurCoefdiving(scip) );
242  SCIP_CALL( SCIPincludeHeurCompletesol(scip) );
243  SCIP_CALL( SCIPincludeHeurConflictdiving(scip) );
244  SCIP_CALL( SCIPincludeHeurCrossover(scip) );
245  SCIP_CALL( SCIPincludeHeurDins(scip) );
246  SCIP_CALL( SCIPincludeHeurDistributiondiving(scip) );
247  SCIP_CALL( SCIPincludeHeurDps(scip) );
248  SCIP_CALL( SCIPincludeHeurDualval(scip) );
249  SCIP_CALL( SCIPincludeHeurFarkasdiving(scip) );
250  SCIP_CALL( SCIPincludeHeurFeaspump(scip) );
251  SCIP_CALL( SCIPincludeHeurFixandinfer(scip) );
252  SCIP_CALL( SCIPincludeHeurFracdiving(scip) );
253  SCIP_CALL( SCIPincludeHeurGins(scip) );
254  SCIP_CALL( SCIPincludeHeurGuideddiving(scip) );
255  SCIP_CALL( SCIPincludeHeurIndicator(scip) );
256  SCIP_CALL( SCIPincludeHeurIntdiving(scip) );
257  SCIP_CALL( SCIPincludeHeurIntshifting(scip) );
258  SCIP_CALL( SCIPincludeHeurLinesearchdiving(scip) );
259  SCIP_CALL( SCIPincludeHeurLocalbranching(scip) );
260  SCIP_CALL( SCIPincludeHeurLocks(scip) );
261  SCIP_CALL( SCIPincludeHeurLpface(scip) );
262  SCIP_CALL( SCIPincludeHeurAlns(scip) );
263  SCIP_CALL( SCIPincludeHeurMultistart(scip) );
264  SCIP_CALL( SCIPincludeHeurMpec(scip) );
265  SCIP_CALL( SCIPincludeHeurMutation(scip) );
266  SCIP_CALL( SCIPincludeHeurNlpdiving(scip) );
267  SCIP_CALL( SCIPincludeHeurObjpscostdiving(scip) );
268  SCIP_CALL( SCIPincludeHeurOctane(scip) );
269  SCIP_CALL( SCIPincludeHeurOfins(scip) );
270  SCIP_CALL( SCIPincludeHeurOneopt(scip) );
271  SCIP_CALL( SCIPincludeHeurPADM(scip) );
272  SCIP_CALL( SCIPincludeHeurProximity(scip) );
273  SCIP_CALL( SCIPincludeHeurPscostdiving(scip) );
274  SCIP_CALL( SCIPincludeHeurRandrounding(scip) );
275  SCIP_CALL( SCIPincludeHeurRens(scip) );
276  SCIP_CALL( SCIPincludeHeurReoptsols(scip) );
277  SCIP_CALL( SCIPincludeHeurRepair(scip) );
278  SCIP_CALL( SCIPincludeHeurRins(scip) );
279  SCIP_CALL( SCIPincludeHeurRootsoldiving(scip) );
280  SCIP_CALL( SCIPincludeHeurRounding(scip) );
281  SCIP_CALL( SCIPincludeHeurShiftandpropagate(scip) );
282  SCIP_CALL( SCIPincludeHeurShifting(scip) );
283  SCIP_CALL( SCIPincludeHeurSubNlp(scip) );
284  SCIP_CALL( SCIPincludeHeurTrivial(scip) );
285  SCIP_CALL( SCIPincludeHeurTrivialnegation(scip) );
286  SCIP_CALL( SCIPincludeHeurTrustregion(scip) );
287  SCIP_CALL( SCIPincludeHeurTrySol(scip) );
288  SCIP_CALL( SCIPincludeHeurTwoopt(scip) );
289  SCIP_CALL( SCIPincludeHeurUndercover(scip) );
290  SCIP_CALL( SCIPincludeHeurVbounds(scip) );
291  SCIP_CALL( SCIPincludeHeurVeclendiving(scip) );
292  SCIP_CALL( SCIPincludeHeurZirounding(scip) );
293  SCIP_CALL( SCIPincludeHeurZeroobj(scip) );
294 
295  SCIP_CALL( SCIPincludeHeurSimplerounding(scip) );
296 
297  /* Christian's heuristics */
298  SCIP_CALL( SCIPincludeHeurGreedycolsel(scip) );
299  SCIP_CALL( SCIPincludeEventHdlrMasterdiving(scip) );
300  SCIP_CALL( GCGincludeHeurMastercoefdiving(scip) );
301  SCIP_CALL( GCGincludeHeurMasterfracdiving(scip) );
302  SCIP_CALL( GCGincludeHeurMasterlinesdiving(scip) );
303  SCIP_CALL( GCGincludeHeurMastervecldiving(scip) );
304  SCIP_CALL( SCIPincludeHeurRelaxcolsel(scip) );
305  SCIP_CALL( SCIPincludeHeurRestmaster(scip) );
306  SCIP_CALL( SCIPincludeHeurSetcover(scip) );
307 #endif
308 
309 #if USESEPA
310  SCIP_CALL( SCIPincludeSepaClique(scip) );
311  SCIP_CALL( SCIPincludeSepaCmir(scip) );
312  SCIP_CALL( SCIPincludeSepaFlowcover(scip) );
313  SCIP_CALL( SCIPincludeSepaGomory(scip) );
314  SCIP_CALL( SCIPincludeSepaImpliedbounds(scip) );
315  SCIP_CALL( SCIPincludeSepaIntobj(scip) );
316  SCIP_CALL( SCIPincludeSepaMcf(scip) );
317  SCIP_CALL( SCIPincludeSepaOddcycle(scip) );
318  SCIP_CALL( SCIPincludeSepaRedcost(scip) );
319  SCIP_CALL( SCIPincludeSepaZerohalf(scip) );
320 #endif
321  SCIP_CALL( SCIPincludeSepaMaster(scip) );
322  SCIP_CALL( SCIPincludeDispMaster(scip) );
323  SCIP_CALL( SCIPdebugIncludeProp(scip) ); /*lint !e506 !e774*/
324  SCIP_CALL( SCIPincludeTableDefault(scip) );
325 
326  /* Jonas' stuff */
327  SCIP_CALL( SCIPincludeSepaBasis(scip) );
328 
329  SCIP_CALL( GCGincludeSolverKnapsack(scip) );
330  SCIP_CALL( GCGincludeSolverMip(scip) );
331 
332 #ifdef WITH_CLIQUER
333  SCIP_CALL( GCGincludeSolverCliquer(scip) );
334 #endif
335 
336 #ifdef WITH_CPLEXSOLVER
337  SCIP_CALL( GCGincludeSolverCplex(scip) );
338 #endif
339 
340  /* include masterbranch constraint handler */
341  SCIP_CALL( SCIPincludeConshdlrMasterbranch(scip) );
342 
343  SCIP_CALL( SCIPincludeEventHdlrBestsol(scip) );
344  SCIP_CALL( SCIPincludeEventHdlrRelaxsol(scip) );
345  SCIP_CALL( SCIPincludeEventHdlrSolvingstats(scip) );
346  SCIP_CALL( SCIPincludeEventHdlrDisplay(scip) );
347 
348  return SCIP_OKAY;
349 }
master LP diving heuristic that rounds variables with long column vectors
master LP diving heuristic that chooses fixings w.r.t. the fractionalities
SCIP_RETCODE GCGincludeHeurMastercoefdiving(SCIP *scip)
SCIP_RETCODE SCIPincludeBranchruleRelpsprob(SCIP *scip)
Restricted Master Heuristic.
eventhdlr to disable the master display after the root node
SCIP_RETCODE GCGincludeSolverCplex(SCIP *scip)
SCIP plugins for generic column generation.
branching rule for original problem in GCG implementing the Ryan and Foster branching scheme
SCIP_RETCODE GCGincludeHeurMasterlinesdiving(SCIP *scip)
eventhdlr for writing various types of information during the solving process
heuristic solver for pricing problems that solves independent set problems with cliquer
SCIP_RETCODE SCIPincludeHeurSetcover(SCIP *scip)
branching rule for original problem in GCG
GCG variable pricer.
SCIP_RETCODE SCIPincludeBranchruleBPStrong(SCIP *scip)
greedy column selection primal heuristic
knapsack solver for pricing problems
roundbound presolver: round fractional bounds on integer variables
cplex solver for pricing problems
SCIP_RETCODE SCIPincludeHeurRelaxcolsel(SCIP *scip)
constraint handler for the integrality constraint
user interface dialog for master problem
constraint handler for storing the branching decisions at each node of the tree
SCIP_RETCODE GCGincludeSolverMip(SCIP *scip)
Definition: solver_mip.c:677
SCIP_RETCODE GCGincludeSolverCliquer(SCIP *scip)
master separator
branching rule based on vanderbeck's generic branching scheme
basis separator
SCIP_RETCODE SCIPincludeEventHdlrMasterdiving(SCIP *scip)
SCIP_RETCODE SCIPincludeConshdlrMasterbranch(SCIP *scip)
relaxation based column selection primal heuristic
primal heuristic interface for LP diving heuristics on the master variables
SCIP_RETCODE SCIPincludeSepaBasis(SCIP *scip)
Definition: sepa_basis.c:1592
SCIP_RETCODE SCIPincludeEventHdlrBestsol(SCIP *scip)
SCIP_RETCODE GCGincludeHeurMasterfracdiving(SCIP *scip)
SCIP_RETCODE SCIPincludeEventHdlrRelaxsol(SCIP *scip)
SCIP_RETCODE SCIPincludeBranchruleGeneric(SCIP *scip)
master display columns
Node selector for coordination of master and original formulation.
SCIP_RETCODE SCIPincludeHeurRestmaster(SCIP *scip)
master LP diving heuristic that fixes variables with a large difference to their root solution
eventhandler to update the relaxation solution in the original problem when the master LP has been so...
SCIP_RETCODE SCIPincludeBranchruleOrig(SCIP *scip)
Definition: branch_orig.c:993
SCIP_RETCODE SCIPincludeHeurGreedycolsel(SCIP *scip)
SCIP_RETCODE SCIPincludeDialogMaster(SCIP *scip)
Definition: dialog_master.c:73
SCIP_RETCODE SCIPincludeConshdlrIntegralOrig(SCIP *scip)
SCIP_RETCODE SCIPincludeDispMaster(SCIP *scip)
Definition: disp_master.c:89
set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)
eventhdlr to record the best primal bound for each heuristic
SCIP_RETCODE GCGincludeSolverKnapsack(SCIP *scip)
SCIP_RETCODE SCIPincludeNodeselMaster(SCIP *scip)
generic branch and price strong branching as described in Pecin, D., Pessoa, A., Poggi,...
SCIP_RETCODE SCIPincludeEventHdlrDisplay(SCIP *scip)
Definition: event_display.c:82
master LP diving heuristic that chooses fixings w.r.t. the matrix coefficients
SCIP_RETCODE SCIPincludePresolRoundbound(SCIP *scip)
SCIP_RETCODE GCGincludeHeurMastervecldiving(SCIP *scip)
SCIP_RETCODE SCIPincludeEventHdlrSolvingstats(SCIP *scip)
SCIP_RETCODE GCGincludeMasterPlugins(SCIP *scip)
reliable pseudo costs branching rule
SCIP_RETCODE SCIPincludeSepaMaster(SCIP *scip)
Definition: sepa_master.c:368
mip solver for pricing problems
SCIP_RETCODE SCIPincludeBranchruleRyanfoster(SCIP *scip)