1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 */
SCIPvalidateSolve(SCIP * scip,SCIP_Real primalreference,SCIP_Real dualreference,SCIP_Real reftol,SCIP_Bool quiet,SCIP_Bool * feasible,SCIP_Bool * primalboundcheck,SCIP_Bool * dualboundcheck)60 SCIP_RETCODE SCIPvalidateSolve(
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 */
143 if( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MINIMIZE )
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 }
191