gcgplugins.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-2017 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 
36 #include "gcgplugins.h"
37 #include "scip/debug.h"
38 
39 #define USEHEURS 1
40 #define USESEPA 1
41 #define USEPROP 1
42 
43 /* include header files here, such that the user only has to include
44  * gcgplugins.h
45  */
46 #include "scip/cons_integral.h"
47 #include "scip/cons_knapsack.h"
48 #include "scip/cons_linear.h"
49 #include "scip/cons_logicor.h"
50 #include "scip/cons_setppc.h"
51 #include "scip/cons_varbound.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_nlpdiving.h"
70 #include "scip/heur_objpscostdiving.h"
71 #include "scip/heur_octane.h"
72 #include "scip/heur_oneopt.h"
73 #include "scip/heur_proximity.h"
74 #include "scip/heur_pscostdiving.h"
75 #include "scip/heur_randrounding.h"
76 #include "scip/heur_rens.h"
77 #include "scip/heur_rins.h"
78 #include "scip/heur_rootsoldiving.h"
79 #include "scip/heur_rounding.h"
80 #include "scip/heur_shiftandpropagate.h"
81 #include "scip/heur_shifting.h"
82 #include "scip/heur_simplerounding.h"
83 #include "scip/heur_subnlp.h"
84 #include "scip/heur_trivial.h"
85 #include "scip/heur_trysol.h"
86 #include "scip/heur_twoopt.h"
87 #include "scip/heur_undercover.h"
88 #include "scip/heur_vbounds.h"
89 #include "scip/heur_veclendiving.h"
90 #include "scip/heur_zirounding.h"
91 #include "scip/heur_zeroobj.h"
92 #endif
93 
94 #include "scip/nodesel_bfs.h"
95 #include "scip/nodesel_dfs.h"
96 #include "scip/nodesel_estimate.h"
97 #include "scip/nodesel_hybridestim.h"
98 #include "scip/nodesel_restartdfs.h"
99 
100 #include "scip/presol_implics.h"
101 #include "scip/presol_inttobinary.h"
102 #include "scip/presol_trivial.h"
103 #include "scip/presol_boundshift.h"
104 #include "scip/presol_domcol.h"
105 #include "scip/presol_convertinttobin.h"
106 
107 #if USEPROP
108 #include "scip/prop_dualfix.h"
109 #include "scip/prop_probing.h"
110 #include "scip/prop_pseudoobj.h"
111 #include "scip/prop_rootredcost.h"
112 #include "scip/prop_redcost.h"
113 #include "scip/prop_genvbounds.h"
114 #include "scip/prop_vbounds.h"
115 #include "scip/prop_obbt.h"
116 #endif
117 
118 #include "scip/reader_bnd.h"
119 #include "scip/reader_ccg.h"
120 #include "scip/reader_cip.h"
121 #include "scip/reader_cnf.h"
122 #include "scip/reader_fix.h"
123 #include "scip/reader_fzn.h"
124 #include "scip/reader_gms.h"
125 #include "scip/reader_lp.h"
126 #include "scip/reader_mps.h"
127 #include "scip/reader_opb.h"
128 #include "scip/reader_osil.h"
129 #include "scip/reader_pip.h"
130 #include "scip/reader_pbm.h"
131 #include "scip/reader_rlp.h"
132 #include "scip/reader_sol.h"
133 #include "scip/reader_wbo.h"
134 #include "scip/reader_zpl.h"
135 
136 #if USESEPA
137 #include "scip/sepa_clique.h"
138 #include "scip/sepa_cmir.h"
139 #include "scip/sepa_flowcover.h"
140 #include "scip/sepa_gomory.h"
141 #include "scip/sepa_impliedbounds.h"
142 #include "scip/sepa_intobj.h"
143 #include "scip/sepa_mcf.h"
144 #include "scip/sepa_oddcycle.h"
145 #include "scip/sepa_strongcg.h"
146 #include "scip/sepa_zerohalf.h"
147 
149 #include "scip/sepa_closecuts.h"
150 #include "scip/sepa_rapidlearning.h"
151 #endif
152 
153 
154 
155 #include "scip/scipshell.h"
156 #include "reader_blk.h"
157 #include "reader_dec.h"
158 #include "pricer_gcg.h"
159 #include "relax_gcg.h"
160 #include "branch_empty.h"
161 
162 #include "cons_origbranch.h"
163 #include "disp_gcg.h"
164 #include "dialog_gcg.h"
165 #include "reader_ref.h"
166 #include "event_bestsol.h"
167 #include "event_mastersol.h"
168 
169 /* Martin's detection stuff */
170 #include "reader_gp.h"
171 #include "cons_decomp.h"
172 #include "dec_connected.h"
173 
174 #ifndef NBLISS
175 #include "dec_isomorph.h"
176 #endif
177 
178 #include "dec_arrowheur.h"
179 #include "dec_stairheur.h"
180 #include "dec_staircase.h"
181 #include "dec_random.h"
182 #include "dec_colors.h"
183 
184 /* Christian's heuristics */
185 #include "heur_gcgcoefdiving.h"
186 #include "heur_gcgdins.h"
187 #include "heur_gcgfeaspump.h"
188 #include "heur_gcgfracdiving.h"
189 #include "heur_gcgguideddiving.h"
190 #include "heur_gcglinesdiving.h"
191 #include "heur_gcgpscostdiving.h"
192 #include "heur_gcgrens.h"
193 #include "heur_gcgrins.h"
194 #include "heur_gcgrounding.h"
195 #include "heur_gcgshifting.h"
196 #include "heur_gcgsimplerounding.h"
197 #include "heur_gcgveclendiving.h"
198 #include "heur_gcgzirounding.h"
199 #include "heur_origdiving.h"
200 #include "heur_xpcrossover.h"
201 #include "heur_xprins.h"
202 
203 /* Friedrike's detection stuff */
204 #include "dec_cutpacking.h"
205 #include "scip_misc.h"
206 
207 
210  SCIP* scip
211  )
212 {
213  SCIP_CALL( SCIPincludeConshdlrLinear(scip) ); /* linear must be first due to constraint upgrading */
214  SCIP_CALL( SCIPincludeConshdlrIntegral(scip) );
215  SCIP_CALL( SCIPincludeConshdlrKnapsack(scip) );
216  SCIP_CALL( SCIPincludeConshdlrLogicor(scip) );
217  SCIP_CALL( SCIPincludeConshdlrSetppc(scip) );
218  SCIP_CALL( SCIPincludeConshdlrVarbound(scip) );
219 
220  SCIP_CALL( SCIPincludeReaderBnd(scip) );
221  SCIP_CALL( SCIPincludeReaderCcg(scip) );
222  SCIP_CALL( SCIPincludeReaderCip(scip) );
223  SCIP_CALL( SCIPincludeReaderCnf(scip) );
224  SCIP_CALL( SCIPincludeReaderFix(scip) );
225  SCIP_CALL( SCIPincludeReaderFzn(scip) );
226  SCIP_CALL( SCIPincludeReaderGms(scip) );
227  SCIP_CALL( SCIPincludeReaderLp(scip) );
228  SCIP_CALL( SCIPincludeReaderMps(scip) );
229  SCIP_CALL( SCIPincludeReaderOpb(scip) );
230  SCIP_CALL( SCIPincludeReaderOsil(scip) );
231  SCIP_CALL( SCIPincludeReaderPip(scip) );
232  SCIP_CALL( SCIPincludeReaderPbm(scip) );
233  SCIP_CALL( SCIPincludeReaderRlp(scip) );
234  SCIP_CALL( SCIPincludeReaderSol(scip) );
235  SCIP_CALL( SCIPincludeReaderWbo(scip) );
236  SCIP_CALL( SCIPincludeReaderZpl(scip) );
237 
238  SCIP_CALL( SCIPincludePresolBoundshift(scip) );
239  SCIP_CALL( SCIPincludePresolImplics(scip) );
240  SCIP_CALL( SCIPincludePresolInttobinary(scip) );
241  SCIP_CALL( SCIPincludePresolTrivial(scip) );
242  SCIP_CALL( SCIPincludePresolDomcol(scip) );
243  SCIP_CALL( SCIPincludePresolConvertinttobin(scip) );
244 
245  SCIP_CALL( SCIPincludeNodeselBfs(scip) );
246  SCIP_CALL( SCIPincludeNodeselDfs(scip) );
247  SCIP_CALL( SCIPincludeNodeselEstimate(scip) );
248  SCIP_CALL( SCIPincludeNodeselHybridestim(scip) );
249  SCIP_CALL( SCIPincludeNodeselRestartdfs(scip) );
250 
251 #if USEPROP
252  SCIP_CALL( SCIPincludePropDualfix(scip) );
253  SCIP_CALL( SCIPincludePropPseudoobj(scip) );
254  SCIP_CALL( SCIPincludePropRootredcost(scip) );
255  SCIP_CALL( SCIPincludePropGenvbounds(scip) );
256  SCIP_CALL( SCIPincludePropProbing(scip) );
257  SCIP_CALL( SCIPincludePropRedcost(scip) );
258  SCIP_CALL( SCIPincludePropVbounds(scip) );
259  SCIP_CALL( SCIPincludePropObbt(scip) );
260 #endif
261 
262 
263 #if USEHEURS
264  SCIP_CALL( SCIPincludeHeurActconsdiving(scip) );
265  SCIP_CALL( SCIPincludeHeurClique(scip) );
266  SCIP_CALL( SCIPincludeHeurCoefdiving(scip) );
267  SCIP_CALL( SCIPincludeHeurCrossover(scip) );
268  SCIP_CALL( SCIPincludeHeurDins(scip) );
269  SCIP_CALL( SCIPincludeHeurDualval(scip) );
270  SCIP_CALL( SCIPincludeHeurFeaspump(scip) );
271  SCIP_CALL( SCIPincludeHeurFixandinfer(scip) );
272  SCIP_CALL( SCIPincludeHeurFracdiving(scip) );
273  SCIP_CALL( SCIPincludeHeurGuideddiving(scip) );
274  SCIP_CALL( SCIPincludeHeurIntdiving(scip) );
275  SCIP_CALL( SCIPincludeHeurIntshifting(scip) );
276  SCIP_CALL( SCIPincludeHeurLinesearchdiving(scip) );
277  SCIP_CALL( SCIPincludeHeurLocalbranching(scip) );
278  SCIP_CALL( SCIPincludeHeurMutation(scip) );
279  SCIP_CALL( SCIPincludeHeurNlpdiving(scip) );
280  SCIP_CALL( SCIPincludeHeurObjpscostdiving(scip) );
281  SCIP_CALL( SCIPincludeHeurOctane(scip) );
282  SCIP_CALL( SCIPincludeHeurOneopt(scip) );
283  SCIP_CALL( SCIPincludeHeurProximity(scip) );
284  SCIP_CALL( SCIPincludeHeurPscostdiving(scip) );
285  SCIP_CALL( SCIPincludeHeurRandrounding(scip) );
286  SCIP_CALL( SCIPincludeHeurRens(scip) );
287  SCIP_CALL( SCIPincludeHeurRins(scip) );
288  SCIP_CALL( SCIPincludeHeurRootsoldiving(scip) );
289  SCIP_CALL( SCIPincludeHeurRounding(scip) );
290  SCIP_CALL( SCIPincludeHeurShiftandpropagate(scip) );
291  SCIP_CALL( SCIPincludeHeurShifting(scip) );
292  SCIP_CALL( SCIPincludeHeurSubNlp(scip) );
293  SCIP_CALL( SCIPincludeHeurTrivial(scip) );
294  SCIP_CALL( SCIPincludeHeurTrySol(scip) );
295  SCIP_CALL( SCIPincludeHeurTwoopt(scip) );
296  SCIP_CALL( SCIPincludeHeurUndercover(scip) );
297  SCIP_CALL( SCIPincludeHeurVbounds(scip) );
298  SCIP_CALL( SCIPincludeHeurVeclendiving(scip) );
299  SCIP_CALL( SCIPincludeHeurZirounding(scip) );
300  SCIP_CALL( SCIPincludeHeurZeroobj(scip) );
301 #endif
302  SCIP_CALL( SCIPincludeHeurSimplerounding(scip) );
303 
304 #if USESEPA
305  SCIP_CALL( SCIPincludeSepaClique(scip) );
306  SCIP_CALL( SCIPincludeSepaCmir(scip) );
307  SCIP_CALL( SCIPincludeSepaFlowcover(scip) );
308  SCIP_CALL( SCIPincludeSepaGomory(scip) );
309  SCIP_CALL( SCIPincludeSepaImpliedbounds(scip) );
310  SCIP_CALL( SCIPincludeSepaIntobj(scip) );
311  SCIP_CALL( SCIPincludeSepaMcf(scip) );
312  SCIP_CALL( SCIPincludeSepaOddcycle(scip) );
313  SCIP_CALL( SCIPincludeSepaStrongcg(scip) );
314  SCIP_CALL( SCIPincludeSepaZerohalf(scip) );
315 
316  /* added by Jonas */
317  SCIP_CALL( SCIPincludeSepaClosecuts(scip) );
318  SCIP_CALL( SCIPincludeSepaRapidlearning(scip) );
319 #endif
320 
321  SCIP_CALL( SCIPincludeRelaxGcg(scip) );
322  SCIP_CALL( SCIPincludeReaderBlk(scip) );
323  SCIP_CALL( SCIPincludeReaderDec(scip) );
324  SCIP_CALL( SCIPincludeReaderRef(scip) );
325  SCIP_CALL( SCIPincludeBranchruleEmpty(scip) );
326 
327  SCIP_CALL( SCIPincludeConshdlrOrigbranch(scip) );
328  SCIP_CALL( SCIPincludeEventHdlrBestsol(scip) );
329  SCIP_CALL( SCIPincludeEventHdlrMastersol(scip) );
330 
331  /* Detectors and decompositions */
332  SCIP_CALL( SCIPincludeReaderGp(scip) );
333  SCIP_CALL( SCIPincludeConshdlrDecomp(scip) );
334  SCIP_CALL( SCIPincludeDetectorConnected(scip) );
335  SCIP_CALL( SCIPincludeDetectorArrowheur(scip) );
336  SCIP_CALL( SCIPincludeDetectorStairheur(scip) );
337  SCIP_CALL( SCIPincludeDetectorStaircase(scip) );
338  SCIP_CALL( SCIPincludeDetectorRandom(scip) );
339  SCIP_CALL( SCIPincludeDetectorColors(scip) );
340  SCIP_CALL( SCIPincludeDetectorCutpacking(scip) );
341 
342 
343 #ifndef NBLISS
344  SCIP_CALL( SCIPincludeDetectorIsomorphism(scip) );
345 #endif
346 
347  /* Christian's heuristics */
348  SCIP_CALL( SCIPincludeEventHdlrOrigdiving(scip) );
349  SCIP_CALL( GCGincludeHeurGcgcoefdiving(scip) );
350  SCIP_CALL( GCGincludeHeurGcgfracdiving(scip) );
351  SCIP_CALL( GCGincludeHeurGcgguideddiving(scip) );
352  SCIP_CALL( GCGincludeHeurGcglinesdiving(scip) );
353  SCIP_CALL( GCGincludeHeurGcgpscostdiving(scip) );
354  SCIP_CALL( GCGincludeHeurGcgveclendiving(scip) );
355  SCIP_CALL( SCIPincludeHeurGcgdins(scip) );
356  SCIP_CALL( SCIPincludeHeurGcgfeaspump(scip) );
357  SCIP_CALL( SCIPincludeHeurGcgrens(scip) );
358  SCIP_CALL( SCIPincludeHeurGcgrins(scip) );
359  SCIP_CALL( SCIPincludeHeurGcgrounding(scip) );
360  SCIP_CALL( SCIPincludeHeurGcgshifting(scip) );
361  SCIP_CALL( SCIPincludeHeurGcgsimplerounding(scip) );
362  SCIP_CALL( SCIPincludeHeurGcgzirounding(scip) );
363  SCIP_CALL( SCIPincludeHeurXpcrossover(scip) );
364  SCIP_CALL( SCIPincludeHeurXprins(scip) );
365 
366  /* Jonas' stuff */
367  SCIP_CALL( SCIPsetSeparating(scip, SCIP_PARAMSETTING_OFF, TRUE) );
368 
369  SCIP_CALL( SCIPincludeDispGcg(scip) );
370  SCIP_CALL( SCIPincludeDialogGcg(scip) );
371  SCIP_CALL( GCGincludeDialogsGraph(scip) );
372 
373  return SCIP_OKAY;
374 }
SCIP_RETCODE SCIPincludeConshdlrOrigbranch(SCIP *scip)
arrowhead and bordered detector via graph partitioning (uses hmetis)
SCIP_RETCODE SCIPincludeHeurXpcrossover(SCIP *scip)
random detector
SCIP_RETCODE SCIPincludeDetectorStairheur(SCIP *scip)
staircase compontent detector
SCIP_RETCODE SCIPincludeHeurGcgshifting(SCIP *scip)
branching rule for original problem in GCG while real branching is in the master
LNS heuristic that combines the incumbent with the LP optimum.
SCIP_RETCODE SCIPincludeGcgPlugins(SCIP *scip)
Definition: gcgplugins.c:209
SCIP_RETCODE SCIPincludeEventHdlrOrigdiving(SCIP *scip)
SCIP_RETCODE GCGincludeHeurGcgfracdiving(SCIP *scip)
SCIP_RETCODE SCIPincludeEventHdlrMastersol(SCIP *scip)
SCIP_RETCODE SCIPincludeBranchruleEmpty(SCIP *scip)
Definition: branch_empty.c:365
detector for pricing problems that can be aggregated (uses bliss)
SCIP_RETCODE SCIPincludeHeurGcgrounding(SCIP *scip)
SCIP_RETCODE GCGincludeHeurGcgguideddiving(SCIP *scip)
LP diving heuristic that chooses fixings in direction of incumbent solutions.
SCIP plugins for generic column generation.
GCG display columns.
SCIP_RETCODE SCIPincludeHeurGcgfeaspump(SCIP *scip)
zirounding primal heuristic
LP gcgrounding heuristic that tries to recover from intermediate infeasibilities. ...
DEC file reader for structure information.
SCIP_RETCODE SCIPincludeDetectorConnected(SCIP *scip)
SCIP_RETCODE GCGincludeHeurGcgveclendiving(SCIP *scip)
LP diving heuristic that chooses fixings w.r.t. the matrix coefficients.
connected compontent detector
LP diving heuristic that fixes variables with a large difference to their root solution.
detector for staircase structures via ROC algorithms
GP file reader writing gnuplot files.
BLK file reader for structure information.
Objective Feasibility Pump 2.0.
SCIP_RETCODE SCIPincludeHeurGcgrens(SCIP *scip)
Definition: heur_gcgrens.c:813
SCIP_RETCODE SCIPincludeHeurGcgzirounding(SCIP *scip)
various SCIP helper methods
LP diving heuristic that chooses fixings w.r.t. the pseudo cost values.
SCIP_RETCODE SCIPincludeHeurGcgrins(SCIP *scip)
Definition: heur_gcgrins.c:737
SCIP_RETCODE SCIPincludeConshdlrDecomp(SCIP *scip)
Definition: cons_decomp.c:251
SCIP_RETCODE SCIPincludeDetectorStaircase(SCIP *scip)
GCG relaxator.
SCIP_RETCODE SCIPincludeDetectorRandom(SCIP *scip)
Definition: dec_random.c:253
SCIP_RETCODE SCIPincludeRelaxGcg(SCIP *scip)
Definition: relax_gcg.c:2445
SCIP_RETCODE SCIPincludeDetectorCutpacking(SCIP *scip)
SCIP_RETCODE SCIPincludeEventHdlrBestsol(SCIP *scip)
GCG variable pricer.
staircase detector via recursive partitioning (uses hmetis)
SCIP_RETCODE SCIPincludeReaderRef(SCIP *scip)
Definition: reader_ref.c:760
DINS primal heuristic.
SCIP_RETCODE SCIPincludeDetectorIsomorphism(SCIP *scip)
eventhdlr to record the best primal bound for each heuristic
LP gcgrounding heuristic that tries to recover from intermediate infeasibilities and shifts continuou...
primal heuristic interface for LP diving heuristics on the original variables
SCIP_RETCODE SCIPincludeReaderGp(SCIP *scip)
Definition: reader_gp.c:397
SCIP_RETCODE SCIPincludeReaderDec(SCIP *scip)
Definition: reader_dec.c:934
LP diving heuristic that chooses fixings w.r.t. the fractionalities.
SCIP_RETCODE SCIPincludeHeurGcgdins(SCIP *scip)
SCIP_RETCODE SCIPincludeReaderBlk(SCIP *scip)
Definition: reader_blk.c:1102
SCIP_RETCODE SCIPincludeDispGcg(SCIP *scip)
Definition: disp_gcg.c:1226
REF file reader for structure information.
SCIP_RETCODE GCGincludeHeurGcgpscostdiving(SCIP *scip)
SCIP_RETCODE GCGincludeHeurGcgcoefdiving(SCIP *scip)
detector assigning color classes to constraints and try combinations of colors in the master ...
SCIP_RETCODE SCIPincludeDialogGcg(SCIP *scip)
Definition: dialog_gcg.c:647
SCIP_RETCODE SCIPincludeHeurXprins(SCIP *scip)
Definition: heur_xprins.c:1575
LP diving heuristic that rounds variables with long column vectors.
constraint handler for storing the branching decisions at each node of the tree
simple and fast LP rounding heuristic
SCIP_RETCODE SCIPincludeDetectorArrowheur(SCIP *scip)
SCIP_RETCODE GCGincludeDialogsGraph(SCIP *scip)
Extreme Point Crossover.
eventhdlr to transfer solutions found in the original problem to the master problem ...
GCG user interface dialog.
constraint handler for structure detection
LNS heuristic that finds the optimal rounding to a given point.
SCIP_RETCODE GCGincludeHeurGcglinesdiving(SCIP *scip)
SCIP_RETCODE SCIPincludeDetectorColors(SCIP *scip)
Definition: dec_colors.cpp:430
Extreme Point RINS.
SCIP_RETCODE SCIPincludeHeurGcgsimplerounding(SCIP *scip)