1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 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" 53 #include "scip/scip_solvingstats.h" 54 #include "scip/scip_validation.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 */ 69 SCIP_RETCODE SCIPvalidateSolve( 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 */ 91 if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM ) 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 */ 140 if( SCIPgetNSols(scip) > 0 && ((SCIPgetObjsense(scip) == SCIP_OBJSENSE_MINIMIZE && SCIPisInfinity(scip, dualreference)) 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 */ 148 SCIP_Real pb = SCIPgetPrimalbound(scip); 149 SCIP_Real db = SCIPgetDualbound(scip); 150 151 /* compute the relative violation between the primal bound and dual reference value, and vice versa */ 152 if( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MINIMIZE ) 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 } 200