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-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 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 <ctype.h>
36 #include <stdarg.h>
37 #include <assert.h>
38 #include <string.h>
39 #if defined(_WIN32) || defined(_WIN64)
40 #else
41 #include <strings.h> /*lint --e{766}*/
42 #endif
43 
44 
45 #include "lpi/lpi.h"
46 #include "nlpi/exprinterpret.h"
47 #include "nlpi/nlpi.h"
48 #include "scip/benders.h"
49 #include "scip/benderscut.h"
50 #include "scip/branch.h"
51 #include "scip/branch_nodereopt.h"
52 #include "scip/clock.h"
53 #include "scip/compr.h"
54 #include "scip/concsolver.h"
55 #include "scip/concurrent.h"
56 #include "scip/conflict.h"
57 #include "scip/conflictstore.h"
58 #include "scip/cons.h"
59 #include "scip/cons_linear.h"
60 #include "scip/cutpool.h"
61 #include "scip/cuts.h"
62 #include "scip/debug.h"
63 #include "scip/def.h"
64 #include "scip/dialog.h"
65 #include "scip/dialog_default.h"
66 #include "scip/disp.h"
67 #include "scip/event.h"
68 #include "scip/heur.h"
69 #include "scip/heur_ofins.h"
70 #include "scip/heur_reoptsols.h"
72 #include "scip/heuristics.h"
73 #include "scip/history.h"
74 #include "scip/implics.h"
75 #include "scip/interrupt.h"
76 #include "scip/lp.h"
77 #include "scip/mem.h"
78 #include "scip/message_default.h"
79 #include "scip/misc.h"
80 #include "scip/nlp.h"
81 #include "scip/nodesel.h"
82 #include "scip/paramset.h"
83 #include "scip/presol.h"
84 #include "scip/presolve.h"
85 #include "scip/pricer.h"
86 #include "scip/pricestore.h"
87 #include "scip/primal.h"
88 #include "scip/prob.h"
89 #include "scip/prop.h"
90 #include "scip/reader.h"
91 #include "scip/relax.h"
92 #include "scip/reopt.h"
93 #include "scip/retcode.h"
94 #include "scip/scipbuildflags.h"
95 #include "scip/scipcoreplugins.h"
96 #include "scip/scipgithash.h"
97 #include "scip/sepa.h"
98 #include "scip/sepastore.h"
99 #include "scip/set.h"
100 #include "scip/sol.h"
101 #include "scip/solve.h"
102 #include "scip/stat.h"
103 #include "scip/syncstore.h"
104 #include "scip/table.h"
105 #include "scip/tree.h"
106 #include "scip/var.h"
107 #include "scip/visual.h"
108 #include "xml/xml.h"
109 
110 #include "scip/scip_general.h"
111 #include "scip/scip_message.h"
112 #include "scip/scip_numerics.h"
113 #include "scip/scip_param.h"
114 #include "scip/scip_prob.h"
115 #include "scip/scip_sol.h"
116 #include "scip/scip_solvingstats.h"
117 #include "scip/scip_validation.h"
118 
119 #include "scip/pub_message.h"
120 #include "scip/pub_misc.h"
121 
122 
123 /* In debug mode, we include the SCIP's structure in scip.c, such that no one can access
124  * this structure except the interface methods in scip.c.
125  * In optimized mode, the structure is included in scip.h, because some of the methods
126  * are implemented as defines for performance reasons (e.g. the numerical comparisons)
127  */
128 #ifndef NDEBUG
129 #include "scip/struct_scip.h"
130 #endif
131 
132 /** validate the result of the solve
133  *
134  * the validation includes
135  *
136  * - checking the feasibility of the incumbent solution in the original problem (using SCIPcheckSolOrig())
137  *
138  * - checking if the objective bounds computed by SCIP agree with external primal and dual reference bounds.
139  *
140  * All external reference bounds the original problem space and the original objective sense.
141  *
142  * For infeasible problems, +/-SCIPinfinity() should be passed as reference bounds depending on the objective sense
143  * of the original problem.
144  */
146  SCIP* scip, /**< SCIP data structure */
147  SCIP_Real primalreference, /**< external primal reference value for the problem, or SCIP_UNKNOWN */
148  SCIP_Real dualreference, /**< external dual reference value for the problem, or SCIP_UNKNOWN */
149  SCIP_Real reftol, /**< relative tolerance for acceptable violation of reference values */
150  SCIP_Bool quiet, /**< TRUE if no status line should be printed */
151  SCIP_Bool* feasible, /**< pointer to store if the best solution is feasible in the original problem,
152  * or NULL */
153  SCIP_Bool* primalboundcheck, /**< pointer to store if the primal bound respects the given dual reference
154  * value, or NULL */
155  SCIP_Bool* dualboundcheck /**< pointer to store if the dual bound respects the given primal reference
156  * value, or NULL */
157  )
158 {
159  SCIP_Bool localfeasible;
160  SCIP_Bool localprimalboundcheck;
161  SCIP_Bool localdualboundcheck;
162  SCIP_Real primviol;
163  SCIP_Real dualviol;
164  assert(scip != NULL);
165 
166  /* if no problem exists, there is no need for validation */
167  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
168  {
169  if( feasible != NULL )
170  *feasible = TRUE;
171  if( primalboundcheck != NULL )
172  *primalboundcheck = TRUE;
173  if( dualboundcheck != NULL )
174  *dualboundcheck = TRUE;
175 
176  return SCIP_OKAY;
177  }
178 
179  localfeasible = TRUE;
180  localdualboundcheck = TRUE;
181 
182  /* check the best solution for feasibility in the original problem */
183  if( SCIPgetNSols(scip) > 0 )
184  {
185  SCIP_SOL* bestsol = SCIPgetBestSol(scip);
186  SCIP_Real checkfeastolfac;
187  SCIP_Real oldfeastol;
188 
189  assert(bestsol != NULL);
190 
191  /* scale feasibility tolerance by set->num_checkfeastolfac */
192  oldfeastol = SCIPfeastol(scip);
193  SCIP_CALL( SCIPgetRealParam(scip, "numerics/checkfeastolfac", &checkfeastolfac) );
194  if( !SCIPisEQ(scip, checkfeastolfac, 1.0) )
195  {
196  SCIP_CALL( SCIPchgFeastol(scip, oldfeastol * checkfeastolfac) );
197  }
198 
199  SCIP_CALL( SCIPcheckSolOrig(scip, bestsol, &localfeasible, !quiet, TRUE) );
200 
201  /* restore old feasibilty tolerance */
202  if( !SCIPisEQ(scip, checkfeastolfac, 1.0) )
203  {
204  SCIP_CALL( SCIPchgFeastol(scip, oldfeastol) );
205  }
206  }
207  else
208  {
209  localfeasible = TRUE;
210  }
211 
212  primviol = 0.0;
213  dualviol = 0.0;
214  /* check the primal and dual bounds computed by SCIP against the external reference values within reference tolerance */
215  /* solution for an infeasible problem */
216  if( SCIPgetNSols(scip) > 0 && ((SCIPgetObjsense(scip) == SCIP_OBJSENSE_MINIMIZE && SCIPisInfinity(scip, dualreference))
217  || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE && SCIPisInfinity(scip, -dualreference))) )
218  localprimalboundcheck = FALSE;
219  else
220  {
221  /* check if reference primal bound is not better than the proven dual bound and, if SCIP claims to be optimal,
222  * if the
223  */
224  SCIP_Real pb = SCIPgetPrimalbound(scip);
225  SCIP_Real db = SCIPgetDualbound(scip);
226 
227  /* compute the relative violation between the primal bound and dual reference value, and vice versa */
229  {
230  if( dualreference != SCIP_UNKNOWN ) /*lint !e777 */
231  primviol = SCIPrelDiff(dualreference, pb);
232  if( primalreference != SCIP_UNKNOWN ) /*lint !e777 */
233  dualviol = SCIPrelDiff(db, primalreference);
234  }
235  else
236  {
237  if( dualreference != SCIP_UNKNOWN ) /*lint !e777 */
238  primviol = SCIPrelDiff(pb, dualreference);
239 
240  if( primalreference != SCIP_UNKNOWN ) /*lint !e777 */
241  dualviol = SCIPrelDiff(primalreference, db);
242  }
243  primviol = MAX(primviol, 0.0);
244  dualviol = MAX(dualviol, 0.0);
245 
246  localprimalboundcheck = EPSP(reftol, primviol);
247  localdualboundcheck = EPSP(reftol, dualviol);
248  }
249 
250  if( !quiet )
251  {
252  SCIPinfoMessage(scip, NULL, "Validation : ");
253  if( ! localfeasible )
254  SCIPinfoMessage(scip, NULL, "Fail (infeasible)");
255  else if( ! localprimalboundcheck )
256  SCIPinfoMessage(scip, NULL, "Fail (primal bound)");
257  else if( ! localdualboundcheck )
258  SCIPinfoMessage(scip, NULL, "Fail (dual bound)");
259  else
260  SCIPinfoMessage(scip, NULL, "Success");
261  SCIPinfoMessage(scip, NULL, "\n");
262  SCIPinfoMessage(scip, NULL, " %-17s: %10u\n", "cons violation", !localfeasible);
263  SCIPinfoMessage(scip, NULL, " %-17s: %10.8g (reference: %16.9e)\n", "primal violation", primviol, dualreference);
264  SCIPinfoMessage(scip, NULL, " %-17s: %10.8g (reference: %16.9e)\n", "dual violation", dualviol, primalreference);
265  }
266 
267  if( feasible != NULL )
268  *feasible = localfeasible;
269  if( primalboundcheck != NULL )
270  *primalboundcheck = localprimalboundcheck;
271  if( dualboundcheck != NULL )
272  *dualboundcheck = localdualboundcheck;
273 
274  return SCIP_OKAY;
275 }
internal methods for separators
#define NULL
Definition: def.h:239
internal methods for managing events
SCIP_Real SCIPfeastol(SCIP *scip)
default message handler
trivialnegation primal heuristic
internal methods for storing primal CIP solutions
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:412
methods to interpret (evaluate) an expression tree "fast"
internal methods for branch and bound tree
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
methods for implications, variable bounds, and cliques
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
internal methods for clocks and timing issues
internal methods for NLPI solver interfaces
interface methods for specific LP solvers
internal methods for displaying statistics tables
#define FALSE
Definition: def.h:65
methods for the aggregation rows
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10325
internal methods for Benders&#39; decomposition
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
methods commonly used by primal heuristics
#define EPSP(x, eps)
Definition: def.h:181
internal methods for branching rules and branching candidate storage
datastructures for concurrent solvers
public methods for validation
internal methods for handling parameter settings
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
methods for creating output for visualization tools (VBC, BAK)
nodereopt branching rule
internal methods for LP management
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
internal methods for branching and inference history
public methods for numerical tolerances
internal methods for collecting primal CIP solutions and primal informations
public methods for querying solving statistics
internal methods for propagators
git hash methods
internal methods for storing and manipulating the main problem
methods for block memory pools and memory buffers
SCIP_Real SCIPgetDualbound(SCIP *scip)
register additional core functionality that is designed as plugins
internal methods for presolvers
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3533
internal methods for NLP management
internal miscellaneous methods
internal methods for node selectors and node priority queues
internal methods for variable pricers
internal methods for global SCIP settings
internal methods for storing conflicts
#define SCIP_CALL(x)
Definition: def.h:351
SCIP main data structure.
internal methods for storing priced variables
internal methods for relaxators
internal methods for storing separated cuts
methods commonly used for presolving
methods for catching the user CTRL-C interrupt
internal methods for problem variables
data structures and methods for collecting reoptimization information
the function declarations for the synchronization store
#define SCIP_UNKNOWN
Definition: def.h:171
public data structures and miscellaneous methods
internal methods for user interface dialog
#define SCIP_Bool
Definition: def.h:62
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)
internal methods for input file readers
methods for debugging
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2280
reoptsols primal heuristic
internal methods for storing cuts in a cut pool
SCIP_RETCODE SCIPchgFeastol(SCIP *scip, SCIP_Real feastol)
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
helper functions for concurrent scip solvers
internal methods for return codes for SCIP methods
general public methods
#define MAX(x, y)
Definition: def.h:208
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
public methods for solutions
internal methods for conflict analysis
internal methods for tree compressions
internal methods for main solving loop and node processing
public methods for message output
default user interface dialog
#define SCIP_Real
Definition: def.h:150
internal methods for problem statistics
public methods for message handling
internal methods for constraints and constraint handlers
declarations for XML parsing
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1281
build flags methods
common defines and data types used in all packages of SCIP
internal methods for primal heuristics
public methods for global and local (sub)problems
internal methods for Benders&#39; decomposition cuts
internal methods for displaying runtime statistics
OFINS - Objective Function Induced Neighborhood Search - a primal heuristic for reoptimization.