Scippy

SCIP

Solving Constraint Integer Programs

scip_validation.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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip_validation.c
17  * @brief public methods for validation
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Gerald Gamrath
21  * @author Robert Lion Gottwald
22  * @author Stefan Heinz
23  * @author Gregor Hendel
24  * @author Thorsten Koch
25  * @author Alexander Martin
26  * @author Marc Pfetsch
27  * @author Michael Winkler
28  * @author Kati Wolter
29  *
30  * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc.h"
37 #include "scip/scip_general.h"
38 #include "scip/scip_message.h"
39 #include "scip/scip_numerics.h"
40 #include "scip/scip_param.h"
41 #include "scip/scip_prob.h"
42 #include "scip/scip_sol.h"
43 #include "scip/scip_solvingstats.h"
44 #include "scip/scip_validation.h"
45 
46 /** validate the result of the solve
47  *
48  * the validation includes
49  *
50  * - checking the feasibility of the incumbent solution in the original problem (using SCIPcheckSolOrig())
51  *
52  * - checking if the objective bounds computed by SCIP agree with external primal and dual reference bounds.
53  *
54  * All external reference bounds the original problem space and the original objective sense.
55  *
56  * For infeasible problems, +/-SCIPinfinity() should be passed as reference bounds depending on the objective sense
57  * of the original problem.
58  */
60  SCIP* scip, /**< SCIP data structure */
61  SCIP_Real primalreference, /**< external primal reference value for the problem, or SCIP_UNKNOWN */
62  SCIP_Real dualreference, /**< external dual reference value for the problem, or SCIP_UNKNOWN */
63  SCIP_Real reftol, /**< relative tolerance for acceptable violation of reference values */
64  SCIP_Bool quiet, /**< TRUE if no status line should be printed */
65  SCIP_Bool* feasible, /**< pointer to store if the best solution is feasible in the original problem,
66  * or NULL */
67  SCIP_Bool* primalboundcheck, /**< pointer to store if the primal bound respects the given dual reference
68  * value, or NULL */
69  SCIP_Bool* dualboundcheck /**< pointer to store if the dual bound respects the given primal reference
70  * value, or NULL */
71  )
72 {
73  SCIP_Bool localfeasible;
74  SCIP_Bool localprimalboundcheck;
75  SCIP_Bool localdualboundcheck;
76  SCIP_Real primviol;
77  SCIP_Real dualviol;
78  assert(scip != NULL);
79 
80  /* if no problem exists, there is no need for validation */
81  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
82  {
83  if( feasible != NULL )
84  *feasible = TRUE;
85  if( primalboundcheck != NULL )
86  *primalboundcheck = TRUE;
87  if( dualboundcheck != NULL )
88  *dualboundcheck = TRUE;
89 
90  return SCIP_OKAY;
91  }
92 
93  localfeasible = TRUE;
94  localdualboundcheck = TRUE;
95 
96  /* check the best solution for feasibility in the original problem */
97  if( SCIPgetNSols(scip) > 0 )
98  {
99  SCIP_SOL* bestsol = SCIPgetBestSol(scip);
100  SCIP_Real checkfeastolfac;
101  SCIP_Real oldfeastol;
102 
103  assert(bestsol != NULL);
104 
105  /* scale feasibility tolerance by set->num_checkfeastolfac */
106  oldfeastol = SCIPfeastol(scip);
107  SCIP_CALL( SCIPgetRealParam(scip, "numerics/checkfeastolfac", &checkfeastolfac) );
108  if( !SCIPisEQ(scip, checkfeastolfac, 1.0) )
109  {
110  SCIP_CALL( SCIPchgFeastol(scip, oldfeastol * checkfeastolfac) );
111  }
112 
113  SCIP_CALL( SCIPcheckSolOrig(scip, bestsol, &localfeasible, !quiet, TRUE) );
114 
115  /* restore old feasibilty tolerance */
116  if( !SCIPisEQ(scip, checkfeastolfac, 1.0) )
117  {
118  SCIP_CALL( SCIPchgFeastol(scip, oldfeastol) );
119  }
120  }
121  else
122  {
123  localfeasible = TRUE;
124  }
125 
126  primviol = 0.0;
127  dualviol = 0.0;
128  /* check the primal and dual bounds computed by SCIP against the external reference values within reference tolerance */
129  /* solution for an infeasible problem */
130  if( SCIPgetNSols(scip) > 0 && ((SCIPgetObjsense(scip) == SCIP_OBJSENSE_MINIMIZE && SCIPisInfinity(scip, dualreference))
131  || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE && SCIPisInfinity(scip, -dualreference))) )
132  localprimalboundcheck = FALSE;
133  else
134  {
135  /* check if reference primal bound is not better than the proven dual bound and, if SCIP claims to be optimal,
136  * if the
137  */
138  SCIP_Real pb = SCIPgetPrimalbound(scip);
139  SCIP_Real db = SCIPgetDualbound(scip);
140 
141  /* compute the relative violation between the primal bound and dual reference value, and vice versa */
143  {
144  if( dualreference != SCIP_UNKNOWN ) /*lint !e777 */
145  primviol = SCIPrelDiff(dualreference, pb);
146  if( primalreference != SCIP_UNKNOWN ) /*lint !e777 */
147  dualviol = SCIPrelDiff(db, primalreference);
148  }
149  else
150  {
151  if( dualreference != SCIP_UNKNOWN ) /*lint !e777 */
152  primviol = SCIPrelDiff(pb, dualreference);
153 
154  if( primalreference != SCIP_UNKNOWN ) /*lint !e777 */
155  dualviol = SCIPrelDiff(primalreference, db);
156  }
157  primviol = MAX(primviol, 0.0);
158  dualviol = MAX(dualviol, 0.0);
159 
160  localprimalboundcheck = EPSP(reftol, primviol);
161  localdualboundcheck = EPSP(reftol, dualviol);
162  }
163 
164  if( !quiet )
165  {
166  SCIPinfoMessage(scip, NULL, "Validation : ");
167  if( ! localfeasible )
168  SCIPinfoMessage(scip, NULL, "Fail (infeasible)");
169  else if( ! localprimalboundcheck )
170  SCIPinfoMessage(scip, NULL, "Fail (primal bound)");
171  else if( ! localdualboundcheck )
172  SCIPinfoMessage(scip, NULL, "Fail (dual bound)");
173  else
174  SCIPinfoMessage(scip, NULL, "Success");
175  SCIPinfoMessage(scip, NULL, "\n");
176  SCIPinfoMessage(scip, NULL, " %-17s: %10u\n", "cons violation", !localfeasible);
177  SCIPinfoMessage(scip, NULL, " %-17s: %10.8g (reference: %16.9e)\n", "primal violation", primviol, dualreference);
178  SCIPinfoMessage(scip, NULL, " %-17s: %10.8g (reference: %16.9e)\n", "dual violation", dualviol, primalreference);
179  }
180 
181  if( feasible != NULL )
182  *feasible = localfeasible;
183  if( primalboundcheck != NULL )
184  *primalboundcheck = localprimalboundcheck;
185  if( dualboundcheck != NULL )
186  *dualboundcheck = localdualboundcheck;
187 
188  return SCIP_OKAY;
189 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeastol(SCIP *scip)
#define NULL
Definition: def.h:253
SCIP_RETCODE SCIPvalidateSolve(SCIP *scip, SCIP_Real primalreference, SCIP_Real dualreference, SCIP_Real reftol, SCIP_Bool quiet, SCIP_Bool *feasible, SCIP_Bool *primalboundcheck, SCIP_Bool *dualboundcheck)
public methods for SCIP parameter handling
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define EPSP(x, eps)
Definition: def.h:195
public methods for validation
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10571
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1224
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:297
#define SCIP_UNKNOWN
Definition: def.h:185
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3460
general public methods
#define MAX(x, y)
Definition: def.h:222
public methods for solutions
public methods for message output
#define SCIP_Real
Definition: def.h:164
public methods for message handling
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:198
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
SCIP_RETCODE SCIPchgFeastol(SCIP *scip, SCIP_Real feastol)
public methods for global and local (sub)problems
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304