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-2022 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 visit scipopt.org. */
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
76  && 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
84  && strcmp(conshdlrname, "setppc") != 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, 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  /* skip relaxation-only variables: they don't appear in relaxation (and don't need to) */
129  continue;
130 
131  relaxvar = SCIPhashmapGetImage(varmap, SCIPgetVars(scip)[i]);
132  assert(relaxvar != NULL);
133 
134  solval = SCIPgetSolVal(relaxscip, SCIPgetBestSol(relaxscip), relaxvar);
135 
136  SCIP_CALL( SCIPsetRelaxSolVal(scip, relax, SCIPgetVars(scip)[i], solval) );
137  }
138 
139  /* mark relaxation solution to be valid and inform SCIP that the relaxation included all LP rows */
141  }
142 
143  SCIPdebugMsg(scip, "LP lower bound = %g\n", relaxval);
144  *lowerbound = relaxval;
145  *result = SCIP_SUCCESS;
146  }
147  else if( SCIPgetStatus(relaxscip) == SCIP_STATUS_INFEASIBLE )
148  {
149  SCIPdebugMsg(scip, "cutting off node\n");
150  *result = SCIP_CUTOFF;
151  }
152 
153  /* free memory */
154  SCIPhashmapFree(&varmap);
155  SCIP_CALL( SCIPfree(&relaxscip) );
156 
157  return SCIP_OKAY;
158 }
159 
160 
161 /*
162  * relaxator specific interface methods
163  */
164 
165 /** creates the lp relaxator and includes it in SCIP */
167  SCIP* scip /**< SCIP data structure */
168  )
169 {
170  SCIP_RELAXDATA* relaxdata;
171  SCIP_RELAX* relax;
172 
173  /* create lp relaxator data */
174  relaxdata = NULL;
175  relax = NULL;
176 
177  /* include relaxator */
179  relaxExecLp, relaxdata) );
180  assert(relax != NULL);
181 
182  return SCIP_OKAY;
183 }
SCIP_RETCODE SCIPclearRelaxSolVals(SCIP *scip, SCIP_RELAX *relax)
Definition: scip_var.c:2361
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2857
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
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_relax.c:94
SCIP_RETCODE SCIPincludeRelaxLp(SCIP *scip)
Definition: relax_lp.c:166
SCIP_Real SCIPinfinity(SCIP *scip)
static SCIP_DECL_RELAXEXEC(relaxExecLp)
Definition: relax_lp.c:50
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip_var.c:2629
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3086
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
#define SCIPdebugMsg
Definition: scip_message.h:69
#define RELAX_FREQ
Definition: relax_lp.c:31
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8173
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_RELAX *relax, SCIP_VAR *var, SCIP_Real val)
Definition: scip_var.c:2411
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
lp relaxator
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17538
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip, SCIP_RELAX *relax, SCIP_Bool includeslp)
Definition: scip_var.c:2554
void SCIPsetMessagehdlrQuiet(SCIP *scip, SCIP_Bool quiet)
Definition: scip_message.c:99
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
#define RELAX_NAME
Definition: relax_lp.c:28
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:38
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3040
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip_var.c:2534
#define RELAX_DESC
Definition: relax_lp.c:29
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
#define SCIP_Real
Definition: def.h:177
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:358
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
#define RELAX_PRIORITY
Definition: relax_lp.c:30
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315