1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file lpi.h
17 * @ingroup LPIS
18 * @brief interface methods for specific LP solvers
19 * @author Tobias Achterberg
20 * @author Marc Pfetsch
21 *
22 */
23
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25
26 #ifndef __SCIP_LPI_H__
27 #define __SCIP_LPI_H__
28
29 #include "blockmemshell/memory.h"
30 #include "lpi/type_lpi.h"
31 #include "scip/def.h"
32 #include "scip/type_message.h"
33 #include "scip/type_retcode.h"
34
35 #ifdef __cplusplus
36 extern "C" {
37 #endif
38
39 /**@addtogroup LPIS
40 *
41 * This file specifies a generic LP solver interface used by SCIP to create, modify, and solve linear programs of the
42 * form
43 *
44 * min/max obj * x
45 * lhs <= A * x <= rhs
46 * lb <= x <= ub
47 *
48 * and query information about the solution. Although it includes a few SCIP header files, e.g., because it uses SCIP's
49 * return codes, it can be used independently of any SCIP instance.
50 *
51 * The basis status for (column) variables are as follows:
52 * - If x_j = lb, then j is at its lower bound (SCIP_BASESTAT_LOWER).
53 * - If x_j = ub, then j is at its lower bound (SCIP_BASESTAT_UPPER).
54 * - If x_j is in the basis, it has SCIP_BASESTAT_BASIC status.
55 * - If x_j is free and non-basic, it has SCIP_BASESTAT_ZERO status.
56 *
57 * The basis status for (row) slack variables are:
58 * - If (A * x)_i = lhs, then i is at its lower bound (SCIP_BASESTAT_LOWER).
59 * - If (A * x)_i = rhs, then i is at its upper bound (SCIP_BASESTAT_UPPER).
60 * - If the slack variable for row i is basic, it has SCIP_BASESTAT_BASIC status.
61 *
62 * If the solvers use their status differently, those status codes have to be corrected.
63 *
64 * In the methods accessing information about the (inverse of the) basis matrix, the interface assumes the following
65 * column-oriented format: slack variables of rows have coefficient +1 and the basis matrix is a regular m times m
66 * submatrix of (A,I), where m is the number of rows and I is the identity matrix. This means that if, internally, the
67 * LP solver uses coefficients -1 for some of the slack variables, then every row associated with a slack variable whose
68 * coefficient is -1 should be negated in order to return the result in terms of the LP interface definition.
69 *
70 * The creation of a new LP should always be done in the following ways: Either one can use SCIPlpiLoadColLP() or one
71 * first adds empty columns or rows. Then the matrix entries can be added by adding columns and rows, respectively.
72 * Adding matrix entries for a row or column that have not been added before will result in an error.
73 *
74 * The handling of the objective limit is as follows, if supported by the LP-solver: If the objective is larger than the
75 * objective limit for minimization problems or smaller than the objective limit for maximization problems, the solution
76 * process can be stopped. This naturally occurs in a branch-and-bound process, where the objective limit is set to the
77 * value of the best solution found so far. If the problem is a minimization problem and we use the dual simplex, the
78 * dual feasible solutions are maximized. If their value are larger than the objective limit, the process can be
79 * stopped. In this case, no feasible integer solution can be found in the corresponding branch.
80 *
81 * Some LP-solvers also support the opposite setting, but this can easily be checked after the solution process (i.e.,
82 * for a minimization problem a check whether the optimal value is smaller than the limit). Note that this check can
83 * only be determined at the end of the optimization. Thus, we do not support this.
84 *
85 * @{
86 */
87
88 /*
89 * Miscellaneous Methods
90 */
91
92 /**@name Miscellaneous Methods */
93 /**@{ */
94
95 /** gets name and version of LP solver */
96 SCIP_EXPORT
97 const char* SCIPlpiGetSolverName(
98 void
99 );
100
101 /** gets description of LP solver (developer, webpage, ...) */
102 SCIP_EXPORT
103 const char* SCIPlpiGetSolverDesc(
104 void
105 );
106
107 /** gets pointer for LP solver - use only with great care
108 *
109 * The behavior of this function depends on the solver and its use is
110 * therefore only recommended if you really know what you are
111 * doing. In general, it returns a pointer to the LP solver object.
112 */
113 SCIP_EXPORT
114 void* SCIPlpiGetSolverPointer(
115 SCIP_LPI* lpi /**< pointer to an LP interface structure */
116 );
117
118 /** pass integrality information about variables to the solver */
119 SCIP_EXPORT
120 SCIP_RETCODE SCIPlpiSetIntegralityInformation(
121 SCIP_LPI* lpi, /**< pointer to an LP interface structure */
122 int ncols, /**< length of integrality array */
123 int* intInfo /**< integrality array (0: continuous, 1: integer). May be NULL iff ncols is 0. */
124 );
125
126 /** informs about availability of a primal simplex solving method */
127 SCIP_EXPORT
128 SCIP_Bool SCIPlpiHasPrimalSolve(
129 void
130 );
131
132 /** informs about availability of a dual simplex solving method */
133 SCIP_EXPORT
134 SCIP_Bool SCIPlpiHasDualSolve(
135 void
136 );
137
138 /** informs about availability of a barrier solving method */
139 SCIP_EXPORT
140 SCIP_Bool SCIPlpiHasBarrierSolve(
141 void
142 );
143
144 /**@} */
145
146
147
148
149 /*
150 * LPI Creation and Destruction Methods
151 */
152
153 /**@name LPI Creation and Destruction Methods */
154 /**@{ */
155
156 /** creates an LP problem object */
157 SCIP_EXPORT
158 SCIP_RETCODE SCIPlpiCreate(
159 SCIP_LPI** lpi, /**< pointer to an LP interface structure */
160 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler to use for printing messages, or NULL */
161 const char* name, /**< problem name */
162 SCIP_OBJSEN objsen /**< objective sense */
163 );
164
165 /** deletes an LP problem object */
166 SCIP_EXPORT
167 SCIP_RETCODE SCIPlpiFree(
168 SCIP_LPI** lpi /**< pointer to an LP interface structure */
169 );
170
171 /**@} */
172
173
174
175
176 /*
177 * Modification Methods
178 */
179
180 /**@name Modification Methods */
181 /**@{ */
182
183 /** copies LP data with column matrix into LP solver */
184 SCIP_EXPORT
185 SCIP_RETCODE SCIPlpiLoadColLP(
186 SCIP_LPI* lpi, /**< LP interface structure */
187 SCIP_OBJSEN objsen, /**< objective sense */
188 int ncols, /**< number of columns */
189 const SCIP_Real* obj, /**< objective function values of columns */
190 const SCIP_Real* lb, /**< lower bounds of columns */
191 const SCIP_Real* ub, /**< upper bounds of columns */
192 char** colnames, /**< column names, or NULL */
193 int nrows, /**< number of rows */
194 const SCIP_Real* lhs, /**< left hand sides of rows */
195 const SCIP_Real* rhs, /**< right hand sides of rows */
196 char** rownames, /**< row names, or NULL */
197 int nnonz, /**< number of nonzero elements in the constraint matrix */
198 const int* beg, /**< start index of each column in ind- and val-array */
199 const int* ind, /**< row indices of constraint matrix entries */
200 const SCIP_Real* val /**< values of constraint matrix entries */
201 );
202
203 /** adds columns to the LP
204 *
205 * @note ind array is not checked for duplicates, problems may appear if indices are added more than once
206 */
207 SCIP_EXPORT
208 SCIP_RETCODE SCIPlpiAddCols(
209 SCIP_LPI* lpi, /**< LP interface structure */
210 int ncols, /**< number of columns to be added */
211 const SCIP_Real* obj, /**< objective function values of new columns */
212 const SCIP_Real* lb, /**< lower bounds of new columns */
213 const SCIP_Real* ub, /**< upper bounds of new columns */
214 char** colnames, /**< column names, or NULL */
215 int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
216 const int* beg, /**< start index of each column in ind- and val-array, or NULL if nnonz == 0 */
217 const int* ind, /**< row indices of constraint matrix entries, or NULL if nnonz == 0 */
218 const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
219 );
220
221 /** deletes all columns in the given range from LP */
222 SCIP_EXPORT
223 SCIP_RETCODE SCIPlpiDelCols(
224 SCIP_LPI* lpi, /**< LP interface structure */
225 int firstcol, /**< first column to be deleted */
226 int lastcol /**< last column to be deleted */
227 );
228
229 /** deletes columns from SCIP_LPI; the new position of a column must not be greater that its old position */
230 SCIP_EXPORT
231 SCIP_RETCODE SCIPlpiDelColset(
232 SCIP_LPI* lpi, /**< LP interface structure */
233 int* dstat /**< deletion status of columns
234 * input: 1 if column should be deleted, 0 if not
235 * output: new position of column, -1 if column was deleted */
236 );
237
238 /** adds rows to the LP
239 *
240 * @note ind array is not checked for duplicates, problems may appear if indices are added more than once
241 */
242 SCIP_EXPORT
243 SCIP_RETCODE SCIPlpiAddRows(
244 SCIP_LPI* lpi, /**< LP interface structure */
245 int nrows, /**< number of rows to be added */
246 const SCIP_Real* lhs, /**< left hand sides of new rows */
247 const SCIP_Real* rhs, /**< right hand sides of new rows */
248 char** rownames, /**< row names, or NULL */
249 int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
250 const int* beg, /**< start index of each row in ind- and val-array, or NULL if nnonz == 0 */
251 const int* ind, /**< column indices of constraint matrix entries, or NULL if nnonz == 0 */
252 const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
253 );
254
255 /** deletes all rows in the given range from LP */
256 SCIP_EXPORT
257 SCIP_RETCODE SCIPlpiDelRows(
258 SCIP_LPI* lpi, /**< LP interface structure */
259 int firstrow, /**< first row to be deleted */
260 int lastrow /**< last row to be deleted */
261 );
262
263 /** deletes rows from SCIP_LPI; the new position of a row must not be greater that its old position */
264 SCIP_EXPORT
265 SCIP_RETCODE SCIPlpiDelRowset(
266 SCIP_LPI* lpi, /**< LP interface structure */
267 int* dstat /**< deletion status of rows
268 * input: 1 if row should be deleted, 0 if not
269 * output: new position of row, -1 if row was deleted */
270 );
271
272 /** clears the whole LP */
273 SCIP_EXPORT
274 SCIP_RETCODE SCIPlpiClear(
275 SCIP_LPI* lpi /**< LP interface structure */
276 );
277
278 /** changes lower and upper bounds of columns */
279 SCIP_EXPORT
280 SCIP_RETCODE SCIPlpiChgBounds(
281 SCIP_LPI* lpi, /**< LP interface structure */
282 int ncols, /**< number of columns to change bounds for */
283 const int* ind, /**< column indices or NULL if ncols is zero */
284 const SCIP_Real* lb, /**< values for the new lower bounds or NULL if ncols is zero */
285 const SCIP_Real* ub /**< values for the new upper bounds or NULL if ncols is zero */
286 );
287
288 /** changes left and right hand sides of rows */
289 SCIP_EXPORT
290 SCIP_RETCODE SCIPlpiChgSides(
291 SCIP_LPI* lpi, /**< LP interface structure */
292 int nrows, /**< number of rows to change sides for */
293 const int* ind, /**< row indices */
294 const SCIP_Real* lhs, /**< new values for left hand sides */
295 const SCIP_Real* rhs /**< new values for right hand sides */
296 );
297
298 /** changes a single coefficient */
299 SCIP_EXPORT
300 SCIP_RETCODE SCIPlpiChgCoef(
301 SCIP_LPI* lpi, /**< LP interface structure */
302 int row, /**< row number of coefficient to change */
303 int col, /**< column number of coefficient to change */
304 SCIP_Real newval /**< new value of coefficient */
305 );
306
307 /** changes the objective sense */
308 SCIP_EXPORT
309 SCIP_RETCODE SCIPlpiChgObjsen(
310 SCIP_LPI* lpi, /**< LP interface structure */
311 SCIP_OBJSEN objsen /**< new objective sense */
312 );
313
314 /** changes objective values of columns in the LP */
315 SCIP_EXPORT
316 SCIP_RETCODE SCIPlpiChgObj(
317 SCIP_LPI* lpi, /**< LP interface structure */
318 int ncols, /**< number of columns to change objective value for */
319 const int* ind, /**< column indices to change objective value for */
320 const SCIP_Real* obj /**< new objective values for columns */
321 );
322
323 /** multiplies a row with a non-zero scalar; for negative scalars, the row's sense is switched accordingly */
324 SCIP_EXPORT
325 SCIP_RETCODE SCIPlpiScaleRow(
326 SCIP_LPI* lpi, /**< LP interface structure */
327 int row, /**< row number to scale */
328 SCIP_Real scaleval /**< scaling multiplier */
329 );
330
331 /** multiplies a column with a non-zero scalar; the objective value is multiplied with the scalar, and the bounds
332 * are divided by the scalar; for negative scalars, the column's bounds are switched
333 */
334 SCIP_EXPORT
335 SCIP_RETCODE SCIPlpiScaleCol(
336 SCIP_LPI* lpi, /**< LP interface structure */
337 int col, /**< column number to scale */
338 SCIP_Real scaleval /**< scaling multiplier */
339 );
340
341 /**@} */
342
343
344
345
346 /*
347 * Data Accessing Methods
348 */
349
350 /**@name Data Accessing Methods */
351 /**@{ */
352
353 /** gets the number of rows in the LP */
354 SCIP_EXPORT
355 SCIP_RETCODE SCIPlpiGetNRows(
356 SCIP_LPI* lpi, /**< LP interface structure */
357 int* nrows /**< pointer to store the number of rows */
358 );
359
360 /** gets the number of columns in the LP */
361 SCIP_EXPORT
362 SCIP_RETCODE SCIPlpiGetNCols(
363 SCIP_LPI* lpi, /**< LP interface structure */
364 int* ncols /**< pointer to store the number of cols */
365 );
366
367 /** gets the objective sense of the LP */
368 SCIP_EXPORT
369 SCIP_RETCODE SCIPlpiGetObjsen(
370 SCIP_LPI* lpi, /**< LP interface structure */
371 SCIP_OBJSEN* objsen /**< pointer to store objective sense */
372 );
373
374 /** gets the number of nonzero elements in the LP constraint matrix */
375 SCIP_EXPORT
376 SCIP_RETCODE SCIPlpiGetNNonz(
377 SCIP_LPI* lpi, /**< LP interface structure */
378 int* nnonz /**< pointer to store the number of nonzeros */
379 );
380
381 /** gets columns from LP problem object; the arrays have to be large enough to store all values;
382 * Either both, lb and ub, have to be NULL, or both have to be non-NULL,
383 * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
384 */
385 SCIP_EXPORT
386 SCIP_RETCODE SCIPlpiGetCols(
387 SCIP_LPI* lpi, /**< LP interface structure */
388 int firstcol, /**< first column to get from LP */
389 int lastcol, /**< last column to get from LP */
390 SCIP_Real* lb, /**< buffer to store the lower bound vector, or NULL */
391 SCIP_Real* ub, /**< buffer to store the upper bound vector, or NULL */
392 int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
393 int* beg, /**< buffer to store start index of each column in ind- and val-array, or NULL */
394 int* ind, /**< buffer to store row indices of constraint matrix entries, or NULL */
395 SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
396 );
397
398 /** gets rows from LP problem object; the arrays have to be large enough to store all values.
399 * Either both, lhs and rhs, have to be NULL, or both have to be non-NULL,
400 * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
401 */
402 SCIP_EXPORT
403 SCIP_RETCODE SCIPlpiGetRows(
404 SCIP_LPI* lpi, /**< LP interface structure */
405 int firstrow, /**< first row to get from LP */
406 int lastrow, /**< last row to get from LP */
407 SCIP_Real* lhs, /**< buffer to store left hand side vector, or NULL */
408 SCIP_Real* rhs, /**< buffer to store right hand side vector, or NULL */
409 int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
410 int* beg, /**< buffer to store start index of each row in ind- and val-array, or NULL */
411 int* ind, /**< buffer to store column indices of constraint matrix entries, or NULL */
412 SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
413 );
414
415 /** gets column names */
416 SCIP_EXPORT
417 SCIP_RETCODE SCIPlpiGetColNames(
418 SCIP_LPI* lpi, /**< LP interface structure */
419 int firstcol, /**< first column to get name from LP */
420 int lastcol, /**< last column to get name from LP */
421 char** colnames, /**< pointers to column names (of size at least lastcol-firstcol+1) or NULL if namestoragesize is zero */
422 char* namestorage, /**< storage for col names or NULL if namestoragesize is zero */
423 int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */
424 int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */
425 );
426
427 /** gets row names */
428 SCIP_EXPORT
429 SCIP_RETCODE SCIPlpiGetRowNames(
430 SCIP_LPI* lpi, /**< LP interface structure */
431 int firstrow, /**< first row to get name from LP */
432 int lastrow, /**< last row to get name from LP */
433 char** rownames, /**< pointers to row names (of size at least lastrow-firstrow+1) or NULL if namestoragesize is zero */
434 char* namestorage, /**< storage for row names or NULL if namestoragesize is zero */
435 int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */
436 int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */
437 );
438
439 /** gets objective coefficients from LP problem object */
440 SCIP_EXPORT
441 SCIP_RETCODE SCIPlpiGetObj(
442 SCIP_LPI* lpi, /**< LP interface structure */
443 int firstcol, /**< first column to get objective coefficient for */
444 int lastcol, /**< last column to get objective coefficient for */
445 SCIP_Real* vals /**< array to store objective coefficients */
446 );
447
448 /** gets current bounds from LP problem object */
449 SCIP_EXPORT
450 SCIP_RETCODE SCIPlpiGetBounds(
451 SCIP_LPI* lpi, /**< LP interface structure */
452 int firstcol, /**< first column to get bounds for */
453 int lastcol, /**< last column to get bounds for */
454 SCIP_Real* lbs, /**< array to store lower bound values, or NULL */
455 SCIP_Real* ubs /**< array to store upper bound values, or NULL */
456 );
457
458 /** gets current row sides from LP problem object */
459 SCIP_EXPORT
460 SCIP_RETCODE SCIPlpiGetSides(
461 SCIP_LPI* lpi, /**< LP interface structure */
462 int firstrow, /**< first row to get sides for */
463 int lastrow, /**< last row to get sides for */
464 SCIP_Real* lhss, /**< array to store left hand side values, or NULL */
465 SCIP_Real* rhss /**< array to store right hand side values, or NULL */
466 );
467
468 /** gets a single coefficient */
469 SCIP_EXPORT
470 SCIP_RETCODE SCIPlpiGetCoef(
471 SCIP_LPI* lpi, /**< LP interface structure */
472 int row, /**< row number of coefficient */
473 int col, /**< column number of coefficient */
474 SCIP_Real* val /**< pointer to store the value of the coefficient */
475 );
476
477 /**@} */
478
479
480
481
482 /*
483 * Solving Methods
484 */
485
486 /**@name Solving Methods */
487 /**@{ */
488
489 /** calls primal simplex to solve the LP */
490 SCIP_EXPORT
491 SCIP_RETCODE SCIPlpiSolvePrimal(
492 SCIP_LPI* lpi /**< LP interface structure */
493 );
494
495 /** calls dual simplex to solve the LP */
496 SCIP_EXPORT
497 SCIP_RETCODE SCIPlpiSolveDual(
498 SCIP_LPI* lpi /**< LP interface structure */
499 );
500
501 /** calls barrier or interior point algorithm to solve the LP with crossover to simplex basis */
502 SCIP_EXPORT
503 SCIP_RETCODE SCIPlpiSolveBarrier(
504 SCIP_LPI* lpi, /**< LP interface structure */
505 SCIP_Bool crossover /**< perform crossover */
506 );
507
508 /** start strong branching - call before any strong branching */
509 SCIP_EXPORT
510 SCIP_RETCODE SCIPlpiStartStrongbranch(
511 SCIP_LPI* lpi /**< LP interface structure */
512 );
513
514 /** end strong branching - call after any strong branching */
515 SCIP_EXPORT
516 SCIP_RETCODE SCIPlpiEndStrongbranch(
517 SCIP_LPI* lpi /**< LP interface structure */
518 );
519
520 /** performs strong branching iterations on one @b fractional candidate */
521 SCIP_EXPORT
522 SCIP_RETCODE SCIPlpiStrongbranchFrac(
523 SCIP_LPI* lpi, /**< LP interface structure */
524 int col, /**< column to apply strong branching on */
525 SCIP_Real psol, /**< fractional current primal solution value of column */
526 int itlim, /**< iteration limit for strong branchings */
527 SCIP_Real* down, /**< stores dual bound after branching column down */
528 SCIP_Real* up, /**< stores dual bound after branching column up */
529 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
530 * otherwise, it can only be used as an estimate value */
531 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
532 * otherwise, it can only be used as an estimate value */
533 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
534 );
535
536 /** performs strong branching iterations on given @b fractional candidates */
537 SCIP_EXPORT
538 SCIP_RETCODE SCIPlpiStrongbranchesFrac(
539 SCIP_LPI* lpi, /**< LP interface structure */
540 int* cols, /**< columns to apply strong branching on */
541 int ncols, /**< number of columns */
542 SCIP_Real* psols, /**< fractional current primal solution values of columns */
543 int itlim, /**< iteration limit for strong branchings */
544 SCIP_Real* down, /**< stores dual bounds after branching columns down */
545 SCIP_Real* up, /**< stores dual bounds after branching columns up */
546 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
547 * otherwise, they can only be used as an estimate values */
548 SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
549 * otherwise, they can only be used as an estimate values */
550 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
551 );
552
553 /** performs strong branching iterations on one candidate with @b integral value */
554 SCIP_EXPORT
555 SCIP_RETCODE SCIPlpiStrongbranchInt(
556 SCIP_LPI* lpi, /**< LP interface structure */
557 int col, /**< column to apply strong branching on */
558 SCIP_Real psol, /**< current integral primal solution value of column */
559 int itlim, /**< iteration limit for strong branchings */
560 SCIP_Real* down, /**< stores dual bound after branching column down */
561 SCIP_Real* up, /**< stores dual bound after branching column up */
562 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
563 * otherwise, it can only be used as an estimate value */
564 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
565 * otherwise, it can only be used as an estimate value */
566 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
567 );
568
569 /** performs strong branching iterations on given candidates with @b integral values */
570 SCIP_EXPORT
571 SCIP_RETCODE SCIPlpiStrongbranchesInt(
572 SCIP_LPI* lpi, /**< LP interface structure */
573 int* cols, /**< columns to apply strong branching on */
574 int ncols, /**< number of columns */
575 SCIP_Real* psols, /**< current integral primal solution values of columns */
576 int itlim, /**< iteration limit for strong branchings */
577 SCIP_Real* down, /**< stores dual bounds after branching columns down */
578 SCIP_Real* up, /**< stores dual bounds after branching columns up */
579 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
580 * otherwise, they can only be used as an estimate values */
581 SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
582 * otherwise, they can only be used as an estimate values */
583 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
584 );
585 /**@} */
586
587
588
589
590 /*
591 * Solution Information Methods
592 */
593
594 /**@name Solution Information Methods */
595 /**@{ */
596
597 /** returns whether a solve method was called after the last modification of the LP */
598 SCIP_EXPORT
599 SCIP_Bool SCIPlpiWasSolved(
600 SCIP_LPI* lpi /**< LP interface structure */
601 );
602
603 /** gets information about primal and dual feasibility of the current LP solution
604 *
605 * The feasibility information is with respect to the last solving call and it is only relevant if SCIPlpiWasSolved()
606 * returns true. If the LP is changed, this information might be invalidated.
607 *
608 * Note that @p primalfeasible and @p dualfeasible should only return true if the solver has proved the respective LP to
609 * be feasible. Thus, the return values should be equal to the values of SCIPlpiIsPrimalFeasible() and
610 * SCIPlpiIsDualFeasible(), respectively. Note that if feasibility cannot be proved, they should return false (even if
611 * the problem might actually be feasible).
612 */
613 SCIP_EXPORT
614 SCIP_RETCODE SCIPlpiGetSolFeasibility(
615 SCIP_LPI* lpi, /**< LP interface structure */
616 SCIP_Bool* primalfeasible, /**< pointer to store primal feasibility status */
617 SCIP_Bool* dualfeasible /**< pointer to store dual feasibility status */
618 );
619
620 /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point);
621 * this does not necessarily mean, that the solver knows and can return the primal ray
622 */
623 SCIP_EXPORT
624 SCIP_Bool SCIPlpiExistsPrimalRay(
625 SCIP_LPI* lpi /**< LP interface structure */
626 );
627
628 /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point),
629 * and the solver knows and can return the primal ray
630 */
631 SCIP_EXPORT
632 SCIP_Bool SCIPlpiHasPrimalRay(
633 SCIP_LPI* lpi /**< LP interface structure */
634 );
635
636 /** returns TRUE iff LP is proven to be primal unbounded */
637 SCIP_EXPORT
638 SCIP_Bool SCIPlpiIsPrimalUnbounded(
639 SCIP_LPI* lpi /**< LP interface structure */
640 );
641
642 /** returns TRUE iff LP is proven to be primal infeasible */
643 SCIP_EXPORT
644 SCIP_Bool SCIPlpiIsPrimalInfeasible(
645 SCIP_LPI* lpi /**< LP interface structure */
646 );
647
648 /** returns TRUE iff LP is proven to be primal feasible */
649 SCIP_EXPORT
650 SCIP_Bool SCIPlpiIsPrimalFeasible(
651 SCIP_LPI* lpi /**< LP interface structure */
652 );
653
654 /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point);
655 * this does not necessarily mean, that the solver knows and can return the dual ray
656 */
657 SCIP_EXPORT
658 SCIP_Bool SCIPlpiExistsDualRay(
659 SCIP_LPI* lpi /**< LP interface structure */
660 );
661
662 /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point),
663 * and the solver knows and can return the dual ray
664 */
665 SCIP_EXPORT
666 SCIP_Bool SCIPlpiHasDualRay(
667 SCIP_LPI* lpi /**< LP interface structure */
668 );
669
670 /** returns TRUE iff LP is proven to be dual unbounded */
671 SCIP_EXPORT
672 SCIP_Bool SCIPlpiIsDualUnbounded(
673 SCIP_LPI* lpi /**< LP interface structure */
674 );
675
676 /** returns TRUE iff LP is proven to be dual infeasible */
677 SCIP_EXPORT
678 SCIP_Bool SCIPlpiIsDualInfeasible(
679 SCIP_LPI* lpi /**< LP interface structure */
680 );
681
682 /** returns TRUE iff LP is proven to be dual feasible */
683 SCIP_EXPORT
684 SCIP_Bool SCIPlpiIsDualFeasible(
685 SCIP_LPI* lpi /**< LP interface structure */
686 );
687
688 /** returns TRUE iff LP was solved to optimality */
689 SCIP_EXPORT
690 SCIP_Bool SCIPlpiIsOptimal(
691 SCIP_LPI* lpi /**< LP interface structure */
692 );
693
694 /** returns TRUE iff current LP solution is stable
695 *
696 * This function should return true if the solution is reliable, i.e., feasible and optimal (or proven
697 * infeasible/unbounded) with respect to the original problem. The optimality status might be with respect to a scaled
698 * version of the problem, but the solution might not be feasible to the unscaled original problem; in this case,
699 * SCIPlpiIsStable() should return false.
700 */
701 SCIP_EXPORT
702 SCIP_Bool SCIPlpiIsStable(
703 SCIP_LPI* lpi /**< LP interface structure */
704 );
705
706 /** returns TRUE iff the objective limit was reached */
707 SCIP_EXPORT
708 SCIP_Bool SCIPlpiIsObjlimExc(
709 SCIP_LPI* lpi /**< LP interface structure */
710 );
711
712 /** returns TRUE iff the iteration limit was reached */
713 SCIP_EXPORT
714 SCIP_Bool SCIPlpiIsIterlimExc(
715 SCIP_LPI* lpi /**< LP interface structure */
716 );
717
718 /** returns TRUE iff the time limit was reached */
719 SCIP_EXPORT
720 SCIP_Bool SCIPlpiIsTimelimExc(
721 SCIP_LPI* lpi /**< LP interface structure */
722 );
723
724 /** returns the internal solution status of the solver */
725 SCIP_EXPORT
726 int SCIPlpiGetInternalStatus(
727 SCIP_LPI* lpi /**< LP interface structure */
728 );
729
730 /** tries to reset the internal status of the LP solver in order to ignore an instability of the last solving call */
731 SCIP_EXPORT
732 SCIP_RETCODE SCIPlpiIgnoreInstability(
733 SCIP_LPI* lpi, /**< LP interface structure */
734 SCIP_Bool* success /**< pointer to store, whether the instability could be ignored */
735 );
736
737 /** gets objective value of solution */
738 SCIP_EXPORT
739 SCIP_RETCODE SCIPlpiGetObjval(
740 SCIP_LPI* lpi, /**< LP interface structure */
741 SCIP_Real* objval /**< stores the objective value */
742 );
743
744 /** gets primal and dual solution vectors for feasible LPs
745 *
746 * Before calling this function, the caller must ensure that the LP has been solved to optimality, i.e., that
747 * SCIPlpiIsOptimal() returns true.
748 */
749 SCIP_EXPORT
750 SCIP_RETCODE SCIPlpiGetSol(
751 SCIP_LPI* lpi, /**< LP interface structure */
752 SCIP_Real* objval, /**< stores the objective value, may be NULL if not needed */
753 SCIP_Real* primsol, /**< primal solution vector, may be NULL if not needed */
754 SCIP_Real* dualsol, /**< dual solution vector, may be NULL if not needed */
755 SCIP_Real* activity, /**< row activity vector, may be NULL if not needed */
756 SCIP_Real* redcost /**< reduced cost vector, may be NULL if not needed */
757 );
758
759 /** gets primal ray for unbounded LPs */
760 SCIP_EXPORT
761 SCIP_RETCODE SCIPlpiGetPrimalRay(
762 SCIP_LPI* lpi, /**< LP interface structure */
763 SCIP_Real* ray /**< primal ray */
764 );
765
766 /** gets dual Farkas proof for infeasibility */
767 SCIP_EXPORT
768 SCIP_RETCODE SCIPlpiGetDualfarkas(
769 SCIP_LPI* lpi, /**< LP interface structure */
770 SCIP_Real* dualfarkas /**< dual Farkas row multipliers */
771 );
772
773 /** gets the number of LP iterations of the last solve call */
774 SCIP_EXPORT
775 SCIP_RETCODE SCIPlpiGetIterations(
776 SCIP_LPI* lpi, /**< LP interface structure */
777 int* iterations /**< pointer to store the number of iterations of the last solve call */
778 );
779
780 /** gets information about the quality of an LP solution
781 *
782 * Such information is usually only available, if also a (maybe not optimal) solution is available.
783 * The LPI should return SCIP_INVALID for @p quality, if the requested quantity is not available.
784 */
785 SCIP_EXPORT
786 SCIP_RETCODE SCIPlpiGetRealSolQuality(
787 SCIP_LPI* lpi, /**< LP interface structure */
788 SCIP_LPSOLQUALITY qualityindicator, /**< indicates which quality should be returned */
789 SCIP_Real* quality /**< pointer to store quality number */
790 );
791
792 /**@} */
793
794
795
796
797 /*
798 * LP Basis Methods
799 */
800
801 /**@name LP Basis Methods */
802 /**@{ */
803
804 /** gets current basis status for columns and rows; arrays must be large enough to store the basis status */
805 SCIP_EXPORT
806 SCIP_RETCODE SCIPlpiGetBase(
807 SCIP_LPI* lpi, /**< LP interface structure */
808 int* cstat, /**< array to store column basis status, or NULL */
809 int* rstat /**< array to store row basis status, or NULL */
810 );
811
812 /** sets current basis status for columns and rows */
813 SCIP_EXPORT
814 SCIP_RETCODE SCIPlpiSetBase(
815 SCIP_LPI* lpi, /**< LP interface structure */
816 const int* cstat, /**< array with column basis status */
817 const int* rstat /**< array with row basis status */
818 );
819
820 /** returns the indices of the basic columns and rows; basic column n gives value n, basic row m gives value -1-m */
821 SCIP_EXPORT
822 SCIP_RETCODE SCIPlpiGetBasisInd(
823 SCIP_LPI* lpi, /**< LP interface structure */
824 int* bind /**< pointer to store basis indices ready to keep number of rows entries */
825 );
826
827 /** get row of inverse basis matrix B^-1
828 *
829 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
830 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
831 * see also the explanation in lpi.h.
832 */
833 SCIP_EXPORT
834 SCIP_RETCODE SCIPlpiGetBInvRow(
835 SCIP_LPI* lpi, /**< LP interface structure */
836 int r, /**< row number */
837 SCIP_Real* coef, /**< pointer to store the coefficients of the row */
838 int* inds, /**< array to store the non-zero indices, or NULL */
839 int* ninds /**< pointer to store the number of non-zero indices, or NULL
840 * (-1: if we do not store sparsity information) */
841 );
842
843 /** get column of inverse basis matrix B^-1
844 *
845 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
846 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
847 * see also the explanation in lpi.h.
848 */
849 SCIP_EXPORT
850 SCIP_RETCODE SCIPlpiGetBInvCol(
851 SCIP_LPI* lpi, /**< LP interface structure */
852 int c, /**< column number of B^-1; this is NOT the number of the column in the LP;
853 * you have to call SCIPlpiGetBasisInd() to get the array which links the
854 * B^-1 column numbers to the row and column numbers of the LP!
855 * c must be between 0 and nrows-1, since the basis has the size
856 * nrows * nrows */
857 SCIP_Real* coef, /**< pointer to store the coefficients of the column */
858 int* inds, /**< array to store the non-zero indices, or NULL */
859 int* ninds /**< pointer to store the number of non-zero indices, or NULL
860 * (-1: if we do not store sparsity information) */
861 );
862
863 /** get row of inverse basis matrix times constraint matrix B^-1 * A
864 *
865 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
866 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
867 * see also the explanation in lpi.h.
868 */
869 SCIP_EXPORT
870 SCIP_RETCODE SCIPlpiGetBInvARow(
871 SCIP_LPI* lpi, /**< LP interface structure */
872 int r, /**< row number */
873 const SCIP_Real* binvrow, /**< row in (A_B)^-1 from prior call to SCIPlpiGetBInvRow(), or NULL */
874 SCIP_Real* coef, /**< vector to return coefficients of the row */
875 int* inds, /**< array to store the non-zero indices, or NULL */
876 int* ninds /**< pointer to store the number of non-zero indices, or NULL
877 * (-1: if we do not store sparsity information) */
878 );
879
880 /** get column of inverse basis matrix times constraint matrix B^-1 * A
881 *
882 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
883 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
884 * see also the explanation in lpi.h.
885 */
886 SCIP_EXPORT
887 SCIP_RETCODE SCIPlpiGetBInvACol(
888 SCIP_LPI* lpi, /**< LP interface structure */
889 int c, /**< column number */
890 SCIP_Real* coef, /**< vector to return coefficients of the column */
891 int* inds, /**< array to store the non-zero indices, or NULL */
892 int* ninds /**< pointer to store the number of non-zero indices, or NULL
893 * (-1: if we do not store sparsity information) */
894 );
895
896 /**@} */
897
898
899
900
901 /*
902 * LPi State Methods
903 */
904
905 /**@name LPi State Methods */
906 /**@{ */
907
908 /** stores LPi state (like basis information) into lpistate object */
909 SCIP_EXPORT
910 SCIP_RETCODE SCIPlpiGetState(
911 SCIP_LPI* lpi, /**< LP interface structure */
912 BMS_BLKMEM* blkmem, /**< block memory */
913 SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
914 );
915
916 /** loads LPi state (like basis information) into solver; note that the LP might have been extended with additional
917 * columns and rows since the state was stored with SCIPlpiGetState()
918 */
919 SCIP_EXPORT
920 SCIP_RETCODE SCIPlpiSetState(
921 SCIP_LPI* lpi, /**< LP interface structure */
922 BMS_BLKMEM* blkmem, /**< block memory */
923 const SCIP_LPISTATE* lpistate /**< LPi state information (like basis information), or NULL */
924 );
925
926 /** clears current LPi state (like basis information) of the solver */
927 SCIP_EXPORT
928 SCIP_RETCODE SCIPlpiClearState(
929 SCIP_LPI* lpi /**< LP interface structure */
930 );
931
932 /** frees LPi state information */
933 SCIP_EXPORT
934 SCIP_RETCODE SCIPlpiFreeState(
935 SCIP_LPI* lpi, /**< LP interface structure */
936 BMS_BLKMEM* blkmem, /**< block memory */
937 SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
938 );
939
940 /** checks, whether the given LPi state contains simplex basis information */
941 SCIP_EXPORT
942 SCIP_Bool SCIPlpiHasStateBasis(
943 SCIP_LPI* lpi, /**< LP interface structure */
944 SCIP_LPISTATE* lpistate /**< LPi state information (like basis information) */
945 );
946
947 /** reads LPi state (like basis information from a file */
948 SCIP_EXPORT
949 SCIP_RETCODE SCIPlpiReadState(
950 SCIP_LPI* lpi, /**< LP interface structure */
951 const char* fname /**< file name */
952 );
953
954 /** writes LPi state (i.e. basis information) to a file */
955 SCIP_EXPORT
956 SCIP_RETCODE SCIPlpiWriteState(
957 SCIP_LPI* lpi, /**< LP interface structure */
958 const char* fname /**< file name */
959 );
960
961 /**@} */
962
963
964 /*
965 * LPi Pricing Norms Methods
966 */
967
968 /**@name LPi Pricing Norms Methods */
969 /**@{ */
970
971 /** stores LPi pricing norms into lpinorms object */
972 SCIP_RETCODE SCIPlpiGetNorms(
973 SCIP_LPI* lpi, /**< LP interface structure */
974 BMS_BLKMEM* blkmem, /**< block memory */
975 SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
976 );
977
978 /** loads LPi pricing norms into solver; note that the LP might have been extended with additional
979 * columns and rows since the norms were stored with SCIPlpiGetNorms()
980 */
981 SCIP_RETCODE SCIPlpiSetNorms(
982 SCIP_LPI* lpi, /**< LP interface structure */
983 BMS_BLKMEM* blkmem, /**< block memory */
984 const SCIP_LPINORMS* lpinorms /**< LPi pricing norms information, or NULL */
985 );
986
987 /** frees LPi pricing norms information */
988 SCIP_RETCODE SCIPlpiFreeNorms(
989 SCIP_LPI* lpi, /**< LP interface structure */
990 BMS_BLKMEM* blkmem, /**< block memory */
991 SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information, or NULL */
992 );
993
994
995 /**@} */
996
997
998
999
1000 /*
1001 * Parameter Methods
1002 */
1003
1004 /**@name Parameter Methods */
1005 /**@{ */
1006
1007 /** gets integer parameter of LP */
1008 SCIP_EXPORT
1009 SCIP_RETCODE SCIPlpiGetIntpar(
1010 SCIP_LPI* lpi, /**< LP interface structure */
1011 SCIP_LPPARAM type, /**< parameter number */
1012 int* ival /**< buffer to store the parameter value */
1013 );
1014
1015 /** sets integer parameter of LP */
1016 SCIP_EXPORT
1017 SCIP_RETCODE SCIPlpiSetIntpar(
1018 SCIP_LPI* lpi, /**< LP interface structure */
1019 SCIP_LPPARAM type, /**< parameter number */
1020 int ival /**< parameter value */
1021 );
1022
1023 /** gets floating point parameter of LP */
1024 SCIP_EXPORT
1025 SCIP_RETCODE SCIPlpiGetRealpar(
1026 SCIP_LPI* lpi, /**< LP interface structure */
1027 SCIP_LPPARAM type, /**< parameter number */
1028 SCIP_Real* dval /**< buffer to store the parameter value */
1029 );
1030
1031 /** sets floating point parameter of LP */
1032 SCIP_EXPORT
1033 SCIP_RETCODE SCIPlpiSetRealpar(
1034 SCIP_LPI* lpi, /**< LP interface structure */
1035 SCIP_LPPARAM type, /**< parameter number */
1036 SCIP_Real dval /**< parameter value */
1037 );
1038
1039 /** interrupts the currently ongoing lp solve or disables the interrupt */
1040 SCIP_EXPORT
1041 SCIP_RETCODE SCIPlpiInterrupt(
1042 SCIP_LPI* lpi, /**< LP interface structure */
1043 SCIP_Bool interrupt /**< TRUE if interrupt should be set, FALSE if it should be disabled */
1044 );
1045
1046 /**@} */
1047
1048
1049
1050
1051 /*
1052 * Numerical Methods
1053 */
1054
1055 /**@name Numerical Methods */
1056 /**@{ */
1057
1058 /** returns value treated as infinity in the LP solver */
1059 SCIP_EXPORT
1060 SCIP_Real SCIPlpiInfinity(
1061 SCIP_LPI* lpi /**< LP interface structure */
1062 );
1063
1064 /** checks if given value is treated as infinity in the LP solver */
1065 SCIP_EXPORT
1066 SCIP_Bool SCIPlpiIsInfinity(
1067 SCIP_LPI* lpi, /**< LP interface structure */
1068 SCIP_Real val /**< value to be checked for infinity */
1069 );
1070
1071 /**@} */
1072
1073
1074
1075
1076 /*
1077 * File Interface Methods
1078 */
1079
1080 /**@name File Interface Methods */
1081 /**@{ */
1082
1083 /** reads LP from a file */
1084 SCIP_EXPORT
1085 SCIP_RETCODE SCIPlpiReadLP(
1086 SCIP_LPI* lpi, /**< LP interface structure */
1087 const char* fname /**< file name */
1088 );
1089
1090 /** writes LP to a file */
1091 SCIP_EXPORT
1092 SCIP_RETCODE SCIPlpiWriteLP(
1093 SCIP_LPI* lpi, /**< LP interface structure */
1094 const char* fname /**< file name */
1095 );
1096
1097 /**@} */
1098
1099 /**@} */
1100
1101
1102 #ifdef __cplusplus
1103 }
1104 #endif
1105
1106 #endif
1107