Scippy

GCG

Branch-and-Price & Column Generation for Everyone

Detailed Description

This page contains a list of all relaxators which are currently available.

Files

file  relax_gcg.c
 GCG relaxator.
 
GCG_EXPORT SCIP_RETCODE SCIPincludeRelaxGcg (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxIncludeBranchrule (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_DECL_BRANCHACTIVEMASTER((*branchactivemaster)), GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster)), GCG_DECL_BRANCHPROPMASTER((*branchpropmaster)), GCG_DECL_BRANCHMASTERSOLVED((*branchmastersolved)), GCG_DECL_BRANCHDATADELETE((*branchdatadelete)))
 
GCG_EXPORT SCIP_RETCODE GCGrelaxBranchActiveMaster (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxBranchDeactiveMaster (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxBranchPropMaster (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_RESULT *result)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxBranchMasterSolved (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_Real newlowerbound)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxBranchDataDelete (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA **branchdata)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxTransOrigToMasterCons (SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
 
GCG_EXPORT SCIP_SOL * GCGrelaxGetCurrentOrigSol (SCIP *scip)
 
GCG_EXPORT SCIP_Bool GCGrelaxIsOrigSolFeasible (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxStartProbing (SCIP *scip, SCIP_HEUR *probingheur)
 
GCG_EXPORT SCIP_HEUR * GCGrelaxGetProbingheur (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxNewProbingnodeOrig (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxNewProbingnodeMaster (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxNewProbingnodeMasterCons (SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss, int maxorigbranchconss)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxBacktrackProbing (SCIP *scip, int probingdepth)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxPerformProbing (SCIP *scip, int maxlpiterations, SCIP_Longint *nlpiterations, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxPerformProbingWithPricing (SCIP *scip, int maxpricerounds, SCIP_Longint *nlpiterations, int *npricerounds, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxEndProbing (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGrelaxUpdateCurrentSol (SCIP *scip)
 
GCG_EXPORT DEC_DECMODE GCGgetDecompositionMode (SCIP *scip)
 
GCG_EXPORT DEC_DECMODE GCGgetMasterDecompMode (SCIP *masterprob)
 
GCG_EXPORT DEC_DECOMPGCGgetStructDecomp (SCIP *scip)
 
GCG_EXPORT GCG_PARAMDATAGCGgetParamsVisu (SCIP *scip)
 
GCG_EXPORT SCIP_CLOCK * GCGgetRootNodeTime (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGtransformProb (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGpresolve (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGdetect (SCIP *scip)
 
GCG_EXPORT SCIP_RETCODE GCGsolve (SCIP *scip)
 

Function Documentation

◆ SCIPincludeRelaxGcg()

◆ GCGrelaxIncludeBranchrule()

GCG_EXPORT SCIP_RETCODE GCGrelaxIncludeBranchrule ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_DECL_BRANCHACTIVEMASTER((*branchactivemaster))  ,
GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster))  ,
GCG_DECL_BRANCHPROPMASTER((*branchpropmaster))  ,
GCG_DECL_BRANCHMASTERSOLVED((*branchmastersolved))  ,
GCG_DECL_BRANCHDATADELETE((*branchdatadelete))   
)

includes a branching rule into the relaxator data

Definition at line 3539 of file relax_gcg.c.

References ensureSizeBranchrules(), and RELAX_NAME.

Referenced by SCIP_DECL_BRANCHINIT().

◆ GCGrelaxBranchActiveMaster()

GCG_EXPORT SCIP_RETCODE GCGrelaxBranchActiveMaster ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_BRANCHDATA branchdata 
)

perform activation method of the given branchrule for the given branchdata

Definition at line 3580 of file relax_gcg.c.

References RELAX_NAME.

Referenced by SCIP_DECL_CONSACTIVE().

◆ GCGrelaxBranchDeactiveMaster()

GCG_EXPORT SCIP_RETCODE GCGrelaxBranchDeactiveMaster ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_BRANCHDATA branchdata 
)

perform deactivation method of the given branchrule for the given branchdata

Definition at line 3618 of file relax_gcg.c.

References RELAX_NAME.

Referenced by SCIP_DECL_CONSDEACTIVE().

◆ GCGrelaxBranchPropMaster()

GCG_EXPORT SCIP_RETCODE GCGrelaxBranchPropMaster ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_BRANCHDATA branchdata,
SCIP_RESULT *  result 
)

perform propagation method of the given branchrule for the given branchdata

Definition at line 3656 of file relax_gcg.c.

References RELAX_NAME.

Referenced by SCIP_DECL_CONSPROP().

◆ GCGrelaxBranchMasterSolved()

GCG_EXPORT SCIP_RETCODE GCGrelaxBranchMasterSolved ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_BRANCHDATA branchdata,
SCIP_Real  newlowerbound 
)

perform method of the given branchrule that is called after the master LP is solved

Definition at line 3743 of file relax_gcg.c.

References RELAX_NAME.

Referenced by relaxExecGcgDantzigWolfe().

◆ GCGrelaxBranchDataDelete()

GCG_EXPORT SCIP_RETCODE GCGrelaxBranchDataDelete ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_BRANCHDATA **  branchdata 
)

frees branching data created by the given branchrule

Definition at line 3698 of file relax_gcg.c.

References GCGgetMasterprob(), and RELAX_NAME.

Referenced by SCIP_DECL_CONSDELETE().

◆ GCGrelaxTransOrigToMasterCons()

GCG_EXPORT SCIP_RETCODE GCGrelaxTransOrigToMasterCons ( SCIP *  scip,
SCIP_CONS *  cons,
SCIP_CONS **  transcons 
)

transformes a constraint of the original problem into the master variable space and adds it to the master problem

transforms a constraint of the original problem into the master variable space and stores information about the constraints in the variable

Definition at line 3783 of file relax_gcg.c.

References ensureSizeMasterConss(), GCGconsGetLhs(), GCGconsGetRhs(), GCGmasterAddMasterconsToHashmap(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), GCGoriginalVarAddCoef(), and RELAX_NAME.

Referenced by GCG_DECL_BRANCHACTIVEMASTER().

◆ GCGrelaxGetCurrentOrigSol()

GCG_EXPORT SCIP_SOL* GCGrelaxGetCurrentOrigSol ( SCIP *  scip)

returns the current solution for the original problem

Definition at line 4175 of file relax_gcg.c.

References RELAX_NAME.

Referenced by GCGbranchGenericInitbranch(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_SEPAEXECLP().

◆ GCGrelaxIsOrigSolFeasible()

GCG_EXPORT SCIP_Bool GCGrelaxIsOrigSolFeasible ( SCIP *  scip)

returns whether the current solution is primal feasible in the original problem

Definition at line 4194 of file relax_gcg.c.

References RELAX_NAME.

Referenced by SCIP_DECL_BRANCHEXECEXT(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_SEPAEXECLP().

◆ GCGrelaxStartProbing()

GCG_EXPORT SCIP_RETCODE GCGrelaxStartProbing ( SCIP *  scip,
SCIP_HEUR *  probingheur 
)

start probing mode on both the original and master problems

Note
This mode is intended for working on the original variables but using the master LP; it currently only supports bound changes on the original variables, but no additional rows

Definition at line 4256 of file relax_gcg.c.

References RELAX_NAME.

Referenced by applyProbing(), executeStrongBranching(), and SCIP_DECL_HEUREXEC().

◆ GCGrelaxGetProbingheur()

GCG_EXPORT SCIP_HEUR* GCGrelaxGetProbingheur ( SCIP *  scip)

returns the heuristic that started probing in the master problem, or NULL

Definition at line 4301 of file relax_gcg.c.

References RELAX_NAME.

Referenced by createOriginalProblemSolution(), and GCGtransformMastersolToOrigsol().

◆ GCGrelaxNewProbingnodeOrig()

GCG_EXPORT SCIP_RETCODE GCGrelaxNewProbingnodeOrig ( SCIP *  scip)

add a new probing node the original problem together with an original branching constraint

Note
A corresponding probing node must be added to the master problem right before solving the probing LP

Definition at line 4323 of file relax_gcg.c.

References GCGconsOrigbranchGetActiveCons(), GCGcreateConsOrigbranch(), GCGgetMasterprob(), and RELAX_NAME.

Referenced by applyProbing(), executeStrongBranching(), and SCIP_DECL_HEUREXEC().

◆ GCGrelaxNewProbingnodeMaster()

GCG_EXPORT SCIP_RETCODE GCGrelaxNewProbingnodeMaster ( SCIP *  scip)

add a new probing node the master problem together with a master branching constraint which ensures that bound changes are transferred to master and pricing problems

Note
A corresponding probing node must have been added to the original problem beforehand; furthermore, this method must be called after bound changes to the original problem have been made

Definition at line 4370 of file relax_gcg.c.

References GCGconsMasterbranchGetActiveCons(), GCGcreateConsMasterbranch(), and RELAX_NAME.

Referenced by applyProbing(), executeStrongBranching(), and SCIP_DECL_HEUREXEC().

◆ GCGrelaxNewProbingnodeMasterCons()

GCG_EXPORT SCIP_RETCODE GCGrelaxNewProbingnodeMasterCons ( SCIP *  scip,
SCIP_BRANCHRULE *  branchrule,
GCG_BRANCHDATA branchdata,
SCIP_CONS **  origbranchconss,
int  norigbranchconss,
int  maxorigbranchconss 
)

add a new probing node the master problem together with a master branching constraint which ensures that bound changes are transferred to master and pricing problems as well as additional constraints

Note
A corresponding probing node must have been added to the original problem beforehand; furthermore, this method must be called after bound changes to the original problem have been made

Definition at line 4422 of file relax_gcg.c.

References GCGconsMasterbranchGetActiveCons(), GCGcreateConsMasterbranch(), and RELAX_NAME.

Referenced by newProbingNodeRyanfosterMaster().

◆ GCGrelaxBacktrackProbing()

GCG_EXPORT SCIP_RETCODE GCGrelaxBacktrackProbing ( SCIP *  scip,
int  probingdepth 
)

add probing nodes to both the original and master problem; furthermore, add origbranch and masterbranch constraints to transfer branching decisions from the original to the master problem

Definition at line 4476 of file relax_gcg.c.

References RELAX_NAME.

Referenced by SCIP_DECL_HEUREXEC().

◆ GCGrelaxPerformProbing()

GCG_EXPORT SCIP_RETCODE GCGrelaxPerformProbing ( SCIP *  scip,
int  maxlpiterations,
SCIP_Longint *  nlpiterations,
SCIP_Real *  lpobjvalue,
SCIP_Bool *  lpsolved,
SCIP_Bool *  lperror,
SCIP_Bool *  cutoff 
)

solve the master probing LP without pricing

Definition at line 4612 of file relax_gcg.c.

References performProbing().

Referenced by executeStrongBranching(), and SCIP_DECL_HEUREXEC().

◆ GCGrelaxPerformProbingWithPricing()

GCG_EXPORT SCIP_RETCODE GCGrelaxPerformProbingWithPricing ( SCIP *  scip,
int  maxpricerounds,
SCIP_Longint *  nlpiterations,
int *  npricerounds,
SCIP_Real *  lpobjvalue,
SCIP_Bool *  lpsolved,
SCIP_Bool *  lperror,
SCIP_Bool *  cutoff 
)

solve the master probing LP with pricing

Definition at line 4631 of file relax_gcg.c.

References performProbing().

Referenced by applyProbing(), executeStrongBranching(), and SCIP_DECL_HEUREXEC().

◆ GCGrelaxEndProbing()

GCG_EXPORT SCIP_RETCODE GCGrelaxEndProbing ( SCIP *  scip)

end probing mode in both the original and master problems

Definition at line 4650 of file relax_gcg.c.

References GCGtransformMastersolToOrigsol(), RELAX_INCLUDESLP, and RELAX_NAME.

Referenced by applyProbing(), executeStrongBranching(), and SCIP_DECL_HEUREXEC().

◆ GCGrelaxUpdateCurrentSol()

GCG_EXPORT SCIP_RETCODE GCGrelaxUpdateCurrentSol ( SCIP *  scip)

transforms the current solution of the master problem into the original problem's space and saves this solution as currentsol in the relaxator's data

Definition at line 4788 of file relax_gcg.c.

References checkAndAddExternalBranchingCandidate(), DEC_DECMODE_BENDERS, DEC_DECMODE_DANTZIGWOLFE, GCGgetDecompositionMode(), GCGgetMasterprob(), GCGmasterIsSolValid(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvars(), GCGtransformMastersolToOrigsol(), RELAX_INCLUDESLP, and RELAX_NAME.

Referenced by performProbing(), SCIP_DECL_BENDERSPOSTSOLVE(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_SEPAEXECLP().

◆ GCGgetDecompositionMode()

◆ GCGgetMasterDecompMode()

GCG_EXPORT DEC_DECMODE GCGgetMasterDecompMode ( SCIP *  masterprob)

returns the decomposition mode of the master problem. The mode is given by the existence of either the GCG pricer or the GCG Benders' decomposition plugins.

Definition at line 5136 of file relax_gcg.c.

References DEC_DECMODE_BENDERS, DEC_DECMODE_DANTZIGWOLFE, DEC_DECMODE_ORIGINAL, and DEC_DECMODE_UNKNOWN.

Referenced by GCGcreateInitialMasterVar(), GCGmasterIsBestsolValid(), GCGmasterIsCurrentSolValid(), GCGmasterIsSolValid(), and SCIP_DECL_RELAXINITSOL().

◆ GCGgetStructDecomp()

GCG_EXPORT DEC_DECOMP* GCGgetStructDecomp ( SCIP *  scip)

gets the structure information

Parameters
scipSCIP data structure

Definition at line 2397 of file relax_gcg.c.

References RELAX_NAME.

Referenced by GCGprintStatistics(), and writeREFFile().

◆ GCGgetParamsVisu()

◆ GCGgetRootNodeTime()

GCG_EXPORT SCIP_CLOCK* GCGgetRootNodeTime ( SCIP *  scip)

return root node clock

return root node time clock

Definition at line 5173 of file relax_gcg.c.

References RELAX_NAME.

Referenced by GCGwriteSolvingDetails().

◆ GCGtransformProb()

GCG_EXPORT SCIP_RETCODE GCGtransformProb ( SCIP *  scip)

initializes solving data structures and transforms problem for solving with GCG

Returns
SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.
Precondition
This method can be called if scip is in one of the following stages:
  • SCIP_STAGE_PROBLEM
  • SCIP_STAGE_TRANSFORMED
  • SCIP_STAGE_INITPRESOLVE
  • SCIP_STAGE_PRESOLVING
  • SCIP_STAGE_EXITPRESOLVE
  • SCIP_STAGE_PRESOLVED
  • SCIP_STAGE_INITSOLVE
  • SCIP_STAGE_SOLVING
  • SCIP_STAGE_SOLVED
  • SCIP_STAGE_EXITSOLVE
  • SCIP_STAGE_FREETRANS
  • SCIP_STAGE_FREE
Postcondition
When calling this method in the SCIP_STAGE_PROBLEM stage, the SCIP stage is changed to SCIP_STAGE_TRANSFORMED; otherwise, the stage is not changed

See SCIP_STAGE for a complete list of all possible solving stages.

Parameters
scipSCIP data structure

Definition at line 5191 of file relax_gcg.c.

References SCIPconshdlrDecompRepairConsNames().

Referenced by fromCommandLine(), GCGdetect(), GCGpresolve(), GCGsolve(), and SCIP_DECL_DIALOGEXEC().

◆ GCGpresolve()

GCG_EXPORT SCIP_RETCODE GCGpresolve ( SCIP *  scip)

transforms and presolves the problem suitable for GCG

Returns
SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.
Precondition
This method can be called if scip is in one of the following stages:
  • SCIP_STAGE_PROBLEM
  • SCIP_STAGE_TRANSFORMED
  • SCIP_STAGE_PRESOLVING
  • SCIP_STAGE_PRESOLVED
Postcondition
After calling this method SCIP reaches one of the following stages:
  • SCIP_STAGE_PRESOLVING if the presolving process was interrupted
  • SCIP_STAGE_PRESOLVED if the presolving process was finished and did not solve the problem
  • SCIP_STAGE_SOLVED if the problem was solved during presolving

See SCIP_STAGE for a complete list of all possible solving stages.

Parameters
scipSCIP data structure

Definition at line 5229 of file relax_gcg.c.

References GCGconshdlrDecompTranslateOrigPartialdecs(), and GCGtransformProb().

Referenced by GCGsolve(), and SCIP_DECL_DIALOGEXEC().

◆ GCGdetect()

GCG_EXPORT SCIP_RETCODE GCGdetect ( SCIP *  scip)

transforms and detects the problem

Returns
SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.
Precondition
This method can be called if scip is in one of the following stages:
  • SCIP_STAGE_PROBLEM
  • SCIP_STAGE_TRANSFORMED
  • SCIP_STAGE_PRESOLVING
  • SCIP_STAGE_PRESOLVED
Postcondition
When calling this method in the SCIP_STAGE_PROBLEM stage, the SCIP stage is changed to SCIP_STAGE_TRANSFORMED; otherwise, the stage is not changed

See SCIP_STAGE for a complete list of all possible solving stages.

Parameters
scipSCIP data structure

Definition at line 5275 of file relax_gcg.c.

References DECdetectStructure(), GCGdetectionTookPlace(), and GCGtransformProb().

Referenced by SCIP_DECL_DIALOGEXEC().

◆ GCGsolve()

GCG_EXPORT SCIP_RETCODE GCGsolve ( SCIP *  scip)

transforms, resolves, detects, and solves the problem using GCG

Returns
SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.
Precondition
This method can be called if scip is in one of the following stages:
  • SCIP_STAGE_PROBLEM
  • SCIP_STAGE_TRANSFORMED
  • SCIP_STAGE_PRESOLVING
  • SCIP_STAGE_PRESOLVED
  • SCIP_STAGE_SOLVING
  • SCIP_STAGE_SOLVED
Postcondition
After calling this method SCIP reaches one of the following stages depending on if and when the solution process was interrupted:
  • SCIP_STAGE_PRESOLVING if the solution process was interrupted during presolving
  • SCIP_STAGE_SOLVING if the solution process was interrupted during the tree search
  • SCIP_STAGE_SOLVED if the solving process was not interrupted

See SCIP_STAGE for a complete list of all possible solving stages.

Parameters
scipSCIP data structure

Definition at line 5333 of file relax_gcg.c.

References DECdecompFree(), DECdetectStructure(), DECgetBestDecomp(), GCGconshdlrDecompCheckConsistency(), GCGconshdlrDecompGetNFinishedPartialdecsTransformed(), GCGconshdlrDecompOrigPartialdecExists(), GCGdetectionTookPlace(), GCGpresolve(), and GCGtransformProb().

Referenced by fromCommandLine(), and SCIP_DECL_DIALOGEXEC().