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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file probdata_rpa.h
26  * @brief Problem data for ringpacking problem
27  * @author Benjamin Mueller
28  *
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_PROBDATA_RINGPACKING__
34 #define __SCIP_PROBDATA_RINGPACKING__
35 
36 #include "scip/scip.h"
37 #include "pattern.h"
38 
39 /** sets up the problem data */
41  SCIP* scip, /**< SCIP data structure */
42  const char* probname, /**< problem name */
43  int* demands, /**< array containing the demands */
44  SCIP_Real* rints, /**< internal radii of each ring */
45  SCIP_Real* rexts, /**< external radii of each ring (assumed to be sorted) */
46  int nitems, /**< number of items */
47  SCIP_Real width, /**< width of each rectangle */
48  SCIP_Real height /**< height of each rectangle */
49  );
50 
51 /** enumerates circular patterns and creates restricted master problem */
53  SCIP* scip /**< SCIP data structure */
54  );
55 
56 /** enumerate all non-dominated circular patterns */
58  SCIP* scip, /**< SCIP data structure */
59  SCIP_PROBDATA* probdata, /**< problem data */
60  SCIP_Real nlptilim, /**< time limit for each NLP verification */
61  SCIP_Real heurtilim, /**< time limit for each call of the heuristics */
62  SCIP_Real totaltilim, /**< total time limit for enumeration */
63  SCIP_Longint nlpnodelim, /**< node limit for each NLP verification */
64  int heuriterlim /**< iteration limit for each call of the heuristics */
65  );
66 
67 /** returns number of different types */
69  SCIP_PROBDATA* probdata /**< problem data */
70  );
71 
72 /** returns all external radii */
74  SCIP_PROBDATA* probdata /**< problem data */
75  );
76 
77 /** returns all internal radii */
79  SCIP_PROBDATA* probdata /**< problem data */
80  );
81 
82 /** returns all demands */
84  SCIP_PROBDATA* probdata /**< problem data */
85  );
86 
87 /** returns the width of each rectangle */
89  SCIP_PROBDATA* probdata /**< problem data */
90  );
91 
92 /** returns the height of each rectangle */
94  SCIP_PROBDATA* probdata /**< problem data */
95  );
96 
97 /** returns all information about circular patterns */
99  SCIP_PROBDATA* probdata, /**< problem data */
100  SCIP_PATTERN*** cpatterns, /**< pointer to store the circular patterns (might be NULL) */
101  SCIP_VAR*** cvars, /**< pointer to store the variables corresponding circular patterns (might be NULL) */
102  int* ncpatterns /**< pointer to store the number of circular patterns (might be NULL) */
103  );
104 
105 /** returns all information about rectangular patterns */
107  SCIP_PROBDATA* probdata, /**< problem data */
108  SCIP_PATTERN*** rpatterns, /**< pointer to store the rectangular patterns (might be NULL) */
109  SCIP_VAR*** rvars, /**< pointer to store the variables corresponding rectangular patterns (might be NULL) */
110  int* nrpatterns /**< pointer to store the number of rectangular patterns (might be NULL) */
111  );
112 
113 /** returns array of set pattern constraints */
115  SCIP_PROBDATA* probdata /**< problem data */
116  );
117 
118 /** adds given variable to the problem data */
120  SCIP* scip, /**< SCIP data structure */
121  SCIP_PROBDATA* probdata, /**< problem data */
122  SCIP_PATTERN* pattern, /**< pattern */
123  SCIP_VAR* var /**< variables to add */
124  );
125 
126 /** updates the dual bound */
128  SCIP* scip, /**< SCIP data structure */
129  SCIP_PROBDATA* probdata, /**< problem data */
130  SCIP_Real dualbound /**< new dual bound */
131  );
132 
133 /** marks that further reported dual bounds are not valid */
135  SCIP* scip, /**< SCIP data structure */
136  SCIP_PROBDATA* probdata /**< problem data */
137  );
138 
139 /** returns whether dual bound is marked to be invalid */
141  SCIP_PROBDATA* probdata /**< problem data */
142  );
143 
144 /** Tries to pack a list of elements into a specified boundary circle by using a simple left-first bottom-second
145  * heuristic. Returns the number of elements that could be stored and indicated which ones these are in the buffer
146  * parameter ispacked. This auxiliary method can be used both to find such a packing or to verify a certain pattern.
147  */
149  SCIP* scip, /**< SCIP data structure */
150  SCIP_Real* rexts, /**< outer radii of elements (in original order of probdata) */
151  SCIP_Real* xs, /**< buffer to store the resulting x-coordinates */
152  SCIP_Real* ys, /**< buffer to store the resulting y-coordinates */
153  SCIP_Real rbounding, /**< inner radius of bounding circle (ignored for rectangular patterns) */
154  SCIP_Real width, /**< width of the rectangle */
155  SCIP_Real height, /**< height of the rectangle */
156  SCIP_Bool* ispacked, /**< buffer to store which elements could be packed */
157  int* elements, /**< the order of the elements in the pattern */
158  int nelements, /**< number of elements in the pattern */
159  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
160  int* npacked, /**< pointer to store the number of packed elements */
161  int ncalls /**< total number of calls of the packing heuristic */
162  );
163 
164 /** verifies a circular pattern heuristically */
166  SCIP* scip, /**< SCIP data structure */
167  SCIP_PROBDATA* probdata, /**< problem data */
168  SCIP_PATTERN* pattern, /**< pattern */
169  SCIP_Real timelim, /**< time limit */
170  int iterlim /**< iteration limit */
171  );
172 
173 /** verifies a circular pattern via solving a verification NLP */
175  SCIP* scip, /**< SCIP data structure */
176  SCIP_PROBDATA* probdata, /**< problem data */
177  SCIP_PATTERN* pattern, /**< pattern */
178  SCIP_Real timelim, /**< time limit */
179  SCIP_Longint nodelim /**< node limit */
180  );
181 
182 /** check whether a pattern for consistency */
183 void SCIPcheckPattern(
184  SCIP* scip, /**< SCIP data structure */
185  SCIP_PROBDATA* probdata, /**< problem data */
186  SCIP_PATTERN* pattern /**< pattern */
187  );
188 
189 #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:54
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
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:93
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:53
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:186
#define SCIP_Longint
Definition: def.h:171
SCIP_RETCODE SCIPprobdataAddVar(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
SCIP callable library.