Scippy

SCIP

Solving Constraint Integer Programs

scip_solve.c File Reference

Detailed Description

public solving methods

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

Definition in file scip_solve.c.

#include <ctype.h>
#include <stdarg.h>
#include <assert.h>
#include <string.h>
#include <strings.h>
#include "lpi/lpi.h"
#include "nlpi/exprinterpret.h"
#include "nlpi/nlpi.h"
#include "scip/benders.h"
#include "scip/benderscut.h"
#include "scip/branch.h"
#include "scip/branch_nodereopt.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/cons_linear.h"
#include "scip/cutpool.h"
#include "scip/cuts.h"
#include "scip/debug.h"
#include "scip/def.h"
#include "scip/dialog.h"
#include "scip/dialog_default.h"
#include "scip/disp.h"
#include "scip/event.h"
#include "scip/heur.h"
#include "scip/heur_ofins.h"
#include "scip/heur_reoptsols.h"
#include "scip/heur_trivialnegation.h"
#include "scip/heuristics.h"
#include "scip/history.h"
#include "scip/implics.h"
#include "scip/interrupt.h"
#include "scip/lp.h"
#include "scip/mem.h"
#include "scip/message_default.h"
#include "scip/misc.h"
#include "scip/nlp.h"
#include "scip/nodesel.h"
#include "scip/paramset.h"
#include "scip/presol.h"
#include "scip/presolve.h"
#include "scip/pricer.h"
#include "scip/pricestore.h"
#include "scip/primal.h"
#include "scip/prob.h"
#include "scip/prop.h"
#include "scip/reader.h"
#include "scip/relax.h"
#include "scip/reopt.h"
#include "scip/retcode.h"
#include "scip/scipbuildflags.h"
#include "scip/scipcoreplugins.h"
#include "scip/scipgithash.h"
#include "scip/sepa.h"
#include "scip/sepastore.h"
#include "scip/set.h"
#include "scip/sol.h"
#include "scip/solve.h"
#include "scip/stat.h"
#include "scip/syncstore.h"
#include "scip/table.h"
#include "scip/tree.h"
#include "scip/var.h"
#include "scip/visual.h"
#include "xml/xml.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/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/struct_scip.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_SOLSCIPgetReoptLastOptSol (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:

  1. variable bounds
  2. constraint handlers with positive or zero priority that don't need constraints (e.g. integral constraint handler)
  3. original constraints
  4. constraint handlers with negative priority that don't need constraints (e.g. Benders' decomposition constraint handler)
Parameters
scipSCIP data structure
solprimal CIP solution
feasiblestores whether given solution is feasible
printreasonShould the reason for the violation be printed?
completelyShould all violations be checked?
checkboundsShould the bounds of the variables be checked?
checkintegralityHas integrality to be checked?
checklprowsDo constraints represented by rows in the current LP have to be checked?
checkmodifiablehave modifiable constraint to be checked?

Definition at line 158 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
scipSCIP data structure
nchecknonzerospointer to store number of non-zeros in all check constraints
nactivenonzerospointer to store number of non-zeros in all active constraints
approxchecknonzerospointer to store if the number of non-zeros in all check constraints is only a lowerbound
approxactivenonzerospointer to store if the number of non-zeros in all active constraints is only a lowerbound

Definition at line 296 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()

◆ exitPresolve()

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

◆ 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
scipSCIP data structure
timingpointer to current presolving timing
unboundedpointer to store whether presolving detected unboundedness
infeasiblepointer to store whether presolving detected infeasibility
lastroundis this the last presolving round due to a presolving round limit?
presolstartpointer to get the presolver to start exhaustive presolving with in the current round and store the one to start with in the next round
presolendlast presolver to treat in exhaustive presolving
propstartpointer to get the propagator to start exhaustive presolving with in the current round and store the one to start with in the next round
propendlast propagator to treat in exhaustive presolving
consstartpointer 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
consendlast constraint handler to treat in exhaustive presolving

Definition at line 835 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
scipSCIP data structure
unboundedpointer to store whether presolving detected unboundedness
infeasiblepointer to store whether presolving detected infeasibility

Definition at line 1290 of file scip_solve.c.

References BMSgetNUsedBufferMemory(), calcNonZeros(), Scip::cliquetable, SCIP_Set::disp_verblevel, Scip::eventqueue, exitPresolve(), FALSE, initPresolve(), SCIP_Stat::lastnpresoladdconss, SCIP_Stat::lastnpresoladdholes, SCIP_Stat::lastnpresolaggrvars, SCIP_Stat::lastnpresolchgbds, SCIP_Stat::lastnpresolchgcoefs, SCIP_Stat::lastnpresolchgsides, SCIP_Stat::lastnpresolchgvartypes, SCIP_Stat::lastnpresoldelconss, SCIP_Stat::lastnpresolfixedvars, SCIP_Stat::lastnpresolupgdconss, Scip::lp, MAX, Scip::mem, Scip::messagehdlr, SCIP_Set::nconshdlrs, SCIP_Set::nheurs, SCIP_Stat::nimplications, SCIP_Primal::nlimsolsfound, SCIP_Stat::nnz, 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, SCIP_Stat::nreoptruns, SCIP_Primal::nsols, NULL, Scip::origprob, SCIP_Stat::performpresol, SCIP_Set::presol_maxrounds, presolveRound(), SCIP_Stat::presolvingtime, SCIP_Stat::presolvingtimeoverall, Scip::primal, SCIP_Mem::probmem, Scip::reopt, SCIP_Set::reopt_enable, 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_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIP_VERBLEVEL_NORMAL, SCIPbuffer(), SCIPcleanbuffer(), SCIPcliquetableGetNCliques(), SCIPclockStart(), SCIPclockStop(), SCIPdebugMsg, SCIPgetBestSol(), SCIPgetNConss(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetSolvingTime(), SCIPheurGetName(), SCIPisInfinity(), SCIPisPresolveFinished(), SCIPmessagePrintVerbInfo(), SCIPprimalHeuristics(), SCIPprimalUpdateObjlimit(), SCIPprobMarkNConss(), SCIPprobResortVars(), SCIPsetSortPresols(), SCIPsetSortPropsPresol(), SCIPsolGetHeur(), SCIPsolveIsStopped(), Scip::set, SCIP_Set::stage, Scip::stat, SCIP_Stat::status, Scip::transprob, Scip::tree, and TRUE.

Referenced by SCIPpresolve().

◆ transformSols()

◆ initSolve()

static SCIP_RETCODE initSolve ( SCIP scip,
SCIP_Bool  solved 
)
static

initializes solution process data structures

Parameters
scipSCIP data structure
solvedis problem already solved?

Definition at line 1613 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(), 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()

◆ 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
scipSCIP data structure

Definition at line 1844 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_Set::misc_resetstat, Scip::nlp, SCIP_Prob::nlpenabled, NULL, Scip::origprob, Scip::pricestore, Scip::primal, SCIP_Mem::probmem, Scip::relaxation, Scip::reopt, SCIP_Set::reopt_enable, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_STAGE_EXITSOLVE, SCIP_STAGE_PRESOLVED, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIPconflictstoreClear(), SCIPcutpoolClear(), SCIPcutpoolFree(), SCIPdebugReset, SCIPlpInvalidateRootObjval(), SCIPlpReset(), SCIPnlpFree(), SCIPnodeFocus(), SCIPpricestoreFree(), SCIPprimalClear(), SCIPprobExitSolve(), SCIPprobInvalidateDualbound(), SCIPrelaxationFree(), SCIPreoptReset(), SCIPsepastoreFree(), SCIPsetExitPlugins(), SCIPsetExitsolPlugins(), SCIPsetObjlimit(), SCIPstatReset(), SCIPstatResetCurrentRun(), SCIPstatResetPrimalDualIntegral(), SCIPtreeClear(), SCIPtreeGetFocusNode(), SCIPvisualExit(), Scip::sepastore, Scip::sepastoreprobing, Scip::set, SCIP_Set::stage, Scip::stat, Scip::transprob, Scip::tree, TRUE, and SCIP_Stat::visual.

Referenced by SCIPfreeReoptSolve().

◆ freeTransform()

static SCIP_RETCODE freeTransform ( SCIP scip)
static

◆ displayRelevantStats()

◆ compressReoptTree()

◆ prepareReoptimization()