Scippy

SCIP

Solving Constraint Integer Programs

pricer_rpa.c File Reference

Detailed Description

Ringpacking variable pricer.

Author
Benjamin Mueller

This file implements the variable pricer which checks if variables negative reduced cost exist. See Pricing new variables for more details.

Definition in file pricer_rpa.c.

#include <assert.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include "scip/scipdefplugins.h"
#include "scip/scip.h"
#include "pricer_rpa.h"
#include "probdata_rpa.h"
#include "pattern.h"

Go to the source code of this file.

Macros

#define M_PI   3.141592653589793238462643
 
Pricer properties
#define PRICER_NAME   "ringpacking"
 
#define PRICER_DESC   "pricer for ringpacking"
 
#define PRICER_PRIORITY   0
 
#define PRICER_DELAY   TRUE /* only call pricer if all problem variables have non-negative reduced costs */
 
#define DEFAULT_PRICING_NLPTILIM   1e+20
 
#define DEFAULT_PRICING_NLPNODELIM   1000L
 
#define DEFAULT_PRICING_HEURTILIM   1e+20
 
#define DEFAULT_PRICING_HEURITERLIM   1000
 
#define DEFAULT_PRICING_TOTALTILIM   1e+20
 

Functions

Local methods
static SCIP_Real getDensityUb (int n)
 
static int getNCircles (SCIP *scip, SCIP_Real rext, int demand, SCIP_Real width, SCIP_Real height, SCIP_Real lambda)
 
static SCIP_RETCODE addVariable (SCIP *scip, SCIP_PROBDATA *probdata, int *types, SCIP_Real *xs, SCIP_Real *ys, SCIP_Bool *ispacked, int nelems)
 
static SCIP_RETCODE extractVariablesMINLP (SCIP *scip, SCIP_PROBDATA *probdata, SCIP *subscip, SCIP_VAR **x, SCIP_VAR **y, SCIP_VAR **w, int *types, int nvars, SCIP_Bool *success)
 
static void computeScores (SCIP *scip, SCIP_Real *rexts, SCIP_RANDNUMGEN *randnumgen, int *elements, int nelements, SCIP_Real *lambdas, SCIP_Real *scores, int iter, int iterlim)
 
static SCIP_RETCODE solvePricingHeuristic (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PRICERDATA *pricerdata, SCIP_Real *lambdas, SCIP_Real timelim, int iterlim, SCIP_Bool *addedvar)
 
static SCIP_RETCODE solvePricingMINLP (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real *lambdas, SCIP_Real timelim, SCIP_Longint nodelim, SCIP_Bool *addedvar, SCIP_STATUS *solstat, SCIP_Real *dualbound)
 
static SCIP_DECL_PRICERFREE (pricerFreeRingpacking)
 
static SCIP_DECL_PRICERINIT (pricerInitRingpacking)
 
static SCIP_DECL_PRICEREXIT (pricerExitRingpacking)
 
static SCIP_DECL_PRICERREDCOST (pricerRedcostRingpacking)
 
static SCIP_DECL_PRICERFARKAS (pricerFarkasRingpacking)
 
Interface methods
SCIP_RETCODE SCIPincludePricerRpa (SCIP *scip)
 
SCIP_RETCODE SCIPpricerRpaActivate (SCIP *scip)
 

Macro Definition Documentation

◆ PRICER_NAME

#define PRICER_NAME   "ringpacking"

Definition at line 73 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa(), and SCIPpricerRpaActivate().

◆ PRICER_DESC

#define PRICER_DESC   "pricer for ringpacking"

Definition at line 74 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ PRICER_PRIORITY

#define PRICER_PRIORITY   0

Definition at line 75 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ PRICER_DELAY

#define PRICER_DELAY   TRUE /* only call pricer if all problem variables have non-negative reduced costs */

Definition at line 76 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ DEFAULT_PRICING_NLPTILIM

#define DEFAULT_PRICING_NLPTILIM   1e+20

time limit for each pricing NLP

Definition at line 79 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ DEFAULT_PRICING_NLPNODELIM

#define DEFAULT_PRICING_NLPNODELIM   1000L

node limit for each pricing NLP

Definition at line 80 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ DEFAULT_PRICING_HEURTILIM

#define DEFAULT_PRICING_HEURTILIM   1e+20

time limit for each heuristic pricing

Definition at line 81 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ DEFAULT_PRICING_HEURITERLIM

#define DEFAULT_PRICING_HEURITERLIM   1000

iteration limit for each heuristic pricing

Definition at line 82 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ DEFAULT_PRICING_TOTALTILIM

#define DEFAULT_PRICING_TOTALTILIM   1e+20

total time limit for all pricing NLPs and heuristic calls

Definition at line 83 of file pricer_rpa.c.

Referenced by SCIPincludePricerRpa().

◆ M_PI

Function Documentation

◆ getDensityUb()

static SCIP_Real getDensityUb ( int  n)
static

returns an upper bound on the density for n equal circles in a square (holds also for rectangles); this is a result of Groemer's formula (see, 'Ueber die Einlagerung von Kreisen in einen konvexen Bereich')

Definition at line 118 of file pricer_rpa.c.

References M_PI, SQR, and SQRT.

Referenced by getNCircles().

◆ getNCircles()

static int getNCircles ( SCIP scip,
SCIP_Real  rext,
int  demand,
SCIP_Real  width,
SCIP_Real  height,
SCIP_Real  lambda 
)
static

helper function to count how many circles of a given type are needed

Parameters
scipSCIP data structure
rextexternal radius
demanddemand
widthwidth of the rectangle
heightheight of the rectangle
lambdaobjective coefficient of each circle of the given type

Definition at line 128 of file pricer_rpa.c.

References getDensityUb(), M_PI, MIN, ncircles, SCIP_Real, SCIPfeasFloor(), SCIPfloor(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGT(), SCIPisLE(), SQR, and SQRT.

Referenced by solvePricingHeuristic(), and solvePricingMINLP().

◆ addVariable()

static SCIP_RETCODE addVariable ( SCIP scip,
SCIP_PROBDATA probdata,
int *  types,
SCIP_Real xs,
SCIP_Real ys,
SCIP_Bool ispacked,
int  nelems 
)
static

adds a variable to the restricted master problem

Parameters
scipSCIP data structure
probdataproblem data
typestypes of elements
xsx coordinate of each element
ysy coordinate of each element
ispackedchecks whether an element has been packed (might be NULL)
nelemstotal number of elements

Definition at line 174 of file pricer_rpa.c.

References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PACKABLE_YES, SCIP_VARTYPE_INTEGER, SCIPaddCoefLinear(), SCIPaddPricedVar(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPinfinity(), SCIPpatternAddElement(), SCIPpatternCreateRectangular(), SCIPpatternRelease(), SCIPpatternSetPackableStatus(), SCIPprobdataAddVar(), SCIPprobdataGetNTypes(), SCIPprobdataGetPatternConss(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarMarkDeletable(), SCIPvarSetInitial(), SCIPvarSetRemovable(), and TRUE.

Referenced by extractVariablesMINLP(), and solvePricingHeuristic().

◆ extractVariablesMINLP()

static SCIP_RETCODE extractVariablesMINLP ( SCIP scip,
SCIP_PROBDATA probdata,
SCIP subscip,
SCIP_VAR **  x,
SCIP_VAR **  y,
SCIP_VAR **  w,
int *  types,
int  nvars,
SCIP_Bool success 
)
static
Parameters
scipSCIP data structure
probdataproblem data
subscipsub-SCIP data structure
xx variables of sub-SCIP
yy variables of sub-SCIP
ww variables of sub-SCIP
typestype corresponding to each variable
nvarsnumber of variables
successpointer to store if we could add at least one variable with negative reduced costs

Definition at line 248 of file pricer_rpa.c.

References addVariable(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPisFeasGE(), and TRUE.

Referenced by solvePricingMINLP().

◆ computeScores()

static void computeScores ( SCIP scip,
SCIP_Real rexts,
SCIP_RANDNUMGEN randnumgen,
int *  elements,
int  nelements,
SCIP_Real lambdas,
SCIP_Real scores,
int  iter,
int  iterlim 
)
static

array to compute the score of each element

Parameters
scipSCIP data structure
rextsexternal radii for each type
randnumgenrandom number generator
elementstype of each element
nelementstotal number of elements
lambdasdual multipliers for each type
scoresarray to store the score of each element
iteriteration round
iterlimtotal iteration limit

Definition at line 322 of file pricer_rpa.c.

References SCIP_Real, and SCIPrandomGetReal().

Referenced by solvePricingHeuristic().

◆ solvePricingHeuristic()

static SCIP_RETCODE solvePricingHeuristic ( SCIP scip,
SCIP_PROBDATA probdata,
SCIP_PRICERDATA pricerdata,
SCIP_Real lambdas,
SCIP_Real  timelim,
int  iterlim,
SCIP_Bool addedvar 
)
static

tries to find a column with negative reduced cost by using a greedy packing heuristic

Parameters
scipSCIP data structure
probdataproblem data
pricerdatapricer data
lambdasdual multipliers for pattern constraints
timelimtime limit
iterlimiteration limit
addedvarpointer to store whether a variable with negative reduced cost has been added

Definition at line 375 of file pricer_rpa.c.

References addVariable(), computeScores(), FALSE, getNCircles(), MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PATTERNTYPE_RECTANGULAR, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetTotalTime(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisGT(), SCIPisStopped(), SCIPpackCirclesGreedy(), SCIPprobdataGetDemands(), SCIPprobdataGetHeight(), SCIPprobdataGetNTypes(), SCIPprobdataGetRexts(), SCIPprobdataGetWidth(), SCIPsortDownRealInt(), and TRUE.

Referenced by SCIP_DECL_PRICERREDCOST().

◆ solvePricingMINLP()

static SCIP_RETCODE solvePricingMINLP ( SCIP scip,
SCIP_PROBDATA probdata,
SCIP_Real lambdas,
SCIP_Real  timelim,
SCIP_Longint  nodelim,
SCIP_Bool addedvar,
SCIP_STATUS solstat,
SCIP_Real dualbound 
)
static

◆ SCIP_DECL_PRICERFREE()

static SCIP_DECL_PRICERFREE ( pricerFreeRingpacking  )
static

name Callback methodsdestructor of variable pricer to free user data (called when SCIP is exiting)

Definition at line 753 of file pricer_rpa.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemoryNull, and SCIPpricerGetData().

◆ SCIP_DECL_PRICERINIT()

static SCIP_DECL_PRICERINIT ( pricerInitRingpacking  )
static

initialization method of variable pricer (called after problem was transformed and pricer is active)

Definition at line 767 of file pricer_rpa.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPpricerGetData(), and TRUE.

◆ SCIP_DECL_PRICEREXIT()

static SCIP_DECL_PRICEREXIT ( pricerExitRingpacking  )
static

deinitialization method of variable pricer (called before transformed problem is freed and pricer is active)

Definition at line 781 of file pricer_rpa.c.

References NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPpricerGetData().

◆ SCIP_DECL_PRICERREDCOST()

◆ SCIP_DECL_PRICERFARKAS()

static SCIP_DECL_PRICERFARKAS ( pricerFarkasRingpacking  )
static

farkas pricing method of variable pricer for infeasible LPs

Definition at line 893 of file pricer_rpa.c.

References SCIP_OKAY, and SCIPABORT.

◆ SCIPincludePricerRpa()

◆ SCIPpricerRpaActivate()

SCIP_RETCODE SCIPpricerRpaActivate ( SCIP scip)

added problem specific data to pricer and activates pricer

Parameters
scipSCIP data structure

Definition at line 960 of file pricer_rpa.c.

References NULL, PRICER_NAME, SCIP_CALL, SCIP_OKAY, SCIPactivatePricer(), and SCIPfindPricer().

Referenced by SCIPprobdataCreate().