Scippy

SCIP

Solving Constraint Integer Programs

heur_repair.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 heur_repair.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief repair primal heuristic
28 * @author Gregor Hendel
29 * @author Thomas Nagel
30 *
31 */
32
33/* This heuristic takes an infeasible solution and tries to repair it.
34 * This can happen by variable fixing as long as the sum of all potential possible shiftings
35 * is higher than alpha*slack or slack variables with a strong penalty on the objective function.
36 * This heuristic cannot run if variable fixing and slack variables are turned off.
37 */
38
39/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40
42#include "scip/cons_linear.h"
43#include "scip/cons_varbound.h"
44#include "scip/heur_repair.h"
45#include "scip/pub_heur.h"
46#include "scip/pub_lp.h"
47#include "scip/pub_message.h"
48#include "scip/pub_misc.h"
49#include "scip/pub_misc_sort.h"
50#include "scip/pub_var.h"
51#include "scip/scip_branch.h"
52#include "scip/scip_cons.h"
53#include "scip/scip_copy.h"
54#include "scip/scip_general.h"
55#include "scip/scip_heur.h"
56#include "scip/scip_lp.h"
57#include "scip/scip_mem.h"
58#include "scip/scip_message.h"
59#include "scip/scip_numerics.h"
60#include "scip/scip_param.h"
61#include "scip/scip_prob.h"
62#include "scip/scip_sol.h"
63#include "scip/scip_solve.h"
65#include "scip/scip_timing.h"
66#include "scip/scip_tree.h"
67#include "scip/scip_var.h"
68#include "scip/scipdefplugins.h"
69#include <string.h>
70
71#define HEUR_NAME "repair"
72#define HEUR_DESC "tries to repair a primal infeasible solution"
73#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
74#define HEUR_PRIORITY -20
75#define HEUR_FREQ -1
76#define HEUR_FREQOFS 0
77#define HEUR_MAXDEPTH -1
78#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
79#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
80#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */
81
82#define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */
83#define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */
84#define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */
85#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
86
87#define DEFAULT_FILENAME "-" /**< file name of a solution to be used as infeasible starting point */
88#define DEFAULT_ROUNDIT TRUE /**< if it is TRUE : fractional variables which are not fractional in the given
89 * solution are rounded, if it is FALSE : solving process of this heuristic
90 * is stopped
91 */
92#define DEFAULT_USEOBJFACTOR FALSE /**< should a scaled objective function for original variables be used in repair
93 * subproblem?
94 */
95#define DEFAULT_USEVARFIX TRUE /**< should variable fixings be used in repair subproblem? */
96#define DEFAULT_USESLACKVARS FALSE /**< should slack variables be used in repair subproblem? */
97#define DEFAULT_ALPHA 2.0 /**< how many times the potential should be bigger than the slack? */
98
99/*
100 * Data structures
101 */
102
103
104/** primal heuristic data */
105struct SCIP_HeurData
106{
107 SCIP_SOL* infsol; /**< infeasible solution to start with */
108 char* filename; /**< file name of a solution to be used as infeasible starting point */
109 SCIP_Longint usednodes; /**< number of already used nodes by repair */
110 SCIP_Longint subnodes; /**< number of nodes which were necessary to solve the sub-SCIP */
111 SCIP_Longint subiters; /**< contains total number of iterations used in primal and dual simplex
112 * and barrier algorithm to solve the sub-SCIP
113 */
114 SCIP_Real relvarfixed; /**< relative number of fixed variables */
115 SCIP_Real alpha; /**< how many times the potential should be bigger than the slack? */
116 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
117 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
118#ifdef SCIP_STATISTIC
119 SCIP_Real relviolatedvars; /**< relative number of violated variables */
120 SCIP_Real subpresoltime; /**< time for presolving the sub-SCIP */
121 SCIP_Real relviolatedcons; /**< relative number of violated cons */
122 SCIP_Real originalsolval; /**< value of the solution find by repair, in the original Problem*/
123 SCIP_Real improvedoldsol; /**< value of the given solution after being improved by SCIP */
124 int nviolatedvars; /**< number of violated variables in the given solution */
125 int norigvars; /**< number of all variables in the given problem */
126 int nviolatedcons; /**< number of violated cons in the given solution */
127 int norcons; /**< number of all cons in the given problem */
128#endif
129 int nvarfixed; /**< number of all variables fixed in the sub problem */
130 int runs; /**< number of branch and bound runs performed to solve the sub-SCIP */
131 int nodesofs; /**< number of nodes added to the contingent of the total nodes */
132 int maxnodes; /**< maximum number of nodes to regard in the subproblem */
133 int minnodes; /**< minimum number of nodes to regard in the subproblem */
134 SCIP_Bool roundit; /**< if it is TRUE : fractional variables which are not fractional in the
135 * given solution are rounded, if it is FALSE : solving process of this
136 * heuristic is stopped.
137 */
138 SCIP_Bool useobjfactor; /**< should a scaled objective function for original variables be used in
139 * repair subproblem?
140 */
141 SCIP_Bool usevarfix; /**< should variable fixings be used in repair subproblem? */
142 SCIP_Bool useslackvars; /**< should slack variables be used in repair subproblem? */
143};
144
145
146/*
147 * Local methods
148 */
149
150/** computes a factor, so that (factor) * (original objective upper bound) <= 1.*/
151static
153 SCIP* scip, /**< SCIP data structure */
154 SCIP* subscip, /**< SCIP data structure */
155 SCIP_Real* factor, /**< SCIP_Real to save the factor for the old objective function*/
156 SCIP_Bool* success /**< SCIP_Bool: Is the factor real?*/
157 )
158{
159 SCIP_VAR** vars;
160 SCIP_Real lprelaxobj;
161 SCIP_Real upperbound;
162 SCIP_Real objoffset;
163 int nvars;
164 int i;
165
166 *success = TRUE;
167 *factor = 0.0;
168 upperbound = 0.0;
169
170 lprelaxobj = SCIPgetLowerbound(scip);
171
172 if( SCIPisInfinity(scip, -lprelaxobj) )
173 {
174 return SCIP_OKAY;
175 }
176
178 {
179 upperbound = SCIPgetUpperbound(scip);
180 }
181 else
182 {
183 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
184
185 /* tries to find an upper bound for the original objective function, by compute the worst objective value of the
186 * LP-relaxation, which holds all variable bounds
187 */
188 for (i = 0; i < nvars; ++i)
189 {
190 upperbound = SCIPvarGetObj(vars[i]);
191 if( SCIPisInfinity(scip, upperbound) || SCIPisInfinity(scip, -upperbound) )
192 {
193 /* TODO fancy diving function to find a solution for the max problem */
194 *factor = 1 / SCIPinfinity(scip);
195 return SCIP_OKAY;
196 }
197 else if( SCIPisZero(scip, upperbound) )
198 {
199 continue;
200 }
201 else if( SCIPisGT(scip, 0.0, upperbound) )
202 {
203 *factor += upperbound * SCIPvarGetLbGlobal(vars[i]);
204 }
205 else
206 {
207 *factor += upperbound * SCIPvarGetUbGlobal(vars[i]);
208 }
209 }
210 }
211
212 /* Ending-sequence */
213 *factor = upperbound - lprelaxobj;
214 if( !SCIPisZero(scip, *factor) )
215 {
216 *factor = 1.0 / *factor;
217 }
218
219 /* set an offset which guarantees positive objective values */
220 objoffset = -lprelaxobj * (*factor);
221 SCIP_CALL( SCIPaddOrigObjoffset(subscip, -objoffset) );
222
223 return SCIP_OKAY;
224}
225
226/** returns the contributed potential for a variable */
227static
229 SCIP* scip, /**< SCIP data structure */
230 SCIP_SOL* sol, /**< infeasible solution */
231 SCIP_VAR* var, /**< variable, which potential should be returned */
232 SCIP_Real coefficient, /**< variables coefficient in corresponding row */
233 int sgn /**< sign of the slack */
234 )
235{
236 SCIP_Real potential;
237
238 assert(NULL != scip);
239 assert(NULL != var);
240
241 if( 0 > sgn * coefficient )
242 {
244 {
245 potential = SCIPinfinity(scip);
246 }
247 else
248 {
249 potential = coefficient * (SCIPgetSolVal(scip, sol, var) - SCIPvarGetLbGlobal(var));
250 }
251 }
252 else
253 {
255 {
256 potential = -SCIPinfinity(scip);
257 }
258 else
259 {
260 potential = coefficient * (SCIPgetSolVal(scip, sol, var) - SCIPvarGetUbGlobal(var));
261 }
262 }
263
264 if( SCIPisZero(scip, potential) )
265 {
266 potential = 0.0;
267 }
268 return potential;
269}
270
271/** finds out if a variable can be fixed with respect to the potentials of all rows, if it is possible, the potentials
272 * of rows are adapted and TRUE is returned.
273 */
274static
276 SCIP* scip, /**< SCIP data structure */
277 SCIP* subscip, /**< sub-SCIP data structure */
278 SCIP_SOL* sol, /**< solution data structure */
279 SCIP_Real* potential, /**< array with all potential values */
280 SCIP_Real* slack, /**< array with all slack values */
281 SCIP_VAR* var, /**< variable to be fixed? */
282 SCIP_VAR* subvar, /**< representative variable for var in the sub-SCIP */
283 int* inftycounter, /**< counters how many variables have an infinity potential in a row */
284 SCIP_HEURDATA* heurdata, /**< repairs heuristic data */
285 SCIP_Bool* fixed /**< pointer to store whether the fixing was performed (variable was unfixed) */
286 )
287{
288 SCIP_ROW** rows;
289 SCIP_COL* col;
290 SCIP_Real* vals;
291 SCIP_Real alpha;
292 SCIP_Real solval;
293 SCIP_Bool infeasible;
294 int nrows;
295 int i;
296 int sgn;
297 int rowindex;
298
299 assert(NULL != scip);
300 assert(NULL != potential);
301 assert(NULL != slack);
302 assert(NULL != var);
303 assert(NULL != inftycounter);
304 assert(NULL != heurdata);
305
306 alpha = heurdata->alpha;
307 infeasible = TRUE;
308 *fixed = FALSE;
309
310 solval = SCIPgetSolVal(scip, sol, var);
311
312 if( SCIPisFeasLT(scip, solval, SCIPvarGetLbGlobal(var)) )
313 {
314 return SCIP_OKAY;
315 }
316 if( SCIPisFeasGT(scip, solval, SCIPvarGetUbGlobal(var)) )
317 {
318 return SCIP_OKAY;
319 }
320
321 col = SCIPvarGetCol(var);
322 rows = SCIPcolGetRows(col);
323 nrows = SCIPcolGetNLPNonz(col);
324 vals = SCIPcolGetVals(col);
325
326 if( NULL == rows )
327 {
328 SCIP_CALL( SCIPfixVar(subscip, subvar, solval,
329 &infeasible, fixed) );
330 assert(!infeasible && *fixed);
331 heurdata->nvarfixed++;
332 SCIPdebugMsg(scip,"Variable %s is fixed to %g\n",SCIPvarGetName(var), solval);
333 return SCIP_OKAY;
334 }
335 assert(NULL != rows);
336
337 /* iterate over rows, where the variable coefficient is nonzero */
338 for( i = 0; i < nrows; ++i )
339 {
340 SCIP_Real contribution;
341 rowindex = SCIProwGetLPPos(rows[i]);
342 assert(rowindex >= 0);
343
344 sgn = 1;
345
346 if( SCIPisFeasZero(scip, slack[rowindex]) )
347 {
348 continue;
349 }
350 else if( SCIPisFeasGT(scip, 0.0 , slack[rowindex]) )
351 {
352 sgn = -1;
353 }
354
355 contribution = getPotentialContributed(scip, sol, var, vals[i], sgn);
356
357 if( !SCIPisInfinity(scip, REALABS(contribution)) )
358 {
359 potential[rowindex] -= contribution;
360 }
361 else
362 {
363 inftycounter[rowindex]--;
364 }
365
366 assert(0 <= inftycounter[rowindex]);
367 if( 0 == inftycounter[rowindex] && REALABS(potential[rowindex]) < alpha * REALABS(slack[rowindex]) )
368 {
369 /* revert the changes before */
370 int j = i;
371 for( ; j >= 0; --j )
372 {
373 sgn = 1;
374 if( 0 == slack[rowindex] )
375 {
376 continue;
377 }
378 rowindex = SCIProwGetLPPos(rows[j]);
379 if( 0 > slack[rowindex])
380 {
381 sgn = -1;
382 }
383 contribution = getPotentialContributed(scip, sol, var, vals[j], sgn);
384 if( !SCIPisInfinity(scip, REALABS(contribution)) )
385 {
386 potential[rowindex] += contribution;
387 }
388 else
389 {
390 inftycounter[rowindex]++;
391 }
392 }
393 return SCIP_OKAY;
394 }
395 }
396
397 SCIP_CALL( SCIPfixVar(subscip, subvar, solval, &infeasible, fixed) );
398 assert(!infeasible && *fixed);
399 heurdata->nvarfixed++;
400 SCIPdebugMsg(scip,"Variable %s is fixed to %g\n",SCIPvarGetName(var),
401 SCIPgetSolVal(scip, sol, var));
402
403 return SCIP_OKAY;
404}
405
406/** checks if all integral variables in the given solution are integral. */
407static
409 SCIP* scip, /**< SCIP data structure */
410 SCIP_SOL* sol, /**< solution pointer to the to be checked solution */
411 SCIP_Bool roundit, /**< round fractional solution values of integer variables */
412 SCIP_Bool* success /**< pointer to store if all integral variables are integral or could
413 * be rounded
414 */
415 )
416{
417 SCIP_VAR** vars;
418 int nvars;
419 int nfracvars;
420 int nbinvars;
421 int nintvars;
422 int i;
423
424 assert(NULL != success);
425 assert(NULL != sol);
426
427 *success = TRUE;
428
429 /* get variable data */
430 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
431
432 /* check if the candidates are fractional and round them if necessary */
433 nfracvars = nbinvars + nintvars;
434 for( i = 0; i < nfracvars; ++i)
435 {
436 SCIP_Real value = SCIPgetSolVal(scip, sol, vars[i]);
437
438 if( SCIPisInfinity(scip, REALABS(value)) )
439 {
440 *success = FALSE;
441 SCIPdebugMsg(scip, "Variable with infinite solution value");
442
443 return SCIP_OKAY;
444 }
445 if( !SCIPisFeasIntegral(scip, value) )
446 {
447 if( roundit )
448 {
449 SCIP_Real roundedvalue;
450
452 {
453 roundedvalue = SCIPceil(scip, value - 1.0);
454 }
455 else
456 {
457 roundedvalue = SCIPfloor(scip, value + 1.0);
458 }
459
460 SCIP_CALL( SCIPsetSolVal(scip, sol, vars[i], roundedvalue) );
461 }
462 else
463 {
464 *success = FALSE;
465 SCIPdebugMsg(scip, "Repair: All variables are integral.\n");
466 return SCIP_OKAY;
467 }
468 }
469 }
470
471 /* ensure that no other variables have infinite LP solution values */
472 for( ; i < nvars; ++i )
473 {
474 if( SCIPisInfinity(scip, REALABS(SCIPgetSolVal(scip, sol, vars[i]))) )
475 {
476 *success = FALSE;
477 SCIPdebugMsg(scip, "Variable with infinite solution value");
478
479 return SCIP_OKAY;
480 }
481 }
482
483 SCIPdebugMsg(scip, "All variables rounded.\n");
484 return SCIP_OKAY;
485}
486
487/** creates a new solution for the original problem by copying the solution of the subproblem */
488static
490 SCIP* scip, /**< original SCIP data structure */
491 SCIP* subscip, /**< SCIP structure of the subproblem */
492 SCIP_VAR** subvars, /**< the variables of the subproblem */
493 SCIP_HEUR* heur, /**< Repair heuristic structure */
494 SCIP_SOL* subsol, /**< solution of the subproblem */
495 SCIP_Bool* success /**< used to store whether new solution was found or not */
496 )
497{
498 SCIP_SOL* newsol; /* solution to be created for the original problem */
499
500 assert(scip != NULL);
501 assert(subscip != NULL);
502 assert(subvars != NULL);
503 assert(subsol != NULL);
504
505 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsol, heur, subvars, &newsol) );
506
507 /* try to add new solution to SCIP and free it immediately */
508 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
509
510#ifdef SCIP_STATISTIC
511 {
512 SCIP_HEURDATA* heurdata;
513 heurdata = SCIPheurGetData(heur);
514
515 if( *success )
516 {
517 heurdata->originalsolval = SCIPgetSolOrigObj(scip, newsol);
518 }
519 }
520#endif
521
522 return SCIP_OKAY;
523}
524
525/** tries to fix variables as an approach to repair a solution. */
526static
528 SCIP* scip, /**< SCIP data structure of the problem */
529 SCIP_HEUR* heur, /**< pointer to this heuristic instance */
530 SCIP_RESULT* result, /**< pointer to return the result status */
531 SCIP_Longint nnodes /**< nodelimit for sub-SCIP */
532 )
533{
534 SCIP* subscip = NULL;
535 SCIP_VAR** vars = NULL;
536 SCIP_VAR** subvars = NULL;
537 SCIP_ROW** rows;
538 SCIP_CONS** subcons = NULL;
539 int* nviolatedrows = NULL;
540 int* permutation = NULL;
541 int* inftycounter = NULL;
542 SCIP_SOL* sol;
543 SCIP_SOL* subsol = NULL;
544 SCIP_HEURDATA* heurdata;
545 SCIP_Real* potential = NULL;
546 SCIP_Real* slacks = NULL;
547 SCIP_RETCODE retcode = SCIP_OKAY;
548 SCIP_Real timelimit;
549 SCIP_Real memorylimit;
550 SCIP_Real factor;
551 char probname[SCIP_MAXSTRLEN];
552 int i;
553 int nbinvars;
554 int nintvars;
555 int nvars;
556 int nrows;
557 int ndiscvars;
558 int nfixeddiscvars;
559 SCIP_Bool success;
560 SCIP_Bool avoidmemout;
561
562 heurdata = SCIPheurGetData(heur);
563 sol = heurdata->infsol;
564
565 /* initializes the sub-SCIP */
566 SCIP_CALL( SCIPcreate(&subscip) );
569
570 /* use inference branching */
571 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
572 {
573 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
574 }
575
576 /* get name of the original problem and add the string "_repairsub" */
577 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_repairsub", SCIPgetProbName(scip));
578
579 SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
580
581 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
582 if( heurdata->useslackvars )
583 {
584 SCIP_CALL( SCIPcreateSol(subscip, &subsol, heur) );
585 }
586
587 /* gets all original variables */
588 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
589 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
590 SCIP_CALL( SCIPallocBufferArray(scip, &nviolatedrows, nvars) );
591 SCIP_CALL( SCIPallocBufferArray(scip, &permutation, nvars) );
592
593 SCIPdebugMsg(scip,"\n\n Calling objective factor calculation \n\n");
594 if( heurdata->useobjfactor )
595 {
596 SCIP_CALL( getObjectiveFactor(scip, subscip, &factor, &success) );
597 }
598 else
599 {
600 factor = 0.0;
601 }
602
603 /* adds all original variables */
604 ndiscvars = 0;
605 for( i = 0; i < nvars; ++i )
606 {
607 SCIP_CONS* cons;
608 SCIP_Real lb;
609 SCIP_Real ub;
610 SCIP_Real lborig;
611 SCIP_Real uborig;
612 SCIP_Real varslack;
613 SCIP_Real objval;
614 SCIP_Real value;
615 SCIP_VARTYPE vartype;
616 char varname[SCIP_MAXSTRLEN];
617 char slackvarname[SCIP_MAXSTRLEN];
618 char consvarname[SCIP_MAXSTRLEN];
619
620#ifdef SCIP_STATISTIC
621 heurdata->norigvars++;
622#endif
623
624 varslack = 0.0;
625 lborig = SCIPvarGetLbGlobal(vars[i]);
626 uborig = SCIPvarGetUbGlobal(vars[i]);
627 value = SCIPgetSolVal(scip, sol, vars[i]);
628 vartype = SCIPvarGetType(vars[i]);
629
630 nviolatedrows[i] = 0;
631
632 /* if the value of x is lower than the variables lower bound, sets the slack to a correcting value */
633 if( heurdata->useslackvars && SCIPisFeasLT(scip, value, lborig) )
634 {
635 lb = value;
636 varslack = lborig - value;
637 }
638 else
639 {
640 lb = lborig;
641 }
642
643 /* if the value of x is bigger than the variables upper bound, sets the slack to a correcting value */
644 if( heurdata->useslackvars && SCIPisFeasGT(scip, value, uborig) )
645 {
646 ub = value;
647 varslack = uborig - value;
648 }
649 else
650 {
651 ub = uborig;
652 }
653
654 if( heurdata->useobjfactor )
655 {
656 objval = SCIPvarGetObj(vars[i])*factor;
657
658 if( SCIPisZero(scip, objval) )
659 {
660 objval = 0.0;
661 }
662 }
663 else
664 {
665 objval = SCIPvarGetObj(vars[i]);
666 }
667
668 /* if a binary variable is out of bound, generalize it to an integer variable */
669 if( !SCIPisFeasZero(scip, varslack) && SCIP_VARTYPE_BINARY == vartype )
670 {
671 vartype = SCIP_VARTYPE_INTEGER;
672 }
673
674 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "sub_%s", SCIPvarGetName(vars[i]));
675
676 /* Adds the sub representing variable to the sub-SCIP. */
677 SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[i], varname, lb, ub, objval, vartype) );
678 SCIP_CALL( SCIPaddVar(subscip, subvars[i]) );
679
680 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
681 if( heurdata->useslackvars )
682 {
683 SCIP_CALL( SCIPsetSolVal(subscip, subsol, subvars[i], value) );
684 }
685
686 /* if necessary adds a constraint to represent the original bounds of x.*/
687 if( !SCIPisFeasEQ(scip, varslack, 0.0) )
688 {
689 SCIP_VAR* newvar;
690 (void) SCIPsnprintf(slackvarname, SCIP_MAXSTRLEN, "artificialslack_%s", SCIPvarGetName(vars[i]));
691 (void) SCIPsnprintf(consvarname, SCIP_MAXSTRLEN, "boundcons_%s", SCIPvarGetName(vars[i]));
692
693 /* initialize and add an artificial slack variable */
694 if( heurdata->useobjfactor )
695 {
696 SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, slackvarname, 0.0, 1.0, 1.0, SCIP_VARTYPE_CONTINUOUS));
697 }
698 else
699 {
700 SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, slackvarname, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY));
701 }
702 SCIP_CALL( SCIPaddVar(subscip, newvar) );
703
704 /* set the value of the slack variable to 1 to punish the use of it.
705 * note that a trivial feasible solution can be only constructed if violations are modeled with slack variables
706 */
707 if( heurdata->useslackvars )
708 {
709 SCIP_CALL( SCIPsetSolVal(subscip, subsol, newvar, 1.0) );
710 }
711
712 /* adds a linear constraint to represent the old bounds */
713 SCIP_CALL( SCIPcreateConsBasicVarbound(subscip, &cons, consvarname, subvars[i], newvar, varslack, lb, ub) );
714 SCIP_CALL( SCIPaddCons(subscip, cons) );
715 SCIP_CALL( SCIPreleaseVar(subscip, &newvar) );
716 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
717
718 /* increases the counter for violated vars */
719#ifdef SCIP_STATISTIC
720 heurdata->nviolatedvars++;
721#endif
722 }
723
724#ifdef SCIP_STATISTIC
725 if( SCIPisFeasLT(scip, value, lb) || SCIPisFeasGT(scip, value, ub) )
726 {
727 heurdata->nviolatedvars++;
728 }
729#endif
730 if( SCIP_VARTYPE_BINARY == vartype || SCIP_VARTYPE_INTEGER == vartype )
731 {
732 ndiscvars++;
733 }
734 }
735
736 /* check solution for feasibility regarding the LP rows (SCIPgetRowSolActivity()) */
737 rows = SCIPgetLPRows(scip);
738 nrows = SCIPgetNLPRows(scip);
739
740 SCIP_CALL( SCIPallocBufferArray(scip, &potential, nrows) );
741 SCIP_CALL( SCIPallocBufferArray(scip, &slacks, nrows) );
742 SCIP_CALL( SCIPallocBufferArray(scip, &subcons, nrows) );
743 SCIP_CALL( SCIPallocBufferArray(scip, &inftycounter, nrows) );
744
745 /* Adds all original constraints and computes potentials and slacks */
746 for (i = 0; i < nrows; ++i)
747 {
748 SCIP_COL** cols;
749 SCIP_VAR** consvars;
750 SCIP_Real* vals;
751 SCIP_Real constant;
752 SCIP_Real lhs;
753 SCIP_Real rhs;
754 SCIP_Real rowsolact;
755 int nnonz;
756 int j;
757
758#ifdef SCIP_STATISTIC
759 heurdata->norcons++;
760#endif
761
762 /* gets the values to check the constraint */
763 constant = SCIProwGetConstant(rows[i]);
764 lhs = SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) ? SCIProwGetLhs(rows[i]) : SCIProwGetLhs(rows[i]) - constant;
765 rhs = SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) ? SCIProwGetRhs(rows[i]) : SCIProwGetRhs(rows[i]) - constant;
766 rowsolact = SCIPgetRowSolActivity(scip, rows[i], sol) - constant;
767 vals = SCIProwGetVals(rows[i]);
768 potential[i] = 0.0;
769 inftycounter[i] = 0;
770
771 assert(SCIPisFeasLE(scip, lhs, rhs));
772
773 nnonz = SCIProwGetNNonz(rows[i]);
774 cols = SCIProwGetCols(rows[i]);
775 SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, nnonz) );
776
777 /* sets the slack if its necessary */
778 if( SCIPisFeasLT(scip, rowsolact, lhs) )
779 {
780 slacks[i] = lhs - rowsolact;
781#ifdef SCIP_STATISTIC
782 heurdata->nviolatedcons++;
783#endif
784 }
785 else if( SCIPisFeasGT(scip, rowsolact, rhs) )
786 {
787 slacks[i] = rhs - rowsolact;
788#ifdef SCIP_STATISTIC
789 heurdata->nviolatedcons++;
790#endif
791 }
792 else
793 {
794 slacks[i] = 0.0;
795 }
796
797 /* translate all variables from the original SCIP to the sub-SCIP with sub-SCIP variables. */
798 for( j = 0; j < nnonz; ++j )
799 {
800 SCIP_Real contribution;
801 int pos;
802 int sgn = 1;
803
804 /* negative slack represents a right hand side violation */
805 if( SCIPisFeasGT(scip, 0.0, slacks[i]) )
806 {
807 assert(!SCIPisInfinity(scip, rhs));
808 sgn = -1;
809 }
810 #ifndef NDEBUG
811 else
812 assert(!SCIPisInfinity(scip, lhs));
813 #endif
814
815 pos = SCIPvarGetProbindex(SCIPcolGetVar(cols[j]));
816 consvars[j] = subvars[pos];
817 assert(pos >= 0);
818
819 /* compute potentials */
820 contribution = getPotentialContributed(scip, sol, vars[pos], vals[j], sgn);
821 if( !SCIPisInfinity(scip, REALABS(contribution)) )
822 {
823 potential[i] += contribution;
824 }
825 else
826 {
827 inftycounter[i]++;
828 }
829
830 if( !SCIPisZero(scip, slacks[i]) )
831 {
832 nviolatedrows[pos]++;
833 }
834 }
835
836 /* create a new linear constraint, representing the old one */
837 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &subcons[i], SCIProwGetName(rows[i]),
838 nnonz, consvars, vals, lhs, rhs) );
839
840 if( heurdata->useslackvars )
841 {
842 SCIP_VAR* newvar;
843 char varname[SCIP_MAXSTRLEN];
844
845 /*if necessary adds a new artificial slack variable*/
846 if( !SCIPisFeasEQ(subscip, slacks[i], 0.0) )
847 {
848 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "artificialslack_%s", SCIProwGetName(rows[i]));
849 SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, varname, 0.0, 1.0, 1.0, SCIP_VARTYPE_CONTINUOUS) );
850 SCIP_CALL( SCIPaddVar(subscip, newvar) );
851
852 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
853 SCIP_CALL( SCIPsetSolVal(subscip, subsol, newvar, 1.0) );
854 SCIP_CALL( SCIPaddCoefLinear(subscip, subcons[i], newvar, slacks[i]) );
855 SCIP_CALL( SCIPreleaseVar(subscip, &newvar) );
856 }
857 }
858
859 /*Adds the Constraint and release it.*/
860 SCIP_CALL( SCIPaddCons(subscip, subcons[i]) );
861 SCIP_CALL( SCIPreleaseCons(subscip, &subcons[i]) );
862 SCIPfreeBufferArray(subscip, &consvars);
863 }
864
865 if( heurdata->usevarfix )
866 {
867 /* get the greedy order */
868 for( i = 0; i < nvars; ++i )
869 {
870 permutation[i] = i;
871 }
872 SCIPsortIntInt(nviolatedrows, permutation, nvars);
873
874 /* loops over variables and greedily fix variables, but preserve the cover property that enough slack is given to
875 * violated rows
876 */
877 nfixeddiscvars = 0;
878 heurdata->nvarfixed = 0;
879 for( i = 0; i < nvars; ++i )
880 {
881 SCIP_Bool fixed;
882
883 /* continue if we have a loose variable */
884 if( SCIPvarGetStatus(vars[permutation[i]]) != SCIP_VARSTATUS_COLUMN )
885 continue;
886
887 SCIP_CALL( tryFixVar(scip, subscip, sol, potential, slacks, vars[permutation[i]], subvars[permutation[i]], inftycounter, heurdata, &fixed) );
888
889 if( fixed && (SCIP_VARTYPE_BINARY == SCIPvarGetType(subvars[permutation[i]])
890 || SCIP_VARTYPE_INTEGER == SCIPvarGetType(subvars[permutation[i]])) )
891 {
892 nfixeddiscvars++;
893 }
894 }
895 SCIPdebugMsg(scip,"fixings finished\n\n");
896 if( heurdata->minfixingrate > ((SCIP_Real)nfixeddiscvars/MAX((SCIP_Real)ndiscvars,1.0)) )
897 {
898 goto TERMINATE;
899 }
900 }
901
902 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
903 if( heurdata->useslackvars )
904 {
905 SCIP_CALL( SCIPaddSolFree(subscip, &subsol, &success) );
906
907 if( !success )
908 {
909 SCIPdebugMsg(scip, "Initial repair solution was not accepted.\n");
910 }
911 }
912
913#ifdef SCIP_STATISTIC
914 if( heurdata->useslackvars )
915 heurdata->improvedoldsol = SCIPgetSolOrigObj(subscip, subsol);
916#endif
917
918 /* check whether there is enough time and memory left */
919 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
920 if( !SCIPisInfinity(scip, timelimit) )
921 timelimit -= SCIPgetSolvingTime(scip);
922 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
923 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
924
925 /* subtract the memory already used by the main SCIP and the estimated memory usage of external software */
926 if( !SCIPisInfinity(scip, memorylimit) )
927 {
928 memorylimit -= SCIPgetMemUsed(scip) / 1048576.0;
929 memorylimit -= SCIPgetMemExternEstim(scip) / 1048576.0;
930 }
931
932 /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == FALSE)
933 * to create a copy of SCIP, including external memory usage */
934 if( timelimit <= 0.0 || (avoidmemout && memorylimit <= 2.0 * SCIPgetMemExternEstim(scip) / 1048576.0) )
935 goto TERMINATE;
936
937 /* set limits for the subproblem */
938 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
939 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
940 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
941 SCIP_CALL( SCIPsetObjlimit(subscip, 1.0) );
942
943 /* disable bound limits */
944 SCIP_CALL( SCIPsetRealParam(subscip, "limits/primal", SCIP_INVALID) );
945 SCIP_CALL( SCIPsetRealParam(subscip, "limits/dual", SCIP_INVALID) );
946
947 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
948 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
949
950 /* disable output to console */
951 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
952
953#ifdef SCIP_DEBUG
954 /* for debugging Repair, enable MIP output */
955 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int)SCIP_VERBLEVEL_FULL) );
956 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) );
957#endif
958
959 /* solve the subproblem */
960 retcode = SCIPsolve(subscip);
961
962 /* errors in sub-SCIPs should not kill the overall solving process. Hence, we print a warning message. Only
963 * in debug mode, SCIP will stop
964 */
965 if( retcode != SCIP_OKAY )
966 {
967 SCIPwarningMessage(scip, "Error while solving subproblem in REPAIR heuristic; sub-SCIP terminated with code <%d>\n", retcode);
968 SCIPABORT(); /*lint --e{527}*/
969 goto TERMINATE;
970 }
971
972 success = FALSE;
973
974 /* if a solution is found, save its value and create a new solution instance for the original SCIP */
975 if( SCIPgetBestSol(subscip) != NULL )
976 {
977#ifdef SCIP_STATISTIC
978 heurdata->improvedoldsol = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip));
979#endif
980 /* print solving statistics of subproblem if we are in SCIP's debug mode */
982
983 assert(SCIPgetNSols(subscip) > 0);
984 SCIP_CALL( createNewSol(scip, subscip, subvars, heur, SCIPgetBestSol(subscip), &success) );
985
986 if( success )
987 {
988 *result = SCIP_FOUNDSOL;
989 }
990 }
991 else
992 {
993 SCIPdebugMsg(scip,"No solution found!\n");
994 }
995
996 if( SCIPgetStage(subscip) >= SCIP_STAGE_SOLVED )
997 {
998 heurdata->subiters = SCIPgetNLPIterations(subscip);
999 heurdata->subnodes = SCIPgetNTotalNodes(subscip);
1000#ifdef SCIP_STATISTIC
1001 heurdata->subpresoltime = SCIPgetPresolvingTime(subscip);
1002#endif
1003 heurdata->runs = SCIPgetNRuns(subscip);
1004 }
1005
1006 /* terminates the solving process */
1007TERMINATE:
1008 if( NULL != sol )
1009 {
1010 SCIP_CALL( SCIPfreeSol(scip, &sol) );
1011 }
1012 SCIPfreeBufferArrayNull(scip, &nviolatedrows);
1013 for( i = 0; i < nvars; ++i )
1014 {
1015 SCIP_CALL( SCIPreleaseVar(subscip, &subvars[i]) );
1016 }
1017 SCIPfreeBufferArrayNull(scip, &inftycounter);
1018 SCIPfreeBufferArrayNull(scip, &subcons);
1019 SCIPfreeBufferArrayNull(scip, &slacks);
1020 SCIPfreeBufferArrayNull(scip, &potential);
1021 SCIPfreeBufferArrayNull(scip, &permutation);
1022 SCIPfreeBufferArrayNull(scip, &subvars);
1023
1024 if( NULL != subsol )
1025 {
1026 SCIP_CALL( SCIPfreeSol(subscip, &subsol) );
1027 }
1028
1029 SCIP_CALL( SCIPfree(&subscip) );
1030
1031 SCIPdebugMsg(scip, "repair finished\n");
1032 return SCIP_OKAY;
1033}
1034
1035
1036/*
1037 * Callback methods of primal heuristic
1038 */
1039
1040/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1041static
1042SCIP_DECL_HEURFREE(heurFreeRepair)
1043{ /*lint --e{715}*/
1044 SCIP_HEURDATA* heurdata;
1045
1046 heurdata = SCIPheurGetData(heur);
1047
1048 assert(heurdata != NULL);
1049 SCIPfreeMemory(scip, &heurdata);
1050
1051 SCIPheurSetData(heur, NULL);
1052
1053 return SCIP_OKAY;
1054}
1055
1056
1057/** initialization method of primal heuristic (called after problem was transformed) */
1058static
1059SCIP_DECL_HEURINIT(heurInitRepair)
1060{ /*lint --e{715}*/
1061 SCIP_HEURDATA* heurdata;
1062
1063 heurdata = SCIPheurGetData(heur);
1064
1065 heurdata->subiters = -1;
1066 heurdata->subnodes = -1;
1067 heurdata->runs = 0;
1068
1069 heurdata->nvarfixed = 0;
1070 heurdata->relvarfixed = -1;
1071
1072#ifdef SCIP_STATISTIC
1073 heurdata->subpresoltime = 0;
1074
1075 heurdata->nviolatedvars = 0;
1076 heurdata->norigvars = 0;
1077 heurdata->relviolatedvars = 0;
1078 heurdata->nviolatedcons = 0;
1079 heurdata->norcons = 0;
1080 heurdata->relviolatedcons = 0;
1081
1082 heurdata->originalsolval = SCIP_INVALID;
1083
1084 heurdata->improvedoldsol = SCIP_UNKNOWN;
1085#endif
1086
1087 heurdata->usednodes = 0;
1088
1089 return SCIP_OKAY;
1090}
1091
1092
1093/** deinitialization method of primal heuristic (called before transformed problem is freed) */
1094static
1095SCIP_DECL_HEUREXIT(heurExitRepair)
1096{ /*lint --e{715}*/
1097#ifdef SCIP_STATISTIC
1098 SCIP_HEURDATA* heurdata;
1099 SCIP_Real time;
1100 SCIP_Real relvars;
1101 SCIP_Real relcons;
1102 SCIP_Real relfixed;
1103 char solval[SCIP_MAXSTRLEN];
1104 int violateds;
1105 int ninvars;
1106 int ninvcons;
1107 int nvars;
1108 int ncons;
1109 int iterations;
1110 int nodes;
1111 int runs;
1112
1113 heurdata = SCIPheurGetData(heur);
1114 violateds = heurdata->nviolatedvars+heurdata->nviolatedcons;
1115 ninvars = heurdata->nviolatedvars;
1116 ninvcons = heurdata->nviolatedcons;
1117 nvars = heurdata->norigvars;
1118 ncons = heurdata->norcons;
1119 iterations = heurdata->subiters;
1120 nodes = heurdata->subnodes;
1121 time = heurdata->subpresoltime;
1122 runs = heurdata->runs;
1123
1124 if( SCIP_INVALID == heurdata->originalsolval )
1125 {
1126 (void) SCIPsnprintf(solval, SCIP_MAXSTRLEN ,"--");
1127 }
1128 else
1129 {
1130 (void) SCIPsnprintf(solval, SCIP_MAXSTRLEN, "%15.9g", heurdata->originalsolval);
1131 }
1132
1133 heurdata->relviolatedvars = MAX((SCIP_Real)heurdata->norigvars, 1.0);
1134 heurdata->relviolatedvars = heurdata->nviolatedvars/heurdata->relviolatedvars;
1135 heurdata->relviolatedcons = MAX((SCIP_Real)heurdata->norcons, 1.0);
1136 heurdata->relviolatedcons = heurdata->nviolatedcons/heurdata->relviolatedcons;
1137
1138 heurdata->relvarfixed = MAX((SCIP_Real)heurdata->norigvars, 1.0);
1139 heurdata->relvarfixed = heurdata->nvarfixed/heurdata->relvarfixed;
1140 relvars = heurdata->relviolatedvars;
1141 relcons = heurdata->relviolatedcons;
1142 relfixed = heurdata->relvarfixed;
1143
1144 /* prints all statistic data for a user*/
1146 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "<repair> \n total violations : %10d\n", violateds);
1147 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " violated variables : %10d\n", ninvars);
1148 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " total variables : %10d\n", nvars);
1149 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative violated variables : %10.2f%%\n", 100 * relvars);
1150 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " violated constraints : %10d\n", ninvcons);
1151 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " total constraints : %10d\n", ncons);
1152 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative violated constraints: %10.2f%%\n", 100* relcons);
1153 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " fixed variables : %10d\n", heurdata->nvarfixed);
1154 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative fixed variables : %10.2f%%\n\n", 100* relfixed);
1155 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " iterations : %10d\n", iterations);
1156 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " nodes : %10d\n", nodes);
1157 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " number of runs : %10d\n", runs);
1158 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " presolve time : %10.2f\n", time);
1159 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "</repair>\n\n");
1160 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " value of best solution : %10g\n", solval);
1161 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " improved orig. solval : %10g\n", heurdata->improvedoldsol);
1162 )
1163
1164#endif
1165 return SCIP_OKAY;
1166}
1167
1168/** execution method of primal heuristic. Repair needs an incorrect solution, in which all variables are in their bound. */
1169static
1170SCIP_DECL_HEUREXEC(heurExecRepair)
1171{ /*lint --e{715}*/
1172 SCIP_HEURDATA* heurdata;
1173 SCIP_RETCODE retcode;
1174 SCIP_Bool success;
1175 SCIP_Bool error;
1177
1178 heurdata = SCIPheurGetData(heur);
1179 SCIPdebugMsg(scip, "%s\n", heurdata->filename);
1180
1181 /* checks the result pointer */
1182 assert(result != NULL);
1183 *result = SCIP_DIDNOTRUN;
1184
1185 /* if repair already ran or neither variable fixing nor slack variables are enabled, stop */
1186 if( 0 < SCIPheurGetNCalls(heur) || !(heurdata->usevarfix || heurdata->useslackvars) )
1187 return SCIP_OKAY;
1188
1189 /* do not run if the neither the LP is constructed nor a user given solution exists */
1190 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && strcmp(heurdata->filename, DEFAULT_FILENAME) == 0 )
1191 return SCIP_OKAY;
1192
1193 /* calculate the maximal number of branching nodes until heuristic is aborted */
1194 nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
1195
1196 /* reward REPAIR if it succeeded often */
1197 nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
1198 nnodes -= (SCIP_Longint)(100.0 * SCIPheurGetNCalls(heur)); /* count the setup costs for the sub-MIP as 100 nodes */
1199 nnodes += heurdata->nodesofs;
1200
1201 /* determine the node limit for the current process */
1202 nnodes -= heurdata->usednodes;
1203 nnodes = MIN(nnodes, heurdata->maxnodes);
1204
1205 /* check whether we have enough nodes left to call subproblem solving */
1206 if( nnodes < heurdata->minnodes )
1207 return SCIP_OKAY;
1208
1210 return SCIP_OKAY;
1211
1213 {
1214 SCIP_Bool cutoff;
1215
1216 SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1217
1218 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1219 if( cutoff )
1220 {
1222 return SCIP_OKAY;
1223 }
1224 }
1225
1226 /* create original solution */
1227 SCIP_CALL( SCIPcreateOrigSol(scip, &(heurdata->infsol), heur) );
1228
1229 /* use read method to enter solution from a file */
1230 if( strcmp(heurdata->filename, DEFAULT_FILENAME) == 0 )
1231 {
1232 retcode = SCIPlinkLPSol(scip, heurdata->infsol);
1233 }
1234 else
1235 {
1236 error = FALSE;
1237 retcode = SCIPreadSolFile(scip, heurdata->filename, heurdata->infsol, FALSE, NULL, &error);
1238 }
1239
1240 if( SCIP_NOFILE == retcode )
1241 {
1242 assert(strcmp(heurdata->filename, DEFAULT_FILENAME) != 0);
1243 SCIPwarningMessage(scip, "cannot open file <%s> for reading\n", heurdata->filename);
1244
1245 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1246 return SCIP_OKAY;
1247 }
1248 else if( retcode != SCIP_OKAY )
1249 {
1250 SCIPwarningMessage(scip, "cannot run repair, unknown return status <%d>\n", retcode);
1251 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1252 return SCIP_OKAY;
1253 }
1254 SCIPdebugMsg(scip, "Repair: Solution file read.\n");
1255
1256 /* checks the integrality of all discrete variable */
1257 SCIP_CALL( checkCands(scip, heurdata->infsol, heurdata->roundit, &success) );
1258 if( !success )
1259 {
1260 SCIPdebugMsg(scip,"Given solution is not integral, repair terminates.\n");
1261 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1262 return SCIP_OKAY;
1263 }
1264
1265 *result = SCIP_DIDNOTFIND;
1266
1267 SCIP_CALL( SCIPtrySol(scip, heurdata->infsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1268
1269 /* the solution is not feasible for the original problem; we will try to repair it */
1270 if( !success )
1271 {
1272 assert(NULL != heurdata->infsol);
1273 assert(heurdata->usevarfix || heurdata->useslackvars);
1274 SCIP_CALL( applyRepair(scip, heur, result, nnodes) );
1275 }
1276 else
1277 {
1278 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1279 }
1280
1281 return SCIP_OKAY;
1282}
1283
1284/* primal heuristic specific interface methods */
1285
1286/** creates the repair primal heuristic and includes it in SCIP */
1288 SCIP* scip /**< SCIP data structure */
1289 )
1290{
1291 SCIP_HEURDATA* heurdata;
1292 SCIP_HEUR* heur;
1293
1294 /* create repair primal heuristic data */
1295 heurdata = NULL;
1296
1297 SCIP_CALL( SCIPallocMemory(scip ,&heurdata) );
1298
1299 heur = NULL;
1300
1301 /* include primal heuristic */
1304 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRepair, heurdata) );
1305
1306 assert(heur != NULL);
1307 assert(heurdata != NULL);
1308
1309 /* set non fundamental callbacks via setter functions */
1310 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRepair) );
1311 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRepair) );
1312 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRepair) );
1313
1314 /* add repair primal heuristic parameters */
1315
1316 heurdata->filename = NULL;
1317 /* add string parameter for filename containing a solution */
1318 SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/filename",
1319 "file name of a solution to be used as infeasible starting point, [-] if not available",
1320 &heurdata->filename, FALSE, DEFAULT_FILENAME, NULL, NULL) );
1321
1322 /* add bool parameter for decision how to deal with unfractional cands */
1323 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/roundit",
1324 "True : fractional variables which are not fractional in the given solution are rounded, "
1325 "FALSE : solving process of this heuristic is stopped. ",
1326 &heurdata->roundit, FALSE, DEFAULT_ROUNDIT, NULL, NULL));
1327
1328 /* add bool parameter for decision how the objective function should be */
1329 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useobjfactor",
1330 "should a scaled objective function for original variables be used in repair subproblem?",
1331 &heurdata->useobjfactor, FALSE, DEFAULT_USEOBJFACTOR, NULL, NULL));
1332
1333 /* add bool parameter for decision if variable fixings should be used */
1334 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usevarfix",
1335 "should variable fixings be used in repair subproblem?",
1336 &heurdata->usevarfix, FALSE, DEFAULT_USEVARFIX, NULL, NULL));
1337
1338 /* add bool parameter for decision how the objective function should be */
1339 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useslackvars",
1340 "should slack variables be used in repair subproblem?",
1341 &heurdata->useslackvars, FALSE, DEFAULT_USESLACKVARS, NULL, NULL));
1342
1343 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/alpha", "factor for the potential of var fixings",
1344 &heurdata->alpha, TRUE, DEFAULT_ALPHA, 0.0, 100.00, NULL, NULL) );
1345
1346 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1347 "number of nodes added to the contingent of the total nodes",
1348 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
1349
1350 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1351 "maximum number of nodes to regard in the subproblem",
1352 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
1353
1354 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1355 "minimum number of nodes required to start the subproblem",
1356 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
1357
1358 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1359 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1360 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1361
1362 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1363 "minimum percentage of integer variables that have to be fixed",
1364 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1365
1366 return SCIP_OKAY;
1367}
Constraint handler for linear constraints in their most general form, .
Constraint handler for variable bound constraints .
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#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 SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsBasicVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1408
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:2564
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPaddOrigObjoffset(SCIP *scip, SCIP_Real addval)
Definition: scip_prob.c:1290
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:117
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:194
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPincludeHeurRepair(SCIP *scip)
Definition: heur_repair.c:1287
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:17140
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:124
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:101
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:605
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:126
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:60
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2144
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPreadSolFile(SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool xml, SCIP_Bool *partial, SCIP_Bool *error)
Definition: scip_sol.c:2751
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:2855
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:421
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:2954
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3050
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
int SCIPgetNRuns(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Real SCIPgetPresolvingTime(SCIP *scip)
Definition: scip_timing.c:442
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:434
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:194
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define DEFAULT_USEOBJFACTOR
Definition: heur_repair.c:92
static SCIP_Real getPotentialContributed(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real coefficient, int sgn)
Definition: heur_repair.c:228
#define DEFAULT_NODESQUOT
Definition: heur_repair.c:85
#define DEFAULT_FILENAME
Definition: heur_repair.c:87
static SCIP_DECL_HEUREXEC(heurExecRepair)
Definition: heur_repair.c:1170
#define DEFAULT_NODESOFS
Definition: heur_repair.c:82
#define DEFAULT_USEVARFIX
Definition: heur_repair.c:95
#define DEFAULT_MAXNODES
Definition: heur_repair.c:83
#define HEUR_TIMING
Definition: heur_repair.c:78
#define DEFAULT_MINNODES
Definition: heur_repair.c:84
#define HEUR_FREQOFS
Definition: heur_repair.c:76
#define HEUR_DESC
Definition: heur_repair.c:72
static SCIP_RETCODE applyRepair(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Longint nnodes)
Definition: heur_repair.c:527
static SCIP_DECL_HEUREXIT(heurExitRepair)
Definition: heur_repair.c:1095
static SCIP_RETCODE tryFixVar(SCIP *scip, SCIP *subscip, SCIP_SOL *sol, SCIP_Real *potential, SCIP_Real *slack, SCIP_VAR *var, SCIP_VAR *subvar, int *inftycounter, SCIP_HEURDATA *heurdata, SCIP_Bool *fixed)
Definition: heur_repair.c:275
#define DEFAULT_MINFIXINGRATE
Definition: heur_repair.c:80
static SCIP_DECL_HEURFREE(heurFreeRepair)
Definition: heur_repair.c:1042
#define HEUR_DISPCHAR
Definition: heur_repair.c:73
#define HEUR_MAXDEPTH
Definition: heur_repair.c:77
#define HEUR_PRIORITY
Definition: heur_repair.c:74
static SCIP_RETCODE checkCands(SCIP *scip, SCIP_SOL *sol, SCIP_Bool roundit, SCIP_Bool *success)
Definition: heur_repair.c:408
#define HEUR_NAME
Definition: heur_repair.c:71
#define DEFAULT_ALPHA
Definition: heur_repair.c:97
static SCIP_RETCODE getObjectiveFactor(SCIP *scip, SCIP *subscip, SCIP_Real *factor, SCIP_Bool *success)
Definition: heur_repair.c:152
#define HEUR_FREQ
Definition: heur_repair.c:75
#define DEFAULT_USESLACKVARS
Definition: heur_repair.c:96
#define HEUR_USESSUBSCIP
Definition: heur_repair.c:79
#define DEFAULT_ROUNDIT
Definition: heur_repair.c:88
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_repair.c:489
static SCIP_DECL_HEURINIT(heurInitRepair)
Definition: heur_repair.c:1059
repair primal heuristic
memory allocation routines
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPstatistic(x)
Definition: pub_message.h:120
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
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 solving methods
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_VERBLEVEL_NONE
Definition: type_message.h:52
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
@ SCIP_VERBLEVEL_FULL
Definition: type_message.h:57
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_NOFILE
Definition: type_retcode.h:47
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_SOLVED
Definition: type_set.h:54
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:73