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-2018 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 scip.zib.de. */
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 */
31 extern
33  SCIP* scip, /**< SCIP data structure */
34  const char* probname, /**< problem name */
35  int* demands, /**< array containing the demands */
36  SCIP_Real* rints, /**< internal radii of each ring */
37  SCIP_Real* rexts, /**< external radii of each ring (assumed to be sorted) */
38  int nitems, /**< number of items */
39  SCIP_Real width, /**< width of each rectangle */
40  SCIP_Real height /**< height of each rectangle */
41  );
42 
43 /** enumerates circular patterns and creates restricted master problem */
44 extern
46  SCIP* scip /**< SCIP data structure */
47  );
48 
49 /** enumerate all non-dominated circular patterns */
50 extern
52  SCIP* scip, /**< SCIP data structure */
53  SCIP_PROBDATA* probdata, /**< problem data */
54  SCIP_Real nlptilim, /**< time limit for each NLP verification */
55  SCIP_Real heurtilim, /**< time limit for each call of the heuristics */
56  SCIP_Real totaltilim, /**< total time limit for enumeration */
57  SCIP_Longint nlpnodelim, /**< node limit for each NLP verification */
58  int heuriterlim /**< iteration limit for each call of the heuristics */
59  );
60 
61 /** returns number of different types */
62 extern
64  SCIP_PROBDATA* probdata /**< problem data */
65  );
66 
67 /** returns all external radii */
68 extern
70  SCIP_PROBDATA* probdata /**< problem data */
71  );
72 
73 /** returns all internal radii */
74 extern
76  SCIP_PROBDATA* probdata /**< problem data */
77  );
78 
79 /** returns all demands */
80 extern
82  SCIP_PROBDATA* probdata /**< problem data */
83  );
84 
85 /** returns the width of each rectangle */
86 extern
88  SCIP_PROBDATA* probdata /**< problem data */
89  );
90 
91 /** returns the height of each rectangle */
92 extern
94  SCIP_PROBDATA* probdata /**< problem data */
95  );
96 
97 /** returns all information about circular patterns */
98 extern
100  SCIP_PROBDATA* probdata, /**< problem data */
101  SCIP_PATTERN*** cpatterns, /**< pointer to store the circular patterns (might be NULL) */
102  SCIP_VAR*** cvars, /**< pointer to store the variables corresponding circular patterns (might be NULL) */
103  int* ncpatterns /**< pointer to store the number of circular patterns (might be NULL) */
104  );
105 
106 /** returns all information about rectangular patterns */
107 extern
109  SCIP_PROBDATA* probdata, /**< problem data */
110  SCIP_PATTERN*** rpatterns, /**< pointer to store the rectangular patterns (might be NULL) */
111  SCIP_VAR*** rvars, /**< pointer to store the variables corresponding rectangular patterns (might be NULL) */
112  int* nrpatterns /**< pointer to store the number of rectangular patterns (might be NULL) */
113  );
114 
115 /** returns array of set pattern constraints */
116 extern
118  SCIP_PROBDATA* probdata /**< problem data */
119  );
120 
121 /** adds given variable to the problem data */
122 extern
124  SCIP* scip, /**< SCIP data structure */
125  SCIP_PROBDATA* probdata, /**< problem data */
126  SCIP_PATTERN* pattern, /**< pattern */
127  SCIP_VAR* var /**< variables to add */
128  );
129 
130 /** updates the dual bound */
131 extern
133  SCIP* scip, /**< SCIP data structure */
134  SCIP_PROBDATA* probdata, /**< problem data */
135  SCIP_Real dualbound /**< new dual bound */
136  );
137 
138 /** marks that further reported dual bounds are not valid */
139 extern
141  SCIP* scip, /**< SCIP data structure */
142  SCIP_PROBDATA* probdata /**< problem data */
143  );
144 
145 /** returns whether dual bound is marked to be invalid */
146 extern
148  SCIP_PROBDATA* probdata /**< problem data */
149  );
150 
151 /** Tries to pack a list of elements into a specified boundary circle by using a simple left-first bottom-second
152  * heuristic. Returns the number of elements that could be stored and indicated which ones these are in the buffer
153  * parameter ispacked. This auxiliary method can be used both to find such a packing or to verify a certain pattern.
154  */
155 extern
157  SCIP* scip, /**< SCIP data structure */
158  SCIP_Real* rexts, /**< outer radii of elements (in original order of probdata) */
159  SCIP_Real* xs, /**< buffer to store the resulting x-coordinates */
160  SCIP_Real* ys, /**< buffer to store the resulting y-coordinates */
161  SCIP_Real rbounding, /**< inner radius of bounding circle (ignored for rectangular patterns) */
162  SCIP_Real width, /**< width of the rectangle */
163  SCIP_Real height, /**< height of the rectangle */
164  SCIP_Bool* ispacked, /**< buffer to store which elements could be packed */
165  int* elements, /**< the order of the elements in the pattern */
166  int nelements, /**< number of elements in the pattern */
167  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
168  int* npacked, /**< pointer to store the number of packed elements */
169  int ncalls /**< total number of calls of the packing heuristic */
170  );
171 
172 /** verifies a circular pattern heuristically */
173 extern
175  SCIP* scip, /**< SCIP data structure */
176  SCIP_PROBDATA* probdata, /**< problem data */
177  SCIP_PATTERN* pattern, /**< pattern */
178  SCIP_Real timelim, /**< time limit */
179  int iterlim /**< iteration limit */
180  );
181 
182 /** verifies a circular pattern via solving a verification NLP */
183 extern
185  SCIP* scip, /**< SCIP data structure */
186  SCIP_PROBDATA* probdata, /**< problem data */
187  SCIP_PATTERN* pattern, /**< pattern */
188  SCIP_Real timelim, /**< time limit */
189  SCIP_Longint nodelim /**< node limit */
190  );
191 
192 /** check whether a pattern for consistency */
193 extern
194 void SCIPcheckPattern(
195  SCIP* scip, /**< SCIP data structure */
196  SCIP_PROBDATA* probdata, /**< problem data */
197  SCIP_PATTERN* pattern /**< pattern */
198  );
199 
200 #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:53
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:62
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:150
#define SCIP_Longint
Definition: def.h:135
SCIP_RETCODE SCIPprobdataAddVar(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
SCIP callable library.