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_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	checkSolOrig (SCIP scip, SCIP_SOL sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool checkmodifiable)

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)

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	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_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

◆ checkSolOrig()

static SCIP_RETCODE checkSolOrig	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_Bool *	feasible,
		SCIP_Bool	printreason,
		SCIP_Bool	completely,
		SCIP_Bool	checkbounds,
		SCIP_Bool	checkintegrality,
		SCIP_Bool	checklprows,
		SCIP_Bool	checkmodifiable
	)

static

checks solution for feasibility in original problem without adding it to the solution store; to improve the performance we use the following order when checking for violations:

variable bounds
constraint handlers with positive or zero priority that don't need constraints (e.g. integral constraint handler)
original constraints
constraint handlers with negative priority that don't need constraints (e.g. Benders' decomposition constraint handler)

Parameters

scip	SCIP data structure
sol	primal CIP solution
feasible	stores whether given solution is feasible
printreason	Should the reason for the violation be printed?
completely	Should all violations be checked?
checkbounds	Should the bounds of the variables be checked?
checkintegrality	Has integrality to be checked?
checklprows	Do constraints represented by rows in the current LP have to be checked?
checkmodifiable	have modifiable constraint to be checked?

Definition at line 115 of file scip_solve.c.

References SCIP_Set::conshdlrs, SCIP_Prob::conss, FALSE, h, Scip::mem, Scip::messagehdlr, SCIP_Set::nconshdlrs, SCIP_Prob::nconss, NULL, SCIP_Prob::nvars, Scip::origprob, SCIP_Mem::probmem, SCIP_CALL, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPcheckStage(), SCIPconsCheck(), SCIPconshdlrCheck(), SCIPconshdlrGetCheckPriority(), SCIPconshdlrNeedsCons(), SCIPconsIsChecked(), SCIPconsIsModifiable(), SCIPmessagePrintInfo(), SCIPrelDiff(), SCIPsetIsFeasGT(), SCIPsetIsFeasLT(), SCIPsolGetVal(), SCIPsolResetViolations(), SCIPupdateSolBoundViolation(), SCIPvarGetLbOriginal(), SCIPvarGetName(), SCIPvarGetUbOriginal(), Scip::set, Scip::stat, TRUE, and SCIP_Prob::vars.

Referenced by SCIPtransformProb().

◆ 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 253 of file scip_solve.c.

References SCIP_Set::conshdlrs, FALSE, h, SCIP_Set::nconshdlrs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetNVars(), SCIPconshdlrGetCheckConss(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconshdlrGetNCheckConss(), SCIPconsIsActive(), SCIPconsIsChecked(), Scip::set, 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 576 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), Scip::branchcand, Scip::cliquetable, Scip::conflict, Scip::conflictstore, Scip::eventfilter, Scip::eventqueue, Scip::lp, Scip::mem, Scip::messagehdlr, SCIP_Stat::nruns, NULL, SCIP_Prob::nvars, Scip::origprob, SCIP_Stat::prevrunnvars, Scip::primal, SCIP_Mem::probmem, Scip::reopt, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_PRESOLVING, SCIP_STAGE_TRANSFORMED, SCIPbuffer(), SCIPcleanbuffer(), SCIPprimalRetransformSolutions(), SCIPprobPerformVarDeletions(), SCIPsetInitprePlugins(), SCIPstatResetPresolving(), SCIPtreeCreatePresolvingRoot(), Scip::set, SCIP_Set::stage, Scip::stat, Scip::transprob, and Scip::tree.

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 640 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), Scip::branchcand, Scip::cliquetable, Scip::conflict, Scip::conflictstore, SCIP_Set::disp_verblevel, SCIP_Prob::dualbound, Scip::eventfilter, Scip::eventqueue, FALSE, SCIP_Stat::lastlowerbound, Scip::lp, Scip::mem, Scip::messagehdlr, SCIP_Set::misc_calcintegral, NULL, Scip::origprob, Scip::primal, SCIP_Mem::probmem, Scip::reopt, 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(), SCIPvarGetStatus(), Scip::set, SCIP_Set::stage, Scip::stat, Scip::transprob, and Scip::tree.

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 793 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), Scip::branchcand, Scip::cliquetable, SCIP_Set::conshdlrs, SCIP_Set::disp_verblevel, Scip::eventfilter, Scip::eventqueue, FALSE, Scip::lp, Scip::mem, Scip::messagehdlr, SCIP_Set::nconshdlrs, SCIP_Set::nheurs, SCIP_Stat::npresoladdconss, SCIP_Stat::npresoladdholes, SCIP_Stat::npresolaggrvars, SCIP_Stat::npresolchgbds, SCIP_Stat::npresolchgcoefs, SCIP_Stat::npresolchgsides, SCIP_Stat::npresolchgvartypes, SCIP_Stat::npresoldelconss, SCIP_Stat::npresolfixedvars, SCIP_Stat::npresolrounds, SCIP_Stat::npresolroundsext, SCIP_Stat::npresolroundsfast, SCIP_Stat::npresolroundsmed, SCIP_Set::npresols, SCIP_Stat::npresolupgdconss, SCIP_Set::nprops, NULL, Scip::origprob, SCIP_Set::presols, Scip::primal, SCIP_Mem::probmem, SCIP_Set::props_presol, SCIP_Set::propspresolsorted, Scip::reopt, 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(), Scip::set, Scip::stat, Scip::transprob, Scip::tree, and TRUE.

Referenced by presolve().

◆ presolve()

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

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

Definition at line 1248 of file scip_solve.c.

Referenced by SCIPincludePresolMILP(), 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 1496 of file scip_solve.c.

References Scip::eventfilter, Scip::eventqueue, Scip::lp, Scip::mem, Scip::messagehdlr, SCIP_Stat::nexternalsolsfound, SCIP_Primal::nsolsfound, NULL, SCIP_Prob::nvars, Scip::origprob, Scip::primal, SCIP_Mem::probmem, Scip::reopt, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNSols(), SCIPgetSols(), SCIPprimalTransformSol(), SCIPsolIsOriginal(), SCIPverbMessage(), Scip::set, Scip::stat, Scip::transprob, and Scip::tree.

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 1571 of file scip_solve.c.

References SCIP_Primal::cutoffbound, Scip::cutpool, Scip::delayedcutpool, SCIP_Prob::dualbound, Scip::eventfilter, Scip::eventqueue, FALSE, SCIP_Stat::lastlowerbound, Scip::lp, Scip::mem, Scip::messagehdlr, SCIP_Set::misc_transorigsols, SCIP_Set::nactivepricers, Scip::nlp, SCIP_Set::nlp_disable, SCIP_Prob::nlpenabled, NULL, SCIP_Prob::nvars, Scip::origprob, Scip::pricestore, Scip::primal, SCIP_Mem::probmem, REALABS, Scip::reopt, SCIP_CALL, SCIP_INVALID, 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(), SCIP_Set::sepa_cutagelimit, Scip::sepastore, Scip::sepastoreprobing, Scip::set, SCIP_Set::stage, Scip::stat, transformSols(), Scip::transprob, Scip::tree, TRUE, SCIP_Prob::vars, and SCIP_Stat::visual.

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 1704 of file scip_solve.c.

References Scip::branchcand, Scip::cliquetable, Scip::conflict, Scip::conflictstore, Scip::cutpool, Scip::delayedcutpool, Scip::eventfilter, Scip::eventqueue, FALSE, SCIP_Stat::inrestart, Scip::lp, Scip::mem, Scip::messagehdlr, Scip::nlp, SCIP_Prob::nlpenabled, NULL, Scip::origprob, Scip::pricestore, Scip::primal, SCIP_Mem::probmem, Scip::reopt, 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(), Scip::sepastore, Scip::sepastoreprobing, Scip::set, SCIP_Set::stage, Scip::stat, SCIP_Stat::status, Scip::transprob, Scip::tree, TRUE, and SCIP_Stat::visual.

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