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