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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file relax_lp.c
26  * @brief lp relaxator
27  * @author Benjamin Mueller
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include <assert.h>
33 #include <string.h>
34 
35 #include "relax_lp.h"
36 
37 #define RELAX_NAME "lp"
38 #define RELAX_DESC "relaxator solving LP relaxation"
39 #define RELAX_PRIORITY 0
40 #define RELAX_FREQ 0
41 
42 
43 /*
44  * Data structures
45  */
46 
47 
48 /*
49  * Local methods
50  */
51 
52 
53 /*
54  * Callback methods of relaxator
55  */
56 
57 /** execution method of relaxator */
58 static
59 SCIP_DECL_RELAXEXEC(relaxExecLp)
60 { /*lint --e{715}*/
61  SCIP* relaxscip;
62  SCIP_HASHMAP* varmap;
63  SCIP_CONS** conss;
64  SCIP_Real relaxval;
65  SCIP_Bool valid;
66  int nconss;
67  int i;
68  int c;
69 
70  *lowerbound = -SCIPinfinity(scip);
71  *result = SCIP_DIDNOTRUN;
72 
73  /* we can only run if none of the present constraints expect their variables to be binary or integer during transformation */
74  conss = SCIPgetConss(scip);
75  nconss = SCIPgetNConss(scip);
76 
77  for( c = 0; c < nconss; ++c )
78  {
79  const char* conshdlrname;
80 
81  conshdlrname = SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c]));
82 
83  /* skip if there are any "and", "linking", or", "orbitope", "pseudoboolean", "superindicator", "xor" or new/unknown constraints */
84  if( strcmp(conshdlrname, "SOS1") != 0 && strcmp(conshdlrname, "SOS2") != 0
85  && strcmp(conshdlrname, "bounddisjunction") != 0
86  && strcmp(conshdlrname, "cardinality") != 0 && strcmp(conshdlrname, "components") != 0
87  && strcmp(conshdlrname, "conjunction") != 0 && strcmp(conshdlrname, "countsols") != 0
88  && strcmp(conshdlrname, "cumulative") != 0 && strcmp(conshdlrname, "disjunction") != 0
89  && strcmp(conshdlrname, "indicator") != 0 && strcmp(conshdlrname, "integral") != 0
90  && strcmp(conshdlrname, "knapsack") != 0 && strcmp(conshdlrname, "linear") != 0
91  && strcmp(conshdlrname, "logicor") != 0 && strcmp(conshdlrname, "nonlinear") != 0
92  && strcmp(conshdlrname, "orbisack") != 0
93  && strcmp(conshdlrname, "setppc") != 0
94  && strcmp(conshdlrname, "symresack") != 0 && strcmp(conshdlrname, "varbound") != 0 )
95  return SCIP_OKAY;
96  }
97 
98  /* create the variable mapping hash map */
99  SCIP_CALL( SCIPcreate(&relaxscip) );
100  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(relaxscip), SCIPgetNVars(scip)) );
101  valid = FALSE;
102  SCIP_CALL( SCIPcopy(scip, relaxscip, varmap, NULL, "relaxscip", FALSE, FALSE, FALSE, FALSE, &valid) );
103 
104  /* change variable types */
105  for( i = 0; i < SCIPgetNVars(relaxscip); ++i )
106  {
107  SCIP_VAR* var;
108  SCIP_Bool infeasible;
109 
110  var = SCIPgetVars(relaxscip)[i];
111  assert(var != NULL);
112 
113  SCIP_CALL( SCIPchgVarType(relaxscip, var, SCIP_VARTYPE_CONTINUOUS, &infeasible) );
114  assert(!infeasible);
115  }
116 
117  SCIPsetMessagehdlrQuiet(relaxscip, TRUE);
118  SCIP_CALL( SCIPtransformProb(relaxscip) );
119  SCIP_CALL( SCIPsolve(relaxscip) );
120  relaxval = SCIPgetPrimalbound(relaxscip);
121  SCIPdebugMessage("relaxation bound = %e status = %d\n", relaxval, SCIPgetStatus(relaxscip));
122 
123  if( SCIPgetStatus(relaxscip) == SCIP_STATUS_OPTIMAL )
124  {
125  /* store relaxation solution in original SCIP if it improves the best relaxation solution thus far */
126  if( (! SCIPisRelaxSolValid(scip)) || SCIPisGT(scip, relaxval, SCIPgetRelaxSolObj(scip)) )
127  {
128  SCIPdebugMsg(scip, "Setting LP relaxation solution, which improved upon earlier solution\n");
130 
131  for( i = 0; i < SCIPgetNVars(scip); ++i )
132  {
133  SCIP_VAR* relaxvar;
134  SCIP_Real solval;
135 
136  /* skip relaxation-only variables: they don't appear in relaxation (and don't need to) */
138  continue;
139 
140  relaxvar = SCIPhashmapGetImage(varmap, SCIPgetVars(scip)[i]);
141  assert(relaxvar != NULL);
142 
143  solval = SCIPgetSolVal(relaxscip, SCIPgetBestSol(relaxscip), relaxvar);
144 
145  SCIP_CALL( SCIPsetRelaxSolVal(scip, relax, SCIPgetVars(scip)[i], solval) );
146  }
147 
148  /* mark relaxation solution to be valid and inform SCIP that the relaxation included all LP rows */
150  }
151 
152  SCIPdebugMsg(scip, "LP lower bound = %g\n", relaxval);
153  *lowerbound = relaxval;
154  *result = SCIP_SUCCESS;
155  }
156  else if( SCIPgetStatus(relaxscip) == SCIP_STATUS_INFEASIBLE )
157  {
158  SCIPdebugMsg(scip, "cutting off node\n");
159  *result = SCIP_CUTOFF;
160  }
161 
162  /* free memory */
163  SCIPhashmapFree(&varmap);
164  SCIP_CALL( SCIPfree(&relaxscip) );
165 
166  return SCIP_OKAY;
167 }
168 
169 
170 /*
171  * relaxator specific interface methods
172  */
173 
174 /** creates the lp relaxator and includes it in SCIP */
176  SCIP* scip /**< SCIP data structure */
177  )
178 {
179  SCIP_RELAXDATA* relaxdata;
180  SCIP_RELAX* relax;
181 
182  /* create lp relaxator data */
183  relaxdata = NULL;
184  relax = NULL;
185 
186  /* include relaxator */
188  relaxExecLp, relaxdata) );
189  assert(relax != NULL);
190 
191  return SCIP_OKAY;
192 }
#define NULL
Definition: def.h:267
SCIP_RETCODE SCIPclearRelaxSolVals(SCIP *scip, SCIP_RELAX *relax)
Definition: scip_var.c:2366
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:2875
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
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:103
SCIP_RETCODE SCIPincludeRelaxLp(SCIP *scip)
Definition: relax_lp.c:175
SCIP_Real SCIPinfinity(SCIP *scip)
static SCIP_DECL_RELAXEXEC(relaxExecLp)
Definition: relax_lp.c:59
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip_var.c:2634
#define SCIPdebugMessage
Definition: pub_message.h:96
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3088
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
#define SCIPdebugMsg
Definition: scip_message.h:78
#define RELAX_FREQ
Definition: relax_lp.c:40
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8178
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2488
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_RELAX *relax, SCIP_VAR *var, SCIP_Real val)
Definition: scip_var.c:2416
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
lp relaxator
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17707
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip, SCIP_RELAX *relax, SCIP_Bool includeslp)
Definition: scip_var.c:2559
void SCIPsetMessagehdlrQuiet(SCIP *scip, SCIP_Bool quiet)
Definition: scip_message.c:108
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8236
#define RELAX_NAME
Definition: relax_lp.c:37
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:47
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip_var.c:2539
#define RELAX_DESC
Definition: relax_lp.c:38
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
#define SCIP_Real
Definition: def.h:173
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
#define RELAX_PRIORITY
Definition: relax_lp.c:39
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339