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-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 pub_lp.h
17  * @ingroup PUBLICCOREAPI
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 "lpi/type_lpi.h"
29 #include "scip/def.h"
30 #include "scip/type_cons.h"
31 #include "scip/type_lp.h"
32 #include "scip/type_sepa.h"
33 #include "scip/type_var.h"
34 #include "scip/type_misc.h"
35 
36 #ifdef NDEBUG
37 #include "scip/struct_lp.h"
38 #endif
39 
40 #ifdef __cplusplus
41 extern "C" {
42 #endif
43 
44 
45 /**@addtogroup PublicColumnMethods
46  *
47  * @{
48  */
49 
50 /** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones
51  */
52 extern
53 void SCIPcolSort(
54  SCIP_COL* col /**< column to be sorted */
55  );
56 
57 /** gets objective value of column */
58 extern
60  SCIP_COL* col /**< LP column */
61  );
62 
63 /** gets lower bound of column */
64 extern
66  SCIP_COL* col /**< LP column */
67  );
68 
69 /** gets upper bound of column */
70 extern
72  SCIP_COL* col /**< LP column */
73  );
74 
75 /** gets best bound of column with respect to the objective function */
76 extern
78  SCIP_COL* col /**< LP column */
79  );
80 
81 /** gets the primal LP solution of a column */
82 extern
84  SCIP_COL* col /**< LP column */
85  );
86 
87 /** gets the minimal LP solution value, this column ever assumed */
88 extern
90  SCIP_COL* col /**< LP column */
91  );
92 
93 /** gets the maximal LP solution value, this column ever assumed */
94 extern
96  SCIP_COL* col /**< LP column */
97  );
98 
99 /** gets the basis status of a column in the LP solution; only valid for LPs with status SCIP_LPSOLSTAT_OPTIMAL
100  * and with SCIPisLPSolBasic(scip) == TRUE; returns SCIP_BASESTAT_ZERO for columns not in the current SCIP_LP
101  */
102 extern
104  SCIP_COL* col /**< LP column */
105  );
106 
107 /** gets variable this column represents */
108 extern
110  SCIP_COL* col /**< LP column */
111  );
112 
113 /** gets unique index of col */
114 extern
115 int SCIPcolGetIndex(
116  SCIP_COL* col /**< LP col */
117  );
118 
119 /** returns whether the associated variable is of integral type (binary, integer, implicit integer) */
120 extern
122  SCIP_COL* col /**< LP column */
123  );
124 
125 /** returns TRUE iff column is removable from the LP (due to aging or cleanup) */
126 extern
128  SCIP_COL* col /**< LP column */
129  );
130 
131 /** gets position of column in current LP, or -1 if it is not in LP */
132 extern
133 int SCIPcolGetLPPos(
134  SCIP_COL* col /**< LP column */
135  );
136 
137 /** gets depth in the tree where the column entered the LP, or -1 if it is not in LP */
138 extern
140  SCIP_COL* col /**< LP column */
141  );
142 
143 /** returns TRUE iff column is member of current LP */
144 extern
146  SCIP_COL* col /**< LP column */
147  );
148 
149 /** get number of nonzero entries in column vector */
150 extern
151 int SCIPcolGetNNonz(
152  SCIP_COL* col /**< LP column */
153  );
154 
155 /** get number of nonzero entries in column vector, that correspond to rows currently in the SCIP_LP;
156  *
157  * @warning This method is only applicable on columns, that are completely linked to their rows (e.g. a column
158  * 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
159  */
160 extern
162  SCIP_COL* col /**< LP column */
163  );
164 
165 /** gets array with rows of nonzero entries */
166 extern
168  SCIP_COL* col /**< LP column */
169  );
170 
171 /** gets array with coefficients of nonzero entries */
172 extern
174  SCIP_COL* col /**< LP column */
175  );
176 
177 /** gets node number of the last node in current branch and bound run, where strong branching was used on the
178  * given column, or -1 if strong branching was never applied to the column in current run
179  */
180 extern
182  SCIP_COL* col /**< LP column */
183  );
184 
185 /** gets number of times, strong branching was applied in current run on the given column */
186 extern
188  SCIP_COL* col /**< LP column */
189  );
190 
191 /** gets opposite bound type of given bound type */
192 extern
194  SCIP_BOUNDTYPE boundtype /**< type of bound (lower or upper) */
195  );
196 
197 #ifdef NDEBUG
198 
199 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
200  * speed up the algorithms.
201  */
202 
203 #define SCIPcolGetObj(col) (col)->obj
204 #define SCIPcolGetLb(col) (col)->lb
205 #define SCIPcolGetUb(col) (col)->ub
206 #define SCIPcolGetBestBound(col) ((col)->obj >= 0.0 ? (col)->lb : (col)->ub)
207 #define SCIPcolGetPrimsol(col) ((col)->lppos >= 0 ? (col)->primsol : 0.0)
208 #define SCIPcolGetMinPrimsol(col) ((col)->minprimsol)
209 #define SCIPcolGetMaxPrimsol(col) ((col)->maxprimsol)
210 #define SCIPcolGetBasisStatus(col) ((SCIP_BASESTAT)(col)->basisstatus)
211 #define SCIPcolGetVar(col) (col)->var
212 #define SCIPcolGetIndex(col) (col)->index
213 #define SCIPcolIsIntegral(col) (col)->integral
214 #define SCIPcolIsRemovable(col) (col)->removable
215 #define SCIPcolGetLPPos(col) (col)->lppos
216 #define SCIPcolGetLPDepth(col) (col)->lpdepth
217 #define SCIPcolIsInLP(col) ((col)->lppos >= 0)
218 #define SCIPcolGetNNonz(col) (col)->len
219 #define SCIPcolGetNLPNonz(col) (col)->nlprows
220 #define SCIPcolGetRows(col) (col)->rows
221 #define SCIPcolGetVals(col) (col)->vals
222 #define SCIPcolGetStrongbranchNode(col) (col)->sbnode
223 #define SCIPcolGetNStrongbranchs(col) (col)->nsbcalls
224 #define SCIPboundtypeOpposite(boundtype) \
225  ((boundtype) == SCIP_BOUNDTYPE_LOWER ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER)
226 
227 #endif
228 
229 /**@} */
230 
231 
232 
233 /**@addtogroup PublicRowMethods
234  *
235  * @{
236  */
237 
238 /** comparison method for sorting rows by non-decreasing index */
239 extern
240 SCIP_DECL_SORTPTRCOMP(SCIProwComp);
241 
242 /** locks an unmodifiable row, which forbids further changes; has no effect on modifiable rows */
243 extern
244 void SCIProwLock(
245  SCIP_ROW* row /**< LP row */
246  );
247 
248 /** unlocks a lock of an unmodifiable row; a row with no sealed lock may be modified; has no effect on modifiable rows */
249 extern
250 void SCIProwUnlock(
251  SCIP_ROW* row /**< LP row */
252  );
253 
254 /** returns the scalar product of the coefficient vectors of the two given rows */
255 extern
257  SCIP_ROW* row1, /**< first LP row */
258  SCIP_ROW* row2 /**< second LP row */
259  );
260 
261 /** returns the degree of parallelism between the hyperplanes defined by the two row vectors v, w:
262  * p = |v*w|/(|v|*|w|);
263  * the hyperplanes are parallel, iff p = 1, they are orthogonal, iff p = 0
264  */
265 extern
267  SCIP_ROW* row1, /**< first LP row */
268  SCIP_ROW* row2, /**< second LP row */
269  char orthofunc /**< function used for calc. scalar prod. ('e'uclidean, 'd'iscrete) */
270  );
271 
272 /** returns the degree of orthogonality between the hyperplanes defined by the two row vectors v, w:
273  * o = 1 - |v*w|/(|v|*|w|);
274  * the hyperplanes are orthogonal, iff p = 1, they are parallel, iff p = 0
275  */
276 extern
278  SCIP_ROW* row1, /**< first LP row */
279  SCIP_ROW* row2, /**< second LP row */
280  char orthofunc /**< function used for calc. scalar prod. ('e'uclidean, 'd'iscrete) */
281  );
282 
283 /** sorts row entries such that LP columns precede non-LP columns and inside both parts lower column indices precede
284  * higher ones
285  */
286 extern
287 void SCIProwSort(
288  SCIP_ROW* row /**< row to be sorted */
289  );
290 
291 /** get number of nonzero entries in row vector */
292 extern
293 int SCIProwGetNNonz(
294  SCIP_ROW* row /**< LP row */
295  );
296 
297 /** get number of nonzero entries in row vector, that correspond to columns currently in the SCIP_LP;
298  *
299  * @warning This method is only applicable on rows, that are completely linked to their columns (e.g. a row
300  * 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
301  */
302 extern
304  SCIP_ROW* row /**< LP row */
305  );
306 
307 /** gets array with columns of nonzero entries */
308 extern
310  SCIP_ROW* row /**< LP row */
311  );
312 
313 /** gets array with coefficients of nonzero entries */
314 extern
316  SCIP_ROW* row /**< LP row */
317  );
318 
319 /** gets constant shift of row */
320 extern
322  SCIP_ROW* row /**< LP row */
323  );
324 
325 /** gets Euclidean norm of row vector */
326 extern
328  SCIP_ROW* row /**< LP row */
329  );
330 
331 /** gets sum norm of row vector (sum of absolute values of coefficients) */
332 extern
334  SCIP_ROW* row /**< LP row */
335  );
336 
337 /** returns the left hand side of the row */
338 extern
340  SCIP_ROW* row /**< LP row */
341  );
342 
343 /** returns the right hand side of the row */
344 extern
346  SCIP_ROW* row /**< LP row */
347  );
348 
349 /** gets the dual LP solution of a row */
350 extern
352  SCIP_ROW* row /**< LP row */
353  );
354 
355 /** gets the dual Farkas coefficient of a row in an infeasible LP */
356 extern
358  SCIP_ROW* row /**< LP row */
359  );
360 
361 /** gets the basis status of a row in the LP solution; only valid for LPs with status SCIP_LPSOLSTAT_OPTIMAL
362  * and with SCIPisLPSolBasic(scip) == TRUE; returns SCIP_BASESTAT_BASIC for rows not in the current SCIP_LP
363  */
364 extern
366  SCIP_ROW* row /**< LP row */
367  );
368 
369 /** returns the name of the row */
370 extern
371 const char* SCIProwGetName(
372  SCIP_ROW* row /**< LP row */
373  );
374 
375 /** gets unique index of row */
376 extern
377 int SCIProwGetIndex(
378  SCIP_ROW* row /**< LP row */
379  );
380 
381 /** gets age of row */
382 extern
383 int SCIProwGetAge(
384  SCIP_ROW* row /**< LP row */
385  );
386 
387 /** gets rank of row */
388 extern
389 int SCIProwGetRank(
390  SCIP_ROW* row /**< LP row */
391  );
392 
393 /** returns TRUE iff the activity of the row (without the row's constant) is always integral in a feasible solution */
394 extern
396  SCIP_ROW* row /**< LP row */
397  );
398 
399 /** returns TRUE iff row is only valid locally */
400 extern
402  SCIP_ROW* row /**< LP row */
403  );
404 
405 /** returns TRUE iff row is modifiable during node processing (subject to column generation) */
406 extern
408  SCIP_ROW* row /**< LP row */
409  );
410 
411 /** returns TRUE iff row is removable from the LP (due to aging or cleanup) */
412 extern
414  SCIP_ROW* row /**< LP row */
415  );
416 
417 /** returns type of origin that created the row */
418 extern
420  SCIP_ROW* row /**< LP row */
421  );
422 
423 /** returns origin constraint handler that created the row (NULL if not available) */
424 extern
426  SCIP_ROW* row /**< LP row */
427  );
428 
429 /** returns origin separator that created the row (NULL if not available) */
430 extern
432  SCIP_ROW* row /**< LP row */
433  );
434 
435 /** returns TRUE iff row is member of the global cut pool */
436 extern
438  SCIP_ROW* row /**< LP row */
439  );
440 
441 /** gets position of row in current LP, or -1 if it is not in LP */
442 extern
443 int SCIProwGetLPPos(
444  SCIP_ROW* row /**< LP row */
445  );
446 
447 /** gets depth in the tree where the row entered the LP, or -1 if it is not in LP */
448 extern
450  SCIP_ROW* row /**< LP row */
451  );
452 
453 /** returns TRUE iff row is member of current LP */
454 extern
456  SCIP_ROW* row /**< LP row */
457  );
458 
459 /** returns the number of times that this row has been sharp in an optimal LP solution */
460 extern
462  SCIP_ROW* row /**< row */
463  );
464 
465 /** returns the number of LPs since this row has been created */
466 extern
468  SCIP_ROW* row /**< row */
469  );
470 
471 /** changes the rank of LP row */
472 extern
473 void SCIProwChgRank(
474  SCIP_ROW* row, /**< LP row */
475  int rank /**< new value for rank */
476  );
477 
478 #ifdef NDEBUG
479 
480 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
481  * speed up the algorithms.
482  */
483 
484 #define SCIProwGetNNonz(row) (row)->len
485 #define SCIProwGetNLPNonz(row) (row)->nlpcols
486 #define SCIProwGetCols(row) (row)->cols
487 #define SCIProwGetVals(row) (row)->vals
488 #define SCIProwGetConstant(row) (row)->constant
489 #define SCIProwGetNorm(row) sqrt((row)->sqrnorm)
490 #define SCIProwGetSumNorm(row) (row)->sumnorm
491 #define SCIProwGetLhs(row) (row)->lhs
492 #define SCIProwGetRhs(row) (row)->rhs
493 #define SCIProwGetDualsol(row) ((row)->lppos >= 0 ? (row)->dualsol : 0.0)
494 #define SCIProwGetDualfarkas(row) ((row)->lppos >= 0 ? (row)->dualfarkas : 0.0)
495 #define SCIProwGetBasisStatus(row) ((SCIP_BASESTAT) (row)->basisstatus)
496 #define SCIProwGetName(row) (row)->name
497 #define SCIProwGetIndex(row) (row)->index
498 #define SCIProwGetAge(row) (row)->age
499 #define SCIProwGetRank(row) (row)->rank
500 #define SCIProwIsIntegral(row) (row)->integral
501 #define SCIProwIsLocal(row) (row)->local
502 #define SCIProwIsModifiable(row) (row)->modifiable
503 #define SCIProwIsRemovable(row) (row)->removable
504 #define SCIProwGetOrigintype(row) (row)->origintype
505 #define SCIProwGetOriginCons(row) ((SCIP_CONSHDLR*) ((SCIP_ROWORIGINTYPE) row->origintype == SCIP_ROWORIGINTYPE_CONS ? (row)->origin : NULL))
506 #define SCIProwGetOriginSepa(row) ((SCIP_SEPA*) ((SCIP_ROWORIGINTYPE) row->origintype == SCIP_ROWORIGINTYPE_SEPA ? (row)->origin : NULL))
507 #define SCIProwIsInGlobalCutpool(row) (row)->inglobalcutpool
508 #define SCIProwGetLPPos(row) (row)->lppos
509 #define SCIProwGetLPDepth(row) (row)->lpdepth
510 #define SCIProwIsInLP(row) ((row)->lppos >= 0)
511 #define SCIProwGetActiveLPCount(row) ((row)->activeinlpcounter)
512 #define SCIProwGetNLPsAfterCreation(row) ((row)->nlpsaftercreation)
513 #define SCIProwChgRank(row, cutrank) ((row)->rank = (cutrank))
514 
515 #endif
516 
517 /**@} */
518 
519 #ifdef __cplusplus
520 }
521 #endif
522 
523 #endif
SCIP_Bool SCIProwIsRemovable(SCIP_ROW *row)
Definition: lp.c:16998
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_Real SCIProwGetScalarProduct(SCIP_ROW *row1, SCIP_ROW *row2)
Definition: lp.c:6915
type definitions for miscellaneous datastructures
int SCIProwGetAge(SCIP_ROW *row)
Definition: lp.c:16948
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17033
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:86
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16628
enum SCIP_RowOriginType SCIP_ROWORIGINTYPE
Definition: type_lp.h:68
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16748
SCIP_Longint SCIPcolGetStrongbranchNode(SCIP_COL *col)
Definition: lp.c:16760
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16790
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16928
SCIP_Longint SCIProwGetActiveLPCount(SCIP_ROW *row)
Definition: lp.c:17102
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:16804
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16869
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:16659
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16570
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:16917
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
Definition: lp.c:16550
int SCIPcolGetLPDepth(SCIP_COL *col)
Definition: lp.c:16691
SCIP_ROWORIGINTYPE SCIProwGetOrigintype(SCIP_ROW *row)
Definition: lp.c:17008
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16889
type definitions for LP management
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17080
SCIP_Real SCIProwGetSumNorm(SCIP_ROW *row)
Definition: lp.c:16857
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16593
void SCIProwSort(SCIP_ROW *row)
Definition: lp.c:5923
SCIP_BOUNDTYPE SCIPboundtypeOpposite(SCIP_BOUNDTYPE boundtype)
Definition: lp.c:16780
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16738
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:16978
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16560
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:16968
type definitions for specific LP solvers interface
SCIP_CONSHDLR * SCIProwGetOriginCons(SCIP_ROW *row)
Definition: lp.c:17018
type definitions for problem variables
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16879
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:16988
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16815
int SCIPcolGetIndex(SCIP_COL *col)
Definition: lp.c:16649
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16825
#define SCIP_Bool
Definition: def.h:62
SCIP_Real SCIPcolGetBestBound(SCIP_COL *col)
Definition: lp.c:16580
SCIP_Bool SCIPcolIsRemovable(SCIP_COL *col)
Definition: lp.c:16670
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
Definition: lp.c:16902
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16958
SCIP_Real SCIPcolGetMinPrimsol(SCIP_COL *col)
Definition: lp.c:16606
void SCIProwLock(SCIP_ROW *row)
Definition: lp.c:5285
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7631
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16835
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16713
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16639
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17091
type definitions for separators
data structures for LP management
int SCIPcolGetNStrongbranchs(SCIP_COL *col)
Definition: lp.c:16770
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17058
#define SCIP_Real
Definition: def.h:150
#define SCIP_Longint
Definition: def.h:135
int SCIProwGetLPDepth(SCIP_ROW *row)
Definition: lp.c:17069
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:16938
void SCIPcolSort(SCIP_COL *col)
Definition: lp.c:3372
SCIP_DECL_SORTPTRCOMP(SCIProwComp)
Definition: lp.c:933
common defines and data types used in all packages of SCIP
SCIP_Real SCIPcolGetMaxPrimsol(SCIP_COL *col)
Definition: lp.c:16616
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:16727
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16680
SCIP_Longint SCIProwGetNLPsAfterCreation(SCIP_ROW *row)
Definition: lp.c:17112
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16845
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition: lp.c:16702
SCIP_Real SCIProwGetOrthogonality(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7695
type definitions for constraints and constraint handlers
void SCIProwUnlock(SCIP_ROW *row)
Definition: lp.c:5300
SCIP_Bool SCIProwIsInGlobalCutpool(SCIP_ROW *row)
Definition: lp.c:17048