Scippy

SCIP

Solving Constraint Integer Programs

relax_lp.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file relax_lp.c
17  * @brief lp relaxator
18  * @author Benjamin Mueller
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "relax_lp.h"
27 
28 #define RELAX_NAME "lp"
29 #define RELAX_DESC "relaxator solving LP relaxation"
30 #define RELAX_PRIORITY 0
31 #define RELAX_FREQ 0
32 
33 
34 /*
35  * Data structures
36  */
37 
38 
39 /*
40  * Local methods
41  */
42 
43 
44 /*
45  * Callback methods of relaxator
46  */
47 
48 /** execution method of relaxator */
49 static
50 SCIP_DECL_RELAXEXEC(relaxExecLp)
51 { /*lint --e{715}*/
52  SCIP* relaxscip;
53  SCIP_HASHMAP* varmap;
54  SCIP_CONS** conss;
55  SCIP_Real relaxval;
56  SCIP_Bool valid;
57  int nconss;
58  int i;
59  int c;
60 
61  *lowerbound = -SCIPinfinity(scip);
62  *result = SCIP_DIDNOTRUN;
63 
64  /* we can only run if none of the present constraints expect their variables to be binary or integer during transformation */
65  conss = SCIPgetConss(scip);
66  nconss = SCIPgetNConss(scip);
67 
68  for( c = 0; c < nconss; ++c )
69  {
70  const char* conshdlrname;
71 
72  conshdlrname = SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c]));
73 
74  /* skip if there are any "and", "linking", or", "orbitope", "pseudoboolean", "superindicator", "xor" or new/unknown constraints */
75  if( strcmp(conshdlrname, "SOS1") != 0 && strcmp(conshdlrname, "SOS2") != 0 && strcmp(conshdlrname, "abspower") != 0
76  && strcmp(conshdlrname, "bivariate") != 0 && strcmp(conshdlrname, "bounddisjunction") != 0
77  && strcmp(conshdlrname, "cardinality") != 0 && strcmp(conshdlrname, "components") != 0
78  && strcmp(conshdlrname, "conjunction") != 0 && strcmp(conshdlrname, "countsols") != 0
79  && strcmp(conshdlrname, "cumulative") != 0 && strcmp(conshdlrname, "disjunction") != 0
80  && strcmp(conshdlrname, "indicator") != 0 && strcmp(conshdlrname, "integral") != 0
81  && strcmp(conshdlrname, "knapsack") != 0 && strcmp(conshdlrname, "linear") != 0
82  && strcmp(conshdlrname, "logicor") != 0 && strcmp(conshdlrname, "nonlinear") != 0
83  && strcmp(conshdlrname, "orbisack") != 0 && strcmp(conshdlrname, "quadratic") != 0
84  && strcmp(conshdlrname, "setppc") != 0 && strcmp(conshdlrname, "soc") != 0
85  && strcmp(conshdlrname, "symresack") != 0 && strcmp(conshdlrname, "varbound") != 0 )
86  return SCIP_OKAY;
87  }
88 
89  /* create the variable mapping hash map */
90  SCIP_CALL( SCIPcreate(&relaxscip) );
91  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(relaxscip), SCIPgetNVars(scip)) );
92  valid = FALSE;
93  SCIP_CALL( SCIPcopy(scip, relaxscip, varmap, NULL, "relaxscip", FALSE, FALSE, FALSE, &valid) );
94 
95  /* change variable types */
96  for( i = 0; i < SCIPgetNVars(relaxscip); ++i )
97  {
98  SCIP_VAR* var;
99  SCIP_Bool infeasible;
100 
101  var = SCIPgetVars(relaxscip)[i];
102  assert(var != NULL);
103 
104  SCIP_CALL( SCIPchgVarType(relaxscip, var, SCIP_VARTYPE_CONTINUOUS, &infeasible) );
105  assert(!infeasible);
106  }
107 
108  SCIPsetMessagehdlrQuiet(relaxscip, TRUE);
109  SCIP_CALL( SCIPtransformProb(relaxscip) );
110  SCIP_CALL( SCIPsolve(relaxscip) );
111  relaxval = SCIPgetPrimalbound(relaxscip);
112  SCIPdebugMessage("relaxation bound = %e status = %d\n", relaxval, SCIPgetStatus(relaxscip));
113 
114  if( SCIPgetStatus(relaxscip) == SCIP_STATUS_OPTIMAL )
115  {
116  /* store relaxation solution in original SCIP if it improves the best relaxation solution thus far */
117  if( (! SCIPisRelaxSolValid(scip)) || SCIPisGT(scip, relaxval, SCIPgetRelaxSolObj(scip)) )
118  {
119  SCIPdebugMsg(scip, "Setting LP relaxation solution, which improved upon earlier solution\n");
121 
122  for( i = 0; i < SCIPgetNVars(scip); ++i )
123  {
124  SCIP_VAR* relaxvar;
125  SCIP_Real solval;
126 
127  relaxvar = SCIPhashmapGetImage(varmap, SCIPgetVars(scip)[i]);
128  assert(relaxvar != NULL);
129 
130  solval = SCIPgetSolVal(relaxscip, SCIPgetBestSol(relaxscip), relaxvar);
131 
133  }
134 
135  /* mark relaxation solution to be valid and inform SCIP that the relaxation included all LP rows */
137  }
138 
139  SCIPdebugMsg(scip, "LP lower bound = %g\n", relaxval);
140  *lowerbound = relaxval;
141  *result = SCIP_SUCCESS;
142  }
143 
144  /* free memory */
145  SCIPhashmapFree(&varmap);
146  SCIP_CALL( SCIPfree(&relaxscip) );
147 
148  return SCIP_OKAY;
149 }
150 
151 
152 /*
153  * relaxator specific interface methods
154  */
155 
156 /** creates the lp relaxator and includes it in SCIP */
158  SCIP* scip /**< SCIP data structure */
159  )
160 {
161  SCIP_RELAXDATA* relaxdata;
162  SCIP_RELAX* relax;
163 
164  /* create lp relaxator data */
165  relaxdata = NULL;
166  relax = NULL;
167 
168  /* include relaxator */
170  relaxExecLp, relaxdata) );
171  assert(relax != NULL);
172 
173  return SCIP_OKAY;
174 }
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip, SCIP_Bool includeslp)
Definition: scip.c:20072
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
Definition: scip.c:43402
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPincludeRelaxBasic(SCIP *scip, SCIP_RELAX **relaxptr, const char *name, const char *desc, int priority, int freq, SCIP_DECL_RELAXEXEC((*relaxexec)), SCIP_RELAXDATA *relaxdata)
Definition: scip.c:7148
SCIP_RETCODE SCIPincludeRelaxLp(SCIP *scip)
Definition: relax_lp.c:157
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47028
static SCIP_DECL_RELAXEXEC(relaxExecLp)
Definition: relax_lp.c:50
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPclearRelaxSolVals(SCIP *scip)
Definition: scip.c:19889
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip.c:20145
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip.c:12908
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:748
#define SCIPdebugMsg
Definition: scip.h:455
#define RELAX_FREQ
Definition: relax_lp.c:31
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip.c:25479
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:16115
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:928
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46731
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
lp relaxator
#define SCIP_CALL(x)
Definition: def.h:350
#define SCIP_Bool
Definition: def.h:61
void SCIPsetMessagehdlrQuiet(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:1255
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8006
#define RELAX_NAME
Definition: relax_lp.c:28
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11812
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:19935
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39882
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:38
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47002
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12862
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip.c:20052
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3795
#define RELAX_DESC
Definition: relax_lp.c:29
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11767
#define SCIP_Real
Definition: def.h:149
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13935
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38911
#define RELAX_PRIORITY
Definition: relax_lp.c:30
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:780