Scippy

GCG

Branch-and-Price & Column Generation for Everyone

sepa_basis.c File Reference

Detailed Description

basis separator

Author
Jonas Witt

Definition in file sepa_basis.c.

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "sepa_basis.h"
#include "sepa_master.h"
#include "gcg.h"
#include "relax_gcg.h"
#include "pricer_gcg.h"
#include "pub_gcgvar.h"

Go to the source code of this file.

Data Structures

struct  SCIP_SepaData
 

Macros

#define SEPA_NAME   "basis"
 
#define SEPA_DESC   "separator calculates a basis of the orig problem to generate cuts, which cut off the master lp sol"
 
#define SEPA_PRIORITY   100
 
#define SEPA_FREQ   0
 
#define SEPA_MAXBOUNDDIST   1.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   TRUE
 
#define STARTMAXCUTS   50
 
#define sepaCopyBasis   NULL
 
#define sepaExecsolBasis   NULL
 

Functions

static SCIP_RETCODE ensureSizeCuts (SCIP *scip, SCIP_SEPADATA *sepadata, int size)
 
static SCIP_RETCODE ensureSizeNewCuts (SCIP *scip, SCIP_SEPADATA *sepadata, int size)
 
static SCIP_RETCODE chgProbingObjUsingRows (SCIP *origscip, SCIP_SEPADATA *sepadata, SCIP_SOL *origsol, SCIP_Real objfactor, SCIP_Real objdivisor)
 
static SCIP_RETCODE addPPObjConss (SCIP *scip, SCIP_SEPA *sepa, int ppnumber, SCIP_Real dualsolconv, SCIP_Bool newcuts, SCIP_Bool probing)
 
static SCIP_DECL_SEPAFREE (sepaFreeBasis)
 
static SCIP_DECL_SEPAINIT (sepaInitBasis)
 
static SCIP_DECL_SEPAEXIT (sepaExitBasis)
 
static SCIP_DECL_SEPAINITSOL (sepaInitsolBasis)
 
static SCIP_DECL_SEPAEXITSOL (sepaExitsolBasis)
 
static SCIP_RETCODE initGenconv (SCIP *origscip, SCIP_SEPADATA *sepadata, SCIP_SOL *origsol, int nbasis, SCIP_Real *convex)
 
static SCIP_RETCODE initConvObj (SCIP *origscip, SCIP_SEPADATA *sepadata, SCIP_SOL *origsol, SCIP_Real convex, SCIP_Bool genericconv)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpBasis)
 
SCIP_RETCODE SCIPincludeSepaBasis (SCIP *scip)
 
SCIP_ROW ** GCGsepaBasisGetOrigcuts (SCIP *scip)
 
int GCGsepaBasisGetNOrigcuts (SCIP *scip)
 
SCIP_ROW ** GCGsepaBasisGetMastercuts (SCIP *scip)
 
int GCGsepaBasisGetNMastercuts (SCIP *scip)
 
SCIP_RETCODE GCGsepaBasisAddPricingCut (SCIP *scip, int ppnumber, SCIP_ROW *cut)
 
SCIP_RETCODE SCIPsepaBasisAddPPObjConss (SCIP *scip, int ppnumber, SCIP_Real dualsolconv, SCIP_Bool newcuts)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "basis"

Definition at line 57 of file sepa_basis.c.

◆ SEPA_DESC

#define SEPA_DESC   "separator calculates a basis of the orig problem to generate cuts, which cut off the master lp sol"

Definition at line 58 of file sepa_basis.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   100

Definition at line 59 of file sepa_basis.c.

◆ SEPA_FREQ

#define SEPA_FREQ   0

Definition at line 60 of file sepa_basis.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 61 of file sepa_basis.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 62 of file sepa_basis.c.

◆ SEPA_DELAY

#define SEPA_DELAY   TRUE

should separation method be delayed, if other separators found cuts?

Definition at line 63 of file sepa_basis.c.

◆ STARTMAXCUTS

#define STARTMAXCUTS   50

maximal cuts used at the beginning

Definition at line 65 of file sepa_basis.c.

◆ sepaCopyBasis

#define sepaCopyBasis   NULL

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 808 of file sepa_basis.c.

◆ sepaExecsolBasis

#define sepaExecsolBasis   NULL

arbitrary primal solution separation method of separator

Definition at line 1585 of file sepa_basis.c.

Function Documentation

◆ ensureSizeCuts()

static SCIP_RETCODE ensureSizeCuts ( SCIP *  scip,
SCIP_SEPADATA *  sepadata,
int  size 
)
static

allocates enough memory to hold more cuts

Parameters
scipSCIP data structure
sepadataseparator data data structure
sizenew size of cut arrays

Definition at line 113 of file sepa_basis.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ ensureSizeNewCuts()

static SCIP_RETCODE ensureSizeNewCuts ( SCIP *  scip,
SCIP_SEPADATA *  sepadata,
int  size 
)
static

allocates enough memory to hold more new cuts

Parameters
scipSCIP data structure
sepadataseparator data data structure
sizenew size of cut arrays

Definition at line 142 of file sepa_basis.c.

Referenced by addPPObjConss(), GCGsepaBasisAddPricingCut(), and SCIP_DECL_SEPAEXECLP().

◆ chgProbingObjUsingRows()

static SCIP_RETCODE chgProbingObjUsingRows ( SCIP *  origscip,
SCIP_SEPADATA *  sepadata,
SCIP_SOL *  origsol,
SCIP_Real  objfactor,
SCIP_Real  objdivisor 
)
static
Parameters
origsciporig scip problem
sepadataseparator data
origsolorig solution
objfactorfactor the objective is multiplied with
objdivisorfactor the objective is divided with

Definition at line 362 of file sepa_basis.c.

Referenced by initConvObj().

◆ addPPObjConss()

static SCIP_RETCODE addPPObjConss ( SCIP *  scip,
SCIP_SEPA *  sepa,
int  ppnumber,
SCIP_Real  dualsolconv,
SCIP_Bool  newcuts,
SCIP_Bool  probing 
)
static

add cuts based on the last objective function of the pricing problems, which did not yield any new columns (stating that the reduced cost are non-negative)

Parameters
scipSCIP data structure
sepaseparator basis
ppnumbernumber of pricing problem
dualsolconvdual solution corresponding to convexity constraint
newcutsadd cut to newcuts in sepadata? (otherwise add it just to the cutpool)
probingadd cut to probing LP?

Definition at line 709 of file sepa_basis.c.

References ensureSizeNewCuts(), GCGgetNIdenticalBlocks(), GCGgetPricingprob(), GCGisPricingprobRelevant(), GCGpricingVarGetOrigvars(), and GCGvarIsPricing().

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIPsepaBasisAddPPObjConss().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeBasis  )
static

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

Definition at line 812 of file sepa_basis.c.

◆ SCIP_DECL_SEPAINIT()

static SCIP_DECL_SEPAINIT ( sepaInitBasis  )
static

initialization method of separator (called after problem was transformed)

Definition at line 826 of file sepa_basis.c.

References GCGmasterGetOrigprob(), and STARTMAXCUTS.

◆ SCIP_DECL_SEPAEXIT()

static SCIP_DECL_SEPAEXIT ( sepaExitBasis  )
static

deinitialization method of separator (called before transformed problem is freed)

Definition at line 893 of file sepa_basis.c.

References GCGmasterGetOrigprob().

◆ SCIP_DECL_SEPAINITSOL()

static SCIP_DECL_SEPAINITSOL ( sepaInitsolBasis  )
static

solving process initialization method of separator (called when branch and bound process is about to begin)

Definition at line 932 of file sepa_basis.c.

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolBasis  )
static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 947 of file sepa_basis.c.

References GCGmasterGetOrigprob().

◆ initGenconv()

static SCIP_RETCODE initGenconv ( SCIP *  origscip,
SCIP_SEPADATA *  sepadata,
SCIP_SOL *  origsol,
int  nbasis,
SCIP_Real *  convex 
)
static

Initialize generic convex combination coefficient

Parameters
origsciporiginal SCIP data structure
sepadataseparator data structure
origsolcurrent original solution
nbasisrank of constraint matrix
convexpointer to store convex combination coefficient

Definition at line 969 of file sepa_basis.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ initConvObj()

static SCIP_RETCODE initConvObj ( SCIP *  origscip,
SCIP_SEPADATA *  sepadata,
SCIP_SOL *  origsol,
SCIP_Real  convex,
SCIP_Bool  genericconv 
)
static

Initialize objective as convex combination of so-called face objective function and original objective function

Parameters
origsciporiginal SCIP data structure
sepadataseparator data structure
origsolcurrent original solution
convexconvex coefficient to initialize objective
genericconvwas convex coefficient calculated generically?

Definition at line 1000 of file sepa_basis.c.

References chgProbingObjUsingRows().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIPincludeSepaBasis()

SCIP_RETCODE SCIPincludeSepaBasis ( SCIP *  scip)

creates the basis separator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 1592 of file sepa_basis.c.

References GCGmasterGetOrigprob(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, SEPA_USESSUBSCIP, sepaCopyBasis, and sepaExecsolBasis.

Referenced by GCGincludeMasterPlugins().

◆ GCGsepaBasisGetOrigcuts()

SCIP_ROW** GCGsepaBasisGetOrigcuts ( SCIP *  scip)

returns the array of original cuts saved in the separator data

Parameters
scipSCIP data structure

Definition at line 1683 of file sepa_basis.c.

References SEPA_NAME.

◆ GCGsepaBasisGetNOrigcuts()

int GCGsepaBasisGetNOrigcuts ( SCIP *  scip)

returns the number of original cuts saved in the separator data

Parameters
scipSCIP data structure

Definition at line 1702 of file sepa_basis.c.

References SEPA_NAME.

◆ GCGsepaBasisGetMastercuts()

SCIP_ROW** GCGsepaBasisGetMastercuts ( SCIP *  scip)

returns the array of master cuts saved in the separator data

Parameters
scipSCIP data structure

Definition at line 1721 of file sepa_basis.c.

References SEPA_NAME.

◆ GCGsepaBasisGetNMastercuts()

int GCGsepaBasisGetNMastercuts ( SCIP *  scip)

returns the number of master cuts saved in the separator data

Parameters
scipSCIP data structure

Definition at line 1740 of file sepa_basis.c.

References SEPA_NAME.

◆ GCGsepaBasisAddPricingCut()

SCIP_RETCODE GCGsepaBasisAddPricingCut ( SCIP *  scip,
int  ppnumber,
SCIP_ROW *  cut 
)

transforms cut in pricing variables to cut in original variables and adds it to newcuts array

Definition at line 1759 of file sepa_basis.c.

References ensureSizeNewCuts(), GCGgetNIdenticalBlocks(), GCGgetPricingprob(), GCGisMaster(), GCGmasterGetOrigprob(), GCGpricingVarGetOrigvars(), GCGvarIsPricing(), and SEPA_NAME.

Referenced by ObjPricerGcg::pricingLoop().

◆ SCIPsepaBasisAddPPObjConss()

SCIP_RETCODE SCIPsepaBasisAddPPObjConss ( SCIP *  scip,
int  ppnumber,
SCIP_Real  dualsolconv,
SCIP_Bool  newcuts 
)

add cuts which are due to the latest objective function of the pricing problems (reduced cost non-negative)

Parameters
scipSCIP data structure
ppnumbernumber of pricing problem
dualsolconvdual solution corresponding to convexity constraint
newcutsadd cut to newcuts in sepadata? (otherwise add it just to the cutpool)

Definition at line 1869 of file sepa_basis.c.

References addPPObjConss(), GCGisMaster(), GCGmasterGetOrigprob(), and SEPA_NAME.

Referenced by ObjPricerGcg::pricingLoop().