Scippy

SCIP

Solving Constraint Integer Programs

cons_cumulative.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-2024 Zuse Institute Berlin (ZIB) */
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 cons_cumulative.h
26 * @ingroup CONSHDLRS
27 * @brief constraint handler for cumulative constraints
28 * @author Timo Berthold
29 * @author Stefan Heinz
30 * @author Jens Schulz
31 *
32 */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36#ifndef __SCIP_CONS_CUMULATIVE_H__
37#define __SCIP_CONS_CUMULATIVE_H__
38
39
40#include "scip/def.h"
41#include "scip/type_cons.h"
42#include "scip/type_lp.h"
43#include "scip/type_misc.h"
44#include "scip/type_result.h"
45#include "scip/type_retcode.h"
46#include "scip/type_scip.h"
47#include "scip/type_sol.h"
48#include "scip/type_timing.h"
49#include "scip/type_var.h"
50
51#ifdef __cplusplus
52extern "C" {
53#endif
54
55
56/** creates the constraint handler for cumulative constraints and includes it in SCIP
57 *
58 * @ingroup ConshdlrIncludes
59 */
60SCIP_EXPORT
62 SCIP* scip /**< SCIP data structure */
63 );
64
65/**@addtogroup CONSHDLRS
66 *
67 * @{
68 *
69 * @name Cumulative Constraints
70 *
71 * Given:
72 * - a set of jobs, represented by their integer start time variables \f$S_j\f$, their array of processing times \f$p_j\f$ and of
73 * their demands \f$d_j\f$.
74 * - an integer resource capacity \f$C\f$
75 *
76 * The cumulative constraint ensures that for each point in time \f$t\f$ \f$\sum_{j: S_j \leq t < S_j + p_j} d_j \leq C\f$ holds.
77 *
78 * @par
79 * Separation:
80 * - can be done using binary start time model, see Pritskers, Watters and Wolfe
81 * - or by just separating relatively weak cuts on the start time variables
82 *
83 * @par
84 * Propagation:
85 * - time tabling, Klein & Scholl (1999)
86 * - Edge-finding from Petr Vilim, adjusted and simplified for dynamic repropagation
87 * (2009)
88 * - energetic reasoning, see Baptiste, Le Pape, Nuijten (2001)
89 *
90 * @{
91 */
92
93/** creates and captures a cumulative constraint */
94SCIP_EXPORT
96 SCIP* scip, /**< SCIP data structure */
97 SCIP_CONS** cons, /**< pointer to hold the created constraint */
98 const char* name, /**< name of constraint */
99 int nvars, /**< number of variables (jobs) */
100 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
101 int* durations, /**< array containing corresponding durations */
102 int* demands, /**< array containing corresponding demands */
103 int capacity, /**< available cumulative capacity */
104 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
105 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
106 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
107 * Usually set to TRUE. */
108 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
109 * TRUE for model constraints, FALSE for additional, redundant constraints. */
110 SCIP_Bool check, /**< should the constraint be checked for feasibility?
111 * TRUE for model constraints, FALSE for additional, redundant constraints. */
112 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
113 * Usually set to TRUE. */
114 SCIP_Bool local, /**< is constraint only valid locally?
115 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
116 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
117 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
118 * adds coefficients to this constraint. */
119 SCIP_Bool dynamic, /**< is constraint subject to aging?
120 * Usually set to FALSE. Set to TRUE for own cuts which
121 * are seperated as constraints. */
122 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
123 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
124 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
125 * if it may be moved to a more global node?
126 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
127 );
128
129/** creates and captures an absolute power constraint
130 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
131 * method SCIPcreateConsCumulative(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
132 *
133 * @see SCIPcreateConsCumulative() for information about the basic constraint flag configuration
134 *
135 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
136 */
137SCIP_EXPORT
139 SCIP* scip, /**< SCIP data structure */
140 SCIP_CONS** cons, /**< pointer to hold the created constraint */
141 const char* name, /**< name of constraint */
142 int nvars, /**< number of variables (jobs) */
143 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
144 int* durations, /**< array containing corresponding durations */
145 int* demands, /**< array containing corresponding demands */
146 int capacity /**< available cumulative capacity */
147 );
148
149/** set the left bound of effective horizon */
150SCIP_EXPORT
152 SCIP* scip, /**< SCIP data structure */
153 SCIP_CONS* cons, /**< constraint data */
154 int hmin /**< left bound of time axis to be considered */
155 );
156
157/** returns the left bound of the effective horizon */
158SCIP_EXPORT
160 SCIP* scip, /**< SCIP data structure */
161 SCIP_CONS* cons /**< constraint */
162 );
163
164
165/** set the right bound of the effective horizon */
166SCIP_EXPORT
168 SCIP* scip, /**< SCIP data structure */
169 SCIP_CONS* cons, /**< constraint data */
170 int hmax /**< right bound of time axis to be considered */
171 );
172
173/** returns the right bound of effective horizon */
174SCIP_EXPORT
176 SCIP* scip, /**< SCIP data structure */
177 SCIP_CONS* cons /**< constraint */
178 );
179
180/** returns the start time variables of the cumulative constraint */
181SCIP_EXPORT
183 SCIP* scip, /**< SCIP data structure */
184 SCIP_CONS* cons /**< constraint data */
185 );
186
187/** returns the number of start time variables of the cumulative constraint */
188SCIP_EXPORT
190 SCIP* scip, /**< SCIP data structure */
191 SCIP_CONS* cons /**< constraint data */
192 );
193
194/** returns the capacity of the cumulative constraint */
195SCIP_EXPORT
197 SCIP* scip, /**< SCIP data structure */
198 SCIP_CONS* cons /**< constraint data */
199 );
200
201/** returns the durations of the cumulative constraint */
202SCIP_EXPORT
204 SCIP* scip, /**< SCIP data structure */
205 SCIP_CONS* cons /**< constraint data */
206 );
207
208/** returns the demands of the cumulative constraint */
209SCIP_EXPORT
211 SCIP* scip, /**< SCIP data structure */
212 SCIP_CONS* cons /**< constraint data */
213 );
214
215/** check for the given starting time variables with their demands and durations if the cumulative conditions for the
216 * given solution is satisfied
217 */
218SCIP_EXPORT
220 SCIP* scip, /**< SCIP data structure */
221 SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
222 int nvars, /**< number of variables (jobs) */
223 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
224 int* durations, /**< array containing corresponding durations */
225 int* demands, /**< array containing corresponding demands */
226 int capacity, /**< available cumulative capacity */
227 int hmin, /**< left bound of time axis to be considered */
228 int hmax, /**< right bound of time axis to be considered */
229 SCIP_Bool* violated, /**< pointer to store if the cumulative condition is violated */
230 SCIP_CONS* cons, /**< constraint which is checked */
231 SCIP_Bool printreason /**< should the reason for the violation be printed? */
232 );
233
234/** normalize cumulative condition */
235SCIP_EXPORT
237 SCIP* scip, /**< SCIP data structure */
238 int nvars, /**< number of start time variables (activities) */
239 SCIP_VAR** vars, /**< array of start time variables */
240 int* durations, /**< array of durations */
241 int* demands, /**< array of demands */
242 int* capacity, /**< pointer to store the changed cumulative capacity */
243 int* nchgcoefs, /**< pointer to count total number of changed coefficients */
244 int* nchgsides /**< pointer to count number of side changes */
245 );
246
247/** searches for a time point within the cumulative condition were the cumulative condition can be split */
248SCIP_EXPORT
250 SCIP* scip, /**< SCIP data structure */
251 int nvars, /**< number of variables (jobs) */
252 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
253 int* durations, /**< array containing corresponding durations */
254 int* demands, /**< array containing corresponding demands */
255 int capacity, /**< available cumulative capacity */
256 int* hmin, /**< pointer to store the left bound of the effective horizon */
257 int* hmax, /**< pointer to store the right bound of the effective horizon */
258 int* split /**< point were the cumulative condition can be split */
259 );
260
261/** presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */
262SCIP_EXPORT
264 SCIP* scip, /**< SCIP data structure */
265 int nvars, /**< number of start time variables (activities) */
266 SCIP_VAR** vars, /**< array of start time variables */
267 int* durations, /**< array of durations */
268 int hmin, /**< left bound of time axis to be considered */
269 int hmax, /**< right bound of time axis to be considered (not including hmax) */
270 SCIP_Bool* downlocks, /**< array storing if the variable has a down lock, or NULL */
271 SCIP_Bool* uplocks, /**< array storing if the variable has an up lock, or NULL */
272 SCIP_CONS* cons, /**< constraint which gets propagated, or NULL */
273 SCIP_Bool* delvars, /**< array storing the variable which can be deleted from the constraint */
274 int* nfixedvars, /**< pointer to store the number of fixed variables */
275 int* nchgsides, /**< pointer to store the number of changed sides */
276 SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
277 );
278
279/** propagate the given cumulative condition */
280SCIP_EXPORT
282 SCIP* scip, /**< SCIP data structure */
283 SCIP_PRESOLTIMING presoltiming, /**< current presolving timing */
284 int nvars, /**< number of variables (jobs) */
285 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
286 int* durations, /**< array containing corresponding durations */
287 int* demands, /**< array containing corresponding demands */
288 int capacity, /**< available cumulative capacity */
289 int hmin, /**< left bound of time axis to be considered */
290 int hmax, /**< right bound of time axis to be considered */
291 SCIP_CONS* cons, /**< constraint which gets propagated */
292 int* nchgbds, /**< pointer to store the number of variable bound changes */
293 SCIP_Bool* initialized, /**< was conflict analysis initialized */
294 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
295 SCIP_Bool* cutoff /**< pointer to store if the cumulative condition is violated */
296 );
297
298/** resolve propagation w.r.t. the cumulative condition */
299SCIP_EXPORT
301 SCIP* scip, /**< SCIP data structure */
302 int nvars, /**< number of start time variables (activities) */
303 SCIP_VAR** vars, /**< array of start time variables */
304 int* durations, /**< array of durations */
305 int* demands, /**< array of demands */
306 int capacity, /**< cumulative capacity */
307 int hmin, /**< left bound of time axis to be considered (including hmin) */
308 int hmax, /**< right bound of time axis to be considered (not including hmax) */
309 SCIP_VAR* infervar, /**< the conflict variable whose bound change has to be resolved */
310 int inferinfo, /**< the user information */
311 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
312 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
313 SCIP_Real relaxedbd, /**< the relaxed bound which is sufficient to be explained */
314 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
315 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
316 );
317
318/** this method visualizes the cumulative structure in GML format */
319SCIP_EXPORT
321 SCIP* scip, /**< SCIP data structure */
322 SCIP_CONS* cons /**< cumulative constraint */
323 );
324
325/** solves given cumulative condition as independent sub problem
326 *
327 * @note The time and memory limit should be respected.
328 *
329 * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the
330 * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub
331 * solver was interrupted.
332 *
333 * input:
334 * - njobs : number of jobs (activities)
335 * - objvals : array of objective coefficients for each job (linear objective function), or NULL if none
336 * - durations : array of durations
337 * - demands : array of demands
338 * - capacity : cumulative capacity
339 * - hmin : left bound of time axis to be considered (including hmin)
340 * - hmax : right bound of time axis to be considered (not including hmax)
341 * - timelimit : time limit for solving in seconds
342 * - memorylimit : memory limit for solving in mega bytes (MB)
343 * - maxnodes : maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit)
344 *
345 * input/output:
346 * - ests : array of earliest start times for each job
347 * - lsts : array of latest start times for each job
348 *
349 * output:
350 * - solved : pointer to store if the problem is solved (to optimality)
351 * - infeasible : pointer to store if the problem is infeasible
352 * - unbounded : pointer to store if the problem is unbounded
353 * - error : pointer to store if an error occurred
354 *
355 */
356#define SCIP_DECL_SOLVECUMULATIVE(x) SCIP_RETCODE x (int njobs, SCIP_Real* ests, SCIP_Real* lsts, SCIP_Real* objvals, \
357 int* durations, int* demands, int capacity, int hmin, int hmax, \
358 SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, \
359 SCIP_Bool* solved, SCIP_Bool* infeasible, SCIP_Bool* unbounded, SCIP_Bool* error)
360
361/** sets method to solve an individual cumulative condition */
362SCIP_EXPORT
364 SCIP* scip, /**< SCIP data structure */
365 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)) /**< method to use an individual cumulative condition */
366 );
367
368/** solves given cumulative condition as independent sub problem
369 *
370 * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the
371 * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub
372 * solver was interrupted.
373 */
374SCIP_EXPORT
376 SCIP* scip, /**< SCIP data structure */
377 int njobs, /**< number of jobs (activities) */
378 SCIP_Real* ests, /**< array with the earlier start time for each job */
379 SCIP_Real* lsts, /**< array with the latest start time for each job */
380 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */
381 int* durations, /**< array of durations */
382 int* demands, /**< array of demands */
383 int capacity, /**< cumulative capacity */
384 int hmin, /**< left bound of time axis to be considered (including hmin) */
385 int hmax, /**< right bound of time axis to be considered (not including hmax) */
386 SCIP_Real timelimit, /**< time limit for solving in seconds */
387 SCIP_Real memorylimit, /**< memory limit for solving in mega bytes (MB) */
388 SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) */
389 SCIP_Bool* solved, /**< pointer to store if the problem is solved (to optimality) */
390 SCIP_Bool* infeasible, /**< pointer to store if the problem is infeasible */
391 SCIP_Bool* unbounded, /**< pointer to store if the problem is unbounded */
392 SCIP_Bool* error /**< pointer to store if an error occurred */
393 );
394
395/** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest
396 * completion time
397 */
398SCIP_EXPORT
400 SCIP* scip, /**< SCIP data structure */
401 SCIP_PROFILE* profile, /**< resource profile */
402 int nvars, /**< number of variables (jobs) */
403 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
404 int* durations, /**< array containing corresponding durations */
405 int* demands /**< array containing corresponding demands */
406 );
407
408/** computes w.r.t. the given worst case resource profile the first time point where the given capacity can be violated */
409SCIP_EXPORT
411 SCIP* scip, /**< SCIP data structure */
412 SCIP_PROFILE* profile, /**< worst case resource profile */
413 int capacity /**< capacity to check */
414 );
415
416/** computes w.r.t. the given worst case resource profile the first time point where the given capacity is satisfied for sure */
417SCIP_EXPORT
419 SCIP* scip, /**< SCIP data structure */
420 SCIP_PROFILE* profile, /**< worst case profile */
421 int capacity /**< capacity to check */
422 );
423
424
425/** @} */
426
427/** @} */
428
429#ifdef __cplusplus
430}
431#endif
432
433#endif
static SCIP_RETCODE solveCumulative(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool local, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
common defines and data types used in all packages of SCIP
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
int SCIPgetHminCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPpropCumulativeCondition(SCIP *scip, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetSolveCumulative(SCIP *scip, SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)))
int * SCIPgetDurationsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsplitCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
SCIP_RETCODE SCIPvisualizeConsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity)
#define SCIP_DECL_SOLVECUMULATIVE(x)
int SCIPcomputeHmax(SCIP *scip, SCIP_PROFILE *profile, int capacity)
SCIP_RETCODE SCIPpresolveCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *delvars, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPcheckCumulativeCondition(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason)
SCIP_VAR ** SCIPgetVarsCumulative(SCIP *scip, SCIP_CONS *cons)
int * SCIPgetDemandsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsolveCumulative(SCIP *scip, int njobs, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Real *objvals, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
int SCIPgetHmaxCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPrespropCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool *explanation, SCIP_RESULT *result)
int SCIPgetCapacityCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPnormalizeCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
SCIP_RETCODE SCIPcreateWorstCaseProfile(SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands)
SCIP_RETCODE SCIPsetHminCumulative(SCIP *scip, SCIP_CONS *cons, int hmin)
int SCIPgetNVarsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetHmaxCumulative(SCIP *scip, SCIP_CONS *cons, int hmax)
SCIP_RETCODE SCIPcreateConsCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
int SCIPcomputeHmin(SCIP *scip, SCIP_PROFILE *profile, int capacity)
SCIP_RETCODE SCIPincludeConshdlrCumulative(SCIP *scip)
type definitions for constraints and constraint handlers
type definitions for LP management
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
type definitions for miscellaneous datastructures
result codes for SCIP callback methods
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for SCIP's main datastructure
type definitions for storing primal CIP solutions
timing definitions for SCIP
unsigned int SCIP_PRESOLTIMING
Definition: type_timing.h:61
type definitions for problem variables