Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_mastercoefdiving.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_mastercoefdiving.c
29  * @brief master LP diving heuristic that chooses fixings w.r.t. the matrix coefficients
30  * @author Tobias Achterberg
31  * @author Marc Pfetsch
32  * @author Christian Puchert
33  */
34 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 
37 #include <assert.h>
38 #include <string.h>
39 
40 #include "heur_mastercoefdiving.h"
41 #include "heur_masterdiving.h"
42 
43 
44 #define HEUR_NAME "mastercoefdiving"
45 #define HEUR_DESC "master LP diving heuristic that chooses fixings w.r.t. the matrix coefficients"
46 #define HEUR_DISPCHAR 'c'
47 #define HEUR_PRIORITY -1001000
48 #define HEUR_FREQ 10
49 #define HEUR_FREQOFS 1
50 #define HEUR_MAXDEPTH -1
51 
52 
53 /*
54  * Callback methods
55  */
56 
57 /** variable selection method of diving heuristic;
58  * finds best candidate variable w.r.t. locking numbers:
59  * - prefer variables that may not be rounded without destroying LP feasibility:
60  * - of these variables, round variable with least number of locks in corresponding direction
61  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
62  * - round variable with least number of locks in opposite of its feasible rounding direction
63  * - binary variables are preferred
64  */
65 static
66 GCG_DECL_DIVINGSELECTVAR(heurSelectVarMastercoefdiving) /*lint --e{715}*/
67 { /*lint --e{715}*/
68  SCIP_VAR** lpcands;
69  SCIP_Real* lpcandssol;
70  SCIP_Real* lpcandsfrac;
71  int nlpcands;
72  SCIP_Bool bestcandmayrounddown;
73  SCIP_Bool bestcandmayroundup;
74  int bestnviolrows; /* number of violated rows for best candidate */
75  SCIP_Real bestcandfrac; /* fractionality of best candidate */
76  int c;
77 
78  /* check preconditions */
79  assert(scip != NULL);
80  assert(heur != NULL);
81  assert(bestcand != NULL);
82  assert(bestcandmayround != NULL);
83 
84  /* get fractional variables that should be integral */
85  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
86  assert(lpcands != NULL);
87  assert(lpcandsfrac != NULL);
88  assert(lpcandssol != NULL);
89 
90  bestcandmayrounddown = TRUE;
91  bestcandmayroundup = TRUE;
92  bestnviolrows = INT_MAX;
93  bestcandfrac = SCIP_INVALID;
94 
95  /* get best candidate */
96  for( c = 0; c < nlpcands; ++c )
97  {
98  SCIP_VAR* var;
99 
100  int nviolrows;
101 
102  SCIP_Bool mayrounddown;
103  SCIP_Bool mayroundup;
104  SCIP_Real frac;
105 
106  int i;
107 
108  var = lpcands[c];
109  mayrounddown = SCIPvarMayRoundDown(var);
110  mayroundup = SCIPvarMayRoundUp(var);
111  frac = lpcandsfrac[c];
112 
113  /* if the variable is on the tabu list, do not choose it */
114  for( i = 0; i < tabulistsize; ++i )
115  if( tabulist[i] == var )
116  break;
117  if( i < tabulistsize )
118  continue;
119 
120  if( mayrounddown || mayroundup )
121  {
122  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
123  if( bestcandmayrounddown || bestcandmayroundup )
124  {
125  frac = 1.0 - frac;
126  nviolrows = SCIPvarGetNLocksUp(var);
127 
128  /* penalize too small fractions */
129  if( frac < 0.01 )
130  nviolrows *= 100;
131 
132  /* prefer decisions on binary variables */
133  if( !SCIPvarIsBinary(var) )
134  nviolrows *= 1000;
135 
136  /* check, if candidate is new best candidate */
137  assert( (0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var) );
138  if( nviolrows + frac < bestnviolrows + bestcandfrac )
139  {
140  *bestcand = var;
141  bestnviolrows = nviolrows;
142  bestcandfrac = frac;
143  bestcandmayrounddown = mayrounddown;
144  bestcandmayroundup = mayroundup;
145  }
146  }
147  }
148  else
149  {
150  /* the candidate may not be rounded */
151  frac = 1.0 - frac;
152  nviolrows = SCIPvarGetNLocksUp(var);
153 
154  /* penalize too small fractions */
155  if( frac < 0.01 )
156  nviolrows *= 100;
157 
158  /* prefer decisions on binary variables */
159  if( !SCIPvarIsBinary(var) )
160  nviolrows *= 100;
161 
162  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
163  assert((0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var));
164  if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac )
165  {
166  *bestcand = var;
167  bestnviolrows = nviolrows;
168  bestcandfrac = frac;
169  bestcandmayrounddown = FALSE;
170  bestcandmayroundup = FALSE;
171  }
172  assert(bestcandfrac < SCIP_INVALID);
173  }
174  }
175 
176  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
177 
178  return SCIP_OKAY;
179 }
180 
181 
182 /*
183  * heuristic specific interface methods
184  */
185 
186 /** creates the mastercoefdiving heuristic and includes it in GCG */
188  SCIP* scip /**< SCIP data structure */
189  )
190 {
191  SCIP_HEUR* heur;
192 
193  /* include diving heuristic */
194  SCIP_CALL( GCGincludeDivingHeurMaster(scip, &heur,
196  HEUR_MAXDEPTH, NULL, NULL, NULL, NULL, NULL, NULL, NULL, heurSelectVarMastercoefdiving, NULL) );
197 
198  assert(heur != NULL);
199 
200  return SCIP_OKAY;
201 }
202 
#define HEUR_DISPCHAR
#define HEUR_NAME
SCIP_RETCODE GCGincludeHeurMastercoefdiving(SCIP *scip)
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_MAXDEPTH
primal heuristic interface for LP diving heuristics on the master variables
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarMastercoefdiving)
#define HEUR_FREQ
#define HEUR_PRIORITY
master LP diving heuristic that chooses fixings w.r.t. the matrix coefficients
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)