Scippy

SCIP

Solving Constraint Integer Programs

cons_rpa.c File Reference

Detailed Description

constraint handler for recursive circle packing

Author
Benjamin Mueller

This constraint handler is used to store information about which (not verified) rectangular patterns have been locked and which circular patterns have not been tried to be verified yet.

Definition in file cons_rpa.c.

#include <assert.h>
#include <string.h>
#include "cons_rpa.h"
#include "probdata_rpa.h"
#include "pattern.h"

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "rpa"
 
#define CONSHDLR_DESC   "ringpacking constraint handler"
 
#define CONSHDLR_ENFOPRIORITY   1
 
#define CONSHDLR_CHECKPRIORITY   -1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_NEEDSCONS   FALSE
 
#define CONSHDLR_SEPAPRIORITY   0
 
#define CONSHDLR_SEPAFREQ   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_PROPFREQ   -1
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define EVENTHDLR_NAME   "bestsol"
 
#define EVENTHDLR_DESC   "best solution event handler"
 
#define DEFAULT_VERIFICATION_NLPTILIM   10.0
 
#define DEFAULT_VERIFICATION_NLPNODELIM   10000L
 
#define DEFAULT_VERIFICATION_HEURTILIM   10.0
 
#define DEFAULT_VERIFICATION_HEURITERLIM   1000
 
#define DEFAULT_VERIFICATION_TOTALTILIM   3600.0
 

Functions

static SCIP_Bool isSolFeasible (SCIP *scip, SCIP_SOL *sol)
 
static SCIP_RETCODE verifyCircularPattern (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
 
static SCIP_RETCODE enforceSol (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_RESULT *result)
 
static int getShadingVal (int type, int ntypes)
 
static SCIP_DECL_EVENTEXEC (processNewSolutionEvent)
 
static SCIP_DECL_CONSFREE (consFreeRpa)
 
static SCIP_DECL_CONSINITSOL (consInitsolRpa)
 
static SCIP_DECL_CONSEXITSOL (consExitsolRpa)
 
static SCIP_DECL_CONSENFOLP (consEnfolpRpa)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxRpa)
 
static SCIP_DECL_CONSENFOPS (consEnfopsRpa)
 
static SCIP_DECL_CONSCHECK (consCheckRpa)
 
static SCIP_DECL_CONSLOCK (consLockRpa)
 
SCIP_RETCODE SCIPincludeConshdlrRpa (SCIP *scip)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME   "rpa"

Definition at line 38 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "ringpacking constraint handler"

Definition at line 39 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   1

priority of the constraint handler for constraint enforcing

Definition at line 40 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -1

priority of the constraint handler for checking feasibility

Definition at line 41 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 42 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   FALSE

should the constraint handler be skipped, if no constraints are available?

Definition at line 45 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   0

priority of the constraint handler for separation

Definition at line 49 of file cons_rpa.c.

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   -1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 50 of file cons_rpa.c.

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 51 of file cons_rpa.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   -1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 53 of file cons_rpa.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 54 of file cons_rpa.c.

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask of the constraint handler

Definition at line 55 of file cons_rpa.c.

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM

presolving timing of the constraint handler (fast, medium, or exhaustive)

Definition at line 57 of file cons_rpa.c.

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 58 of file cons_rpa.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "bestsol"

Definition at line 61 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC   "best solution event handler"

Definition at line 62 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ DEFAULT_VERIFICATION_NLPTILIM

#define DEFAULT_VERIFICATION_NLPTILIM   10.0

time limit for each verification NLP

Definition at line 65 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ DEFAULT_VERIFICATION_NLPNODELIM

#define DEFAULT_VERIFICATION_NLPNODELIM   10000L

node limit for each verification NLP

Definition at line 66 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ DEFAULT_VERIFICATION_HEURTILIM

#define DEFAULT_VERIFICATION_HEURTILIM   10.0

time limit for heuristic verification

Definition at line 67 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ DEFAULT_VERIFICATION_HEURITERLIM

#define DEFAULT_VERIFICATION_HEURITERLIM   1000

iteration limit for each heuristic verification

Definition at line 68 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

◆ DEFAULT_VERIFICATION_TOTALTILIM

#define DEFAULT_VERIFICATION_TOTALTILIM   3600.0

total time limit for all verification problems during the solving process

Definition at line 69 of file cons_rpa.c.

Referenced by SCIPincludeConshdlrRpa().

Function Documentation

◆ isSolFeasible()

static SCIP_Bool isSolFeasible ( SCIP scip,
SCIP_SOL sol 
)
static

auxiliary function to decide whether a proposed solution is feasible; a solution is called feasible if and only if z*_C = 0 holds for all circular patterns that are either not packable, i.e., SCIP_PACKABLE_NO or SCIP_PACKABLE_UNKNOWN

Parameters
scipSCIP data structure
solsolution (NULL for LP solution)

Definition at line 100 of file cons_rpa.c.

References FALSE, NULL, SCIP_PACKABLE_YES, SCIP_Real, SCIPdebugMsg, SCIPgetProbData(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPpatternGetPackableStatus(), SCIPprobdataGetCInfos(), TRUE, and verifyCircularPattern().

Referenced by enforceSol(), and SCIP_DECL_CONSCHECK().

◆ verifyCircularPattern()

static SCIP_RETCODE verifyCircularPattern ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_PROBDATA probdata,
SCIP_PATTERN pattern 
)
static

tries to verify a circular pattern; it first tries to call heuristic(s) and afterwards uses a verification NLP

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
probdataproblem data
patterncircular pattern

Definition at line 142 of file cons_rpa.c.

References enforceSol(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_PACKABLE_UNKNOWN, SCIP_PATTERNTYPE_CIRCULAR, SCIP_Real, SCIPcheckPattern(), SCIPdebugMsg, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPpatternGetPackableStatus(), SCIPpatternGetPatternType(), SCIPverifyCircularPatternHeuristic(), and SCIPverifyCircularPatternNLP().

Referenced by enforceSol(), and isSolFeasible().

◆ enforceSol()

static SCIP_RETCODE enforceSol ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
SCIP_RESULT result 
)
static

auxiliary function for enforcing ringpacking constraint; the function checks whether

  1. the solution is feasible; if yes -> skip
  2. tries to verify an unverified circular pattern C with z*_c > 0 2a. case packable or unknown: go to 2. 2b. case not packable: fix z_C to 0 -> skip
  3. fix all unverified circular patterns to 0

Note that after step 3. the dual bound is not valid anymore.

Parameters
scipSCIP data structure
conshdlrconstraint handler
solsolution (NULL for LP solution)
resultpointer to store the result

Definition at line 197 of file cons_rpa.c.

References getShadingVal(), isSolFeasible(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_PACKABLE_NO, SCIP_PACKABLE_UNKNOWN, SCIP_Real, SCIP_REDUCEDDOM, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPfixVar(), SCIPgetProbData(), SCIPgetSolVal(), SCIPisFeasZero(), SCIPpatternGetPackableStatus(), SCIPprintSol(), SCIPprobdataGetCInfos(), SCIPprobdataInvalidateDualbound(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and verifyCircularPattern().

Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSENFORELAX(), and verifyCircularPattern().

◆ getShadingVal()

static int getShadingVal ( int  type,
int  ntypes 
)
static

get shading of a given pattern type

Parameters
typepattern type
ntypestotal number of patterns

Definition at line 308 of file cons_rpa.c.

References MAX, and SCIP_DECL_EVENTEXEC().

Referenced by enforceSol(), and SCIP_DECL_EVENTEXEC().

◆ SCIP_DECL_EVENTEXEC()

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeRpa  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 490 of file cons_rpa.c.

References NULL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_EVENTEXEC().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolRpa  )
static

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

Definition at line 509 of file cons_rpa.c.

References BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_DECL_CONSEXITSOL(), SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcatchEvent(), SCIPconshdlrGetData(), SCIPgetProbData(), and SCIPprobdataGetCInfos().

Referenced by SCIP_DECL_CONSFREE().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolRpa  )
static

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

Definition at line 538 of file cons_rpa.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSENFOLP(), SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdropEvent(), SCIPfreeBlockMemoryArray, SCIPgetProbData(), and SCIPprobdataGetCInfos().

Referenced by SCIP_DECL_CONSINITSOL().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpRpa  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 565 of file cons_rpa.c.

References enforceSol(), NULL, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSEXITSOL().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxRpa  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 575 of file cons_rpa.c.

References enforceSol(), SCIP_CALL, SCIP_DECL_CONSENFOPS(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsRpa  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 585 of file cons_rpa.c.

References enforceSol(), NULL, SCIP_CALL, SCIP_DECL_CONSCHECK(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckRpa  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 595 of file cons_rpa.c.

References isSolFeasible(), SCIP_DECL_CONSLOCK(), SCIP_FEASIBLE, SCIP_INFEASIBLE, and SCIP_OKAY.

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSLOCK()