Scippy

SCIP

Solving Constraint Integer Programs

pub_lp.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-2016 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file pub_lp.h
17  * @ingroup PUBLICMETHODS
18  * @brief public methods for LP management
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_PUB_LP_H__
25 #define __SCIP_PUB_LP_H__
26 
27 
28 #include <stdio.h>
29 
30 #include "scip/def.h"
31 #include "blockmemshell/memory.h"
32 #include "scip/type_set.h"
33 #include "scip/type_stat.h"
34 #include "scip/type_lp.h"
35 #include "scip/type_var.h"
36 #include "scip/type_sol.h"
37 #include "scip/type_sepa.h"
38 #include "scip/type_misc.h"
39 #include "lpi/type_lpi.h"
40 
41 #ifdef NDEBUG
42 #include "scip/struct_lp.h"
43 #endif
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 
50 /**@defgroup ColumnMethods Column methods
51  *
52  * @{
53  */
54 
55 /** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones
56  */
57 extern
58 void SCIPcolSort(
59  SCIP_COL* col /**< column to be sorted */
60  );
61 
62 /** gets objective value of column */
63 extern
65  SCIP_COL* col /**< LP column */
66  );
67 
68 /** gets lower bound of column */
69 extern
71  SCIP_COL* col /**< LP column */
72  );
73 
74 /** gets upper bound of column */
75 extern
77  SCIP_COL* col /**< LP column */
78  );
79 
80 /** gets best bound of column with respect to the objective function */
81 extern
83  SCIP_COL* col /**< LP column */
84  );
85 
86 /** gets the primal LP solution of a column */
87 extern
89  SCIP_COL* col /**< LP column */
90  );
91 
92 /** gets the minimal LP solution value, this column ever assumed */
93 extern
95  SCIP_COL* col /**< LP column */
96  );
97 
98 /** gets the maximal LP solution value, this column ever assumed */
99 extern
101  SCIP_COL* col /**< LP column */
102  );
103 
104 /** gets the basis status of a column in the LP solution; only valid for LPs with status SCIP_LPSOLSTAT_OPTIMAL
105  * and with SCIPisLPSolBasic(scip) == TRUE; returns SCIP_BASESTAT_ZERO for columns not in the current SCIP_LP
106  */
107 extern
109  SCIP_COL* col /**< LP column */
110  );
111 
112 /** gets variable this column represents */
113 extern
115  SCIP_COL* col /**< LP column */
116  );
117 
118 /** gets unique index of col */
119 extern
120 int SCIPcolGetIndex(
121  SCIP_COL* col /**< LP col */
122  );
123 
124 /** returns whether the associated variable is of integral type (binary, integer, implicit integer) */
125 extern
127  SCIP_COL* col /**< LP column */
128  );
129 
130 /** returns TRUE iff column is removable from the LP (due to aging or cleanup) */
131 extern
133  SCIP_COL* col /**< LP column */
134  );
135 
136 /** gets position of column in current LP, or -1 if it is not in LP */
137 extern
138 int SCIPcolGetLPPos(
139  SCIP_COL* col /**< LP column */
140  );
141 
142 /** gets depth in the tree where the column entered the LP, or -1 if it is not in LP */
143 extern
145  SCIP_COL* col /**< LP column */
146  );
147 
148 /** returns TRUE iff column is member of current LP */
149 extern
151  SCIP_COL* col /**< LP column */
152  );
153 
154 /** get number of nonzero entries in column vector */
155 extern
156 int SCIPcolGetNNonz(
157  SCIP_COL* col /**< LP column */
158  );
159 
160 /** get number of nonzero entries in column vector, that correspond to rows currently in the SCIP_LP;
161  *
162  * @warning This method is only applicable on columns, that are completely linked to their rows (e.g. a column
163  * that is in the current LP and the LP was solved, or a column that was in a solved LP and didn't change afterwards
164  */
165 extern
167  SCIP_COL* col /**< LP column */
168  );
169 
170 /** gets array with rows of nonzero entries */
171 extern
173  SCIP_COL* col /**< LP column */
174  );
175 
176 /** gets array with coefficients of nonzero entries */
177 extern
179  SCIP_COL* col /**< LP column */
180  );
181 
182 /** gets node number of the last node in current branch and bound run, where strong branching was used on the
183  * given column, or -1 if strong branching was never applied to the column in current run
184  */
185 extern
187  SCIP_COL* col /**< LP column */
188  );
189 
190 /** gets number of times, strong branching was applied in current run on the given column */
191 extern
193  SCIP_COL* col /**< LP column */
194  );
195 
196 /** gets opposite bound type of given bound type */
197 extern
199  SCIP_BOUNDTYPE boundtype /**< type of bound (lower or upper) */
200  );
201 
202 #ifdef NDEBUG
203 
204 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
205  * speed up the algorithms.
206  */
207 
208 #define SCIPcolGetObj(col) (col)->obj
209 #define SCIPcolGetLb(col) (col)->lb
210 #define SCIPcolGetUb(col) (col)->ub
211 #define SCIPcolGetBestBound(col) ((col)->obj >= 0.0 ? (col)->lb : (col)->ub)
212 #define SCIPcolGetPrimsol(col) ((col)->lppos >= 0 ? (col)->primsol : 0.0)
213 #define SCIPcolGetMinPrimsol(col) ((col)->minprimsol)
214 #define SCIPcolGetMaxPrimsol(col) ((col)->maxprimsol)
215 #define SCIPcolGetBasisStatus(col) ((SCIP_BASESTAT)(col)->basisstatus)
216 #define SCIPcolGetVar(col) (col)->var
217 #define SCIPcolGetIndex(col) (col)->index
218 #define SCIPcolIsIntegral(col) (col)->integral
219 #define SCIPcolIsRemovable(col) (col)->removable
220 #define SCIPcolGetLPPos(col) (col)->lppos
221 #define SCIPcolGetLPDepth(col) (col)->lpdepth
222 #define SCIPcolIsInLP(col) ((col)->lppos >= 0)
223 #define SCIPcolGetNNonz(col) (col)->len
224 #define SCIPcolGetNLPNonz(col) (col)->nlprows
225 #define SCIPcolGetRows(col) (col)->rows
226 #define SCIPcolGetVals(col) (col)->vals
227 #define SCIPcolGetStrongbranchNode(col) (col)->sbnode
228 #define SCIPcolGetNStrongbranchs(col) (col)->nsbcalls
229 #define SCIPboundtypeOpposite(boundtype) \
230  ((boundtype) == SCIP_BOUNDTYPE_LOWER ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER)
231 
232 #endif
233 
234 /**@} */
235 
236 
237 
238 /**@defgroup RowMethods Row methods
239  *
240  * @{
241  */
242 
243 /** comparison method for sorting rows by non-decreasing index */
244 extern
245 SCIP_DECL_SORTPTRCOMP(SCIProwComp);
246 
247 /** locks an unmodifiable row, which forbids further changes; has no effect on modifiable rows */
248 extern
249 void SCIProwLock(
250  SCIP_ROW* row /**< LP row */
251  );
252 
253 /** unlocks a lock of an unmodifiable row; a row with no sealed lock may be modified; has no effect on modifiable rows */
254 extern
255 void SCIProwUnlock(
256  SCIP_ROW* row /**< LP row */
257  );
258 
259 /** returns the scalar product of the coefficient vectors of the two given rows */
260 extern
262  SCIP_ROW* row1, /**< first LP row */
263  SCIP_ROW* row2 /**< second LP row */
264  );
265 
266 /** returns the degree of parallelism between the hyperplanes defined by the two row vectors v, w:
267  * p = |v*w|/(|v|*|w|);
268  * the hyperplanes are parallel, iff p = 1, they are orthogonal, iff p = 0
269  */
270 extern
272  SCIP_ROW* row1, /**< first LP row */
273  SCIP_ROW* row2, /**< second LP row */
274  char orthofunc /**< function used for calc. scalar prod. ('e'uclidean, 'd'iscrete) */
275  );
276 
277 /** returns the degree of orthogonality between the hyperplanes defined by the two row vectors v, w:
278  * o = 1 - |v*w|/(|v|*|w|);
279  * the hyperplanes are orthogonal, iff p = 1, they are parallel, iff p = 0
280  */
281 extern
283  SCIP_ROW* row1, /**< first LP row */
284  SCIP_ROW* row2, /**< second LP row */
285  char orthofunc /**< function used for calc. scalar prod. ('e'uclidean, 'd'iscrete) */
286  );
287 
288 /** sorts row entries such that LP columns precede non-LP columns and inside both parts lower column indices precede
289  * higher ones
290  */
291 extern
292 void SCIProwSort(
293  SCIP_ROW* row /**< row to be sorted */
294  );
295 
296 /** get number of nonzero entries in row vector */
297 extern
298 int SCIProwGetNNonz(
299  SCIP_ROW* row /**< LP row */
300  );
301 
302 /** get number of nonzero entries in row vector, that correspond to columns currently in the SCIP_LP;
303  *
304  * @warning This method is only applicable on rows, that are completely linked to their columns (e.g. a row
305  * that is in the current LP and the LP was solved, or a row that was in a solved LP and didn't change afterwards
306  */
307 extern
309  SCIP_ROW* row /**< LP row */
310  );
311 
312 /** gets array with columns of nonzero entries */
313 extern
315  SCIP_ROW* row /**< LP row */
316  );
317 
318 /** gets array with coefficients of nonzero entries */
319 extern
321  SCIP_ROW* row /**< LP row */
322  );
323 
324 /** gets constant shift of row */
325 extern
327  SCIP_ROW* row /**< LP row */
328  );
329 
330 /** gets Euclidean norm of row vector */
331 extern
333  SCIP_ROW* row /**< LP row */
334  );
335 
336 /** gets sum norm of row vector (sum of absolute values of coefficients) */
337 extern
339  SCIP_ROW* row /**< LP row */
340  );
341 
342 /** returns the left hand side of the row */
343 extern
345  SCIP_ROW* row /**< LP row */
346  );
347 
348 /** returns the right hand side of the row */
349 extern
351  SCIP_ROW* row /**< LP row */
352  );
353 
354 /** gets the dual LP solution of a row */
355 extern
357  SCIP_ROW* row /**< LP row */
358  );
359 
360 /** gets the dual Farkas coefficient of a row in an infeasible LP */
361 extern
363  SCIP_ROW* row /**< LP row */
364  );
365 
366 /** gets the basis status of a row in the LP solution; only valid for LPs with status SCIP_LPSOLSTAT_OPTIMAL
367  * and with SCIPisLPSolBasic(scip) == TRUE; returns SCIP_BASESTAT_BASIC for rows not in the current SCIP_LP
368  */
369 extern
371  SCIP_ROW* row /**< LP row */
372  );
373 
374 /** returns the name of the row */
375 extern
376 const char* SCIProwGetName(
377  SCIP_ROW* row /**< LP row */
378  );
379 
380 /** gets unique index of row */
381 extern
382 int SCIProwGetIndex(
383  SCIP_ROW* row /**< LP row */
384  );
385 
386 /** gets age of row */
387 extern
388 int SCIProwGetAge(
389  SCIP_ROW* row /**< LP row */
390  );
391 
392 /** gets rank of row */
393 extern
394 int SCIProwGetRank(
395  SCIP_ROW* row /**< LP row */
396  );
397 
398 /** returns TRUE iff the activity of the row (without the row's constant) is always integral in a feasible solution */
399 extern
401  SCIP_ROW* row /**< LP row */
402  );
403 
404 /** returns TRUE iff row is only valid locally */
405 extern
407  SCIP_ROW* row /**< LP row */
408  );
409 
410 /** returns TRUE iff row is modifiable during node processing (subject to column generation) */
411 extern
413  SCIP_ROW* row /**< LP row */
414  );
415 
416 /** returns TRUE iff row is removable from the LP (due to aging or cleanup) */
417 extern
419  SCIP_ROW* row /**< LP row */
420  );
421 
422 /** returns type of origin that created the row */
423 extern
425  SCIP_ROW* row /**< LP row */
426  );
427 
428 /** returns origin constraint handler that created the row (NULL if not available) */
429 extern
431  SCIP_ROW* row /**< LP row */
432  );
433 
434 /** returns origin separator that created the row (NULL if not available) */
435 extern
437  SCIP_ROW* row /**< LP row */
438  );
439 
440 /** returns TRUE iff row is member of the global cut pool */
441 extern
443  SCIP_ROW* row /**< LP row */
444  );
445 
446 /** gets position of row in current LP, or -1 if it is not in LP */
447 extern
448 int SCIProwGetLPPos(
449  SCIP_ROW* row /**< LP row */
450  );
451 
452 /** gets depth in the tree where the row entered the LP, or -1 if it is not in LP */
453 extern
455  SCIP_ROW* row /**< LP row */
456  );
457 
458 /** returns TRUE iff row is member of current LP */
459 extern
461  SCIP_ROW* row /**< LP row */
462  );
463 
464 /** returns the number of times that this row has been sharp in an optimal LP solution */
465 extern
467  SCIP_ROW* row /**< row */
468  );
469 
470 /** returns the number of LPs since this row has been created */
471 extern
473  SCIP_ROW* row /**< row */
474  );
475 
476 /** changes the rank of LP row */
477 extern
478 void SCIProwChgRank(
479  SCIP_ROW* row, /**< LP row */
480  int rank /**< new value for rank */
481  );
482 
483 #ifdef NDEBUG
484 
485 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
486  * speed up the algorithms.
487  */
488 
489 #define SCIProwGetNNonz(row) (row)->len
490 #define SCIProwGetNLPNonz(row) (row)->nlpcols
491 #define SCIProwGetCols(row) (row)->cols
492 #define SCIProwGetVals(row) (row)->vals
493 #define SCIProwGetConstant(row) (row)->constant
494 #define SCIProwGetNorm(row) sqrt((row)->sqrnorm)
495 #define SCIProwGetSumNorm(row) (row)->sumnorm
496 #define SCIProwGetLhs(row) (row)->lhs
497 #define SCIProwGetRhs(row) (row)->rhs
498 #define SCIProwGetDualsol(row) ((row)->lppos >= 0 ? (row)->dualsol : 0.0)
499 #define SCIProwGetDualfarkas(row) ((row)->lppos >= 0 ? (row)->dualfarkas : 0.0)
500 #define SCIProwGetBasisStatus(row) ((SCIP_BASESTAT) (row)->basisstatus)
501 #define SCIProwGetName(row) (row)->name
502 #define SCIProwGetIndex(row) (row)->index
503 #define SCIProwGetAge(row) (row)->age
504 #define SCIProwGetRank(row) (row)->rank
505 #define SCIProwIsIntegral(row) (row)->integral
506 #define SCIProwIsLocal(row) (row)->local
507 #define SCIProwIsModifiable(row) (row)->modifiable
508 #define SCIProwIsRemovable(row) (row)->removable
509 #define SCIProwGetOrigintype(row) (row)->origintype
510 #define SCIProwGetOriginCons(row) ((SCIP_CONSHDLR*) ((SCIP_ROWORIGINTYPE) row->origintype == SCIP_ROWORIGINTYPE_CONS ? (row)->origin : NULL))
511 #define SCIProwGetOriginSepa(row) ((SCIP_SEPA*) ((SCIP_ROWORIGINTYPE) row->origintype == SCIP_ROWORIGINTYPE_SEPA ? (row)->origin : NULL))
512 #define SCIProwIsInGlobalCutpool(row) (row)->inglobalcutpool
513 #define SCIProwGetLPPos(row) (row)->lppos
514 #define SCIProwGetLPDepth(row) (row)->lpdepth
515 #define SCIProwIsInLP(row) ((row)->lppos >= 0)
516 #define SCIProwGetActiveLPCount(row) ((row)->activeinlpcounter)
517 #define SCIProwGetNLPsAfterCreation(row) ((row)->nlpsaftercreation)
518 #define SCIProwChgRank(row, cutrank) ((row)->rank = (cutrank))
519 
520 #endif
521 
522 /**@} */
523 
524 /**@defgroup LPMethods LP methods
525  *
526  * @{
527  */
528 
529 /**@} */
530 
531 #ifdef __cplusplus
532 }
533 #endif
534 
535 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_CONSHDLR * SCIProwGetOriginCons(SCIP_ROW *row)
Definition: lp.c:19064
SCIP_Bool SCIProwIsInGlobalCutpool(SCIP_ROW *row)
Definition: lp.c:19094
type definitions for miscellaneous datastructures
SCIP_Longint SCIProwGetNLPsAfterCreation(SCIP_ROW *row)
Definition: lp.c:19158
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:84
enum SCIP_RowOriginType SCIP_ROWORIGINTYPE
Definition: type_lp.h:67
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:18915
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:18861
SCIP_DECL_SORTPTRCOMP(SCIProwComp)
Definition: lp.c:901
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition: lp.c:18748
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:19079
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:18850
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
Definition: lp.c:18596
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:18984
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:18963
void SCIPcolSort(SCIP_COL *col)
Definition: lp.c:3241
type definitions for global SCIP settings
int SCIProwGetLPDepth(SCIP_ROW *row)
Definition: lp.c:19115
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:18881
type definitions for problem statistics
SCIP_Real SCIProwGetScalarProduct(SCIP_ROW *row1, SCIP_ROW *row2)
Definition: lp.c:6687
type definitions for LP management
SCIP_Real SCIPcolGetMaxPrimsol(SCIP_COL *col)
Definition: lp.c:18662
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:18726
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:18674
void SCIProwUnlock(SCIP_ROW *row)
Definition: lp.c:5159
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:18784
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:19034
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:18705
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:18925
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7403
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:18639
int SCIProwGetAge(SCIP_ROW *row)
Definition: lp.c:18994
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:19004
int SCIPcolGetNStrongbranchs(SCIP_COL *col)
Definition: lp.c:18816
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:19126
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:19024
type definitions for specific LP solvers interface
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:18773
type definitions for problem variables
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:18974
void SCIProwLock(SCIP_ROW *row)
Definition: lp.c:5144
SCIP_Bool SCIPcolIsRemovable(SCIP_COL *col)
Definition: lp.c:18716
SCIP_Real SCIPcolGetMinPrimsol(SCIP_COL *col)
Definition: lp.c:18652
SCIP_Real SCIPcolGetBestBound(SCIP_COL *col)
Definition: lp.c:18626
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:19137
#define SCIP_Bool
Definition: def.h:53
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:18891
SCIP_BOUNDTYPE SCIPboundtypeOpposite(SCIP_BOUNDTYPE boundtype)
Definition: lp.c:18826
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:18606
type definitions for storing primal CIP solutions
SCIP_Real SCIProwGetOrthogonality(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7435
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:18935
SCIP_Longint SCIProwGetActiveLPCount(SCIP_ROW *row)
Definition: lp.c:19148
type definitions for separators
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:18871
datastructures for LP management
SCIP_Longint SCIPcolGetStrongbranchNode(SCIP_COL *col)
Definition: lp.c:18806
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:19014
#define SCIP_Real
Definition: def.h:127
void SCIProwSort(SCIP_ROW *row)
Definition: lp.c:5780
SCIP_ROWORIGINTYPE SCIProwGetOrigintype(SCIP_ROW *row)
Definition: lp.c:19054
#define SCIP_Longint
Definition: def.h:112
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:19104
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:18616
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:18836
common defines and data types used in all packages of SCIP
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
Definition: lp.c:18948
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:18685
SCIP_Real SCIProwGetSumNorm(SCIP_ROW *row)
Definition: lp.c:18903
SCIP_Bool SCIProwIsRemovable(SCIP_ROW *row)
Definition: lp.c:19044
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:18794
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:18759
int SCIPcolGetIndex(SCIP_COL *col)
Definition: lp.c:18695
int SCIPcolGetLPDepth(SCIP_COL *col)
Definition: lp.c:18737
memory allocation routines