Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_mastervecldiving.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 heur_mastervecldiving.c
29  * @brief master LP diving heuristic that rounds variables with long column vectors
30  * @author Tobias Achterberg
31  * @author Christian Puchert
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "heur_mastervecldiving.h"
40 #include "heur_masterdiving.h"
41 
42 
43 #define HEUR_NAME "mastervecldiving"
44 #define HEUR_DESC "master LP diving heuristic that rounds variables with long column vectors"
45 #define HEUR_DISPCHAR 'v'
46 #define HEUR_PRIORITY -1003100
47 #define HEUR_FREQ 10
48 #define HEUR_FREQOFS 4
49 #define HEUR_MAXDEPTH -1
50 
51 
52 /*
53  * Callback methods
54  */
55 
56 
57 /** variable selection method of diving heuristic;
58  * finds best candidate variable w.r.t. vector length:
59  * - round variables in direction where objective value gets worse; for zero objective coefficient, round upwards
60  * - round variable with least objective value deficit per row the variable appears in
61  * (we want to "fix" as many rows as possible with the least damage to the objective function)
62  */
63 static
64 GCG_DECL_DIVINGSELECTVAR(heurSelectVarMastervecldiving) /*lint --e{715}*/
65 { /*lint --e{715}*/
66  SCIP_VAR** lpcands;
67  SCIP_Real* lpcandssol;
68  SCIP_Real* lpcandsfrac;
69  int nlpcands;
70  SCIP_Real bestscore;
71  int c;
72 
73  /* check preconditions */
74  assert(scip != NULL);
75  assert(heur != NULL);
76  assert(bestcand != NULL);
77  assert(bestcandmayround != NULL);
78 
79  /* get fractional variables that should be integral */
80  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
81  assert(lpcands != NULL);
82  assert(lpcandsfrac != NULL);
83  assert(lpcandssol != NULL);
84 
85  *bestcandmayround = TRUE;
86  bestscore = SCIP_REAL_MAX;
87 
88  /* get best candidate */
89  for( c = 0; c < nlpcands; ++c )
90  {
91  SCIP_VAR* var;
92 
93  SCIP_Real obj;
94  SCIP_Real objdelta;
95  SCIP_Real frac;
96  SCIP_Real score;
97  int colveclen;
98 
99  int i;
100 
101  var = lpcands[c];
102 
103  /* if the variable is on the tabu list, do not choose it */
104  for( i = 0; i < tabulistsize; ++i )
105  if( tabulist[i] == var )
106  break;
107  if( i < tabulistsize )
108  continue;
109 
110  frac = lpcandsfrac[c];
111  obj = SCIPvarGetObj(var);
112  objdelta = (1.0 - frac) * obj;
113 
114  colveclen = (SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(var)) : 0);
115 
116  /* check whether the variable is roundable */
117  *bestcandmayround = *bestcandmayround && (SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var));
118 
119  /* smaller score is better */
120  score = (objdelta + SCIPsumepsilon(scip))/((SCIP_Real)colveclen+1.0);
121 
122  /* penalize negative scores (i.e. improvements in the objective) */
123  if( score <= 0.0 )
124  score *= 100.0;
125 
126  /* prefer decisions on binary variables */
127  if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
128  score *= 1000.0;
129 
130  /* check, if candidate is new best candidate */
131  if( score < bestscore )
132  {
133  *bestcand = var;
134  bestscore = score;
135  }
136  }
137 
138  return SCIP_OKAY;
139 }
140 
141 
142 /*
143  * heuristic specific interface methods
144  */
145 
146 /** creates the mastervecldiving heuristic and includes it in GCG */
148  SCIP* scip /**< SCIP data structure */
149  )
150 {
151  SCIP_HEUR* heur;
152 
153  /* include diving heuristic */
154  SCIP_CALL( GCGincludeDivingHeurMaster(scip, &heur,
156  HEUR_MAXDEPTH, NULL, NULL, NULL, NULL, NULL, NULL, NULL, heurSelectVarMastervecldiving, NULL) );
157 
158  assert(heur != NULL);
159 
160  return SCIP_OKAY;
161 }
162 
master LP diving heuristic that rounds variables with long column vectors
#define HEUR_DESC
#define HEUR_MAXDEPTH
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarMastervecldiving)
#define HEUR_FREQ
#define HEUR_DISPCHAR
#define HEUR_FREQOFS
primal heuristic interface for LP diving heuristics on the master variables
#define HEUR_NAME
#define HEUR_PRIORITY
SCIP_RETCODE GCGincludeHeurMastervecldiving(SCIP *scip)
SCIP_RETCODE GCGincludeDivingHeurMaster(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, GCG_DECL_DIVINGFREE((*divingfree)), GCG_DECL_DIVINGINIT((*divinginit)), GCG_DECL_DIVINGEXIT((*divingexit)), GCG_DECL_DIVINGINITSOL((*divinginitsol)), GCG_DECL_DIVINGEXITSOL((*divingexitsol)), GCG_DECL_DIVINGINITEXEC((*divinginitexec)), GCG_DECL_DIVINGEXITEXEC((*divingexitexec)), GCG_DECL_DIVINGSELECTVAR((*divingselectvar)), GCG_DIVINGDATA *divingdata)