Scippy

SCIP

Solving Constraint Integer Programs

probdata_rpa.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file probdata_rpa.h
17  * @brief Problem data for ringpacking problem
18  * @author Benjamin Mueller
19  *
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_PROBDATA_RINGPACKING__
25 #define __SCIP_PROBDATA_RINGPACKING__
26 
27 #include "scip/scip.h"
28 #include "pattern.h"
29 
30 /** sets up the problem data */
32  SCIP* scip, /**< SCIP data structure */
33  const char* probname, /**< problem name */
34  int* demands, /**< array containing the demands */
35  SCIP_Real* rints, /**< internal radii of each ring */
36  SCIP_Real* rexts, /**< external radii of each ring (assumed to be sorted) */
37  int nitems, /**< number of items */
38  SCIP_Real width, /**< width of each rectangle */
39  SCIP_Real height /**< height of each rectangle */
40  );
41 
42 /** enumerates circular patterns and creates restricted master problem */
44  SCIP* scip /**< SCIP data structure */
45  );
46 
47 /** enumerate all non-dominated circular patterns */
49  SCIP* scip, /**< SCIP data structure */
50  SCIP_PROBDATA* probdata, /**< problem data */
51  SCIP_Real nlptilim, /**< time limit for each NLP verification */
52  SCIP_Real heurtilim, /**< time limit for each call of the heuristics */
53  SCIP_Real totaltilim, /**< total time limit for enumeration */
54  SCIP_Longint nlpnodelim, /**< node limit for each NLP verification */
55  int heuriterlim /**< iteration limit for each call of the heuristics */
56  );
57 
58 /** returns number of different types */
60  SCIP_PROBDATA* probdata /**< problem data */
61  );
62 
63 /** returns all external radii */
65  SCIP_PROBDATA* probdata /**< problem data */
66  );
67 
68 /** returns all internal radii */
70  SCIP_PROBDATA* probdata /**< problem data */
71  );
72 
73 /** returns all demands */
75  SCIP_PROBDATA* probdata /**< problem data */
76  );
77 
78 /** returns the width of each rectangle */
80  SCIP_PROBDATA* probdata /**< problem data */
81  );
82 
83 /** returns the height of each rectangle */
85  SCIP_PROBDATA* probdata /**< problem data */
86  );
87 
88 /** returns all information about circular patterns */
90  SCIP_PROBDATA* probdata, /**< problem data */
91  SCIP_PATTERN*** cpatterns, /**< pointer to store the circular patterns (might be NULL) */
92  SCIP_VAR*** cvars, /**< pointer to store the variables corresponding circular patterns (might be NULL) */
93  int* ncpatterns /**< pointer to store the number of circular patterns (might be NULL) */
94  );
95 
96 /** returns all information about rectangular patterns */
98  SCIP_PROBDATA* probdata, /**< problem data */
99  SCIP_PATTERN*** rpatterns, /**< pointer to store the rectangular patterns (might be NULL) */
100  SCIP_VAR*** rvars, /**< pointer to store the variables corresponding rectangular patterns (might be NULL) */
101  int* nrpatterns /**< pointer to store the number of rectangular patterns (might be NULL) */
102  );
103 
104 /** returns array of set pattern constraints */
106  SCIP_PROBDATA* probdata /**< problem data */
107  );
108 
109 /** adds given variable to the problem data */
111  SCIP* scip, /**< SCIP data structure */
112  SCIP_PROBDATA* probdata, /**< problem data */
113  SCIP_PATTERN* pattern, /**< pattern */
114  SCIP_VAR* var /**< variables to add */
115  );
116 
117 /** updates the dual bound */
119  SCIP* scip, /**< SCIP data structure */
120  SCIP_PROBDATA* probdata, /**< problem data */
121  SCIP_Real dualbound /**< new dual bound */
122  );
123 
124 /** marks that further reported dual bounds are not valid */
126  SCIP* scip, /**< SCIP data structure */
127  SCIP_PROBDATA* probdata /**< problem data */
128  );
129 
130 /** returns whether dual bound is marked to be invalid */
132  SCIP_PROBDATA* probdata /**< problem data */
133  );
134 
135 /** Tries to pack a list of elements into a specified boundary circle by using a simple left-first bottom-second
136  * heuristic. Returns the number of elements that could be stored and indicated which ones these are in the buffer
137  * parameter ispacked. This auxiliary method can be used both to find such a packing or to verify a certain pattern.
138  */
140  SCIP* scip, /**< SCIP data structure */
141  SCIP_Real* rexts, /**< outer radii of elements (in original order of probdata) */
142  SCIP_Real* xs, /**< buffer to store the resulting x-coordinates */
143  SCIP_Real* ys, /**< buffer to store the resulting y-coordinates */
144  SCIP_Real rbounding, /**< inner radius of bounding circle (ignored for rectangular patterns) */
145  SCIP_Real width, /**< width of the rectangle */
146  SCIP_Real height, /**< height of the rectangle */
147  SCIP_Bool* ispacked, /**< buffer to store which elements could be packed */
148  int* elements, /**< the order of the elements in the pattern */
149  int nelements, /**< number of elements in the pattern */
150  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
151  int* npacked, /**< pointer to store the number of packed elements */
152  int ncalls /**< total number of calls of the packing heuristic */
153  );
154 
155 /** verifies a circular pattern heuristically */
157  SCIP* scip, /**< SCIP data structure */
158  SCIP_PROBDATA* probdata, /**< problem data */
159  SCIP_PATTERN* pattern, /**< pattern */
160  SCIP_Real timelim, /**< time limit */
161  int iterlim /**< iteration limit */
162  );
163 
164 /** verifies a circular pattern via solving a verification NLP */
166  SCIP* scip, /**< SCIP data structure */
167  SCIP_PROBDATA* probdata, /**< problem data */
168  SCIP_PATTERN* pattern, /**< pattern */
169  SCIP_Real timelim, /**< time limit */
170  SCIP_Longint nodelim /**< node limit */
171  );
172 
173 /** check whether a pattern for consistency */
174 void SCIPcheckPattern(
175  SCIP* scip, /**< SCIP data structure */
176  SCIP_PROBDATA* probdata, /**< problem data */
177  SCIP_PATTERN* pattern /**< pattern */
178  );
179 
180 #endif /* __SCIP_PROBDATA_RINGPACKING__ */
SCIP_RETCODE SCIPprobdataSetupProblem(SCIP *scip)
SCIP_Real * SCIPprobdataGetRints(SCIP_PROBDATA *probdata)
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
void SCIPcheckPattern(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
enum SCIP_Patterntype SCIP_PATTERNTYPE
Definition: pattern.h:45
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int nitems, SCIP_Real width, SCIP_Real height)
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
SCIP_Bool SCIPprobdataIsDualboundInvalid(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPverifyCircularPatternHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, int iterlim)
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
void SCIPprobdataGetRInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***rpatterns, SCIP_VAR ***rvars, int *nrpatterns)
pattern data for ringpacking problem
SCIP_CONS ** SCIPprobdataGetPatternConss(SCIP_PROBDATA *probdata)
void SCIPpackCirclesGreedy(SCIP *scip, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real rbounding, SCIP_Real width, SCIP_Real height, SCIP_Bool *ispacked, int *elements, int nelements, SCIP_PATTERNTYPE patterntype, int *npacked, int ncalls)
#define SCIP_Bool
Definition: def.h:70
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPverifyCircularPatternNLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, SCIP_Longint nodelim)
void SCIPprobdataGetCInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***cpatterns, SCIP_VAR ***cvars, int *ncpatterns)
void SCIPprobdataUpdateDualbound(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real dualbound)
SCIP_RETCODE SCIPprobdataEnumeratePatterns(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real nlptilim, SCIP_Real heurtilim, SCIP_Real totaltilim, SCIP_Longint nlpnodelim, int heuriterlim)
#define SCIP_Real
Definition: def.h:163
#define SCIP_Longint
Definition: def.h:148
SCIP_RETCODE SCIPprobdataAddVar(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
SCIP callable library.