Scippy

SCIP

Solving Constraint Integer Programs

lpi_glop.cpp
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file lpi_glop.cpp
26 * @ingroup LPIS
27 * @brief LP interface for Glop
28 * @author Frederic Didier
29 * @author Marc Pfetsch
30 */
31
32/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34/* turn off some warnings from includes */
35#pragma GCC diagnostic ignored "-Wsign-compare"
36#pragma GCC diagnostic ignored "-Wpedantic"
37#pragma GCC diagnostic ignored "-Wignored-qualifiers"
38#pragma GCC diagnostic ignored "-Wshadow"
39#pragma GCC diagnostic ignored "-Wnon-virtual-dtor"
40#pragma GCC diagnostic ignored "-Wctor-dtor-privacy"
41#pragma GCC diagnostic ignored "-Woverflow"
42
43#include "ortools/base/version.h"
44#include "ortools/glop/lp_solver.h"
45#include "ortools/glop/revised_simplex.h"
46#include "ortools/lp_data/lp_print_utils.h"
47#include "ortools/lp_data/lp_data_utils.h"
48#include "ortools/lp_data/proto_utils.h"
49#include "ortools/util/file_util.h"
50#include "ortools/util/stats.h"
51#include "ortools/util/time_limit.h"
52
53#include "ortools/base/logging.h"
54#include "ortools/base/vlog_is_on.h"
55
56#include "lpi/lpi.h"
57#include "scip/pub_message.h"
58
59#include <assert.h>
60
61/* turn warnings on again */
62#pragma GCC diagnostic warning "-Wsign-compare"
63#pragma GCC diagnostic warning "-Wpedantic"
64#pragma GCC diagnostic warning "-Wignored-qualifiers"
65#pragma GCC diagnostic warning "-Wshadow"
66#pragma GCC diagnostic warning "-Wnon-virtual-dtor"
67#pragma GCC diagnostic warning "-Wctor-dtor-privacy"
68#pragma GCC diagnostic warning "-Woverflow"
69
70
71using operations_research::TimeLimit;
72using operations_research::glop::BasisState;
73using operations_research::glop::ColIndex;
74using operations_research::glop::ColIndexVector;
75using operations_research::glop::ConstraintStatus;
76using operations_research::glop::ConstraintStatusColumn;
77using operations_research::glop::DenseBooleanColumn;
78using operations_research::glop::DenseBooleanRow;
79using operations_research::glop::DenseColumn;
80using operations_research::glop::DenseRow;
81using operations_research::glop::SparseColumn;
82using operations_research::glop::ScatteredColumn;
83using operations_research::glop::ScatteredColumnIterator;
84using operations_research::glop::SparseMatrix;
85using operations_research::glop::Fractional;
86using operations_research::glop::GetProblemStatusString;
87using operations_research::glop::ProblemStatus;
88using operations_research::glop::RowIndex;
89using operations_research::glop::ScatteredRow;
90using operations_research::glop::ScatteredRowIterator;
91using operations_research::glop::VariableStatus;
92using operations_research::glop::VariableStatusRow;
93using operations_research::MPModelProto;
94
95/** LP interface */
96struct SCIP_LPi
97{
98 operations_research::glop::LinearProgram* linear_program; /**< the linear program */
99 operations_research::glop::LinearProgram* scaled_lp; /**< scaled linear program */
100 operations_research::glop::RevisedSimplex* solver; /**< direct reference to the revised simplex, not passing through lp_solver */
101 operations_research::glop::GlopParameters* parameters; /**< parameters */
102 operations_research::glop::LpScalingHelper* scaler; /**< scaler auxiliary class */
103
104 /* the following is used by SCIPlpiWasSolved() */
107
108 /* store the values of some parameters in order to be able to return them */
109 bool lp_info; /**< whether additional output is turned on */
110 SCIP_PRICING pricing; /**< SCIP pricing setting */
111 bool from_scratch; /**< store whether basis is ignored for next solving call */
112 int numthreads; /**< number of threads used to solve the LP (0 = automatic) */
113 SCIP_Real conditionlimit; /**< maximum condition number of LP basis counted as stable (-1.0: no limit) */
114 bool checkcondition; /**< Should condition number of LP basis be checked for stability? */
115 int timing; /**< type of timer (1 - cpu, 2 - wallclock, 0 - off) */
116
117 /* other data */
118 SCIP_Longint niterations; /**< number of iterations used */
119
120 /* Temporary vectors allocated here for speed. This gain is non-negligible
121 * because in many situations, only a few entries of these vectors are
122 * inspected (hypersparsity) and allocating them is in O(num_rows) or
123 * O(num_cols) instead of O(num_non_zeros) to read/clear them. */
124 ScatteredRow* tmp_row; /**< temporary vector */
125 ScatteredColumn* tmp_column; /**< temporary vector */
126};
127
128/** uncomment to turn off scaling */
129/* #define NOSCALING */
130
131/** define feasibility check to possibly reoptimize: 0: no check, 1: completely new check, 2: check unscaled variable and activity values */
132#ifdef NOSCALING
133#define UNSCALEDFEAS_CHECK 0
134#else
135#define UNSCALEDFEAS_CHECK 2
136#endif
137
138
139/*
140 * LP Interface Methods
141 */
142
143char* initGlopName( );
144
145static char* glopname = initGlopName( );
146
148{
149 glopname = new char[100];
150 (void) snprintf(glopname, 100, "Glop %d.%d", operations_research::OrToolsMajorVersion(), operations_research::OrToolsMinorVersion());
151 return glopname;
152}
153
154/** gets name and version of LP solver */
156 void
157 )
158{
159 return glopname;
160}
161
162/** gets description of LP solver (developer, webpage, ...) */
164 void
165 )
166{
167 return "Glop Linear Solver, developed by Google, part of OR-Tools (developers.google.com/optimization)";
168}
169
170/** gets pointer for LP solver - use only with great care */
172 SCIP_LPI* lpi /**< pointer to an LP interface structure */
173 )
174{
175 assert( lpi != NULL );
176
177 SCIPerrorMessage("SCIPlpiGetSolverPointer() has not been implemented yet.\n");
178
179 return NULL;
180}
181
182/** pass integrality information to LP solver */
184 SCIP_LPI* lpi, /**< pointer to an LP interface structure */
185 int ncols, /**< length of integrality array */
186 int* intInfo /**< integrality array (0: continuous, 1: integer). May be NULL iff ncols is 0. */
187 )
188{
189 assert( lpi != NULL );
190 assert( lpi->linear_program != NULL );
191 assert( ncols == 0 || ncols == lpi->linear_program->num_variables().value() );
192
193 /* Pass on integrality information (currently not used by Glop). */
194 for (ColIndex col(0); col < ColIndex(ncols); ++col)
195 {
196 assert( intInfo != NULL );
197 int info = intInfo[col.value()];
198 assert( info == 0 || info == 1 );
199 if ( info == 0 )
200 lpi->linear_program->SetVariableType(col, operations_research::glop::LinearProgram::VariableType::CONTINUOUS);
201 else
202 lpi->linear_program->SetVariableType(col, operations_research::glop::LinearProgram::VariableType::INTEGER);
203 }
204
205 return SCIP_OKAY;
206}
207
208/** informs about availability of a primal simplex solving method */
210 void
211 )
212{
213 return TRUE;
214}
215
216/** informs about availability of a dual simplex solving method */
218 void
219 )
220{
221 return TRUE;
222}
223
224/** informs about availability of a barrier solving method */
226 void
227 )
228{
229 return FALSE;
230}
231
232
233/*
234 * LPI Creation and Destruction Methods
235 */
236
237/**@name LPI Creation and Destruction Methods */
238/**@{ */
239
240/** creates an LP problem object */
242 SCIP_LPI** lpi, /**< pointer to an LP interface structure */
243 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler to use for printing messages, or NULL */
244 const char* name, /**< problem name */
245 SCIP_OBJSEN objsen /**< objective sense */
246 )
247{
248 assert( lpi != NULL );
249 assert( name != NULL );
250
251 /* Initilialize memory. */
253 (*lpi)->linear_program = new operations_research::glop::LinearProgram();
254 (*lpi)->scaled_lp = new operations_research::glop::LinearProgram();
255 (*lpi)->solver = new operations_research::glop::RevisedSimplex();
256 (*lpi)->parameters = new operations_research::glop::GlopParameters();
257 (*lpi)->scaler = new operations_research::glop::LpScalingHelper();
258
259 /* Set problem name and objective direction. */
260 (*lpi)->linear_program->SetName(std::string(name));
261 SCIP_CALL( SCIPlpiChgObjsen(*lpi, objsen) );
262
263 (*lpi)->from_scratch = false;
264 (*lpi)->lp_info = false;
265 (*lpi)->pricing = SCIP_PRICING_LPIDEFAULT;
266 (*lpi)->lp_modified_since_last_solve = true;
267 (*lpi)->lp_time_limit_was_reached = false;
268 (*lpi)->conditionlimit = -1.0;
269 (*lpi)->checkcondition = false;
270 (*lpi)->niterations = 0LL;
271
272 (*lpi)->tmp_row = new ScatteredRow();
273 (*lpi)->tmp_column = new ScatteredColumn();
274
275#ifdef NOSCALING
276 (*lpi)->parameters->set_use_scaling(false);
277#endif
278
279 return SCIP_OKAY;
280}
281
282/** deletes an LP problem object */
284 SCIP_LPI** lpi /**< pointer to an LP interface structure */
285 )
286{
287 SCIPdebugMessage("SCIPlpiFree\n");
288
289 delete (*lpi)->scaler;
290 delete (*lpi)->parameters;
291 delete (*lpi)->solver;
292 delete (*lpi)->scaled_lp;
293 delete (*lpi)->linear_program;
294
295 delete (*lpi)->tmp_row;
296 delete (*lpi)->tmp_column;
297
298 BMSfreeMemory(lpi);
299
300 return SCIP_OKAY;
301}
302
303/**@} */
304
305
306
307
308/*
309 * Modification Methods
310 */
311
312/**@name Modification Methods */
313/**@{ */
314
315/** copies LP data with column matrix into LP solver */
317 SCIP_LPI* lpi, /**< LP interface structure */
318 SCIP_OBJSEN objsen, /**< objective sense */
319 int ncols, /**< number of columns */
320 const SCIP_Real* obj, /**< objective function values of columns */
321 const SCIP_Real* lb, /**< lower bounds of columns */
322 const SCIP_Real* ub, /**< upper bounds of columns */
323 char** colnames, /**< column names, or NULL */
324 int nrows, /**< number of rows */
325 const SCIP_Real* lhs, /**< left hand sides of rows */
326 const SCIP_Real* rhs, /**< right hand sides of rows */
327 char** rownames, /**< row names, or NULL */
328 int nnonz, /**< number of nonzero elements in the constraint matrix */
329 const int* beg, /**< start index of each column in ind- and val-array */
330 const int* ind, /**< row indices of constraint matrix entries */
331 const SCIP_Real* val /**< values of constraint matrix entries */
332 )
333{
334 assert( lpi != NULL );
335 assert( lpi->linear_program != NULL );
336 assert( obj != NULL );
337 assert( lb != NULL );
338 assert( ub != NULL );
339 assert( beg != NULL );
340 assert( ind != NULL );
341 assert( val != NULL );
342
343 lpi->linear_program->Clear();
344 SCIP_CALL( SCIPlpiAddRows(lpi, nrows, lhs, rhs, rownames, 0, NULL, NULL, NULL) );
345 SCIP_CALL( SCIPlpiAddCols(lpi, ncols, obj, lb, ub, colnames, nnonz, beg, ind, val) );
346 SCIP_CALL( SCIPlpiChgObjsen(lpi, objsen) );
347
348 return SCIP_OKAY;
349}
350
351/** adds columns to the LP */
353 SCIP_LPI* lpi, /**< LP interface structure */
354 int ncols, /**< number of columns to be added */
355 const SCIP_Real* obj, /**< objective function values of new columns */
356 const SCIP_Real* lb, /**< lower bounds of new columns */
357 const SCIP_Real* ub, /**< upper bounds of new columns */
358 char** colnames, /**< column names, or NULL */
359 int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
360 const int* beg, /**< start index of each column in ind- and val-array, or NULL if nnonz == 0 */
361 const int* ind, /**< row indices of constraint matrix entries, or NULL if nnonz == 0 */
362 const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
363 )
364{
365 assert( lpi != NULL );
366 assert( lpi->linear_program != NULL );
367 assert( obj != NULL );
368 assert( lb != NULL );
369 assert( ub != NULL );
370 assert( nnonz >= 0) ;
371 assert( ncols >= 0) ;
372
373 SCIPdebugMessage("adding %d columns with %d nonzeros.\n", ncols, nnonz);
374
375 /* @todo add names */
376 if ( nnonz > 0 )
377 {
378 assert( beg != NULL );
379 assert( ind != NULL );
380 assert( val != NULL );
381 assert( ncols > 0 );
382
383#ifndef NDEBUG
384 /* perform check that no new rows are added */
385 RowIndex num_rows = lpi->linear_program->num_constraints();
386 for (int j = 0; j < nnonz; ++j)
387 {
388 assert( 0 <= ind[j] && ind[j] < num_rows.value() );
389 assert( val[j] != 0.0 );
390 }
391#endif
392
393 int nz = 0;
394 for (int i = 0; i < ncols; ++i)
395 {
396 const ColIndex col = lpi->linear_program->CreateNewVariable();
397 lpi->linear_program->SetVariableBounds(col, lb[i], ub[i]);
398 lpi->linear_program->SetObjectiveCoefficient(col, obj[i]);
399 const int end = (nnonz == 0 || i == ncols - 1) ? nnonz : beg[i + 1];
400 while ( nz < end )
401 {
402 lpi->linear_program->SetCoefficient(RowIndex(ind[nz]), col, val[nz]);
403 ++nz;
404 }
405 }
406 assert( nz == nnonz );
407 }
408 else
409 {
410 for (int i = 0; i < ncols; ++i)
411 {
412 const ColIndex col = lpi->linear_program->CreateNewVariable();
413 lpi->linear_program->SetVariableBounds(col, lb[i], ub[i]);
414 lpi->linear_program->SetObjectiveCoefficient(col, obj[i]);
415 }
416 }
417
419
420 return SCIP_OKAY;
421}
422
423/** deletes all columns in the given range from LP */
425 SCIP_LPI* lpi, /**< LP interface structure */
426 int firstcol, /**< first column to be deleted */
427 int lastcol /**< last column to be deleted */
428 )
429{
430 assert( lpi != NULL );
431 assert( lpi->linear_program != NULL );
432 assert( 0 <= firstcol && firstcol <= lastcol && lastcol < lpi->linear_program->num_variables() );
433
434 SCIPdebugMessage("deleting columns %d to %d.\n", firstcol, lastcol);
435
436 const ColIndex num_cols = lpi->linear_program->num_variables();
437 DenseBooleanRow columns_to_delete(num_cols, false);
438 for (int i = firstcol; i <= lastcol; ++i)
439 columns_to_delete[ColIndex(i)] = true;
440
441 lpi->linear_program->DeleteColumns(columns_to_delete);
443
444 return SCIP_OKAY;
445}
446
447/** deletes columns from SCIP_LP; the new position of a column must not be greater that its old position */
449 SCIP_LPI* lpi, /**< LP interface structure */
450 int* dstat /**< deletion status of columns
451 * input: 1 if column should be deleted, 0 if not
452 * output: new position of column, -1 if column was deleted */
453 )
454{
455 assert( lpi != NULL );
456 assert( lpi->linear_program != NULL );
457 assert( dstat != NULL );
458
459 const ColIndex num_cols = lpi->linear_program->num_variables();
460 DenseBooleanRow columns_to_delete(num_cols, false);
461 int new_index = 0;
462 int num_deleted_columns = 0;
463 for (ColIndex col(0); col < num_cols; ++col)
464 {
465 int i = col.value();
466 if ( dstat[i] == 1 )
467 {
468 columns_to_delete[col] = true;
469 dstat[i] = -1;
470 ++num_deleted_columns;
471 }
472 else
473 dstat[i] = new_index++;
474 }
475 SCIPdebugMessage("SCIPlpiDelColset: deleting %d columns.\n", num_deleted_columns);
476 lpi->linear_program->DeleteColumns(columns_to_delete);
478
479 return SCIP_OKAY;
480}
481
482/** adds rows to the LP */
484 SCIP_LPI* lpi, /**< LP interface structure */
485 int nrows, /**< number of rows to be added */
486 const SCIP_Real* lhs, /**< left hand sides of new rows */
487 const SCIP_Real* rhs, /**< right hand sides of new rows */
488 char** rownames, /**< row names, or NULL */
489 int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
490 const int* beg, /**< start index of each row in ind- and val-array, or NULL if nnonz == 0 */
491 const int* ind, /**< column indices of constraint matrix entries, or NULL if nnonz == 0 */
492 const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
493 )
494{
495 assert( lpi != NULL );
496 assert( lpi->linear_program != NULL );
497 assert( lhs != NULL );
498 assert( rhs != NULL );
499 assert( nnonz >= 0) ;
500 assert( nrows >= 0) ;
501
502 SCIPdebugMessage("adding %d rows with %d nonzeros.\n", nrows, nnonz);
503
504 /* @todo add names */
505 if ( nnonz > 0 )
506 {
507 assert( beg != NULL );
508 assert( ind != NULL );
509 assert( val != NULL );
510 assert( nrows > 0 );
511
512#ifndef NDEBUG
513 /* perform check that no new columns are added - this is likely to be a mistake */
514 const ColIndex num_cols = lpi->linear_program->num_variables();
515 for (int j = 0; j < nnonz; ++j)
516 {
517 assert( val[j] != 0.0 );
518 assert( 0 <= ind[j] && ind[j] < num_cols.value() );
519 }
520#endif
521
522 int nz = 0;
523 for (int i = 0; i < nrows; ++i)
524 {
525 const RowIndex row = lpi->linear_program->CreateNewConstraint();
526 lpi->linear_program->SetConstraintBounds(row, lhs[i], rhs[i]);
527 const int end = (nnonz == 0 || i == nrows - 1) ? nnonz : beg[i + 1];
528 while ( nz < end )
529 {
530 lpi->linear_program->SetCoefficient(row, ColIndex(ind[nz]), val[nz]);
531 ++nz;
532 }
533 }
534 assert( nz == nnonz );
535 }
536 else
537 {
538 for (int i = 0; i < nrows; ++i)
539 {
540 const RowIndex row = lpi->linear_program->CreateNewConstraint();
541 lpi->linear_program->SetConstraintBounds(row, lhs[i], rhs[i]);
542 }
543 }
544
546
547 return SCIP_OKAY;
548}
549
550/** delete rows from LP and update the current basis */
551static
553 SCIP_LPI* lpi, /**< LP interface structure */
554 const DenseBooleanColumn& rows_to_delete /**< array to mark rows that should be deleted */
555 )
556{
557 const RowIndex num_rows = lpi->linear_program->num_constraints();
558 const ColIndex num_cols = lpi->linear_program->num_variables();
559
560 /* try to repair basis status if problem size has not changed before */
561 BasisState state = lpi->solver->GetState();
562 if ( state.statuses.size() == num_cols.value() + num_rows.value() )
563 {
564 /* Shift the status of the non-deleted rows. Note that if the deleted rows where part of the basis (i.e., constraint
565 * not tight), then we should be left with a correct basis afterward. This should be the most common use case in SCIP. */
566 ColIndex new_size = num_cols;
567 for (RowIndex row(0); row < num_rows; ++row)
568 {
569 if ( rows_to_delete[row] )
570 continue;
571 state.statuses[new_size++] = state.statuses[num_cols + RowToColIndex(row)];
572 }
573 state.statuses.resize(new_size);
574 lpi->solver->LoadStateForNextSolve(state);
575 }
576
577 lpi->linear_program->DeleteRows(rows_to_delete);
579}
580
581/** deletes all rows in the given range from LP */
583 SCIP_LPI* lpi, /**< LP interface structure */
584 int firstrow, /**< first row to be deleted */
585 int lastrow /**< last row to be deleted */
586 )
587{
588 assert( lpi != NULL );
589 assert( lpi->linear_program != NULL );
590 assert( 0 <= firstrow && firstrow <= lastrow && lastrow < lpi->linear_program->num_constraints() );
591
592 const RowIndex num_rows = lpi->linear_program->num_constraints();
593 DenseBooleanColumn rows_to_delete(num_rows, false);
594 for (int i = firstrow; i <= lastrow; ++i)
595 rows_to_delete[RowIndex(i)] = true;
596
597 SCIPdebugMessage("deleting rows %d to %d.\n", firstrow, lastrow);
598 deleteRowsAndUpdateCurrentBasis(lpi, rows_to_delete);
599
600 return SCIP_OKAY;
601}
602
603/** deletes rows from SCIP_LP; the new position of a row must not be greater that its old position */
605 SCIP_LPI* lpi, /**< LP interface structure */
606 int* dstat /**< deletion status of rows
607 * input: 1 if row should be deleted, 0 if not
608 * output: new position of row, -1 if row was deleted */
609 )
610{
611 assert( lpi != NULL );
612 assert( lpi->linear_program != NULL );
613
614 const RowIndex num_rows = lpi->linear_program->num_constraints();
615 DenseBooleanColumn rows_to_delete(num_rows, false);
616 int new_index = 0;
617 int num_deleted_rows = 0;
618 for (RowIndex row(0); row < num_rows; ++row)
619 {
620 int i = row.value();
621 if (dstat[i] == 1)
622 {
623 rows_to_delete[row] = true;
624 dstat[i] = -1;
625 ++num_deleted_rows;
626 }
627 else
628 dstat[i] = new_index++;
629 }
630
631 SCIPdebugMessage("SCIPlpiDelRowset: deleting %d rows.\n", num_deleted_rows);
632 deleteRowsAndUpdateCurrentBasis(lpi, rows_to_delete);
633
634 return SCIP_OKAY;
635}
636
637/** clears the whole LP */
639 SCIP_LPI* lpi /**< LP interface structure */
640 )
641{
642 assert( lpi != NULL );
643 assert( lpi->linear_program != NULL );
644
645 SCIPdebugMessage("SCIPlpiClear\n");
646
647 lpi->linear_program->Clear();
649
650 return SCIP_OKAY;
651}
652
653/** changes lower and upper bounds of columns */
655 SCIP_LPI* lpi, /**< LP interface structure */
656 int ncols, /**< number of columns to change bounds for */
657 const int* ind, /**< column indices or NULL if ncols is zero */
658 const SCIP_Real* lb, /**< values for the new lower bounds or NULL if ncols is zero */
659 const SCIP_Real* ub /**< values for the new upper bounds or NULL if ncols is zero */
660 )
661{
662 assert( lpi != NULL );
663 assert( lpi->linear_program != NULL );
664 assert( ncols == 0 || (ind != NULL && lb != NULL && ub != NULL) );
665
666 SCIPdebugMessage("changing %d bounds.\n", ncols);
667 if ( ncols <= 0 )
668 return SCIP_OKAY;
669
670 for (int i = 0; i < ncols; ++i)
671 {
672 SCIPdebugMessage(" col %d: [%g,%g]\n", ind[i], lb[i], ub[i]);
673
674 if ( SCIPlpiIsInfinity(lpi, lb[i]) )
675 {
676 SCIPerrorMessage("LP Error: fixing lower bound for variable %d to infinity.\n", ind[i]);
677 return SCIP_LPERROR;
678 }
679 if ( SCIPlpiIsInfinity(lpi, -ub[i]) )
680 {
681 SCIPerrorMessage("LP Error: fixing upper bound for variable %d to -infinity.\n", ind[i]);
682 return SCIP_LPERROR;
683 }
684
685 lpi->linear_program->SetVariableBounds(ColIndex(ind[i]), lb[i], ub[i]);
686 }
688
689 return SCIP_OKAY;
690}
691
692/** changes left and right hand sides of rows */
694 SCIP_LPI* lpi, /**< LP interface structure */
695 int nrows, /**< number of rows to change sides for */
696 const int* ind, /**< row indices */
697 const SCIP_Real* lhs, /**< new values for left hand sides */
698 const SCIP_Real* rhs /**< new values for right hand sides */
699 )
700{
701 assert( lpi != NULL );
702 assert( lpi->linear_program != NULL );
703
704 if ( nrows <= 0 )
705 return SCIP_OKAY;
706
707 SCIPdebugMessage("changing %d sides\n", nrows);
708
709 for (int i = 0; i < nrows; ++i)
710 lpi->linear_program->SetConstraintBounds(RowIndex(ind[i]), lhs[i], rhs[i]);
711
713
714 return SCIP_OKAY;
715}
716
717/** changes a single coefficient */
719 SCIP_LPI* lpi, /**< LP interface structure */
720 int row, /**< row number of coefficient to change */
721 int col, /**< column number of coefficient to change */
722 SCIP_Real newval /**< new value of coefficient */
723 )
724{
725 assert( lpi != NULL );
726 assert( lpi->linear_program != NULL );
727 assert( 0 <= row && row < lpi->linear_program->num_constraints().value() );
728 assert( 0 <= col && col < lpi->linear_program->num_variables().value() );
729
730 SCIPdebugMessage("Set coefficient (%d,%d) to %f.\n", row, col, newval);
731 lpi->linear_program->CleanUp();
732 assert( lpi->linear_program->IsCleanedUp() );
733 lpi->linear_program->SetCoefficient(RowIndex(row), ColIndex(col), newval);
734
736
737 return SCIP_OKAY;
738}
739
740/** changes the objective sense */
742 SCIP_LPI* lpi, /**< LP interface structure */
743 SCIP_OBJSEN objsen /**< new objective sense */
744 )
745{
746 assert( lpi != NULL);
747 assert( lpi->linear_program != NULL);
748
749 SCIPdebugMessage("changing objective sense to %d\n", objsen);
750
751 switch (objsen)
752 {
754 lpi->linear_program->SetMaximizationProblem(true);
755 break;
757 lpi->linear_program->SetMaximizationProblem(false);
758 break;
759 }
761
762 return SCIP_OKAY;
763}
764
765/** changes objective values of columns in the LP */
767 SCIP_LPI* lpi, /**< LP interface structure */
768 int ncols, /**< number of columns to change objective value for */
769 const int* ind, /**< column indices to change objective value for */
770 const SCIP_Real* obj /**< new objective values for columns */
771 )
772{
773 assert( lpi != NULL );
774 assert( lpi->linear_program != NULL );
775 assert( ind != NULL );
776 assert( obj != NULL );
777
778 SCIPdebugMessage("changing %d objective values\n", ncols);
779
780 for (int i = 0; i < ncols; ++i)
781 lpi->linear_program->SetObjectiveCoefficient(ColIndex(ind[i]), obj[i]);
782
784
785 return SCIP_OKAY;
786}
787
788/** multiplies a row with a non-zero scalar; for negative scalars, the row's sense is switched accordingly */
790 SCIP_LPI* lpi, /**< LP interface structure */
791 int row, /**< row number to scale */
792 SCIP_Real scaleval /**< scaling multiplier */
793 )
794{
795 SCIP_Real* vals;
796 SCIP_Real lhs;
797 SCIP_Real rhs;
798 int nnonz;
799 int* inds;
800 int beg;
801
802 assert( lpi != NULL );
803 assert( lpi->linear_program != NULL );
804
805 SCIPdebugMessage("Scale row %d by %f.\n", row, scaleval);
806
807 /* alloc memory */
808 ColIndex num_cols = lpi->linear_program->num_variables();
809
810 SCIP_ALLOC( BMSallocMemoryArray(&inds, num_cols.value()) );
811 SCIP_ALLOC( BMSallocMemoryArray(&vals, num_cols.value()) );
812
813 /* get the row */
814 SCIP_CALL( SCIPlpiGetRows(lpi, row, row, &lhs, &rhs, &nnonz, &beg, inds, vals) );
815
816 /* scale row coefficients */
817 for (int j = 0; j < nnonz; ++j)
818 {
819 SCIP_CALL( SCIPlpiChgCoef(lpi, row, inds[j], vals[j] * scaleval) );
820 }
821 BMSfreeMemoryArray(&vals);
822 BMSfreeMemoryArray(&inds);
823
824 /* scale row sides */
825 if ( ! SCIPlpiIsInfinity(lpi, -lhs) )
826 lhs *= scaleval;
827 else if ( scaleval < 0.0 )
828 lhs = SCIPlpiInfinity(lpi);
829
830 if ( ! SCIPlpiIsInfinity(lpi, rhs) )
831 rhs *= scaleval;
832 else if ( scaleval < 0.0 )
833 rhs = -SCIPlpiInfinity(lpi);
834
835 if ( scaleval > 0.0 )
836 {
837 SCIP_CALL( SCIPlpiChgSides(lpi, 1, &row, &lhs, &rhs) );
838 }
839 else
840 {
841 SCIP_CALL( SCIPlpiChgSides(lpi, 1, &row, &rhs, &lhs) );
842 }
843
845
846 return SCIP_OKAY;
847}
848
849/** multiplies a column with a non-zero scalar; the objective value is multiplied with the scalar, and the bounds
850 * are divided by the scalar; for negative scalars, the column's bounds are switched
851 */
853 SCIP_LPI* lpi, /**< LP interface structure */
854 int col, /**< column number to scale */
855 SCIP_Real scaleval /**< scaling multiplier */
856 )
857{
858 SCIP_Real* vals;
859 SCIP_Real lb;
860 SCIP_Real ub;
861 SCIP_Real obj;
862 int nnonz;
863 int* inds;
864 int beg;
865
866 assert( lpi != NULL );
867 assert( lpi->linear_program != NULL );
868
869 SCIPdebugMessage("Scale column %d by %f.\n", col, scaleval);
870
871 /* alloc memory */
872 RowIndex num_rows = lpi->linear_program->num_constraints();
873
874 SCIP_ALLOC( BMSallocMemoryArray(&inds, num_rows.value()) );
875 SCIP_ALLOC( BMSallocMemoryArray(&vals, num_rows.value()) );
876
877 /* get the column */
878 SCIP_CALL( SCIPlpiGetCols(lpi, col, col, &lb, &ub, &nnonz, &beg, inds, vals) );
879
880 /* scale column coefficients */
881 for (int j = 0; j < nnonz; ++j)
882 {
883 SCIP_CALL( SCIPlpiChgCoef(lpi, col, inds[j], vals[j] * scaleval) );
884 }
885 BMSfreeMemoryArray(&vals);
886 BMSfreeMemoryArray(&inds);
887
888 /* scale objective value */
889 SCIP_CALL( SCIPlpiGetObj(lpi, col, col, &obj) );
890 obj *= scaleval;
891 SCIP_CALL( SCIPlpiChgObj(lpi, 1, &col, &obj) );
892
893 /* scale bound */
894 if ( ! SCIPlpiIsInfinity(lpi, -lb) )
895 lb *= scaleval;
896 else if ( scaleval < 0.0 )
897 lb = SCIPlpiInfinity(lpi);
898
899 if ( ! SCIPlpiIsInfinity(lpi, ub) )
900 ub *= scaleval;
901 else if ( scaleval < 0.0 )
902 ub = -SCIPlpiInfinity(lpi);
903
904 if ( scaleval > 0.0 )
905 {
906 SCIP_CALL( SCIPlpiChgBounds(lpi, 1, &col, &lb, &ub) );
907 }
908 else
909 {
910 SCIP_CALL( SCIPlpiChgBounds(lpi, 1, &col, &ub, &lb) );
911 }
912
913 return SCIP_OKAY;
914}
915
916
917/**@} */
918
919
920
921
922/*
923 * Data Accessing Methods
924 */
925
926/**@name Data Accessing Methods */
927/**@{ */
928
929/** gets the number of rows in the LP */
931 SCIP_LPI* lpi, /**< LP interface structure */
932 int* nrows /**< pointer to store the number of rows */
933 )
934{
935 assert( lpi != NULL );
936 assert( lpi->linear_program != NULL );
937 assert( nrows != NULL );
938
939 SCIPdebugMessage("getting number of rows.\n");
940
941 *nrows = lpi->linear_program->num_constraints().value();
942
943 return SCIP_OKAY;
944}
945
946/** gets the number of columns in the LP */
948 SCIP_LPI* lpi, /**< LP interface structure */
949 int* ncols /**< pointer to store the number of cols */
950 )
951{
952 assert( lpi != NULL );
953 assert( lpi->linear_program != NULL );
954 assert( ncols != NULL );
955
956 SCIPdebugMessage("getting number of columns.\n");
957
958 *ncols = lpi->linear_program->num_variables().value();
959
960 return SCIP_OKAY;
961}
962
963/** gets objective sense of the LP */
965 SCIP_LPI* lpi, /**< LP interface structure */
966 SCIP_OBJSEN* objsen /**< pointer to store objective sense */
967 )
968{
969 assert( lpi != NULL );
970 assert( lpi->linear_program != NULL );
971 assert( objsen != NULL );
972
973 SCIPdebugMessage("getting objective sense.\n");
974
975 *objsen = lpi->linear_program->IsMaximizationProblem() ? SCIP_OBJSEN_MAXIMIZE : SCIP_OBJSEN_MINIMIZE;
976
977 return SCIP_OKAY;
978}
979
980/** gets the number of nonzero elements in the LP constraint matrix */
982 SCIP_LPI* lpi, /**< LP interface structure */
983 int* nnonz /**< pointer to store the number of nonzeros */
984 )
985{
986 assert( lpi != NULL );
987 assert( lpi->linear_program != NULL );
988 assert( nnonz != NULL );
989
990 SCIPdebugMessage("getting number of non-zeros.\n");
991
992 *nnonz = (int) lpi->linear_program->num_entries().value();
993
994 return SCIP_OKAY;
995}
996
997/** gets columns from LP problem object; the arrays have to be large enough to store all values
998 * Either both, lb and ub, have to be NULL, or both have to be non-NULL,
999 * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
1000 */
1002 SCIP_LPI* lpi, /**< LP interface structure */
1003 int firstcol, /**< first column to get from LP */
1004 int lastcol, /**< last column to get from LP */
1005 SCIP_Real* lb, /**< buffer to store the lower bound vector, or NULL */
1006 SCIP_Real* ub, /**< buffer to store the upper bound vector, or NULL */
1007 int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
1008 int* beg, /**< buffer to store start index of each column in ind- and val-array, or NULL */
1009 int* ind, /**< buffer to store row indices of constraint matrix entries, or NULL */
1010 SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
1011 )
1012{
1013 assert( lpi != NULL );
1014 assert( lpi->linear_program != NULL );
1015 assert( 0 <= firstcol && firstcol <= lastcol && lastcol < lpi->linear_program->num_variables() );
1016 assert( (lb != NULL && ub != NULL) || (lb == NULL && ub == NULL) );
1017 assert( (nnonz != NULL && beg != NULL && ind != NULL && val != NULL) || (nnonz == NULL && beg == NULL && ind == NULL && val == NULL) );
1018
1019 const DenseRow& tmplb = lpi->linear_program->variable_lower_bounds();
1020 const DenseRow& tmpub = lpi->linear_program->variable_upper_bounds();
1021
1022 if ( nnonz != NULL )
1023 {
1024 assert( beg != NULL );
1025 assert( ind != NULL );
1026 assert( val != NULL );
1027
1028 *nnonz = 0;
1029 int index = 0;
1030 for (ColIndex col(firstcol); col <= ColIndex(lastcol); ++col, ++index)
1031 {
1032 if ( lb != NULL )
1033 lb[index] = tmplb[col];
1034 if ( ub != NULL )
1035 ub[index] = tmpub[col];
1036
1037 beg[index] = *nnonz;
1038 const SparseColumn& column = lpi->linear_program->GetSparseColumn(col);
1039 for (const SparseColumn::Entry& entry : column)
1040 {
1041 const RowIndex row = entry.row();
1042 ind[*nnonz] = row.value();
1043 val[*nnonz] = entry.coefficient();
1044 ++(*nnonz);
1045 }
1046 }
1047 }
1048 else
1049 {
1050 int index = 0;
1051 for (ColIndex col(firstcol); col <= ColIndex(lastcol); ++col, ++index)
1052 {
1053 if ( lb != NULL )
1054 lb[index] = tmplb[col];
1055 if ( ub != NULL )
1056 ub[index] = tmpub[col];
1057 }
1058 }
1059
1060 return SCIP_OKAY;
1061}
1062
1063/** gets rows from LP problem object; the arrays have to be large enough to store all values.
1064 * Either both, lhs and rhs, have to be NULL, or both have to be non-NULL,
1065 * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
1066 */
1068 SCIP_LPI* lpi, /**< LP interface structure */
1069 int firstrow, /**< first row to get from LP */
1070 int lastrow, /**< last row to get from LP */
1071 SCIP_Real* lhs, /**< buffer to store left hand side vector, or NULL */
1072 SCIP_Real* rhs, /**< buffer to store right hand side vector, or NULL */
1073 int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
1074 int* beg, /**< buffer to store start index of each row in ind- and val-array, or NULL */
1075 int* ind, /**< buffer to store column indices of constraint matrix entries, or NULL */
1076 SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
1077 )
1078{
1079 assert( lpi != NULL );
1080 assert( lpi->linear_program != NULL );
1081 assert( 0 <= firstrow && firstrow <= lastrow && lastrow < lpi->linear_program->num_constraints() );
1082 assert( (lhs == NULL && rhs == NULL) || (rhs != NULL && lhs != NULL) );
1083 assert( (nnonz != NULL && beg != NULL && ind != NULL && val != NULL) || (nnonz == NULL && beg == NULL && ind == NULL && val == NULL) );
1084
1085 const DenseColumn& tmplhs = lpi->linear_program->constraint_lower_bounds();
1086 const DenseColumn& tmprhs = lpi->linear_program->constraint_upper_bounds();
1087
1088 if ( nnonz != NULL )
1089 {
1090 assert( beg != NULL );
1091 assert( ind != NULL );
1092 assert( val != NULL );
1093
1094 const SparseMatrix& matrixtrans = lpi->linear_program->GetTransposeSparseMatrix();
1095
1096 *nnonz = 0;
1097 int index = 0;
1098 for (RowIndex row(firstrow); row <= RowIndex(lastrow); ++row, ++index)
1099 {
1100 if ( lhs != NULL )
1101 lhs[index] = tmplhs[row];
1102 if ( rhs != NULL )
1103 rhs[index] = tmprhs[row];
1104
1105 beg[index] = *nnonz;
1106 const SparseColumn& column = matrixtrans.column(ColIndex(row.value()));
1107 for (const SparseColumn::Entry& entry : column)
1108 {
1109 const RowIndex rowidx = entry.row();
1110 ind[*nnonz] = rowidx.value();
1111 val[*nnonz] = entry.coefficient();
1112 ++(*nnonz);
1113 }
1114 }
1115 }
1116 else
1117 {
1118 int index = 0;
1119 for (RowIndex row(firstrow); row <= RowIndex(lastrow); ++row, ++index)
1120 {
1121 if ( lhs != NULL )
1122 lhs[index] = tmplhs[row];
1123 if ( rhs != NULL )
1124 rhs[index] = tmprhs[row];
1125 }
1126 }
1127
1128 return SCIP_OKAY;
1129}
1130
1131/** gets column names */
1133 SCIP_LPI* lpi, /**< LP interface structure */
1134 int firstcol, /**< first column to get name from LP */
1135 int lastcol, /**< last column to get name from LP */
1136 char** colnames, /**< pointers to column names (of size at least lastcol-firstcol+1) or NULL if namestoragesize is zero */
1137 char* namestorage, /**< storage for col names or NULL if namestoragesize is zero */
1138 int namestoragesize, /**< size of namestorage (if 0, storageleft returns the storage needed) */
1139 int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */
1140 )
1141{
1142 assert( lpi != NULL );
1143 assert( lpi->linear_program != NULL );
1144 assert( colnames != NULL || namestoragesize == 0 );
1145 assert( namestorage != NULL || namestoragesize == 0 );
1146 assert( namestoragesize >= 0 );
1147 assert( storageleft != NULL );
1148 assert( 0 <= firstcol && firstcol <= lastcol && lastcol < lpi->linear_program->num_variables() );
1149
1150 SCIPerrorMessage("SCIPlpiGetColNames() has not been implemented yet.\n");
1151
1152 return SCIP_NOTIMPLEMENTED;
1153}
1154
1155/** gets row names */
1157 SCIP_LPI* lpi, /**< LP interface structure */
1158 int firstrow, /**< first row to get name from LP */
1159 int lastrow, /**< last row to get name from LP */
1160 char** rownames, /**< pointers to row names (of size at least lastrow-firstrow+1) or NULL if namestoragesize is zero */
1161 char* namestorage, /**< storage for row names or NULL if namestoragesize is zero */
1162 int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */
1163 int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */
1164 )
1165{
1166 assert( lpi != NULL );
1167 assert( lpi->linear_program != NULL );
1168 assert( rownames != NULL || namestoragesize == 0 );
1169 assert( namestorage != NULL || namestoragesize == 0 );
1170 assert( namestoragesize >= 0 );
1171 assert( storageleft != NULL );
1172 assert( 0 <= firstrow && firstrow <= lastrow && lastrow < lpi->linear_program->num_constraints() );
1173
1174 SCIPerrorMessage("SCIPlpiGetRowNames() has not been implemented yet.\n");
1175
1176 return SCIP_NOTIMPLEMENTED;
1177}
1178
1179/** gets objective coefficients from LP problem object */
1181 SCIP_LPI* lpi, /**< LP interface structure */
1182 int firstcol, /**< first column to get objective coefficient for */
1183 int lastcol, /**< last column to get objective coefficient for */
1184 SCIP_Real* vals /**< array to store objective coefficients */
1185 )
1186{
1187 assert( lpi != NULL );
1188 assert( lpi->linear_program != NULL );
1189 assert( firstcol <= lastcol );
1190 assert( vals != NULL );
1191
1192 SCIPdebugMessage("getting objective values %d to %d\n", firstcol, lastcol);
1193
1194 int index = 0;
1195 for (ColIndex col(firstcol); col <= ColIndex(lastcol); ++col)
1196 {
1197 vals[index] = lpi->linear_program->objective_coefficients()[col];
1198 ++index;
1199 }
1200
1201 return SCIP_OKAY;
1202}
1203
1204/** gets current bounds from LP problem object */
1206 SCIP_LPI* lpi, /**< LP interface structure */
1207 int firstcol, /**< first column to get bounds for */
1208 int lastcol, /**< last column to get bounds for */
1209 SCIP_Real* lbs, /**< array to store lower bound values, or NULL */
1210 SCIP_Real* ubs /**< array to store upper bound values, or NULL */
1211 )
1212{
1213 assert( lpi != NULL );
1214 assert( lpi->linear_program != NULL );
1215 assert( firstcol <= lastcol );
1216
1217 SCIPdebugMessage("getting bounds %d to %d\n", firstcol, lastcol);
1218
1219 int index = 0;
1220 for (ColIndex col(firstcol); col <= ColIndex(lastcol); ++col)
1221 {
1222 if ( lbs != NULL )
1223 lbs[index] = lpi->linear_program->variable_lower_bounds()[col];
1224
1225 if ( ubs != NULL )
1226 ubs[index] = lpi->linear_program->variable_upper_bounds()[col];
1227
1228 ++index;
1229 }
1230
1231 return SCIP_OKAY;
1232}
1233
1234/** gets current row sides from LP problem object */
1236 SCIP_LPI* lpi, /**< LP interface structure */
1237 int firstrow, /**< first row to get sides for */
1238 int lastrow, /**< last row to get sides for */
1239 SCIP_Real* lhss, /**< array to store left hand side values, or NULL */
1240 SCIP_Real* rhss /**< array to store right hand side values, or NULL */
1241 )
1242{
1243 assert( lpi != NULL );
1244 assert( lpi->linear_program != NULL );
1245 assert( firstrow <= lastrow );
1246
1247 SCIPdebugMessage("getting row sides %d to %d\n", firstrow, lastrow);
1248
1249 int index = 0;
1250 for (RowIndex row(firstrow); row <= RowIndex(lastrow); ++row)
1251 {
1252 if ( lhss != NULL )
1253 lhss[index] = lpi->linear_program->constraint_lower_bounds()[row];
1254
1255 if ( rhss != NULL )
1256 rhss[index] = lpi->linear_program->constraint_upper_bounds()[row];
1257
1258 ++index;
1259 }
1260
1261 return SCIP_OKAY;
1262}
1263
1264/** gets a single coefficient */
1266 SCIP_LPI* lpi, /**< LP interface structure */
1267 int row, /**< row number of coefficient */
1268 int col, /**< column number of coefficient */
1269 SCIP_Real* val /**< pointer to store the value of the coefficient */
1270 )
1271{
1272 assert( lpi != NULL );
1273 assert( lpi->linear_program != NULL );
1274 assert( val != NULL );
1275
1276 /* quite slow method: possibly needs linear time if matrix is not sorted */
1277 const SparseMatrix& matrix = lpi->linear_program->GetSparseMatrix();
1278 *val = matrix.LookUpValue(RowIndex(row), ColIndex(col));
1279
1280 return SCIP_OKAY;
1281}
1282
1283/**@} */
1284
1285
1286
1287
1288/*
1289 * Solving Methods
1290 */
1291
1292/**@name Solving Methods */
1293/**@{ */
1294
1295/** update scaled linear program */
1296static
1298 SCIP_LPI* lpi /**< LP interface structure */
1299 )
1300{
1301 if ( ! lpi->lp_modified_since_last_solve )
1302 return;
1303
1304 lpi->scaled_lp->PopulateFromLinearProgram(*lpi->linear_program);
1305 lpi->scaled_lp->AddSlackVariablesWhereNecessary(false);
1306
1307 /* @todo: Avoid doing a copy if there is no scaling. */
1308 /* @todo: Avoid rescaling if not much changed. */
1309 if ( lpi->parameters->use_scaling() )
1310 lpi->scaler->Scale(lpi->scaled_lp);
1311 else
1312 lpi->scaler->Clear();
1313}
1314
1315/** check primal feasibility */
1316static
1318 SCIP_LPI* lpi /**< LP interface structure */
1319 )
1320{
1321 assert( lpi != NULL );
1322 assert( lpi->solver != NULL );
1323 assert( lpi->linear_program != NULL );
1324
1325#if UNSCALEDFEAS_CHECK == 1
1326 /* get unscaled solution */
1327 const ColIndex num_cols = lpi->linear_program->num_variables();
1328 DenseRow unscaledsol(num_cols);
1329 for (ColIndex col = ColIndex(0); col < num_cols; ++col)
1330 unscaledsol[col] = lpi->scaler->UnscaleVariableValue(col, lpi->solver->GetVariableValue(col));
1331
1332 /* if the solution is not feasible w.r.t. absolute tolerances, try to fix it in the unscaled problem */
1333 const double feastol = lpi->parameters->primal_feasibility_tolerance();
1334 return lpi->linear_program->SolutionIsLPFeasible(unscaledsol, feastol);
1335
1336#elif UNSCALEDFEAS_CHECK == 2
1337 const double feastol = lpi->parameters->primal_feasibility_tolerance();
1338
1339 /* check bounds of unscaled solution */
1340 const ColIndex num_cols = lpi->linear_program->num_variables();
1341 for (ColIndex col = ColIndex(0); col < num_cols; ++col)
1342 {
1343 const Fractional val = lpi->scaler->UnscaleVariableValue(col, lpi->solver->GetVariableValue(col));
1344 const Fractional lb = lpi->linear_program->variable_lower_bounds()[col];
1345 if ( val < lb - feastol )
1346 return false;
1347 const Fractional ub = lpi->linear_program->variable_upper_bounds()[col];
1348 if ( val > ub + feastol )
1349 return false;
1350 }
1351
1352 /* check activities of unscaled solution */
1353 const RowIndex num_rows = lpi->linear_program->num_constraints();
1354 for (RowIndex row(0); row < num_rows; ++row)
1355 {
1356 const Fractional val = lpi->scaler->UnscaleConstraintActivity(row, lpi->solver->GetConstraintActivity(row));
1357 const Fractional lhs = lpi->linear_program->constraint_lower_bounds()[row];
1358 if ( val < lhs - feastol )
1359 return false;
1360 const Fractional rhs = lpi->linear_program->constraint_upper_bounds()[row];
1361 if ( val > rhs + feastol )
1362 return false;
1363 }
1364#endif
1365
1366 return true;
1367}
1368
1369/** common function between the two LPI Solve() functions */
1370static
1372 SCIP_LPI* lpi, /**< LP interface structure */
1373 bool recursive, /**< Is this a recursive call? */
1374 std::unique_ptr<TimeLimit>& time_limit /**< time limit */
1375 )
1376{
1377 assert( lpi != NULL );
1378 assert( lpi->solver != NULL );
1379 assert( lpi->parameters != NULL );
1380
1381 updateScaledLP(lpi);
1382
1383 lpi->solver->SetParameters(*(lpi->parameters));
1384 lpi->lp_time_limit_was_reached = false;
1385
1386 /* possibly ignore warm start information for next solve */
1387 if ( lpi->from_scratch )
1388 lpi->solver->ClearStateForNextSolve();
1389
1390 if ( ! lpi->solver->Solve(*(lpi->scaled_lp), time_limit.get()).ok() )
1391 {
1392 return SCIP_LPERROR;
1393 }
1394 lpi->lp_time_limit_was_reached = time_limit->LimitReached();
1395 if ( recursive )
1396 lpi->niterations += (SCIP_Longint) lpi->solver->GetNumberOfIterations();
1397 else
1398 lpi->niterations = (SCIP_Longint) lpi->solver->GetNumberOfIterations();
1399
1400 SCIPdebugMessage("status=%s obj=%f iter=%ld.\n", GetProblemStatusString(lpi->solver->GetProblemStatus()).c_str(),
1401 lpi->solver->GetObjectiveValue(), lpi->solver->GetNumberOfIterations());
1402
1403 const ProblemStatus status = lpi->solver->GetProblemStatus();
1404 if ( (status == ProblemStatus::PRIMAL_FEASIBLE || status == ProblemStatus::OPTIMAL) && lpi->parameters->use_scaling() )
1405 {
1406 if ( ! checkUnscaledPrimalFeasibility(lpi) )
1407 {
1408 SCIPdebugMessage("Solution not feasible w.r.t. absolute tolerance %g -> reoptimize.\n", lpi->parameters->primal_feasibility_tolerance());
1409
1410 /* Re-solve without scaling to try to fix the infeasibility. */
1411 lpi->parameters->set_use_scaling(false);
1412 lpi->lp_modified_since_last_solve = true;
1413 SolveInternal(lpi, true, time_limit); /* inherit time limit, so used time is not reset; do not change iteration limit for resolve */
1414 lpi->parameters->set_use_scaling(true);
1415
1416#ifdef SCIP_DEBUG
1417 if ( ! checkUnscaledPrimalFeasibility(lpi) )
1418 SCIPdebugMessage("Solution still not feasible after turning off scaling.\n");
1419#endif
1420 }
1421 }
1422
1423 lpi->lp_modified_since_last_solve = false;
1424
1425 return SCIP_OKAY;
1426}
1427
1428/** calls primal simplex to solve the LP */
1430 SCIP_LPI* lpi /**< LP interface structure */
1431 )
1432{
1433 assert( lpi != NULL );
1434 assert( lpi->solver != NULL );
1435 assert( lpi->linear_program != NULL );
1436 assert( lpi->parameters != NULL );
1437
1438 SCIPdebugMessage("SCIPlpiSolvePrimal: %d rows, %d cols.\n", lpi->linear_program->num_constraints().value(), lpi->linear_program->num_variables().value());
1439 std::unique_ptr<TimeLimit> time_limit = TimeLimit::FromParameters(*lpi->parameters);
1440 lpi->niterations = 0;
1441
1442 lpi->parameters->set_use_dual_simplex(false);
1443 return SolveInternal(lpi, false, time_limit);
1444}
1445
1446/** calls dual simplex to solve the LP */
1448 SCIP_LPI* lpi /**< LP interface structure */
1449 )
1450{
1451 assert( lpi != NULL );
1452 assert( lpi->solver != NULL );
1453 assert( lpi->linear_program != NULL );
1454 assert( lpi->parameters != NULL );
1455
1456 SCIPdebugMessage("SCIPlpiSolveDual: %d rows, %d cols.\n", lpi->linear_program->num_constraints().value(), lpi->linear_program->num_variables().value());
1457 std::unique_ptr<TimeLimit> time_limit = TimeLimit::FromParameters(*lpi->parameters);
1458 lpi->niterations = 0;
1459
1460 lpi->parameters->set_use_dual_simplex(true);
1461 return SolveInternal(lpi, false, time_limit);
1462}
1463
1464/** calls barrier or interior point algorithm to solve the LP with crossover to simplex basis */
1466 SCIP_LPI* lpi, /**< LP interface structure */
1467 SCIP_Bool crossover /**< perform crossover */
1468 )
1469{
1470 assert( lpi != NULL );
1471 assert( lpi->solver != NULL );
1472 assert( lpi->linear_program != NULL );
1473 assert( lpi->parameters != NULL );
1474
1475 SCIPerrorMessage("SCIPlpiSolveBarrier - Not supported.\n");
1476
1477 return SCIP_NOTIMPLEMENTED;
1478}
1479
1480/** start strong branching */
1482 SCIP_LPI* lpi /**< LP interface structure */
1483 )
1484{ /*lint --e{715}*/
1485 assert( lpi != NULL );
1486 assert( lpi->linear_program != NULL );
1487 assert( lpi->solver != NULL );
1488
1489 updateScaledLP(lpi);
1490
1491 /* @todo Save state and do all the branching from there. */
1492 return SCIP_OKAY;
1493}
1494
1495/** end strong branching */
1497 SCIP_LPI* lpi /**< LP interface structure */
1498 )
1499{ /*lint --e{715}*/
1500 assert( lpi != NULL );
1501 assert( lpi->linear_program != NULL );
1502 assert( lpi->solver != NULL );
1503
1504 /* @todo Restore the saved state. */
1505 return SCIP_OKAY;
1506}
1507
1508/** determine whether the dual bound is valid */
1509static
1511 ProblemStatus status /**< status to be checked */
1512 )
1513{
1514 return status == ProblemStatus::OPTIMAL || status == ProblemStatus::DUAL_FEASIBLE || status == ProblemStatus::DUAL_UNBOUNDED;
1515}
1516
1517/** performs strong branching iterations */
1518static
1520 SCIP_LPI* lpi, /**< LP interface structure */
1521 int col_index, /**< column to apply strong branching on */
1522 SCIP_Real psol, /**< fractional current primal solution value of column */
1523 int itlim, /**< iteration limit for strong branchings */
1524 SCIP_Real* down, /**< stores dual bound after branching column down */
1525 SCIP_Real* up, /**< stores dual bound after branching column up */
1526 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
1527 * otherwise, it can only be used as an estimate value */
1528 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
1529 * otherwise, it can only be used as an estimate value */
1530 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
1531 )
1532{
1533 assert( lpi != NULL );
1534 assert( lpi->scaled_lp != NULL );
1535 assert( down != NULL );
1536 assert( up != NULL );
1537 assert( downvalid != NULL );
1538 assert( upvalid != NULL );
1539
1540 SCIPdebugMessage("calling strongbranching on variable %d (%d iterations)\n", col_index, itlim);
1541
1542 /* We work on the scaled problem. */
1543 const ColIndex col(col_index);
1544 const Fractional lb = lpi->scaled_lp->variable_lower_bounds()[col];
1545 const Fractional ub = lpi->scaled_lp->variable_upper_bounds()[col];
1546 const double value = psol * lpi->scaler->VariableScalingFactor(col);
1547
1548 /* Configure solver. */
1549
1550 /* @todo Use the iteration limit once glop supports incrementality. */
1551 int num_iterations = 0;
1552 lpi->parameters->set_use_dual_simplex(true);
1553 lpi->solver->SetParameters(*(lpi->parameters));
1554 const Fractional eps = lpi->parameters->primal_feasibility_tolerance();
1555
1556 std::unique_ptr<TimeLimit> time_limit = TimeLimit::FromParameters(*lpi->parameters);
1557
1558 /* Down branch. */
1559 const Fractional newub = EPSCEIL(value - 1.0, eps);
1560 if ( newub >= lb - 0.5 )
1561 {
1562 lpi->scaled_lp->SetVariableBounds(col, lb, newub);
1563
1564 if ( lpi->solver->Solve(*(lpi->scaled_lp), time_limit.get()).ok() )
1565 {
1566 num_iterations += (int) lpi->solver->GetNumberOfIterations();
1567 *down = lpi->solver->GetObjectiveValue();
1568 *downvalid = IsDualBoundValid(lpi->solver->GetProblemStatus()) ? TRUE : FALSE;
1569
1570 SCIPdebugMessage("down: itlim=%d col=%d [%f,%f] obj=%f status=%d iter=%ld.\n", itlim, col_index, lb, EPSCEIL(value - 1.0, eps),
1571 lpi->solver->GetObjectiveValue(), (int) lpi->solver->GetProblemStatus(), lpi->solver->GetNumberOfIterations());
1572 }
1573 else
1574 {
1575 SCIPerrorMessage("error during solve");
1576 *down = 0.0;
1577 *downvalid = FALSE;
1578 }
1579 }
1580 else
1581 {
1582 if ( lpi->linear_program->IsMaximizationProblem() )
1583 *down = lpi->parameters->objective_lower_limit();
1584 else
1585 *down = lpi->parameters->objective_upper_limit();
1586 *downvalid = TRUE;
1587 }
1588
1589 /* Up branch. */
1590 const Fractional newlb = EPSFLOOR(value + 1.0, eps);
1591 if ( newlb <= ub + 0.5 )
1592 {
1593 lpi->scaled_lp->SetVariableBounds(col, newlb, ub);
1594
1595 if ( lpi->solver->Solve(*(lpi->scaled_lp), time_limit.get()).ok() )
1596 {
1597 num_iterations += (int) lpi->solver->GetNumberOfIterations();
1598 *up = lpi->solver->GetObjectiveValue();
1599 *upvalid = IsDualBoundValid(lpi->solver->GetProblemStatus()) ? TRUE : FALSE;
1600
1601 SCIPdebugMessage("up: itlim=%d col=%d [%f,%f] obj=%f status=%d iter=%ld.\n", itlim, col_index, EPSFLOOR(value + 1.0, eps), ub,
1602 lpi->solver->GetObjectiveValue(), (int) lpi->solver->GetProblemStatus(), lpi->solver->GetNumberOfIterations());
1603 }
1604 else
1605 {
1606 SCIPerrorMessage("error during solve");
1607 *up = 0.0;
1608 *upvalid = FALSE;
1609 }
1610 }
1611 else
1612 {
1613 if (lpi->linear_program->IsMaximizationProblem())
1614 *up = lpi->parameters->objective_lower_limit();
1615 else
1616 *up = lpi->parameters->objective_upper_limit();
1617 *upvalid = TRUE;
1618 }
1619
1620 /* Restore bound. */
1621 lpi->scaled_lp->SetVariableBounds(col, lb, ub);
1622 if ( iter != NULL )
1623 *iter = num_iterations;
1624
1625 return SCIP_OKAY;
1626}
1627
1628/** performs strong branching iterations on one @b fractional candidate */
1630 SCIP_LPI* lpi, /**< LP interface structure */
1631 int col_index, /**< column to apply strong branching on */
1632 SCIP_Real psol, /**< fractional current primal solution value of column */
1633 int itlim, /**< iteration limit for strong branchings */
1634 SCIP_Real* down, /**< stores dual bound after branching column down */
1635 SCIP_Real* up, /**< stores dual bound after branching column up */
1636 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
1637 * otherwise, it can only be used as an estimate value */
1638 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
1639 * otherwise, it can only be used as an estimate value */
1640 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
1641 )
1642{
1643 assert( lpi != NULL );
1644 assert( lpi->scaled_lp != NULL );
1645 assert( down != NULL );
1646 assert( up != NULL );
1647 assert( downvalid != NULL );
1648 assert( upvalid != NULL );
1649
1650 SCIPdebugMessage("calling strongbranching on fractional variable %d (%d iterations)\n", col_index, itlim);
1651
1652 SCIP_CALL( strongbranch(lpi, col_index, psol, itlim, down, up, downvalid, upvalid, iter) );
1653
1654 return SCIP_OKAY;
1655}
1656
1657/** performs strong branching iterations on given @b fractional candidates */
1659 SCIP_LPI* lpi, /**< LP interface structure */
1660 int* cols, /**< columns to apply strong branching on */
1661 int ncols, /**< number of columns */
1662 SCIP_Real* psols, /**< fractional current primal solution values of columns */
1663 int itlim, /**< iteration limit for strong branchings */
1664 SCIP_Real* down, /**< stores dual bounds after branching columns down */
1665 SCIP_Real* up, /**< stores dual bounds after branching columns up */
1666 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
1667 * otherwise, they can only be used as an estimate values */
1668 SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
1669 * otherwise, they can only be used as an estimate values */
1670 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
1671 )
1672{
1673 assert( lpi != NULL );
1674 assert( lpi->linear_program != NULL );
1675 assert( cols != NULL );
1676 assert( psols != NULL );
1677 assert( down != NULL) ;
1678 assert( up != NULL );
1679 assert( downvalid != NULL );
1680 assert( upvalid != NULL );
1681
1682 SCIPerrorMessage("SCIPlpiStrongbranchesFrac - not implemented.\n");
1683
1684 return SCIP_NOTIMPLEMENTED;
1685}
1686
1687/** performs strong branching iterations on one candidate with @b integral value */
1689 SCIP_LPI* lpi, /**< LP interface structure */
1690 int col, /**< column to apply strong branching on */
1691 SCIP_Real psol, /**< current integral primal solution value of column */
1692 int itlim, /**< iteration limit for strong branchings */
1693 SCIP_Real* down, /**< stores dual bound after branching column down */
1694 SCIP_Real* up, /**< stores dual bound after branching column up */
1695 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
1696 * otherwise, it can only be used as an estimate value */
1697 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
1698 * otherwise, it can only be used as an estimate value */
1699 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
1700 )
1701{
1702 assert( lpi != NULL );
1703 assert( lpi->linear_program != NULL );
1704 assert( down != NULL );
1705 assert( up != NULL );
1706 assert( downvalid != NULL );
1707 assert( upvalid != NULL );
1708
1709 SCIP_CALL( strongbranch(lpi, col, psol, itlim, down, up, downvalid, upvalid, iter) );
1710
1711 return SCIP_OKAY;
1712}
1713
1714/** performs strong branching iterations on given candidates with @b integral values */
1716 SCIP_LPI* lpi, /**< LP interface structure */
1717 int* cols, /**< columns to apply strong branching on */
1718 int ncols, /**< number of columns */
1719 SCIP_Real* psols, /**< current integral primal solution values of columns */
1720 int itlim, /**< iteration limit for strong branchings */
1721 SCIP_Real* down, /**< stores dual bounds after branching columns down */
1722 SCIP_Real* up, /**< stores dual bounds after branching columns up */
1723 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
1724 * otherwise, they can only be used as an estimate values */
1725 SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
1726 * otherwise, they can only be used as an estimate values */
1727 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
1728 )
1729{
1730 assert( lpi != NULL );
1731 assert( lpi->linear_program != NULL );
1732 assert( cols != NULL );
1733 assert( psols != NULL );
1734 assert( down != NULL) ;
1735 assert( up != NULL );
1736 assert( downvalid != NULL );
1737 assert( upvalid != NULL );
1738
1739 SCIPerrorMessage("SCIPlpiStrongbranchesInt - not implemented.\n");
1740
1741 return SCIP_NOTIMPLEMENTED;
1742}
1743/**@} */
1744
1745
1746
1747
1748/*
1749 * Solution Information Methods
1750 */
1751
1752/**@name Solution Information Methods */
1753/**@{ */
1754
1755/** returns whether a solve method was called after the last modification of the LP */
1757 SCIP_LPI* lpi /**< LP interface structure */
1758 )
1759{
1760 assert( lpi != NULL );
1761
1762 /* @todo Track this to avoid uneeded resolving. */
1763 return ( ! lpi->lp_modified_since_last_solve );
1764}
1765
1766/** gets information about primal and dual feasibility of the current LP solution
1767 *
1768 * The feasibility information is with respect to the last solving call and it is only relevant if SCIPlpiWasSolved()
1769 * returns true. If the LP is changed, this information might be invalidated.
1770 *
1771 * Note that @a primalfeasible and @a dualfeasible should only return true if the solver has proved the respective LP to
1772 * be feasible. Thus, the return values should be equal to the values of SCIPlpiIsPrimalFeasible() and
1773 * SCIPlpiIsDualFeasible(), respectively. Note that if feasibility cannot be proved, they should return false (even if
1774 * the problem might actually be feasible).
1775 */
1777 SCIP_LPI* lpi, /**< LP interface structure */
1778 SCIP_Bool* primalfeasible, /**< pointer to store primal feasibility status */
1779 SCIP_Bool* dualfeasible /**< pointer to store dual feasibility status */
1780 )
1781{
1782 assert( lpi != NULL );
1783 assert( lpi->solver != NULL );
1784 assert( primalfeasible != NULL );
1785 assert( dualfeasible != NULL );
1786
1787 const ProblemStatus status = lpi->solver->GetProblemStatus();
1788 *primalfeasible = (status == ProblemStatus::OPTIMAL || status == ProblemStatus::PRIMAL_FEASIBLE);
1789 *dualfeasible = (status == ProblemStatus::OPTIMAL || status == ProblemStatus::DUAL_FEASIBLE);
1790
1791 SCIPdebugMessage("SCIPlpiGetSolFeasibility primal:%u dual:%u\n", *primalfeasible, *dualfeasible);
1792
1793 return SCIP_OKAY;
1794}
1795
1796/** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point);
1797 * this does not necessarily mean, that the solver knows and can return the primal ray
1798 */
1800 SCIP_LPI* lpi /**< LP interface structure */
1801 )
1802{
1803 assert( lpi != NULL );
1804 assert( lpi->solver != NULL );
1805
1806 return lpi->solver->GetProblemStatus() == ProblemStatus::PRIMAL_UNBOUNDED;
1807}
1808
1809/** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point),
1810 * and the solver knows and can return the primal ray
1811 */
1813 SCIP_LPI* lpi /**< LP interface structure */
1814 )
1815{
1816 assert( lpi != NULL );
1817 assert( lpi->solver != NULL );
1818
1819 return lpi->solver->GetProblemStatus() == ProblemStatus::PRIMAL_UNBOUNDED;
1820}
1821
1822/** returns TRUE iff LP is proven to be primal unbounded */
1824 SCIP_LPI* lpi /**< LP interface structure */
1825 )
1826{
1827 assert( lpi != NULL );
1828 assert( lpi->solver != NULL );
1829
1830 return lpi->solver->GetProblemStatus() == ProblemStatus::PRIMAL_UNBOUNDED;
1831}
1832
1833/** returns TRUE iff LP is proven to be primal infeasible */
1835 SCIP_LPI* lpi /**< LP interface structure */
1836 )
1837{
1838 assert( lpi != NULL );
1839 assert( lpi->solver != NULL );
1840
1841 const ProblemStatus status = lpi->solver->GetProblemStatus();
1842
1843 return status == ProblemStatus::DUAL_UNBOUNDED || status == ProblemStatus::PRIMAL_INFEASIBLE;
1844}
1845
1846/** returns TRUE iff LP is proven to be primal feasible */
1848 SCIP_LPI* lpi /**< LP interface structure */
1849 )
1850{
1851 assert( lpi != NULL );
1852 assert( lpi->solver != NULL );
1853
1854 const ProblemStatus status = lpi->solver->GetProblemStatus();
1855
1856 return status == ProblemStatus::PRIMAL_FEASIBLE || status == ProblemStatus::OPTIMAL;
1857}
1858
1859/** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point);
1860 * this does not necessarily mean, that the solver knows and can return the dual ray
1861 */
1863 SCIP_LPI* lpi /**< LP interface structure */
1864 )
1865{
1866 assert( lpi != NULL );
1867 assert( lpi->solver != NULL );
1868
1869 const ProblemStatus status = lpi->solver->GetProblemStatus();
1870
1871 return status == ProblemStatus::DUAL_UNBOUNDED;
1872}
1873
1874/** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point),
1875 * and the solver knows and can return the dual ray
1876 */
1878 SCIP_LPI* lpi /**< LP interface structure */
1879 )
1880{
1881 assert( lpi != NULL );
1882 assert( lpi->solver != NULL );
1883
1884 const ProblemStatus status = lpi->solver->GetProblemStatus();
1885
1886 return status == ProblemStatus::DUAL_UNBOUNDED;
1887}
1888
1889/** returns TRUE iff LP is proven to be dual unbounded */
1891 SCIP_LPI* lpi /**< LP interface structure */
1892 )
1893{
1894 assert( lpi != NULL );
1895 assert( lpi->solver != NULL );
1896
1897 const ProblemStatus status = lpi->solver->GetProblemStatus();
1898 return status == ProblemStatus::DUAL_UNBOUNDED;
1899}
1900
1901/** returns TRUE iff LP is proven to be dual infeasible */
1903 SCIP_LPI* lpi /**< LP interface structure */
1904 )
1905{
1906 assert( lpi != NULL );
1907 assert( lpi->solver != NULL );
1908
1909 const ProblemStatus status = lpi->solver->GetProblemStatus();
1910 return status == ProblemStatus::PRIMAL_UNBOUNDED || status == ProblemStatus::DUAL_INFEASIBLE;
1911}
1912
1913/** returns TRUE iff LP is proven to be dual feasible */
1915 SCIP_LPI* lpi /**< LP interface structure */
1916 )
1917{
1918 assert( lpi != NULL );
1919 assert( lpi->solver != NULL );
1920
1921 const ProblemStatus status = lpi->solver->GetProblemStatus();
1922
1923 return status == ProblemStatus::DUAL_FEASIBLE || status == ProblemStatus::OPTIMAL;
1924}
1925
1926/** returns TRUE iff LP was solved to optimality */
1928 SCIP_LPI* lpi /**< LP interface structure */
1929 )
1930{
1931 assert( lpi != NULL );
1932 assert( lpi->solver != NULL );
1933
1934 return lpi->solver->GetProblemStatus() == ProblemStatus::OPTIMAL;
1935}
1936
1937/** returns TRUE iff current LP solution is stable
1938 *
1939 * This function should return true if the solution is reliable, i.e., feasible and optimal (or proven
1940 * infeasible/unbounded) with respect to the original problem. The optimality status might be with respect to a scaled
1941 * version of the problem, but the solution might not be feasible to the unscaled original problem; in this case,
1942 * SCIPlpiIsStable() should return false.
1943 */
1945 SCIP_LPI* lpi /**< LP interface structure */
1946 )
1947{
1948 assert( lpi != NULL );
1949 assert( lpi->solver != NULL );
1950
1951 /* For correctness, we need to report "unstable" if Glop was not able to prove optimality because of numerical
1952 * issues. Currently Glop still reports primal/dual feasible if at the end, one status is within the tolerance but not
1953 * the other. */
1954 const ProblemStatus status = lpi->solver->GetProblemStatus();
1955 if ( (status == ProblemStatus::PRIMAL_FEASIBLE || status == ProblemStatus::DUAL_FEASIBLE) &&
1957 {
1958 SCIPdebugMessage("OPTIMAL not reached and no limit: unstable.\n");
1959 return FALSE;
1960 }
1961
1962 if ( status == ProblemStatus::ABNORMAL || status == ProblemStatus::INVALID_PROBLEM || status == ProblemStatus::IMPRECISE )
1963 return FALSE;
1964
1965 /* If we have a regular basis and the condition limit is set, we compute (an upper bound on) the condition number of
1966 * the basis; everything above the specified threshold is then counted as instable. */
1967 if ( lpi->checkcondition && (SCIPlpiIsOptimal(lpi) || SCIPlpiIsObjlimExc(lpi)) )
1968 {
1969 SCIP_RETCODE retcode;
1970 SCIP_Real kappa;
1971
1973 if ( retcode != SCIP_OKAY )
1974 SCIPABORT();
1975 assert( kappa != SCIP_INVALID ); /*lint !e777*/
1976
1977 if ( kappa > lpi->conditionlimit )
1978 return FALSE;
1979 }
1980
1981 return TRUE;
1982}
1983
1984/** returns TRUE iff the objective limit was reached */
1986 SCIP_LPI* lpi /**< LP interface structure */
1987 )
1988{
1989 assert( lpi != NULL );
1990 assert( lpi->solver != NULL );
1991
1992 return lpi->solver->objective_limit_reached();
1993}
1994
1995/** returns TRUE iff the iteration limit was reached */
1997 SCIP_LPI* lpi /**< LP interface structure */
1998 )
1999{
2000 assert( lpi != NULL );
2001 assert( lpi->solver != NULL );
2002 assert( lpi->niterations >= (int) lpi->solver->GetNumberOfIterations() );
2003
2004 int maxiter = (int) lpi->parameters->max_number_of_iterations();
2005 return maxiter >= 0 && lpi->niterations >= maxiter;
2006}
2007
2008/** returns TRUE iff the time limit was reached */
2010 SCIP_LPI* lpi /**< LP interface structure */
2011 )
2012{
2013 assert( lpi != NULL );
2014 assert( lpi->solver != NULL );
2015
2016 return lpi->lp_time_limit_was_reached;
2017}
2018
2019/** returns the internal solution status of the solver */
2021 SCIP_LPI* lpi /**< LP interface structure */
2022 )
2023{
2024 assert( lpi != NULL );
2025 assert( lpi->solver != NULL );
2026
2027 return static_cast<int>(lpi->solver->GetProblemStatus());
2028}
2029
2030/** tries to reset the internal status of the LP solver in order to ignore an instability of the last solving call */
2032 SCIP_LPI* lpi, /**< LP interface structure */
2033 SCIP_Bool* success /**< pointer to store, whether the instability could be ignored */
2034 )
2035{
2036 assert( lpi != NULL );
2037 assert( lpi->solver != NULL );
2038 assert( success != NULL );
2039
2040 *success = FALSE;
2041
2042 return SCIP_OKAY;
2043}
2044
2045/** gets objective value of solution */
2047 SCIP_LPI* lpi, /**< LP interface structure */
2048 SCIP_Real* objval /**< stores the objective value */
2049 )
2050{
2051 assert( lpi != NULL );
2052 assert( lpi->solver != NULL );
2053 assert( objval != NULL );
2054
2055 *objval = lpi->solver->GetObjectiveValue();
2056
2057 return SCIP_OKAY;
2058}
2059
2060/** gets primal and dual solution vectors for feasible LPs
2061 *
2062 * Before calling this function, the caller must ensure that the LP has been solved to optimality, i.e., that
2063 * SCIPlpiIsOptimal() returns true.
2064 */
2066 SCIP_LPI* lpi, /**< LP interface structure */
2067 SCIP_Real* objval, /**< stores the objective value, may be NULL if not needed */
2068 SCIP_Real* primsol, /**< primal solution vector, may be NULL if not needed */
2069 SCIP_Real* dualsol, /**< dual solution vector, may be NULL if not needed */
2070 SCIP_Real* activity, /**< row activity vector, may be NULL if not needed */
2071 SCIP_Real* redcost /**< reduced cost vector, may be NULL if not needed */
2072 )
2073{
2074 assert( lpi != NULL );
2075 assert( lpi->solver != NULL );
2076
2077 SCIPdebugMessage("SCIPlpiGetSol\n");
2078 if ( objval != NULL )
2079 *objval = lpi->solver->GetObjectiveValue();
2080
2081 const ColIndex num_cols = lpi->linear_program->num_variables();
2082 for (ColIndex col(0); col < num_cols; ++col)
2083 {
2084 int i = col.value();
2085
2086 if ( primsol != NULL )
2087 primsol[i] = lpi->scaler->UnscaleVariableValue(col, lpi->solver->GetVariableValue(col));
2088
2089 if ( redcost != NULL )
2090 redcost[i] = lpi->scaler->UnscaleReducedCost(col, lpi->solver->GetReducedCost(col));
2091 }
2092
2093 const RowIndex num_rows = lpi->linear_program->num_constraints();
2094 for (RowIndex row(0); row < num_rows; ++row)
2095 {
2096 int j = row.value();
2097
2098 if ( dualsol != NULL )
2099 dualsol[j] = lpi->scaler->UnscaleDualValue(row, lpi->solver->GetDualValue(row));
2100
2101 if ( activity != NULL )
2102 activity[j] = lpi->scaler->UnscaleConstraintActivity(row, lpi->solver->GetConstraintActivity(row));
2103 }
2104
2105 return SCIP_OKAY;
2106}
2107
2108/** gets primal ray for unbounded LPs */
2110 SCIP_LPI* lpi, /**< LP interface structure */
2111 SCIP_Real* ray /**< primal ray */
2112 )
2113{
2114 assert( lpi != NULL );
2115 assert( lpi->solver != NULL );
2116 assert( ray != NULL );
2117
2118 SCIPdebugMessage("SCIPlpiGetPrimalRay\n");
2119
2120 const ColIndex num_cols = lpi->linear_program->num_variables();
2121 const DenseRow& primal_ray = lpi->solver->GetPrimalRay();
2122 for (ColIndex col(0); col < num_cols; ++col)
2123 ray[col.value()] = lpi->scaler->UnscaleVariableValue(col, primal_ray[col]);
2124
2125 return SCIP_OKAY;
2126}
2127
2128/** gets dual Farkas proof for infeasibility */
2130 SCIP_LPI* lpi, /**< LP interface structure */
2131 SCIP_Real* dualfarkas /**< dual Farkas row multipliers */
2132 )
2133{
2134 assert( lpi != NULL );
2135 assert( lpi->solver != NULL );
2136 assert( dualfarkas != NULL );
2137
2138 SCIPdebugMessage("SCIPlpiGetDualfarkas\n");
2139
2140 const RowIndex num_rows = lpi->linear_program->num_constraints();
2141 const DenseColumn& dual_ray = lpi->solver->GetDualRay();
2142 for (RowIndex row(0); row < num_rows; ++row)
2143 dualfarkas[row.value()] = -lpi->scaler->UnscaleDualValue(row, dual_ray[row]); /* reverse sign */
2144
2145 return SCIP_OKAY;
2146}
2147
2148/** gets the number of LP iterations of the last solve call */
2150 SCIP_LPI* lpi, /**< LP interface structure */
2151 int* iterations /**< pointer to store the number of iterations of the last solve call */
2152 )
2153{
2154 assert( lpi != NULL );
2155 assert( lpi->solver != NULL );
2156 assert( iterations != NULL );
2157
2158 *iterations = (int) lpi->niterations;
2159
2160 return SCIP_OKAY;
2161}
2162
2163/** gets information about the quality of an LP solution
2164 *
2165 * Such information is usually only available, if also a (maybe not optimal) solution is available.
2166 * The LPI should return SCIP_INVALID for @p quality, if the requested quantity is not available.
2167 */
2169 SCIP_LPI* lpi, /**< LP interface structure */
2170 SCIP_LPSOLQUALITY qualityindicator, /**< indicates which quality should be returned */
2171 SCIP_Real* quality /**< pointer to store quality number */
2172 )
2173{
2174 assert( lpi != NULL );
2175 assert( lpi->solver != NULL );
2176 assert( quality != NULL );
2177
2178 SCIPdebugMessage("Requesting solution quality: quality %d\n", qualityindicator);
2179
2180 switch ( qualityindicator )
2181 {
2183 *quality = lpi->solver->GetBasisFactorization().ComputeInfinityNormConditionNumber();
2184 break;
2185
2187 *quality = lpi->solver->GetBasisFactorization().ComputeInfinityNormConditionNumberUpperBound();
2188 break;
2189
2190 default:
2191 SCIPerrorMessage("Solution quality %d unknown.\n", qualityindicator);
2192 return SCIP_INVALIDDATA;
2193 }
2194
2195 return SCIP_OKAY;
2196}
2197
2198/**@} */
2199
2200
2201
2202
2203/*
2204 * LP Basis Methods
2205 */
2206
2207/**@name LP Basis Methods */
2208/**@{ */
2209
2210/** convert Glop variable basis status to SCIP status */
2211static
2213 VariableStatus status, /**< variable status */
2214 Fractional rc /**< reduced cost of variable */
2215 )
2216{
2217 switch ( status )
2218 {
2219 case VariableStatus::BASIC:
2220 return SCIP_BASESTAT_BASIC;
2221 case VariableStatus::AT_UPPER_BOUND:
2222 return SCIP_BASESTAT_UPPER;
2223 case VariableStatus::AT_LOWER_BOUND:
2224 return SCIP_BASESTAT_LOWER;
2225 case VariableStatus::FREE:
2226 return SCIP_BASESTAT_ZERO;
2227 case VariableStatus::FIXED_VALUE:
2228 return rc > 0.0 ? SCIP_BASESTAT_LOWER : SCIP_BASESTAT_UPPER;
2229 default:
2230 SCIPerrorMessage("invalid Glop basis status.\n");
2231 abort();
2232 }
2233}
2234
2235/** convert Glop constraint basis status to SCIP status */
2236static
2238 ConstraintStatus status, /**< constraint status */
2239 Fractional dual /**< dual variable value */
2240 )
2241{
2242 switch ( status )
2243 {
2244 case ConstraintStatus::BASIC:
2245 return SCIP_BASESTAT_BASIC;
2246 case ConstraintStatus::AT_UPPER_BOUND:
2247 return SCIP_BASESTAT_UPPER;
2248 case ConstraintStatus::AT_LOWER_BOUND:
2249 return SCIP_BASESTAT_LOWER;
2250 case ConstraintStatus::FREE:
2251 return SCIP_BASESTAT_ZERO;
2252 case ConstraintStatus::FIXED_VALUE:
2253 return dual > 0.0 ? SCIP_BASESTAT_LOWER : SCIP_BASESTAT_UPPER;
2254 default:
2255 SCIPerrorMessage("invalid Glop basis status.\n");
2256 abort();
2257 }
2258}
2259
2260/** Convert SCIP variable status to Glop status */
2261static
2263 int status /**< SCIP variable status */
2264 )
2265{
2266 switch ( status )
2267 {
2269 return VariableStatus::BASIC;
2271 return VariableStatus::AT_UPPER_BOUND;
2273 return VariableStatus::AT_LOWER_BOUND;
2274 case SCIP_BASESTAT_ZERO:
2275 return VariableStatus::FREE;
2276 default:
2277 SCIPerrorMessage("invalid SCIP basis status.\n");
2278 abort();
2279 }
2280}
2281
2282/** Convert a SCIP constraint status to its corresponding Glop slack VariableStatus.
2283 *
2284 * Note that we swap the upper/lower bounds.
2285 */
2286static
2288 int status /**< SCIP constraint status */
2289 )
2290{
2291 switch ( status )
2292 {
2294 return VariableStatus::BASIC;
2296 return VariableStatus::AT_LOWER_BOUND;
2298 return VariableStatus::AT_UPPER_BOUND;
2299 case SCIP_BASESTAT_ZERO:
2300 return VariableStatus::FREE;
2301 default:
2302 SCIPerrorMessage("invalid SCIP basis status.\n");
2303 abort();
2304 }
2305}
2306
2307/** gets current basis status for columns and rows; arrays must be large enough to store the basis status */
2309 SCIP_LPI* lpi, /**< LP interface structure */
2310 int* cstat, /**< array to store column basis status, or NULL */
2311 int* rstat /**< array to store row basis status, or NULL */
2312 )
2313{
2314 SCIPdebugMessage("SCIPlpiGetBase\n");
2315
2316 assert( lpi->solver->GetProblemStatus() == ProblemStatus::OPTIMAL );
2317
2318 if ( cstat != NULL )
2319 {
2320 const ColIndex num_cols = lpi->linear_program->num_variables();
2321 for (ColIndex col(0); col < num_cols; ++col)
2322 {
2323 int i = col.value();
2324 cstat[i] = (int) ConvertGlopVariableStatus(lpi->solver->GetVariableStatus(col), lpi->solver->GetReducedCost(col));
2325 }
2326 }
2327
2328 if ( rstat != NULL )
2329 {
2330 const RowIndex num_rows = lpi->linear_program->num_constraints();
2331 for (RowIndex row(0); row < num_rows; ++row)
2332 {
2333 int i = row.value();
2334 rstat[i] = (int) ConvertGlopConstraintStatus(lpi->solver->GetConstraintStatus(row), lpi->solver->GetDualValue(row));
2335 }
2336 }
2337
2338 return SCIP_OKAY;
2339}
2340
2341/** sets current basis status for columns and rows */
2343 SCIP_LPI* lpi, /**< LP interface structure */
2344 const int* cstat, /**< array with column basis status */
2345 const int* rstat /**< array with row basis status */
2346 )
2347{
2348 assert( lpi != NULL );
2349 assert( lpi->linear_program != NULL );
2350 assert( lpi->solver != NULL );
2351
2352 const ColIndex num_cols = lpi->linear_program->num_variables();
2353 const RowIndex num_rows = lpi->linear_program->num_constraints();
2354
2355 assert( cstat != NULL || num_cols == 0 );
2356 assert( rstat != NULL || num_rows == 0 );
2357
2358 SCIPdebugMessage("SCIPlpiSetBase\n");
2359
2360 BasisState state;
2361 state.statuses.reserve(ColIndex(num_cols.value() + num_rows.value()));
2362
2363 for (ColIndex col(0); col < num_cols; ++col)
2364 state.statuses[col] = ConvertSCIPVariableStatus(cstat[col.value()]);
2365
2366 for (RowIndex row(0); row < num_rows; ++row)
2367 state.statuses[num_cols + RowToColIndex(row)] = ConvertSCIPConstraintStatusToSlackStatus(cstat[row.value()]);
2368
2369 lpi->solver->LoadStateForNextSolve(state);
2370
2371 return SCIP_OKAY;
2372}
2373
2374/** returns the indices of the basic columns and rows; basic column n gives value n, basic row m gives value -1-m */
2376 SCIP_LPI* lpi, /**< LP interface structure */
2377 int* bind /**< pointer to store basis indices ready to keep number of rows entries */
2378 )
2379{
2380 assert( lpi != NULL );
2381 assert( lpi->linear_program != NULL );
2382 assert( lpi->solver != NULL );
2383 assert( bind != NULL );
2384
2385 SCIPdebugMessage("SCIPlpiGetBasisInd\n");
2386
2387 /* the order is important! */
2388 const ColIndex num_cols = lpi->linear_program->num_variables();
2389 const RowIndex num_rows = lpi->linear_program->num_constraints();
2390 for (RowIndex row(0); row < num_rows; ++row)
2391 {
2392 const ColIndex col = lpi->solver->GetBasis(row);
2393 if (col < num_cols)
2394 bind[row.value()] = col.value();
2395 else
2396 {
2397 assert( col < num_cols.value() + num_rows.value() );
2398 bind[row.value()] = -1 - (col - num_cols).value();
2399 }
2400 }
2401
2402 return SCIP_OKAY;
2403}
2404
2405/** get row of inverse basis matrix B^-1
2406 *
2407 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2408 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2409 * see also the explanation in lpi.h.
2410 */
2412 SCIP_LPI* lpi, /**< LP interface structure */
2413 int r, /**< row number */
2414 SCIP_Real* coef, /**< pointer to store the coefficients of the row */
2415 int* inds, /**< array to store the non-zero indices, or NULL */
2416 int* ninds /**< pointer to store the number of non-zero indices, or NULL
2417 * (-1: if we do not store sparsity information) */
2418 )
2419{
2420 assert( lpi != NULL );
2421 assert( lpi->linear_program != NULL );
2422 assert( lpi->solver != NULL );
2423 assert( lpi->scaler != NULL );
2424 assert( coef != NULL );
2425
2426 lpi->solver->GetBasisFactorization().LeftSolveForUnitRow(ColIndex(r), lpi->tmp_row);
2427 lpi->scaler->UnscaleUnitRowLeftSolve(lpi->solver->GetBasis(RowIndex(r)), lpi->tmp_row);
2428
2429 const ColIndex size = lpi->tmp_row->values.size();
2430 assert( size.value() == lpi->linear_program->num_constraints() );
2431
2432 /* if we want a sparse vector */
2433 if ( ninds != NULL && inds != NULL )
2434 {
2435 *ninds = 0;
2436 /* Vectors in Glop might be stored in dense or sparse format depending on the values. If non_zeros are given, we
2437 * can directly loop over the non_zeros, otherwise we have to collect the nonzeros. */
2438 if ( ! lpi->tmp_row->non_zeros.empty() )
2439 {
2440 ScatteredRowIterator end = lpi->tmp_row->end();
2441 for (ScatteredRowIterator iter = lpi->tmp_row->begin(); iter != end; ++iter)
2442 {
2443 int idx = (*iter).column().value();
2444 assert( 0 <= idx && idx < lpi->linear_program->num_constraints() );
2445 coef[idx] = (*iter).coefficient();
2446 inds[(*ninds)++] = idx;
2447 }
2448 }
2449 else
2450 {
2451 /* use dense access to tmp_row */
2452 const Fractional eps = lpi->parameters->primal_feasibility_tolerance();
2453 for (ColIndex col(0); col < size; ++col)
2454 {
2455 SCIP_Real val = (*lpi->tmp_row)[col];
2456 if ( fabs(val) >= eps )
2457 {
2458 coef[col.value()] = val;
2459 inds[(*ninds)++] = col.value();
2460 }
2461 }
2462 }
2463 return SCIP_OKAY;
2464 }
2465
2466 /* dense version */
2467 for (ColIndex col(0); col < size; ++col)
2468 coef[col.value()] = (*lpi->tmp_row)[col];
2469
2470 if ( ninds != NULL )
2471 *ninds = -1;
2472
2473 return SCIP_OKAY;
2474}
2475
2476/** get column of inverse basis matrix B^-1
2477 *
2478 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2479 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2480 * see also the explanation in lpi.h.
2481 */
2483 SCIP_LPI* lpi, /**< LP interface structure */
2484 int c, /**< column number of B^-1; this is NOT the number of the column in the LP;
2485 * you have to call SCIPlpiGetBasisInd() to get the array which links the
2486 * B^-1 column numbers to the row and column numbers of the LP!
2487 * c must be between 0 and nrows-1, since the basis has the size
2488 * nrows * nrows */
2489 SCIP_Real* coef, /**< pointer to store the coefficients of the column */
2490 int* inds, /**< array to store the non-zero indices, or NULL */
2491 int* ninds /**< pointer to store the number of non-zero indices, or NULL
2492 * (-1: if we do not store sparsity information) */
2493 )
2494{
2495 assert( lpi != NULL );
2496 assert( lpi->linear_program != NULL );
2497 assert( lpi->solver != NULL );
2498 assert( lpi->scaler != NULL );
2499 assert( coef != NULL );
2500
2501 /* we need to loop through the rows to extract the values for column c */
2502 const ColIndex col(c);
2503 const RowIndex num_rows = lpi->linear_program->num_constraints();
2504
2505 /* if we want a sparse vector */
2506 if ( ninds != NULL && inds != NULL )
2507 {
2508 const Fractional eps = lpi->parameters->primal_feasibility_tolerance();
2509
2510 *ninds = 0;
2511 for (int row = 0; row < num_rows; ++row)
2512 {
2513 lpi->solver->GetBasisFactorization().LeftSolveForUnitRow(ColIndex(row), lpi->tmp_row);
2514 lpi->scaler->UnscaleUnitRowLeftSolve(lpi->solver->GetBasis(RowIndex(row)), lpi->tmp_row);
2515
2516 SCIP_Real val = (*lpi->tmp_row)[col];
2517 if ( fabs(val) >= eps )
2518 {
2519 coef[row] = val;
2520 inds[(*ninds)++] = row;
2521 }
2522 }
2523 return SCIP_OKAY;
2524 }
2525
2526 /* dense version */
2527 for (int row = 0; row < num_rows; ++row)
2528 {
2529 lpi->solver->GetBasisFactorization().LeftSolveForUnitRow(ColIndex(row), lpi->tmp_row);
2530 lpi->scaler->UnscaleUnitRowLeftSolve(lpi->solver->GetBasis(RowIndex(row)), lpi->tmp_row);
2531 coef[row] = (*lpi->tmp_row)[col];
2532 }
2533
2534 if ( ninds != NULL )
2535 *ninds = -1;
2536
2537 return SCIP_OKAY;
2538}
2539
2540/** get row of inverse basis matrix times constraint matrix B^-1 * A
2541 *
2542 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2543 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2544 * see also the explanation in lpi.h.
2545 */
2547 SCIP_LPI* lpi, /**< LP interface structure */
2548 int r, /**< row number */
2549 const SCIP_Real* binvrow, /**< row in (A_B)^-1 from prior call to SCIPlpiGetBInvRow(), or NULL */
2550 SCIP_Real* coef, /**< vector to return coefficients of the row */
2551 int* inds, /**< array to store the non-zero indices, or NULL */
2552 int* ninds /**< pointer to store the number of non-zero indices, or NULL
2553 * (-1: if we do not store sparsity information) */
2554 )
2555{
2556 assert( lpi != NULL );
2557 assert( lpi->linear_program != NULL );
2558 assert( lpi->solver != NULL );
2559 assert( lpi->scaler != NULL );
2560 assert( coef != NULL );
2561
2562 /* get row of basis inverse, loop through columns and muliply with matrix */
2563 lpi->solver->GetBasisFactorization().LeftSolveForUnitRow(ColIndex(r), lpi->tmp_row);
2564 lpi->scaler->UnscaleUnitRowLeftSolve(lpi->solver->GetBasis(RowIndex(r)), lpi->tmp_row);
2565
2566 const ColIndex num_cols = lpi->linear_program->num_variables();
2567
2568 /* if we want a sparse vector */
2569 if ( ninds != NULL && inds != NULL )
2570 {
2571 const Fractional eps = lpi->parameters->primal_feasibility_tolerance();
2572
2573 *ninds = 0;
2574 for (ColIndex col(0); col < num_cols; ++col)
2575 {
2576 SCIP_Real val = operations_research::glop::ScalarProduct(lpi->tmp_row->values, lpi->linear_program->GetSparseColumn(col));
2577 if ( fabs(val) >= eps )
2578 {
2579 coef[col.value()] = val;
2580 inds[(*ninds)++] = col.value();
2581 }
2582 }
2583 return SCIP_OKAY;
2584 }
2585
2586 /* dense version */
2587 for (ColIndex col(0); col < num_cols; ++col)
2588 coef[col.value()] = operations_research::glop::ScalarProduct(lpi->tmp_row->values, lpi->linear_program->GetSparseColumn(col));
2589
2590 if ( ninds != NULL )
2591 *ninds = -1;
2592
2593 return SCIP_OKAY;
2594}
2595
2596/** get column of inverse basis matrix times constraint matrix B^-1 * A
2597 *
2598 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2599 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2600 * see also the explanation in lpi.h.
2601 */
2603 SCIP_LPI* lpi, /**< LP interface structure */
2604 int c, /**< column number */
2605 SCIP_Real* coef, /**< vector to return coefficients of the column */
2606 int* inds, /**< array to store the non-zero indices, or NULL */
2607 int* ninds /**< pointer to store the number of non-zero indices, or NULL
2608 * (-1: if we do not store sparsity information) */
2609 )
2610{
2611 assert( lpi != NULL );
2612 assert( lpi->linear_program != NULL );
2613 assert( lpi->solver != NULL );
2614 assert( lpi->scaler != NULL );
2615 assert( coef != NULL );
2616
2617 lpi->solver->GetBasisFactorization().RightSolveForProblemColumn(ColIndex(c), lpi->tmp_column);
2618 lpi->scaler->UnscaleColumnRightSolve(lpi->solver->GetBasisVector(), ColIndex(c), lpi->tmp_column);
2619
2620 const RowIndex num_rows = lpi->tmp_column->values.size();
2621
2622 /* if we want a sparse vector */
2623 if ( ninds != NULL && inds != NULL )
2624 {
2625 *ninds = 0;
2626 /* Vectors in Glop might be stored in dense or sparse format depending on the values. If non_zeros are given, we
2627 * can directly loop over the non_zeros, otherwise we have to collect the nonzeros. */
2628 if ( ! lpi->tmp_column->non_zeros.empty() )
2629 {
2630 ScatteredColumnIterator end = lpi->tmp_column->end();
2631 for (ScatteredColumnIterator iter = lpi->tmp_column->begin(); iter != end; ++iter)
2632 {
2633 int idx = (*iter).row().value();
2634 assert( 0 <= idx && idx < num_rows );
2635 coef[idx] = (*iter).coefficient();
2636 inds[(*ninds)++] = idx;
2637 }
2638 }
2639 else
2640 {
2641 /* use dense access to tmp_column */
2642 const Fractional eps = lpi->parameters->primal_feasibility_tolerance();
2643 for (RowIndex row(0); row < num_rows; ++row)
2644 {
2645 SCIP_Real val = (*lpi->tmp_column)[row];
2646 if ( fabs(val) > eps )
2647 {
2648 coef[row.value()] = val;
2649 inds[(*ninds)++] = row.value();
2650 }
2651 }
2652 }
2653 return SCIP_OKAY;
2654 }
2655
2656 /* dense version */
2657 for (RowIndex row(0); row < num_rows; ++row)
2658 coef[row.value()] = (*lpi->tmp_column)[row];
2659
2660 if ( ninds != NULL )
2661 *ninds = -1;
2662
2663 return SCIP_OKAY;
2664}
2665
2666/**@} */
2667
2668
2669
2670
2671/*
2672 * LP State Methods
2673 */
2674
2675/**@name LP State Methods */
2676/**@{ */
2677
2678/* SCIP_LPiState stores basis information and is implemented by the glop BasisState class.
2679 * However, because in type_lpi.h there is
2680 * typedef struct SCIP_LPiState SCIP_LPISTATE;
2681 * We cannot just use a typedef here and SCIP_LPiState needs to be a struct.
2682 */
2683struct SCIP_LPiState : BasisState {};
2684
2685/** stores LPi state (like basis information) into lpistate object */
2687 SCIP_LPI* lpi, /**< LP interface structure */
2688 BMS_BLKMEM* blkmem, /**< block memory */
2689 SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
2690 )
2691{
2692 assert( lpi != NULL );
2693 assert( lpi->solver != NULL );
2694 assert( lpistate != NULL );
2695
2696 *lpistate = static_cast<SCIP_LPISTATE*>(new BasisState(lpi->solver->GetState()));
2697
2698 return SCIP_OKAY;
2699}
2700
2701/** loads LPi state (like basis information) into solver; note that the LP might have been extended with additional
2702 * columns and rows since the state was stored with SCIPlpiGetState()
2703 */
2705 SCIP_LPI* lpi, /**< LP interface structure */
2706 BMS_BLKMEM* blkmem, /**< block memory */
2707 const SCIP_LPISTATE* lpistate /**< LPi state information (like basis information), or NULL */
2708 )
2709{
2710 assert( lpi != NULL );
2711 assert( lpi->solver != NULL );
2712 assert( lpistate != NULL );
2713
2714 lpi->solver->LoadStateForNextSolve(*lpistate);
2715
2716 return SCIP_OKAY;
2717}
2718
2719/** clears current LPi state (like basis information) of the solver */
2721 SCIP_LPI* lpi /**< LP interface structure */
2722 )
2723{
2724 assert( lpi != NULL );
2725 assert( lpi->solver != NULL );
2726
2727 lpi->solver->ClearStateForNextSolve();
2728
2729 return SCIP_OKAY;
2730}
2731
2732/** frees LPi state information */
2734 SCIP_LPI* lpi, /**< LP interface structure */
2735 BMS_BLKMEM* blkmem, /**< block memory */
2736 SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
2737 )
2738{
2739 assert( lpi != NULL );
2740 assert( lpi->solver != NULL );
2741 assert( lpistate != NULL );
2742
2743 delete *lpistate;
2744 *lpistate = NULL;
2745
2746 return SCIP_OKAY;
2747}
2748
2749/** checks, whether the given LP state contains simplex basis information */
2751 SCIP_LPI* lpi, /**< LP interface structure */
2752 SCIP_LPISTATE* lpistate /**< LP state information (like basis information), or NULL */
2753 )
2754{
2755 assert( lpi != NULL );
2756 assert( lpi->solver != NULL );
2757
2758 return lpistate != NULL;
2759}
2760
2761/** reads LP state (like basis information from a file */
2763 SCIP_LPI* lpi, /**< LP interface structure */
2764 const char* fname /**< file name */
2765 )
2766{
2767 assert( lpi != NULL );
2768 assert( lpi->solver != NULL );
2769
2770 SCIPerrorMessage("SCIPlpiReadState - not implemented.\n");
2771
2772 return SCIP_NOTIMPLEMENTED;
2773}
2774
2775/** writes LPi state (i.e. basis information) to a file */
2777 SCIP_LPI* lpi, /**< LP interface structure */
2778 const char* fname /**< file name */
2779 )
2780{
2781 assert( lpi != NULL );
2782 assert( lpi->solver != NULL );
2783
2784 SCIPerrorMessage("SCIPlpiWriteState - not implemented.\n");
2785
2786 return SCIP_NOTIMPLEMENTED;
2787}
2788
2789/**@} */
2790
2791
2792
2793
2794/*
2795 * LP Pricing Norms Methods
2796 */
2797
2798/**@name LP Pricing Norms Methods */
2799/**@{ */
2800
2801/* SCIP_LPiNorms stores norm information so they are not recomputed from one state to the next. */
2802/* @todo Implement this. */
2803struct SCIP_LPiNorms {};
2804
2805/** stores LPi pricing norms information
2806 *
2807 * @todo store primal norms as well?
2808 */
2810 SCIP_LPI* lpi, /**< LP interface structure */
2811 BMS_BLKMEM* blkmem, /**< block memory */
2812 SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
2813 )
2814{
2815 assert( lpi != NULL );
2816 assert( blkmem != NULL );
2817 assert( lpi->solver != NULL );
2818 assert( lpinorms != NULL );
2819
2820 return SCIP_OKAY;
2821}
2822
2823/** loads LPi pricing norms into solver; note that the LP might have been extended with additional
2824 * columns and rows since the state was stored with SCIPlpiGetNorms()
2825 */
2827 SCIP_LPI* lpi, /**< LP interface structure */
2828 BMS_BLKMEM* blkmem, /**< block memory */
2829 const SCIP_LPINORMS* lpinorms /**< LPi pricing norms information, or NULL */
2830 )
2831{
2832 assert( lpi != NULL );
2833 assert( blkmem != NULL );
2834 assert( lpi->solver != NULL );
2835 assert( lpinorms != NULL );
2836
2837 return SCIP_OKAY;
2838}
2839
2840/** frees pricing norms information */
2842 SCIP_LPI* lpi, /**< LP interface structure */
2843 BMS_BLKMEM* blkmem, /**< block memory */
2844 SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information, or NULL */
2845 )
2846{
2847 assert( lpi != NULL );
2848 assert( blkmem != NULL );
2849 assert( lpi->solver != NULL );
2850 assert( lpinorms != NULL );
2851
2852 return SCIP_OKAY;
2853}
2854
2855/**@} */
2856
2857
2858
2859
2860/*
2861 * Parameter Methods
2862 */
2863
2864/**@name Parameter Methods */
2865/**@{ */
2866
2867/** gets integer parameter of LP */
2869 SCIP_LPI* lpi, /**< LP interface structure */
2870 SCIP_LPPARAM type, /**< parameter number */
2871 int* ival /**< buffer to store the parameter value */
2872 )
2873{
2874 assert( lpi != NULL );
2875 assert( lpi->parameters != NULL );
2876
2877 /* Not (yet) supported by Glop: SCIP_LPPAR_FASTMIP, SCIP_LPPAR_POLISHING, SCIP_LPPAR_REFACTOR */
2878 switch ( type )
2879 {
2881 *ival = (int) lpi->from_scratch;
2882 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_FROMSCRATCH = %d.\n", *ival);
2883 break;
2884 case SCIP_LPPAR_LPINFO:
2885 *ival = (int) lpi->lp_info;
2886 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_LPINFO = %d.\n", *ival);
2887 break;
2888 case SCIP_LPPAR_LPITLIM:
2889 *ival = (int) lpi->parameters->max_number_of_iterations();
2890 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_LPITLIM = %d.\n", *ival);
2891 break;
2893 *ival = lpi->parameters->use_preprocessing();
2894 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_PRESOLVING = %d.\n", *ival);
2895 break;
2896 case SCIP_LPPAR_PRICING:
2897 *ival = lpi->pricing;
2898 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_PRICING = %d.\n", *ival);
2899 break;
2900#ifndef NOSCALING
2901 case SCIP_LPPAR_SCALING:
2902 *ival = lpi->parameters->use_scaling();
2903 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_SCALING = %d.\n", *ival);
2904 break;
2905#endif
2906 case SCIP_LPPAR_THREADS:
2907 *ival = lpi->numthreads;
2908 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_THREADS = %d.\n", *ival);
2909 break;
2910 case SCIP_LPPAR_TIMING:
2911 *ival = lpi->timing;
2912 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_TIMING = %d.\n", *ival);
2913 break;
2915 *ival = (int) lpi->parameters->random_seed();
2916 SCIPdebugMessage("SCIPlpiGetIntpar: SCIP_LPPAR_RANDOMSEED = %d.\n", *ival);
2917 break;
2918 default:
2919 return SCIP_PARAMETERUNKNOWN;
2920 }
2921
2922 return SCIP_OKAY;
2923}
2924
2925/** sets integer parameter of LP */
2927 SCIP_LPI* lpi, /**< LP interface structure */
2928 SCIP_LPPARAM type, /**< parameter number */
2929 int ival /**< parameter value */
2930 )
2931{
2932 assert( lpi != NULL );
2933 assert( lpi->parameters != NULL );
2934
2935 switch ( type )
2936 {
2938 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_FROMSCRATCH -> %d.\n", ival);
2939 lpi->from_scratch = (bool) ival;
2940 break;
2941 case SCIP_LPPAR_LPINFO:
2942 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_LPINFO -> %d.\n", ival);
2943 if ( ival == 0 )
2944 {
2945 (void) google::SetVLOGLevel("*", google::GLOG_INFO);
2946 lpi->lp_info = false;
2947 }
2948 else
2949 {
2950 (void) google::SetVLOGLevel("*", google::GLOG_ERROR);
2951 lpi->lp_info = true;
2952 }
2953 break;
2954 case SCIP_LPPAR_LPITLIM:
2955 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_LPITLIM -> %d.\n", ival);
2956 lpi->parameters->set_max_number_of_iterations(ival);
2957 break;
2959 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_PRESOLVING -> %d.\n", ival);
2960 lpi->parameters->set_use_preprocessing(ival);
2961 break;
2962 case SCIP_LPPAR_PRICING:
2963 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_PRICING -> %d.\n", ival);
2964 lpi->pricing = (SCIP_Pricing)ival;
2965 switch ( lpi->pricing )
2966 {
2968 case SCIP_PRICING_AUTO:
2970 case SCIP_PRICING_STEEP:
2972 lpi->parameters->set_feasibility_rule(operations_research::glop::GlopParameters_PricingRule_STEEPEST_EDGE);
2973 break;
2974 case SCIP_PRICING_FULL:
2975 /* Dantzig does not really fit, but use it anyway */
2976 lpi->parameters->set_feasibility_rule(operations_research::glop::GlopParameters_PricingRule_DANTZIG);
2977 break;
2978 case SCIP_PRICING_DEVEX:
2979 lpi->parameters->set_feasibility_rule(operations_research::glop::GlopParameters_PricingRule_DEVEX);
2980 break;
2981 default:
2982 return SCIP_PARAMETERUNKNOWN;
2983 }
2984 break;
2985#ifndef NOSCALING
2986 case SCIP_LPPAR_SCALING:
2987 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_SCALING -> %d.\n", ival);
2988 lpi->parameters->set_use_scaling(ival);
2989 break;
2990#endif
2991 case SCIP_LPPAR_THREADS:
2992 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_THREADS -> %d.\n", ival);
2993 assert( ival >= 0 );
2994 lpi->numthreads = ival;
2995 if ( ival == 0 )
2996 lpi->parameters->set_num_omp_threads(1);
2997 else
2998 lpi->parameters->set_num_omp_threads(ival);
2999 break;
3000 case SCIP_LPPAR_TIMING:
3001 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_TIMING -> %d.\n", ival);
3002 assert( 0 <= ival && ival <= 2 );
3003 lpi->timing = ival;
3004 if ( ival == 1 )
3005 absl::SetFlag(&FLAGS_time_limit_use_usertime, true);
3006 else
3007 absl::SetFlag(&FLAGS_time_limit_use_usertime, false);
3008 break;
3010 SCIPdebugMessage("SCIPlpiSetIntpar: SCIP_LPPAR_RANDOMSEED -> %d.\n", ival);
3011 assert( ival >= 0 );
3012 lpi->parameters->set_random_seed(ival);
3013 break;
3014 default:
3015 return SCIP_PARAMETERUNKNOWN;
3016 }
3017
3018 return SCIP_OKAY;
3019}
3020
3021/** gets floating point parameter of LP */
3023 SCIP_LPI* lpi, /**< LP interface structure */
3024 SCIP_LPPARAM type, /**< parameter number */
3025 SCIP_Real* dval /**< buffer to store the parameter value */
3026 )
3027{
3028 assert( lpi != NULL );
3029 assert( lpi->parameters != NULL );
3030
3031 /* Not (yet) supported by Glop: SCIP_LPPAR_ROWREPSWITCH, SCIP_LPPAR_BARRIERCONVTOL */
3032 switch ( type )
3033 {
3034 case SCIP_LPPAR_FEASTOL:
3035 *dval = lpi->parameters->primal_feasibility_tolerance();
3036 SCIPdebugMessage("SCIPlpiGetRealpar: SCIP_LPPAR_FEASTOL = %g.\n", *dval);
3037 break;
3039 *dval = lpi->parameters->dual_feasibility_tolerance();
3040 SCIPdebugMessage("SCIPlpiGetRealpar: SCIP_LPPAR_DUALFEASTOL = %g.\n", *dval);
3041 break;
3042 case SCIP_LPPAR_OBJLIM:
3043 if (lpi->linear_program->IsMaximizationProblem())
3044 *dval = lpi->parameters->objective_lower_limit();
3045 else
3046 *dval = lpi->parameters->objective_upper_limit();
3047 SCIPdebugMessage("SCIPlpiGetRealpar: SCIP_LPPAR_OBJLIM = %f.\n", *dval);
3048 break;
3049 case SCIP_LPPAR_LPTILIM:
3050 if ( absl::GetFlag(FLAGS_time_limit_use_usertime) )
3051 *dval = lpi->parameters->max_time_in_seconds();
3052 else
3053 *dval = lpi->parameters->max_deterministic_time();
3054 SCIPdebugMessage("SCIPlpiGetRealpar: SCIP_LPPAR_LPTILIM = %f.\n", *dval);
3055 break;
3057 *dval = lpi->conditionlimit;
3058 break;
3059#ifdef SCIP_DISABLED_CODE
3060 /* currently do not apply Markowitz parameter, since the default value does not seem suitable for Glop */
3062 *dval = lpi->parameters->markowitz_singularity_threshold();
3063 SCIPdebugMessage("SCIPlpiGetRealpar: SCIP_LPPAR_MARKOWITZ = %f.\n", *dval);
3064 break;
3065#endif
3066 default:
3067 return SCIP_PARAMETERUNKNOWN;
3068 }
3069
3070 return SCIP_OKAY;
3071}
3072
3073/** sets floating point parameter of LP */
3075 SCIP_LPI* lpi, /**< LP interface structure */
3076 SCIP_LPPARAM type, /**< parameter number */
3077 SCIP_Real dval /**< parameter value */
3078 )
3079{
3080 assert( lpi != NULL );
3081 assert( lpi->parameters != NULL );
3082
3083 switch( type )
3084 {
3085 case SCIP_LPPAR_FEASTOL:
3086 SCIPdebugMessage("SCIPlpiSetRealpar: SCIP_LPPAR_FEASTOL -> %g.\n", dval);
3087 lpi->parameters->set_primal_feasibility_tolerance(dval);
3088 break;
3090 SCIPdebugMessage("SCIPlpiSetRealpar: SCIP_LPPAR_DUALFEASTOL -> %g.\n", dval);
3091 lpi->parameters->set_dual_feasibility_tolerance(dval);
3092 break;
3093 case SCIP_LPPAR_OBJLIM:
3094 SCIPdebugMessage("SCIPlpiSetRealpar: SCIP_LPPAR_OBJLIM -> %f.\n", dval);
3095 if (lpi->linear_program->IsMaximizationProblem())
3096 lpi->parameters->set_objective_lower_limit(dval);
3097 else
3098 lpi->parameters->set_objective_upper_limit(dval);
3099 break;
3100 case SCIP_LPPAR_LPTILIM:
3101 SCIPdebugMessage("SCIPlpiSetRealpar: SCIP_LPPAR_LPTILIM -> %f.\n", dval);
3102 if ( absl::GetFlag(FLAGS_time_limit_use_usertime) )
3103 lpi->parameters->set_max_time_in_seconds(dval);
3104 else
3105 lpi->parameters->set_max_deterministic_time(dval);
3106 break;
3108 lpi->conditionlimit = dval;
3109 lpi->checkcondition = (dval >= 0.0);
3110 break;
3111#ifdef SCIP_DISABLED_CODE
3112 /* currently do not apply Markowitz parameter, since the default value does not seem suitable for Glop */
3114 SCIPdebugMessage("SCIPlpiSetRealpar: SCIP_LPPAR_MARKOWITZ -> %f.\n", dval);
3115 lpi->parameters->set_markowitz_singularity_threshold(dval);
3116 break;
3117#endif
3118 default:
3119 return SCIP_PARAMETERUNKNOWN;
3120 }
3121
3122 return SCIP_OKAY;
3123}
3124
3125/** interrupts the currently ongoing lp solve or disables the interrupt */
3127 SCIP_LPI* lpi, /**< LP interface structure */
3128 SCIP_Bool interrupt /**< TRUE if interrupt should be set, FALSE if it should be disabled */
3129 )
3130{
3131 /*lint --e{715}*/
3132 assert(lpi != NULL);
3133
3134 return SCIP_OKAY;
3135}
3136
3137/**@} */
3138
3139
3140
3141
3142/*
3143 * Numerical Methods
3144 */
3145
3146/**@name Numerical Methods */
3147/**@{ */
3148
3149/** returns value treated as infinity in the LP solver */
3151 SCIP_LPI* lpi /**< LP interface structure */
3152 )
3153{
3154 assert( lpi != NULL );
3156}
3157
3158/** checks if given value is treated as infinity in the LP solver */
3160 SCIP_LPI* lpi, /**< LP interface structure */
3161 SCIP_Real val /**< value to be checked for infinity */
3162 )
3163{
3164 assert( lpi != NULL );
3165
3167}
3168
3169/**@} */
3170
3171
3172
3173
3174/*
3175 * File Interface Methods
3176 */
3177
3178/**@name File Interface Methods */
3179/**@{ */
3180
3181/** reads LP from a file */
3183 SCIP_LPI* lpi, /**< LP interface structure */
3184 const char* fname /**< file name */
3185 )
3186{
3187 assert( lpi != NULL );
3188 assert( lpi->linear_program != NULL );
3189 assert( fname != NULL );
3190
3191 const std::string filespec(fname);
3192 MPModelProto proto;
3193 if ( ! ReadFileToProto(filespec, &proto) )
3194 {
3195 SCIPerrorMessage("Could not read <%s>\n", fname);
3196 return SCIP_READERROR;
3197 }
3198 lpi->linear_program->Clear();
3199 MPModelProtoToLinearProgram(proto, lpi->linear_program);
3200
3201 return SCIP_OKAY;
3202}
3203
3204/** writes LP to a file */
3206 SCIP_LPI* lpi, /**< LP interface structure */
3207 const char* fname /**< file name */
3208 )
3209{
3210 assert( lpi != NULL );
3211 assert( lpi->linear_program != NULL );
3212 assert( fname != NULL );
3213
3214 MPModelProto proto;
3215 LinearProgramToMPModelProto(*lpi->linear_program, &proto);
3216 const std::string filespec(fname);
3217 if ( ! WriteProtoToFile(filespec, proto, operations_research::ProtoWriteFormat::kProtoText, true) )
3218 {
3219 SCIPerrorMessage("Could not write <%s>\n", fname);
3220 return SCIP_READERROR;
3221 }
3222
3223 return SCIP_OKAY;
3224}
3225
3226/**@} */
SCIP_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define SCIP_ALLOC(x)
Definition: def.h:385
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define EPSCEIL(x, eps)
Definition: def.h:207
#define SCIPABORT()
Definition: def.h:346
#define EPSFLOOR(x, eps)
Definition: def.h:206
#define SCIP_CALL(x)
Definition: def.h:374
#define infinity
Definition: gastrans.c:80
SCIP_RETCODE SCIPlpiChgSides(SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
Definition: lpi_glop.cpp:693
SCIP_RETCODE SCIPlpiSetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPISTATE *lpistate)
Definition: lpi_glop.cpp:2704
SCIP_RETCODE SCIPlpiGetBInvACol(SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_glop.cpp:2602
SCIP_RETCODE SCIPlpiGetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real *dval)
Definition: lpi_glop.cpp:3022
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:3150
SCIP_Bool SCIPlpiIsObjlimExc(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1985
SCIP_RETCODE SCIPlpiChgObjsen(SCIP_LPI *lpi, SCIP_OBJSEN objsen)
Definition: lpi_glop.cpp:741
SCIP_Bool SCIPlpiIsInfinity(SCIP_LPI *lpi, SCIP_Real val)
Definition: lpi_glop.cpp:3159
SCIP_RETCODE SCIPlpiClear(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:638
SCIP_RETCODE SCIPlpiClearState(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:2720
SCIP_Bool SCIPlpiExistsDualRay(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1862
SCIP_Bool SCIPlpiExistsPrimalRay(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1799
SCIP_RETCODE SCIPlpiGetBase(SCIP_LPI *lpi, int *cstat, int *rstat)
Definition: lpi_glop.cpp:2308
SCIP_RETCODE SCIPlpiReadState(SCIP_LPI *lpi, const char *fname)
Definition: lpi_glop.cpp:2762
SCIP_RETCODE SCIPlpiAddRows(SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_glop.cpp:483
SCIP_RETCODE SCIPlpiGetPrimalRay(SCIP_LPI *lpi, SCIP_Real *ray)
Definition: lpi_glop.cpp:2109
SCIP_RETCODE SCIPlpiGetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int *ival)
Definition: lpi_glop.cpp:2868
SCIP_RETCODE SCIPlpiWriteLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_glop.cpp:3205
SCIP_RETCODE SCIPlpiSetIntegralityInformation(SCIP_LPI *lpi, int ncols, int *intInfo)
Definition: lpi_glop.cpp:183
SCIP_Bool SCIPlpiIsDualInfeasible(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1902
static void deleteRowsAndUpdateCurrentBasis(SCIP_LPI *lpi, const DenseBooleanColumn &rows_to_delete)
Definition: lpi_glop.cpp:552
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
Definition: lpi_glop.cpp:3074
SCIP_RETCODE SCIPlpiStrongbranchFrac(SCIP_LPI *lpi, int col_index, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_glop.cpp:1629
SCIP_RETCODE SCIPlpiSetNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPINORMS *lpinorms)
Definition: lpi_glop.cpp:2826
SCIP_RETCODE SCIPlpiGetNNonz(SCIP_LPI *lpi, int *nnonz)
Definition: lpi_glop.cpp:981
SCIP_Bool SCIPlpiHasPrimalSolve(void)
Definition: lpi_glop.cpp:209
SCIP_RETCODE SCIPlpiStrongbranchInt(SCIP_LPI *lpi, int col, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_glop.cpp:1688
SCIP_RETCODE SCIPlpiGetBounds(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *lbs, SCIP_Real *ubs)
Definition: lpi_glop.cpp:1205
SCIP_Bool SCIPlpiHasBarrierSolve(void)
Definition: lpi_glop.cpp:225
SCIP_RETCODE SCIPlpiGetDualfarkas(SCIP_LPI *lpi, SCIP_Real *dualfarkas)
Definition: lpi_glop.cpp:2129
SCIP_RETCODE SCIPlpiGetObjval(SCIP_LPI *lpi, SCIP_Real *objval)
Definition: lpi_glop.cpp:2046
SCIP_RETCODE SCIPlpiScaleCol(SCIP_LPI *lpi, int col, SCIP_Real scaleval)
Definition: lpi_glop.cpp:852
int SCIPlpiGetInternalStatus(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:2020
SCIP_RETCODE SCIPlpiStartStrongbranch(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1481
SCIP_RETCODE SCIPlpiGetSolFeasibility(SCIP_LPI *lpi, SCIP_Bool *primalfeasible, SCIP_Bool *dualfeasible)
Definition: lpi_glop.cpp:1776
SCIP_RETCODE SCIPlpiFreeNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
Definition: lpi_glop.cpp:2841
SCIP_Bool SCIPlpiIsIterlimExc(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1996
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_glop.cpp:654
SCIP_Bool SCIPlpiIsPrimalUnbounded(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1823
SCIP_RETCODE SCIPlpiIgnoreInstability(SCIP_LPI *lpi, SCIP_Bool *success)
Definition: lpi_glop.cpp:2031
SCIP_RETCODE SCIPlpiWriteState(SCIP_LPI *lpi, const char *fname)
Definition: lpi_glop.cpp:2776
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
Definition: lpi_glop.cpp:283
SCIP_RETCODE SCIPlpiStrongbranchesFrac(SCIP_LPI *lpi, int *cols, int ncols, SCIP_Real *psols, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_glop.cpp:1658
SCIP_RETCODE SCIPlpiGetCoef(SCIP_LPI *lpi, int row, int col, SCIP_Real *val)
Definition: lpi_glop.cpp:1265
SCIP_Bool SCIPlpiIsPrimalFeasible(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1847
SCIP_RETCODE SCIPlpiReadLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_glop.cpp:3182
SCIP_RETCODE SCIPlpiGetRealSolQuality(SCIP_LPI *lpi, SCIP_LPSOLQUALITY qualityindicator, SCIP_Real *quality)
Definition: lpi_glop.cpp:2168
SCIP_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1914
SCIP_RETCODE SCIPlpiGetNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
Definition: lpi_glop.cpp:2809
SCIP_Bool SCIPlpiIsTimelimExc(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:2009
SCIP_Bool SCIPlpiHasStateBasis(SCIP_LPI *lpi, SCIP_LPISTATE *lpistate)
Definition: lpi_glop.cpp:2750
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_glop.cpp:2926
const char * SCIPlpiGetSolverName(void)
Definition: lpi_glop.cpp:155
SCIP_RETCODE SCIPlpiSetBase(SCIP_LPI *lpi, const int *cstat, const int *rstat)
Definition: lpi_glop.cpp:2342
SCIP_Bool SCIPlpiHasPrimalRay(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1812
SCIP_RETCODE SCIPlpiGetBInvRow(SCIP_LPI *lpi, int r, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_glop.cpp:2411
SCIP_RETCODE SCIPlpiDelRows(SCIP_LPI *lpi, int firstrow, int lastrow)
Definition: lpi_glop.cpp:582
SCIP_RETCODE SCIPlpiGetCols(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *lb, SCIP_Real *ub, int *nnonz, int *beg, int *ind, SCIP_Real *val)
Definition: lpi_glop.cpp:1001
SCIP_RETCODE SCIPlpiGetBInvCol(SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_glop.cpp:2482
SCIP_RETCODE SCIPlpiGetColNames(SCIP_LPI *lpi, int firstcol, int lastcol, char **colnames, char *namestorage, int namestoragesize, int *storageleft)
Definition: lpi_glop.cpp:1132
SCIP_RETCODE SCIPlpiGetBInvARow(SCIP_LPI *lpi, int r, const SCIP_Real *binvrow, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_glop.cpp:2546
SCIP_RETCODE SCIPlpiGetRows(SCIP_LPI *lpi, int firstrow, int lastrow, SCIP_Real *lhs, SCIP_Real *rhs, int *nnonz, int *beg, int *ind, SCIP_Real *val)
Definition: lpi_glop.cpp:1067
SCIP_Bool SCIPlpiWasSolved(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1756
const char * SCIPlpiGetSolverDesc(void)
Definition: lpi_glop.cpp:163
SCIP_RETCODE SCIPlpiSolveBarrier(SCIP_LPI *lpi, SCIP_Bool crossover)
Definition: lpi_glop.cpp:1465
SCIP_Bool SCIPlpiIsOptimal(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1927
SCIP_RETCODE SCIPlpiGetRowNames(SCIP_LPI *lpi, int firstrow, int lastrow, char **rownames, char *namestorage, int namestoragesize, int *storageleft)
Definition: lpi_glop.cpp:1156
SCIP_Bool SCIPlpiHasDualSolve(void)
Definition: lpi_glop.cpp:217
SCIP_RETCODE SCIPlpiEndStrongbranch(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1496
SCIP_RETCODE SCIPlpiGetSides(SCIP_LPI *lpi, int firstrow, int lastrow, SCIP_Real *lhss, SCIP_Real *rhss)
Definition: lpi_glop.cpp:1235
SCIP_RETCODE SCIPlpiStrongbranchesInt(SCIP_LPI *lpi, int *cols, int ncols, SCIP_Real *psols, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_glop.cpp:1715
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
Definition: lpi_glop.cpp:2065
SCIP_Bool SCIPlpiHasDualRay(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1877
SCIP_RETCODE SCIPlpiDelColset(SCIP_LPI *lpi, int *dstat)
Definition: lpi_glop.cpp:448
SCIP_RETCODE SCIPlpiGetObj(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *vals)
Definition: lpi_glop.cpp:1180
SCIP_RETCODE SCIPlpiFreeState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition: lpi_glop.cpp:2733
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1834
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1447
SCIP_RETCODE SCIPlpiAddCols(SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_glop.cpp:352
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1429
SCIP_RETCODE SCIPlpiLoadColLP(SCIP_LPI *lpi, SCIP_OBJSEN objsen, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_glop.cpp:316
SCIP_Bool SCIPlpiIsDualUnbounded(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1890
SCIP_RETCODE SCIPlpiGetIterations(SCIP_LPI *lpi, int *iterations)
Definition: lpi_glop.cpp:2149
SCIP_RETCODE SCIPlpiGetBasisInd(SCIP_LPI *lpi, int *bind)
Definition: lpi_glop.cpp:2375
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
Definition: lpi_glop.cpp:241
void * SCIPlpiGetSolverPointer(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:171
SCIP_RETCODE SCIPlpiChgObj(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *obj)
Definition: lpi_glop.cpp:766
SCIP_RETCODE SCIPlpiGetObjsen(SCIP_LPI *lpi, SCIP_OBJSEN *objsen)
Definition: lpi_glop.cpp:964
SCIP_Bool SCIPlpiIsStable(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1944
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
Definition: lpi_glop.cpp:947
SCIP_RETCODE SCIPlpiInterrupt(SCIP_LPI *lpi, SCIP_Bool interrupt)
Definition: lpi_glop.cpp:3126
SCIP_RETCODE SCIPlpiDelCols(SCIP_LPI *lpi, int firstcol, int lastcol)
Definition: lpi_glop.cpp:424
SCIP_RETCODE SCIPlpiDelRowset(SCIP_LPI *lpi, int *dstat)
Definition: lpi_glop.cpp:604
SCIP_RETCODE SCIPlpiScaleRow(SCIP_LPI *lpi, int row, SCIP_Real scaleval)
Definition: lpi_glop.cpp:789
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
Definition: lpi_glop.cpp:930
SCIP_RETCODE SCIPlpiGetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition: lpi_glop.cpp:2686
SCIP_RETCODE SCIPlpiChgCoef(SCIP_LPI *lpi, int row, int col, SCIP_Real newval)
Definition: lpi_glop.cpp:718
interface methods for specific LP solvers
static SCIP_BASESTAT ConvertGlopConstraintStatus(ConstraintStatus status, Fractional dual)
Definition: lpi_glop.cpp:2237
static char * glopname
Definition: lpi_glop.cpp:145
static SCIP_BASESTAT ConvertGlopVariableStatus(VariableStatus status, Fractional rc)
Definition: lpi_glop.cpp:2212
static VariableStatus ConvertSCIPConstraintStatusToSlackStatus(int status)
Definition: lpi_glop.cpp:2287
static bool IsDualBoundValid(ProblemStatus status)
Definition: lpi_glop.cpp:1510
static SCIP_RETCODE strongbranch(SCIP_LPI *lpi, int col_index, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_glop.cpp:1519
static SCIP_RETCODE SolveInternal(SCIP_LPI *lpi, bool recursive, std::unique_ptr< TimeLimit > &time_limit)
Definition: lpi_glop.cpp:1371
char * initGlopName()
Definition: lpi_glop.cpp:147
static void updateScaledLP(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1297
static bool checkUnscaledPrimalFeasibility(SCIP_LPI *lpi)
Definition: lpi_glop.cpp:1317
static VariableStatus ConvertSCIPVariableStatus(int status)
Definition: lpi_glop.cpp:2262
#define BMSfreeMemory(ptr)
Definition: memory.h:145
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:123
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:147
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define BMSallocMemory(ptr)
Definition: memory.h:118
real eps
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebugMessage
Definition: pub_message.h:96
ScatteredColumn * tmp_column
Definition: lpi_glop.cpp:125
int numthreads
Definition: lpi_glop.cpp:112
operations_research::glop::LinearProgram * linear_program
Definition: lpi_glop.cpp:98
ScatteredRow * tmp_row
Definition: lpi_glop.cpp:124
operations_research::glop::LinearProgram * scaled_lp
Definition: lpi_glop.cpp:99
operations_research::glop::GlopParameters * parameters
Definition: lpi_glop.cpp:101
bool lp_info
Definition: lpi_glop.cpp:109
SCIP_Real conditionlimit
Definition: lpi_cpx.c:174
int timing
Definition: lpi_glop.cpp:115
bool lp_time_limit_was_reached
Definition: lpi_glop.cpp:106
bool lp_modified_since_last_solve
Definition: lpi_glop.cpp:105
operations_research::glop::LpScalingHelper * scaler
Definition: lpi_glop.cpp:102
SCIP_Longint niterations
Definition: lpi_glop.cpp:118
SCIP_PRICING pricing
Definition: lpi_clp.cpp:112
operations_research::glop::RevisedSimplex * solver
Definition: lpi_glop.cpp:100
bool checkcondition
Definition: lpi_glop.cpp:114
bool from_scratch
Definition: lpi_glop.cpp:111
SCIP_Bool checkcondition
Definition: lpi_cpx.c:175
SCIP_Pricing
Definition: type_lpi.h:77
@ SCIP_PRICING_STEEPQSTART
Definition: type_lpi.h:83
@ SCIP_PRICING_AUTO
Definition: type_lpi.h:79
@ SCIP_PRICING_DEVEX
Definition: type_lpi.h:84
@ SCIP_PRICING_STEEP
Definition: type_lpi.h:82
@ SCIP_PRICING_FULL
Definition: type_lpi.h:80
@ SCIP_PRICING_LPIDEFAULT
Definition: type_lpi.h:78
@ SCIP_PRICING_PARTIAL
Definition: type_lpi.h:81
enum SCIP_Pricing SCIP_PRICING
Definition: type_lpi.h:86
enum SCIP_LPParam SCIP_LPPARAM
Definition: type_lpi.h:73
@ SCIP_LPSOLQUALITY_EXACTCONDITION
Definition: type_lpi.h:102
@ SCIP_LPSOLQUALITY_ESTIMCONDITION
Definition: type_lpi.h:101
@ SCIP_LPPAR_PRICING
Definition: type_lpi.h:54
@ SCIP_LPPAR_THREADS
Definition: type_lpi.h:66
@ SCIP_LPPAR_LPINFO
Definition: type_lpi.h:55
@ SCIP_LPPAR_SCALING
Definition: type_lpi.h:52
@ SCIP_LPPAR_TIMING
Definition: type_lpi.h:68
@ SCIP_LPPAR_LPTILIM
Definition: type_lpi.h:61
@ SCIP_LPPAR_PRESOLVING
Definition: type_lpi.h:53
@ SCIP_LPPAR_CONDITIONLIMIT
Definition: type_lpi.h:67
@ SCIP_LPPAR_RANDOMSEED
Definition: type_lpi.h:69
@ SCIP_LPPAR_DUALFEASTOL
Definition: type_lpi.h:57
@ SCIP_LPPAR_FROMSCRATCH
Definition: type_lpi.h:50
@ SCIP_LPPAR_MARKOWITZ
Definition: type_lpi.h:62
@ SCIP_LPPAR_FEASTOL
Definition: type_lpi.h:56
@ SCIP_LPPAR_LPITLIM
Definition: type_lpi.h:60
@ SCIP_LPPAR_OBJLIM
Definition: type_lpi.h:59
@ SCIP_BASESTAT_BASIC
Definition: type_lpi.h:92
@ SCIP_BASESTAT_UPPER
Definition: type_lpi.h:93
@ SCIP_BASESTAT_LOWER
Definition: type_lpi.h:91
@ SCIP_BASESTAT_ZERO
Definition: type_lpi.h:94
enum SCIP_LPSolQuality SCIP_LPSOLQUALITY
Definition: type_lpi.h:104
@ SCIP_OBJSEN_MAXIMIZE
Definition: type_lpi.h:42
@ SCIP_OBJSEN_MINIMIZE
Definition: type_lpi.h:43
enum SCIP_ObjSen SCIP_OBJSEN
Definition: type_lpi.h:45
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:96
@ SCIP_LPERROR
Definition: type_retcode.h:49
@ SCIP_READERROR
Definition: type_retcode.h:45
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_PARAMETERUNKNOWN
Definition: type_retcode.h:55
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_NOTIMPLEMENTED
Definition: type_retcode.h:61
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63