Solving Constraint Integer Programs

Detailed Description

repair primal heuristic

Gregor Hendel
Thomas Nagel

Definition in file heur_repair.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/cons_varbound.h"
#include "scip/heur_repair.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/scipdefplugins.h"
#include <string.h>

Go to the source code of this file.


#define HEUR_NAME   "repair"
#define HEUR_DESC   "tries to repair a primal infeasible solution"
#define HEUR_PRIORITY   0
#define HEUR_FREQ   -1
#define HEUR_FREQOFS   0
#define HEUR_MAXDEPTH   -1
#define DEFAULT_MINFIXINGRATE   0.3 /* minimum percentage of integer variables that have to be fixed */
#define DEFAULT_NODESOFS   500 /* number of nodes added to the contingent of the total nodes */
#define DEFAULT_MAXNODES   5000 /* maximum number of nodes to regard in the subproblem */
#define DEFAULT_MINNODES   50 /* minimum number of nodes to regard in the subproblem */
#define DEFAULT_NODESQUOT   0.1 /* subproblem nodes in relation to nodes of the original problem */
#define DEFAULT_FILENAME   "-"
#define DEFAULT_ALPHA   2.0


static SCIP_RETCODE getObjectiveFactor (SCIP *scip, SCIP *subscip, SCIP_Real *factor, SCIP_Bool *success)
static SCIP_Real getPotentialContributed (SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real coefficient, int sgn)
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)
static SCIP_RETCODE checkCands (SCIP *scip, SCIP_SOL *sol, SCIP_Bool roundit, SCIP_Bool *success)
static SCIP_RETCODE createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
static SCIP_RETCODE applyRepair (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Longint nnodes)
static SCIP_DECL_HEURFREE (heurFreeRepair)
static SCIP_DECL_HEURINIT (heurInitRepair)
static SCIP_DECL_HEUREXIT (heurExitRepair)
static SCIP_DECL_HEUREXEC (heurExecRepair)
SCIP_RETCODE SCIPincludeHeurRepair (SCIP *scip)

Macro Definition Documentation


#define HEUR_NAME   "repair"

Definition at line 62 of file heur_repair.c.


#define HEUR_DESC   "tries to repair a primal infeasible solution"

Definition at line 63 of file heur_repair.c.



Definition at line 64 of file heur_repair.c.


#define HEUR_PRIORITY   0

Definition at line 65 of file heur_repair.c.


#define HEUR_FREQ   -1

Definition at line 66 of file heur_repair.c.


#define HEUR_FREQOFS   0

Definition at line 67 of file heur_repair.c.


#define HEUR_MAXDEPTH   -1

Definition at line 68 of file heur_repair.c.



Definition at line 69 of file heur_repair.c.



does the heuristic use a secondary SCIP instance?

Definition at line 70 of file heur_repair.c.


#define DEFAULT_MINFIXINGRATE   0.3 /* minimum percentage of integer variables that have to be fixed */

Definition at line 71 of file heur_repair.c.


#define DEFAULT_NODESOFS   500 /* number of nodes added to the contingent of the total nodes */

Definition at line 73 of file heur_repair.c.


#define DEFAULT_MAXNODES   5000 /* maximum number of nodes to regard in the subproblem */

Definition at line 74 of file heur_repair.c.


#define DEFAULT_MINNODES   50 /* minimum number of nodes to regard in the subproblem */

Definition at line 75 of file heur_repair.c.


#define DEFAULT_NODESQUOT   0.1 /* subproblem nodes in relation to nodes of the original problem */

Definition at line 76 of file heur_repair.c.


#define DEFAULT_FILENAME   "-"

file name of a solution to be used as infeasible starting point

Definition at line 78 of file heur_repair.c.



if it is TRUE : fractional variables which are not fractional in the given solution are rounded, if it is FALSE : solving process of this heuristic is stopped

Definition at line 79 of file heur_repair.c.



should a scaled objective function for original variables be used in repair subproblem?

Definition at line 86 of file heur_repair.c.



should variable fixings be used in repair subproblem?

Definition at line 91 of file heur_repair.c.



should slack variables be used in repair subproblem?

Definition at line 92 of file heur_repair.c.


#define DEFAULT_ALPHA   2.0

how many times the potential should be bigger than the slack?

Definition at line 93 of file heur_repair.c.

Function Documentation

◆ getObjectiveFactor()

static SCIP_RETCODE getObjectiveFactor ( SCIP scip,
SCIP subscip,
SCIP_Real factor,
SCIP_Bool success 

computes a factor, so that (factor) * (original objective upper bound) <= 1.

scipSCIP data structure
subscipSCIP data structure
factorSCIP_Real to save the factor for the old objective function
successSCIP_Bool: Is the factor real?

Definition at line 148 of file heur_repair.c.

References getPotentialContributed(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddOrigObjoffset(), SCIPgetLowerbound(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by applyRepair().

◆ getPotentialContributed()

static SCIP_Real getPotentialContributed ( SCIP scip,
SCIP_Real  coefficient,
int  sgn 

returns the contributed potential for a variable

scipSCIP data structure
solinfeasible solution
varvariable, which potential should be returned
coefficientvariables coefficient in corresponding row
sgnsign of the slack

Definition at line 224 of file heur_repair.c.

References NULL, SCIP_Real, SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and tryFixVar().

Referenced by applyRepair(), getObjectiveFactor(), and tryFixVar().

◆ tryFixVar()

static SCIP_RETCODE tryFixVar ( SCIP scip,
SCIP subscip,
SCIP_Real potential,
SCIP_Real slack,
SCIP_VAR subvar,
int *  inftycounter,
SCIP_Bool fixed 

finds out if a variable can be fixed with respect to the potentials of all rows, if it is possible, the potentials of rows are adapted and TRUE is returned.

scipSCIP data structure
subscipsub-SCIP data structure
solsolution data structure
potentialarray with all potential values
slackarray with all slack values
varvariable to be fixed?
subvarrepresentative variable for var in the sub-SCIP
inftycountercounters how many variables have an infinity potential in a row
heurdatarepairs heuristic data
fixedpointer to store whether the fixing was performed (variable was unfixed)

Definition at line 271 of file heur_repair.c.

References checkCands(), FALSE, getPotentialContributed(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPfixVar(), SCIPgetSolVal(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasZero(), SCIPisInfinity(), SCIProwGetLPPos(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by applyRepair(), and getPotentialContributed().

◆ checkCands()

static SCIP_RETCODE checkCands ( SCIP scip,
SCIP_Bool  roundit,
SCIP_Bool success 

checks if all integral variables in the given solution are integral.

scipSCIP data structure
solsolution pointer to the to be checked solution
rounditround fractional solution values of integer variables
successpointer to store if all integral variables are integral or could be rounded

Definition at line 404 of file heur_repair.c.

References createNewSol(), FALSE, NULL, REALABS, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPsetSolVal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), and TRUE.

Referenced by tryFixVar().

◆ createNewSol()

static SCIP_RETCODE createNewSol ( SCIP scip,
SCIP subscip,
SCIP_VAR **  subvars,
SCIP_SOL subsol,
SCIP_Bool success 

creates a new solution for the original problem by copying the solution of the subproblem

sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
subvarsthe variables of the subproblem
heurRepair heuristic structure
subsolsolution of the subproblem
successused to store whether new solution was found or not

Definition at line 485 of file heur_repair.c.

References applyRepair(), FALSE, nnodes, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPtranslateSubSol(), SCIPtrySolFree(), and TRUE.

Referenced by applyRepair(), and checkCands().

◆ applyRepair()

static SCIP_RETCODE applyRepair ( SCIP scip,
SCIP_Longint  nnodes 

tries to fix variables as an approach to repair a solution.

scipSCIP data structure of the problem
heurpointer to this heuristic instance
resultpointer to return the result status
nnodesnodelimit for sub-SCIP

Definition at line 523 of file heur_repair.c.

References createNewSol(), FALSE, getObjectiveFactor(), getPotentialContributed(), MAX, nnodes, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURFREE(), SCIP_FOUNDSOL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVED, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_NONE, SCIPABORT, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddSolFree(), SCIPaddVar(), SCIPallocBufferArray, SCIPcolGetVar(), SCIPcopyParamSettings(), SCIPcreate(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicVarbound(), SCIPcreateProb(), SCIPcreateSol(), SCIPcreateVarBasic(), SCIPdebug, SCIPdebugMsg, SCIPfindBranchrule(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetLPRows(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNRuns(), SCIPgetNSols(), SCIPgetNTotalNodes(), SCIPgetPresolvingTime(), SCIPgetProbName(), SCIPgetRealParam(), SCIPgetRowSolActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetVarsData(), SCIPheurGetData(), SCIPincludeDefaultPlugins(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisParamFixed(), SCIPisZero(), SCIPprintStatistics(), SCIPreleaseCons(), SCIPreleaseVar(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetRealParam(), SCIPsetSolVal(), SCIPsetSubscipsOff(), SCIPsnprintf(), SCIPsolve(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), TRUE, and tryFixVar().

Referenced by createNewSol().


static SCIP_DECL_HEURFREE ( heurFreeRepair  )

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 1031 of file heur_repair.c.

Referenced by applyRepair().


static SCIP_DECL_HEURINIT ( heurInitRepair  )

initialization method of primal heuristic (called after problem was transformed)

Definition at line 1048 of file heur_repair.c.

References SCIP_Real.


static SCIP_DECL_HEUREXIT ( heurExitRepair  )

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 1084 of file heur_repair.c.


static SCIP_DECL_HEUREXEC ( heurExecRepair  )

execution method of primal heuristic. Repair needs an incorrect solution, in which all variables are in their bound.

Definition at line 1159 of file heur_repair.c.