Detailed Description

public solving methods

Author: Tobias Achterberg; Timo Berthold; Gerald Gamrath; Leona Gottwald; Stefan Heinz; Gregor Hendel; Thorsten Koch; Alexander Martin; Marc Pfetsch; Michael Winkler; Kati Wolter

Definition in file scip_solve.c.

#include "blockmemshell/memory.h"
#include "scip/branch.h"
#include "scip/clock.h"
#include "scip/compr.h"
#include "scip/concsolver.h"
#include "scip/concurrent.h"
#include "scip/conflict.h"
#include "scip/conflictstore.h"
#include "scip/cons.h"
#include "scip/cutpool.h"
#include "scip/dcmp.h"
#include "scip/debug.h"
#include "scip/event.h"
#include "scip/implics.h"
#include "scip/interrupt.h"
#include "scip/lp.h"
#include "scip/nlp.h"
#include "scip/presol.h"
#include "scip/pricestore.h"
#include "scip/primal.h"
#include "scip/prob.h"
#include "scip/prop.h"
#include "scip/pub_branch.h"
#include "scip/pub_compr.h"
#include "scip/pub_cons.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_select.h"
#include "scip/pub_presol.h"
#include "scip/pub_prop.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/relax.h"
#include "scip/reopt.h"
#include "scip/scip_benders.h"
#include "scip/scip_branch.h"
#include "scip/scip_concurrent.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.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_randnumgen.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/sepastore.h"
#include "scip/set.h"
#include "scip/sol.h"
#include "scip/solve.h"
#include "scip/stat.h"
#include "scip/struct_event.h"
#include "scip/struct_mem.h"
#include "scip/struct_primal.h"
#include "scip/struct_prob.h"
#include "scip/struct_scip.h"
#include "scip/struct_set.h"
#include "scip/struct_stat.h"
#include "scip/struct_tree.h"
#include "scip/syncstore.h"
#include "scip/tree.h"
#include "scip/var.h"
#include "scip/visual.h"

Go to the source code of this file.

Functions
static SCIP_RETCODE	calcNonZeros (SCIP scip, SCIP_Longint nchecknonzeros, SCIP_Longint nactivenonzeros, SCIP_Bool approxchecknonzeros, SCIP_Bool *approxactivenonzeros)

SCIP_RETCODE	SCIPtransformProb (SCIP *scip)

static SCIP_RETCODE	initPresolve (SCIP *scip)

static SCIP_RETCODE	exitPresolve (SCIP scip, SCIP_Bool solved, SCIP_Bool infeasible)

static SCIP_RETCODE	presolveRound (SCIP scip, SCIP_PRESOLTIMING timing, SCIP_Bool unbounded, SCIP_Bool infeasible, SCIP_Bool lastround, int presolstart, int presolend, int propstart, int propend, int *consstart, int consend)

static SCIP_RETCODE	presolve (SCIP scip, SCIP_Bool unbounded, SCIP_Bool infeasible, SCIP_Bool vanished)

static SCIP_RETCODE	transformSols (SCIP *scip)

static SCIP_RETCODE	initSolve (SCIP *scip, SCIP_Bool solved)

static SCIP_RETCODE	freeSolve (SCIP *scip, SCIP_Bool restart)

static SCIP_RETCODE	freeReoptSolve (SCIP *scip)

static SCIP_RETCODE	freeTransform (SCIP *scip)

static SCIP_RETCODE	freeTransforming (SCIP *scip)

static SCIP_RETCODE	displayRelevantStats (SCIP *scip)

static SCIP_RETCODE	compressReoptTree (SCIP *scip)

static SCIP_RETCODE	prepareReoptimization (SCIP *scip)

SCIP_RETCODE	SCIPpresolve (SCIP *scip)

SCIP_RETCODE	SCIPsolve (SCIP *scip)

SCIP_RETCODE	SCIPsolveParallel (SCIP *scip)

SCIP_RETCODE	SCIPsolveConcurrent (SCIP *scip)

SCIP_RETCODE	SCIPenableReoptimization (SCIP *scip, SCIP_Bool enable)

SCIP_RETCODE	SCIPaddReoptDualBndchg (SCIP scip, SCIP_NODE node, SCIP_VAR *var, SCIP_Real newbound, SCIP_Real oldbound)

SCIP_SOL *	SCIPgetReoptLastOptSol (SCIP *scip)

SCIP_RETCODE	SCIPgetReoptOldObjCoef (SCIP scip, SCIP_VAR var, int run, SCIP_Real *objcoef)

SCIP_RETCODE	SCIPfreeSolve (SCIP *scip, SCIP_Bool restart)

SCIP_RETCODE	SCIPfreeReoptSolve (SCIP *scip)

SCIP_RETCODE	SCIPfreeTransform (SCIP *scip)

SCIP_RETCODE	SCIPinterruptSolve (SCIP *scip)

SCIP_Bool	SCIPisSolveInterrupted (SCIP *scip)

SCIP_RETCODE	SCIPrestartSolve (SCIP *scip)

SCIP_Bool	SCIPisReoptEnabled (SCIP *scip)

SCIP_RETCODE	SCIPgetReoptSolsRun (SCIP scip, int run, SCIP_SOL sols, int solssize, int nsols)

void	SCIPresetReoptSolMarks (SCIP *scip)

SCIP_RETCODE	SCIPcheckReoptRestart (SCIP scip, SCIP_NODE node, SCIP_Bool *restart)

SCIP_Bool	SCIPisInRestart (SCIP *scip)

Function Documentation

◆ calcNonZeros()

static SCIP_RETCODE calcNonZeros	(	SCIP *	scip,
		SCIP_Longint *	nchecknonzeros,
		SCIP_Longint *	nactivenonzeros,
		SCIP_Bool *	approxchecknonzeros,
		SCIP_Bool *	approxactivenonzeros
	)

static

calculates number of nonzeros in problem

Parameters

scip	SCIP data structure
nchecknonzeros	pointer to store number of non-zeros in all check constraints
nactivenonzeros	pointer to store number of non-zeros in all active constraints
approxchecknonzeros	pointer to store if the number of non-zeros in all check constraints is only a lowerbound
approxactivenonzeros	pointer to store if the number of non-zeros in all active constraints is only a lowerbound

Definition at line 118 of file scip_solve.c.

References FALSE, h, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetNVars(), SCIPconshdlrGetCheckConss(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconshdlrGetNCheckConss(), SCIPconsIsActive(), SCIPconsIsChecked(), and TRUE.

Referenced by presolve(), and SCIPtransformProb().

◆ initPresolve()

static SCIP_RETCODE initPresolve ( SCIP * scip )

static

initializes presolving

Parameters

scip	SCIP data structure

Definition at line 435 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_PRESOLVING, SCIP_STAGE_TRANSFORMED, SCIPbuffer(), SCIPcleanbuffer(), SCIPprimalRetransformSolutions(), SCIPprobPerformVarDeletions(), SCIPsetInitprePlugins(), SCIPstatResetPresolving(), and SCIPtreeCreatePresolvingRoot().

Referenced by presolve(), and SCIPsolveConcurrent().

◆ exitPresolve()

static SCIP_RETCODE exitPresolve	(	SCIP *	scip,
		SCIP_Bool	solved,
		SCIP_Bool *	infeasible
	)

static

deinitializes presolving

Parameters

scip	SCIP data structure
solved	is problem already solved?
infeasible	pointer to store if the clique clean up detects an infeasibility

Definition at line 499 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_EXITPRESOLVE, SCIP_STAGE_PRESOLVED, SCIP_STAGE_PRESOLVING, SCIP_VARSTATUS_MULTAGGR, SCIP_VERBLEVEL_FULL, SCIPbuffer(), SCIPcleanbuffer(), SCIPcliquetableCleanup(), SCIPgetFixedVars(), SCIPgetLowerbound(), SCIPgetNFixedVars(), SCIPgetUpperbound(), SCIPmessagePrintVerbInfo(), SCIPprobCheckObjIntegral(), SCIPprobExitPresolve(), SCIPprobInternObjval(), SCIPprobPerformVarDeletions(), SCIPprobScaleObj(), SCIPsetExitprePlugins(), SCIPstatUpdatePrimalDualIntegrals(), SCIPtreeFreePresolvingRoot(), SCIPvarFlattenAggregationGraph(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrVars(), and SCIPvarGetStatus().

Referenced by presolve(), SCIPfreeReoptSolve(), SCIPfreeSolve(), SCIPfreeTransform(), and SCIPsolveConcurrent().

◆ presolveRound()

static SCIP_RETCODE presolveRound	(	SCIP *	scip,
		SCIP_PRESOLTIMING *	timing,
		SCIP_Bool *	unbounded,
		SCIP_Bool *	infeasible,
		SCIP_Bool	lastround,
		int *	presolstart,
		int	presolend,
		int *	propstart,
		int	propend,
		int *	consstart,
		int	consend
	)

static

applies one round of presolving with the given presolving timing

This method will always be called with presoltiming fast first. It iterates over all presolvers, propagators, and constraint handlers and calls their presolving callbacks with timing fast. If enough reductions are found, it returns and the next presolving round will be started (again with timing fast). If the fast presolving does not find enough reductions, this methods calls itself recursively with presoltiming medium. Again, it calls the presolving callbacks of all presolvers, propagators, and constraint handlers with timing medium. If enough reductions are found, it returns and the next presolving round will be started (with timing fast). Otherwise, it is called recursively with presoltiming exhaustive. In exhaustive presolving, presolvers, propagators, and constraint handlers are called w.r.t. their priority, but this time, we stop as soon as enough reductions were found and do not necessarily call all presolving methods. If we stop, we return and another presolving round is started with timing fast.

Parameters

scip	SCIP data structure
timing	pointer to current presolving timing
unbounded	pointer to store whether presolving detected unboundedness
infeasible	pointer to store whether presolving detected infeasibility
lastround	is this the last presolving round due to a presolving round limit?
presolstart	pointer to get the presolver to start exhaustive presolving with in the current round and store the one to start with in the next round
presolend	last presolver to treat in exhaustive presolving
propstart	pointer to get the propagator to start exhaustive presolving with in the current round and store the one to start with in the next round
propend	last propagator to treat in exhaustive presolving
consstart	pointer to get the constraint handler to start exhaustive presolving with in the current round and store the one to start with in the next round
consend	last constraint handler to treat in exhaustive presolving

Definition at line 652 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), FALSE, NULL, presolveRound(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_EVENTTYPE_PRESOLVEROUND, SCIP_HEURTIMING_DURINGPRESOLLOOP, SCIP_INVALID, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_FINAL, SCIP_PRESOLTIMING_MEDIUM, SCIP_UNBOUNDED, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPbuffer(), SCIPcleanbuffer(), SCIPcliquetableCleanup(), SCIPconshdlrGetName(), SCIPconshdlrPresolve(), SCIPdebugMsg, SCIPeventChgType(), SCIPeventProcess(), SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSolvingTime(), SCIPheurGetName(), SCIPisPresolveFinished(), SCIPmessagePrintVerbInfo(), SCIPpresolExec(), SCIPpresolGetName(), SCIPpresolGetPriority(), SCIPprimalHeuristics(), SCIPprobPerformVarDeletions(), SCIPpropGetName(), SCIPpropGetPresolPriority(), SCIPpropPresol(), SCIPsolGetHeur(), and TRUE.

Referenced by presolve(), and presolveRound().

◆ presolve()

static SCIP_RETCODE presolve	(	SCIP *	scip,
		SCIP_Bool *	unbounded,
		SCIP_Bool *	infeasible,
		SCIP_Bool *	vanished
	)

static

loops through the included presolvers and constraint's presolve methods, until changes are too few

Parameters

scip	SCIP data structure
unbounded	pointer to store whether presolving detected unboundedness
infeasible	pointer to store whether presolving detected infeasibility
vanished	pointer to store whether the problem vanished in presolving

Definition at line 1110 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), calcNonZeros(), exitPresolve(), FALSE, initPresolve(), MAX, NULL, presolveRound(), SCIP_Bool, SCIP_CALL, SCIP_HEURTIMING_BEFOREPRESOL, SCIP_INVALID, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_FINAL, SCIP_PRESOLTIMING_MEDIUM, SCIP_Real, SCIP_STAGE_PRESOLVED, SCIP_STAGE_PRESOLVING, SCIP_STAGE_TRANSFORMED, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_OPTIMAL, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_VARSTATUS_MULTAGGR, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIP_VERBLEVEL_NORMAL, SCIPbuffer(), SCIPcleanbuffer(), SCIPcliquetableGetNCliques(), SCIPclockStart(), SCIPclockStop(), SCIPcreateSol(), SCIPdebugMsg, SCIPflattenVarAggregationGraph(), SCIPgetBestSol(), SCIPgetNConss(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetSolvingTime(), SCIPheurGetName(), SCIPisInfinity(), SCIPisPresolveFinished(), SCIPmessagePrintVerbInfo(), SCIPprimalHeuristics(), SCIPprimalUpdateObjlimit(), SCIPprobMarkNConss(), SCIPprobResortVars(), SCIPsetSortPresols(), SCIPsetSortPropsPresol(), SCIPsolGetHeur(), SCIPsolveIsStopped(), SCIPtrySolFree(), SCIPvarGetStatus(), and TRUE.

Referenced by SCIPlpiGetIntpar(), SCIPlpiSolveBarrier(), SCIPlpiSolveDual(), SCIPlpiSolvePrimal(), SCIPpresolve(), and SolveWSimplex().

◆ transformSols()

static SCIP_RETCODE transformSols ( SCIP * scip )

static

tries to transform original solutions to the transformed problem space

Parameters

scip	SCIP data structure

Definition at line 1397 of file scip_solve.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNSols(), SCIPgetSols(), SCIPprimalTransformSol(), SCIPsolIsOriginal(), and SCIPverbMessage().

Referenced by initSolve().

◆ initSolve()

static SCIP_RETCODE initSolve	(	SCIP *	scip,
		SCIP_Bool	solved
	)

static

initializes solution process data structures

Parameters

scip	SCIP data structure
solved	is problem already solved?

Definition at line 1472 of file scip_solve.c.

References FALSE, NULL, REALABS, SCIP_CALL, SCIP_INVALID, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_STAGE_INITSOLVE, SCIP_STAGE_PRESOLVED, SCIP_STAGE_SOLVING, SCIPcutpoolCreate(), SCIPdebugMsg, SCIPlpReset(), SCIPnextafter(), SCIPnlpAddVars(), SCIPnlpCreate(), SCIPnodeUpdateLowerbound(), SCIPpricestoreCreate(), SCIPprimalSetCutoffbound(), SCIPprimalUpdateObjlimit(), SCIPprobGetName(), SCIPprobInitSolve(), SCIPprobInternObjval(), SCIPprobMarkNConss(), SCIPsepastoreCreate(), SCIPsetCutoffbounddelta(), SCIPsetInfinity(), SCIPsetInitsolPlugins(), SCIPsetIsInfinity(), SCIPsetIsLT(), SCIPsetIsZero(), SCIPstatEnforceLPUpdates(), SCIPstatResetCurrentRun(), SCIPtransformDecompstore(), SCIPtreeCreateRoot(), SCIPtreeGetRootNode(), SCIPvarGetObj(), SCIPvarGetWorstBoundGlobal(), SCIPvisualInit(), transformSols(), and TRUE.

Referenced by SCIPpresolve(), SCIPsolve(), and SCIPsolveConcurrent().

◆ freeSolve()

static SCIP_RETCODE freeSolve	(	SCIP *	scip,
		SCIP_Bool	restart
	)

static

frees solution process data structures

Parameters

scip	SCIP data structure
restart	was this free solve call triggered by a restart?

Definition at line 1613 of file scip_solve.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_EXITSOLVE, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIP_STAGE_TRANSFORMED, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_OPTIMAL, SCIP_STATUS_UNBOUNDED, SCIPconflictstoreClean(), SCIPcutpoolClear(), SCIPcutpoolFree(), SCIPdebugReset, SCIPexitSolveDecompstore(), SCIPgetDualbound(), SCIPlpInvalidateRootObjval(), SCIPlpReset(), SCIPnlpFree(), SCIPnodeFocus(), SCIPpricestoreFree(), SCIPprobExitSolve(), SCIPprobUpdateDualbound(), SCIPsepastoreFree(), SCIPsetExitsolPlugins(), SCIPstatResetCurrentRun(), SCIPtreeClear(), SCIPtreeGetFocusNode(), SCIPvisualExit(), and TRUE.

Referenced by SCIPfreeSolve(), and SCIPsolve().

◆ freeReoptSolve()

static SCIP_RETCODE freeReoptSolve ( SCIP * scip )

static

frees solution process data structures when reoptimization is used

in contrast to a freeSolve() this method will preserve the transformed problem such that another presolving round after changing the problem (modifying the objective function) is not necessary.

Parameters