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