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