Scippy

SCIP

Solving Constraint Integer Programs

lpi_qso.c
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_qso.c
26 * @ingroup LPIS
27 * @brief LP interface for QSopt version >= 070303
28 * @author Daniel Espinoza
29 * @author Marc Pfetsch
30 */
31
32/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include "qsopt.h"
35#include "scip/bitencode.h"
36#include "lpi/lpi.h"
37#include "scip/pub_message.h"
38#include "scip/pub_misc.h"
39#include <string.h>
40
41typedef SCIP_DUALPACKET COLPACKET; /* each column needs two bits of information (basic/on_lower/on_upper) */
42#define COLS_PER_PACKET SCIP_DUALPACKETSIZE
43typedef SCIP_DUALPACKET ROWPACKET; /* each row needs two bit of information (basic/on_lower/on_upper) */
44#define ROWS_PER_PACKET SCIP_DUALPACKETSIZE
45
47{
48 LPI_QSOPT_ALGO_UNKNOWN = 0, /**< unknown */
49 LPI_QSOPT_ALGO_PRIMAL = 1, /**< primal simplex */
50 LPI_QSOPT_ALGO_DUAL = 2 /**< dual simplex */
51};
53
54
55/** LP interface */
56struct SCIP_LPi
57{
58 QSprob prob; /**< LP struct pointer */
59 int solstat; /**< solution status of last optimization call */
60 LPI_QSOPT_ALGO algo; /**< previously used algorithm */
61 int previt; /**< previous number of simplex iterations performed */
62 int rowspace; /**< current size of internal row-related arrays */
63 char* isen; /**< array of length rowspace */
64 double* irhs; /**< array of rhs rowspace */
65 double* irng; /**< array of range rowspace */
66 int* ircnt; /**< array of count rowspace */
67 int* irbeg; /**< array of beginning index rowspace */
68 int colspace; /**< current size of internal column-related arrays */
69 int* iccnt; /**< array of length colspace */
70 char* iccha; /**< array of type colspace */
71 int tbsz; /**< current size of tableau-related arrays */
72 double* itab; /**< array of length tbsz */
73 char* ibas; /**< array of length tbsz */
74 int pricing; /**< SCIP pricing option */
75 SCIP_MESSAGEHDLR* messagehdlr; /**< messagehdlr handler to printing messages, or NULL */
76};
77
78/** row norms */
79struct SCIP_LPiNorms
80{
81 int nrows; /**< number of rows */
82 int ncols; /**< number of columns */
83 char* cstat; /**< basis status of columns */
84 char* rstat; /**< basis status of rows */
85 SCIP_Real* norms; /**< row norms */
86};
87
88
89/** solver name */
90static char __qsstr[SCIP_MAXSTRLEN];
91
92
93
94/*
95 * local defines
96 */
97
98/** (feasibility) tolerance for qsopt */
99#define FEASTOL 1e-6
100
101/** tolerance for testing equality */
102#define EPSILON 1e-9
103
104/** print location of the calling line */
105#define __QS_PRINTLOC__ fprintf(stderr,", in (%s:%d)\n", __FILE__, __LINE__)
106
107/** This macro is to print error messages and jump to the given point in the code, it also prints the
108 * file name and line where this happened. */
109#define QS_TESTG(A,B,C) do{{ \
110 if (A){ \
111 fprintf(stderr, C); \
112 __QS_PRINTLOC__; \
113 goto B;}}}while(0)
114
115/** This macro is to print error messages and to exit with SCIP_LPERROR. */
116#define QS_ERROR(A,...) do{{ \
117 if (A){ \
118 fprintf(stderr,__VA_ARGS__); \
119 __QS_PRINTLOC__; \
120 return SCIP_LPERROR;}}}while(0)
121
122/** Return value macro, if the value is non-zero, write to standard error the returning code and
123 * where this happened, and return SCIP_ERROR, otherwise return normal SCIP_OKAY termination code. */
124#define QS_RETURN(A) do{ \
125 const int __RVAL__ = (A); \
126 if (__RVAL__){ \
127 fprintf(stderr,"LP Error: QSopt returned %d",__RVAL__); \
128 __QS_PRINTLOC__; \
129 return SCIP_ERROR;} \
130 return SCIP_OKAY;}while(0)
131
132/** Return value macro, if the value is non-zero, write to standard error the returning code and
133 * where this happened, and return SCIP_ERROR, otherwise do nothing. */
134#define QS_CONDRET(A) do{ \
135 const int __RVAL__ = (A); \
136 if (__RVAL__){ \
137 fprintf(stderr,"LP Error: QSopt returned %d",__RVAL__); \
138 __QS_PRINTLOC__; \
139 return SCIP_LPERROR;} \
140 }while(0)
141
142
143
144/*
145 * LPi state methods
146 */
147
148
149/** LPi state stores basis information */
150struct SCIP_LPiState
151{
152 int ncols; /**< number of LP columns */
153 int nrows; /**< number of LP rows */
154 COLPACKET* packcstat; /**< column basis status in compressed form */
155 ROWPACKET* packrstat; /**< row basis status in compressed form */
156};
157
158/** returns the number of packets needed to store column packet information */
159static
161 int ncols /**< number of columns to store */
162 )
163{
164 return (ncols + (int)COLS_PER_PACKET-1)/(int)COLS_PER_PACKET;
165}
166
167/** returns the number of packets needed to store row packet information */
168static
170 int nrows /**< number of rows to store */
171 )
172{
173 return (nrows + (int)ROWS_PER_PACKET-1)/(int)ROWS_PER_PACKET;
174}
175
176/** store row and column basis status in a packed LPi state object */
177static
179 SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */
180 const int* cstat, /**< basis status of columns in unpacked format */
181 const int* rstat /**< basis status of rows in unpacked format */
182 )
183{
184 assert(lpistate != NULL);
185 assert(lpistate->packcstat != NULL);
186 assert(lpistate->packrstat != NULL);
187
188 SCIPencodeDualBit(cstat, lpistate->packcstat, lpistate->ncols);
189 SCIPencodeDualBit(rstat, lpistate->packrstat, lpistate->nrows);
190}
191
192/** unpacks row and column basis status from a packed LPi state object */
193static
195 const SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */
196 int* cstat, /**< buffer for storing basis status of columns in unpacked format */
197 int* rstat /**< buffer for storing basis status of rows in unpacked format */
198 )
199{
200 assert(lpistate != NULL);
201 assert(lpistate->packcstat != NULL);
202 assert(lpistate->packrstat != NULL);
203
204 SCIPdecodeDualBit(lpistate->packcstat, cstat, lpistate->ncols);
205 SCIPdecodeDualBit(lpistate->packrstat, rstat, lpistate->nrows);
206}
207
208/** creates LPi state information object */
209static
211 SCIP_LPISTATE** lpistate, /**< pointer to LPi state */
212 BMS_BLKMEM* blkmem, /**< block memory */
213 int ncols, /**< number of columns to store */
214 int nrows /**< number of rows to store */
215 )
216{
217 assert(lpistate != NULL);
218 assert(blkmem != NULL);
219 assert(ncols >= 0);
220 assert(nrows >= 0);
221
222 SCIP_ALLOC( BMSallocBlockMemory(blkmem, lpistate) );
223 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum(ncols)) );
224 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum(nrows)) );
225
226 return SCIP_OKAY;
227}
228
229/** frees LPi state information */
230static
232 SCIP_LPISTATE** lpistate, /**< pointer to LPi state information (like basis information) */
233 BMS_BLKMEM* blkmem /**< block memory */
234 )
235{
236 assert(blkmem != NULL);
237 assert(lpistate != NULL);
238 assert(*lpistate != NULL);
239
240 BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum((*lpistate)->ncols));
241 BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum((*lpistate)->nrows));
242 BMSfreeBlockMemory(blkmem, lpistate);
243}
244
245
246
247/*
248 * local functions
249 */
250
251/** ensure size of column-related arrays */
252static
254 SCIP_LPI* const lpi, /**< pointer to an LP interface structure */
255 int sz /**< size */
256 )
257{
258 assert(lpi != NULL);
259 if( lpi->tbsz < sz )
260 {
261 lpi->tbsz = sz*2;
262 SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->itab), lpi->tbsz) );
263 SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->ibas), lpi->tbsz) );
264 }
265 return SCIP_OKAY;
266}
267
268/** ensure size of column-related arrays */
269static
271 SCIP_LPI* const lpi, /**< pointer to an LP interface structure */
272 int ncols /**< number of columns */
273 )
274{
275 assert(lpi != NULL);
276 if( lpi->colspace < ncols )
277 {
278 lpi->colspace = ncols*2;
281 }
282 return SCIP_OKAY;
283}
284
285/** ensure size of row-related arrays */
286static
288 SCIP_LPI* const lpi, /**< pointer to an LP interface structure */
289 int nrows /**< number of rows */
290 )
291{
292 assert(lpi != NULL);
293 if( lpi->rowspace < nrows )
294 {
295 lpi->rowspace = nrows*2;
301 }
302 return SCIP_OKAY;
303}
304
305/** transform lhs/rhs into qsopt format */
306static
308 SCIP_LPI* const lpi, /**< pointer to an LP interface structure */
309 int nrows, /**< number of rows */
310 const double* const lhs, /**< left hand side */
311 const double* const rhs /**< right hand side */
312 )
313{
314 int state;
315 register int i;
316
317 assert(lpi != NULL);
318 assert(lhs != NULL);
319 assert(rhs!= NULL);
320
321 for( i = 0 ; i < nrows ; ++i )
322 {
323 state = ((lhs[i] <= -QS_MAXDOUBLE ? 1 : 0) | (rhs[i] >= QS_MAXDOUBLE ? 2 : 0));
324 lpi->ircnt[i] = 0;
325 lpi->irbeg[i] = 0;
326 switch( state )
327 {
328 case 0:
329 /* check for equations */
330 if( EPSEQ(lhs[i], rhs[i], EPSILON) )
331 {
332 lpi->isen[i] = 'E';
333 lpi->irhs[i] = lhs[i];
334 lpi->irng[i] = 0.0;
335 }
336 else
337 {
338 lpi->isen[i] = 'R';
339 lpi->irhs[i] = lhs[i];
340 lpi->irng[i] = rhs[i] - lhs[i];
341 assert(lpi->irng[i] >= 0.0);
342 }
343 break;
344 case 1:
345 lpi->isen[i] = 'L';
346 lpi->irhs[i] = rhs[i];
347 lpi->irng[i] = 0;
348 break;
349 case 2:
350 lpi->isen[i] = 'G';
351 lpi->irhs[i] = lhs[i];
352 lpi->irng[i] = 0;
353 break;
354 default:
355 SCIPerrorMessage("Error, constraint %d has no bounds!", i);
356 SCIPABORT();
357 return SCIP_INVALIDDATA; /*lint !e527*/
358 }
359 }
360 return SCIP_OKAY;
361}
362
363
364
365
366/*
367 * Miscellaneous Methods
368 */
369
370
371/**@name Miscellaneous Methods */
372/**@{ */
373
374
375/** gets name and version of LP solver */
376const char* SCIPlpiGetSolverName(void)
377{
378 char* vname;
379 size_t vnamelen;
380
381 /* need to copy string to __qsstr, since vname will be freed */
382 vname = QSversion();
383 vnamelen = strlen(vname);
384 if ( vnamelen >= SCIP_MAXSTRLEN-1 )
385 vnamelen = SCIP_MAXSTRLEN - 2;
386 memcpy(__qsstr, vname, vnamelen);
387 __qsstr[vnamelen+1] = '\0';
388 QSfree(vname);
389 return __qsstr;
390}
391
392/** gets description of LP solver (developer, webpage, ...) */
394 void
395 )
396{
397 return "Linear Programming Solver developed by D. Applegate, W. Cook, S. Dash, and M. Mevenkamp (www.isye.gatech.edu/~wcook/qsopt)";
398}
399
400/** gets pointer for LP solver - use only with great care */
402 SCIP_LPI* lpi /**< pointer to an LP interface structure */
403 )
404{
405 assert(lpi != NULL);
406 return (void*) lpi->prob;
407}
408
409/** pass integrality information to LP solver */
411 SCIP_LPI* lpi, /**< pointer to an LP interface structure */
412 int ncols, /**< length of integrality array */
413 int* intInfo /**< integrality array (0: continuous, 1: integer). May be NULL iff ncols is 0. */
414 )
415{ /*lint --e{715}*/
416 assert( lpi != NULL );
417 assert( ncols >= 0 );
418 assert( ncols == 0 || intInfo != NULL );
419
420 SCIPerrorMessage("SCIPlpiSetIntegralityInformation() has not been implemented yet.\n");
421 return SCIP_LPERROR;
422}
423
424/** informs about availability of a primal simplex solving method */
426 void
427 )
428{
429 return TRUE;
430}
431
432/** informs about availability of a dual simplex solving method */
434 void
435 )
436{
437 return TRUE;
438}
439
440/** informs about availability of a barrier solving method */
442 void
443 )
444{
445 return FALSE;
446}
447
448/**@} */
449
450
451
452
453/*
454 * LPI Creation and Destruction Methods
455 */
456
457/**@name LPI Creation and Destruction Methods */
458/**@{ */
459
460/** creates an LP problem object */
462 SCIP_LPI** lpi, /**< pointer to an LP interface structure */
463 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler to use for printing messages, or NULL */
464 const char* name, /**< problem name */
465 SCIP_OBJSEN objsen /**< objective sense */
466 )
467{
468 /* QSopt only works with doubles as floating points and bool as integers */
469 assert(sizeof(SCIP_Real) == sizeof(double)); /*lint !e506*/
470 assert(sizeof(SCIP_Bool) == sizeof(int)); /*lint !e506*/
471 assert(name != NULL);
472 assert(lpi != NULL);
473
474 SCIPdebugMessage("SCIPlpiCreate()\n");
475
476 /* create LP */
478 memset(*lpi, 0, sizeof(struct SCIP_LPi));
479
480 (*lpi)->prob = QScreate_prob(name, (int) objsen);
481 if ( (*lpi)->prob == NULL )
482 {
483 SCIPerrorMessage("No memory\n");
484 return SCIP_LPERROR;
485 }
486
487 (*lpi)->rowspace = 1024;
488 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->isen),1024) );
489 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->irhs),1024) );
490 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->irng),1024) );
491 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->irbeg),1024) );
492 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->ircnt),1024) );
493
494 (*lpi)->colspace = 1024;
495 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->iccnt), 1024) );
496 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->iccha), 1024) );
497
498 (*lpi)->tbsz = 1024;
499 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->itab), 1024) );
500 SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->ibas), 1024) );
501
502 (*lpi)->messagehdlr = messagehdlr;
503 (*lpi)->algo = LPI_QSOPT_ALGO_UNKNOWN;
504
505 return SCIP_OKAY;
506}
507
508/** deletes an LP problem object */
510 SCIP_LPI** lpi /**< pointer to an LP interface structure */
511 )
512{
513 assert(lpi != NULL);
514 assert(*lpi != NULL);
515
516 SCIPdebugMessage("SCIPlpiFree()\n");
517
518 /* free LP */
519 QSfree_prob((*lpi)->prob);
520 BMSfreeMemoryArray( &((*lpi)->isen) );
521 BMSfreeMemoryArray( &((*lpi)->irhs) );
522 BMSfreeMemoryArray( &((*lpi)->irng) );
523 BMSfreeMemoryArray( &((*lpi)->ircnt) );
524 BMSfreeMemoryArray( &((*lpi)->irbeg) );
525 BMSfreeMemoryArray( &((*lpi)->iccnt) );
526 BMSfreeMemoryArray( &((*lpi)->iccha) );
527 BMSfreeMemoryArray( &((*lpi)->itab) );
528 BMSfreeMemoryArray( &((*lpi)->ibas) );
529
530 /* free memory */
531 BMSfreeMemory(lpi);
532
533 return SCIP_OKAY;
534}
535/**@} */
536
537
538
539
540/*
541 * Modification Methods
542 */
543
544/**@name Modification Methods */
545/**@{ */
546
547
548/** copies LP data with column matrix into LP solver */
550 SCIP_LPI* lpi, /**< LP interface structure */
551 SCIP_OBJSEN objsen, /**< objective sense */
552 int ncols, /**< number of columns */
553 const SCIP_Real* obj, /**< objective function values of columns */
554 const SCIP_Real* lb, /**< lower bounds of columns */
555 const SCIP_Real* ub, /**< upper bounds of columns */
556 char** colnames, /**< column names, or NULL */
557 int nrows, /**< number of rows */
558 const SCIP_Real* lhs, /**< left hand sides of rows */
559 const SCIP_Real* rhs, /**< right hand sides of rows */
560 char** rownames, /**< row names, or NULL */
561 int nnonz, /**< number of nonzero elements in the constraint matrix */
562 const int* beg, /**< start index of each column in ind- and val-array */
563 const int* ind, /**< row indices of constraint matrix entries */
564 const SCIP_Real* val /**< values of constraint matrix entries */
565 )
566{
567 register int i;
568
569#ifndef NDEBUG
570 {
571 int j;
572 for( j = 0; j < nnonz; j++ )
573 assert( val[j] != 0 );
574 }
575#endif
576
577 assert(lpi != NULL);
578 assert(lpi->prob != NULL);
579 assert(lhs != NULL);
580 assert(rhs != NULL);
581 assert(obj != NULL);
582 assert(lb != NULL);
583 assert(ub != NULL);
584 assert(beg != NULL);
585 assert(ind != NULL);
586 assert(val != NULL);
587
588 lpi->solstat = 0;
589
590 SCIPdebugMessage("loading LP in column format into QSopt: %d cols, %d rows\n", ncols, nrows);
591
592 /* delete old LP */
593 SCIP_CALL( SCIPlpiClear(lpi) );
594
595 /* set sense */
596 if( objsen == SCIP_OBJSEN_MAXIMIZE )
597 {
598 QS_CONDRET( QSchange_objsense(lpi->prob, QS_MAX) );
599 }
600 else
601 {
602 QS_CONDRET( QSchange_objsense(lpi->prob, QS_MIN) );
603 }
604
605 /* add rows with no matrix, and then the columns, first ensure space */
606 SCIP_CALL( ensureRowMem(lpi, nrows) );
607
608 /* convert lhs/rhs into sen/rhs/range tuples */
609 SCIP_CALL( convertSides(lpi, nrows, lhs, rhs) );
610
611 /* now we add the rows */
612 QS_CONDRET( QSadd_ranged_rows(lpi->prob, nrows, lpi->ircnt, lpi->irbeg, 0, 0, lpi->irhs, lpi->isen, lpi->irng, (const char**)rownames) );
613
614 /* ensure column size */
615 SCIP_CALL( ensureColMem(lpi, ncols) );
616
617 /* compute column lengths */
618 for( i = 0; i < ncols-1; ++i )
619 {
620 lpi->iccnt[i] = beg[i+1] - beg[i];
621 assert(lpi->iccnt[i] >= 0);
622 }
623
624 if( ncols > 0 )
625 {
626 lpi->iccnt[ncols-1] = nnonz - beg[ncols-1];
627 assert(lpi->iccnt[ncols-1] >= 0);
628 }
629
630 /* and add the columns */
631 QS_CONDRET( QSadd_cols(lpi->prob, ncols, lpi->iccnt, (int*) beg, (int*) ind, (SCIP_Real*) val, (SCIP_Real*) obj,
632 (SCIP_Real*) lb, (SCIP_Real*) ub, (const char**)colnames) );
633
634 return SCIP_OKAY;
635}
636
637
638/** adds columns to the LP */
640 SCIP_LPI* lpi, /**< LP interface structure */
641 int ncols, /**< number of columns to be added */
642 const SCIP_Real* obj, /**< objective function values of new columns */
643 const SCIP_Real* lb, /**< lower bounds of new columns */
644 const SCIP_Real* ub, /**< upper bounds of new columns */
645 char** colnames, /**< column names, or NULL */
646 int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
647 const int* beg, /**< start index of each column in ind- and val-array, or NULL if nnonz == 0 */
648 const int* ind, /**< row indices of constraint matrix entries, or NULL if nnonz == 0 */
649 const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
650 )
651{
652 register int i;
653 int* lbeg;
654
655 assert( lpi != NULL );
656 assert( lpi->prob != NULL );
657 assert(obj != NULL);
658 assert(nnonz == 0 || beg != NULL);
659 assert(nnonz == 0 || ind != NULL);
660 assert(nnonz == 0 || val != NULL);
661 assert(nnonz >= 0);
662 assert(ncols >= 0);
663
664 SCIPdebugMessage("adding %d columns with %d nonzeros to QSopt\n", ncols, nnonz);
665
666 if ( ncols <= 0 )
667 return SCIP_OKAY;
668 assert( lb != NULL && ub != NULL );
669
670 lpi->solstat = 0;
671
672 /* ensure column size */
673 SCIP_CALL( ensureColMem(lpi, ncols) );
674
675 /* if there are no nonzeros, we have to set up an artificial beg array */
676 if ( nnonz == 0 )
677 {
678 SCIP_ALLOC( BMSallocMemoryArray(&lbeg, ncols) );
679
680 /* compute column lengths */
681 for( i = 0; i < ncols; ++i )
682 {
683 lpi->iccnt[i] = 0;
684 lbeg[i] = 0;
685 }
686 }
687 else
688 {
689#ifndef NDEBUG
690 /* perform check that no new rows are added - this is forbidden */
691 int nrows;
692
693 nrows = QSget_rowcount(lpi->prob);
694 for (i = 0; i < nnonz; ++i)
695 {
696 assert( 0 <= ind[i] && ind[i] < nrows );
697 assert( val[i] != 0.0 );
698 }
699#endif
700
701 /* compute column lengths */
702 for( i = 0; i < ncols - 1; ++i )
703 {
704 lpi->iccnt[i] = beg[i+1] - beg[i];
705 assert(lpi->iccnt[i] >= 0);
706 }
707
708 lpi->iccnt[ncols-1] = nnonz - beg[ncols-1];
709 assert(lpi->iccnt[ncols-1] >= 0);
710 lbeg = (int*) beg;
711 }
712
713 /* add the columns */
714 QS_CONDRET( QSadd_cols(lpi->prob, ncols, lpi->iccnt, (int*) lbeg, (int*) ind, (SCIP_Real*) val, (SCIP_Real*) obj,
715 (SCIP_Real*) lb, (SCIP_Real*) ub, (const char**)colnames) );
716
717 /* possibly free space */
718 if ( nnonz == 0 )
719 {
720 BMSfreeMemoryArray(&lbeg);
721 }
722
723 return SCIP_OKAY;
724}
725
726/** deletes all columns in the given range from LP */
728 SCIP_LPI* lpi, /**< LP interface structure */
729 int firstcol, /**< first column to be deleted */
730 int lastcol /**< last column to be deleted */
731 )
732{
733 int len;
734 register int i;
735
736 assert(lpi != NULL);
737 assert(lpi->prob != NULL);
738
739 len = lastcol - firstcol +1;
740 lpi->solstat = 0;
741
742 assert(0 <= firstcol && len > 0 && lastcol < QSget_colcount(lpi->prob));
743
744 SCIPdebugMessage("deleting %d columns from QSopt\n", len);
745
746 SCIP_CALL( ensureColMem(lpi, len) );
747 for( i = firstcol ; i <= lastcol ; i++ )
748 lpi->iccnt[i-firstcol] = i;
749
750 QS_CONDRET( QSdelete_cols(lpi->prob, len, lpi->iccnt) );
751
752 return SCIP_OKAY;
753}
754
755/** deletes columns from SCIP_LP; the new position of a column must not be greater that its old position */
757 SCIP_LPI* lpi, /**< LP interface structure */
758 int* dstat /**< deletion status of columns
759 * input: 1 if column should be deleted, 0 if not
760 * output: new position of column, -1 if column was deleted */
761 )
762{
763 int ncols;
764 int ccnt;
765 register int i;
766
767 assert(lpi != NULL);
768 assert(lpi->prob != NULL);
769 assert(dstat != NULL);
770
771 ncols = QSget_colcount(lpi->prob);
772 lpi->solstat = 0;
773
774 SCIPdebugMessage("deleting a column set from QSopt\n");
775
776 QS_CONDRET( QSdelete_setcols(lpi->prob,dstat) );
777
778 for( i=0, ccnt=0; i < ncols; i++ )
779 {
780 if( dstat[i] )
781 dstat[i] = -1;
782 else
783 dstat[i] = ccnt++;
784 }
785
786 return SCIP_OKAY;
787}
788
789
790/** adds rows to the LP */
792 SCIP_LPI* lpi, /**< LP interface structure */
793 int nrows, /**< number of rows to be added */
794 const SCIP_Real* lhs, /**< left hand sides of new rows */
795 const SCIP_Real* rhs, /**< right hand sides of new rows */
796 char** rownames, /**< row names, or NULL */
797 int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
798 const int* beg, /**< start index of each row in ind- and val-array, or NULL if nnonz == 0 */
799 const int* ind, /**< column indices of constraint matrix entries, or NULL if nnonz == 0 */
800 const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
801 )
802{
803 register int i;
804
805 assert( lpi != NULL );
806 assert( lpi->prob != NULL );
807 assert( nrows >= 0 );
808 assert(lhs != NULL);
809 assert(rhs != NULL);
810
811 lpi->solstat = 0;
812
813 SCIPdebugMessage("adding %d rows with %d nonzeros to QSopt\n", nrows, nnonz);
814
815 if ( nrows <= 0 )
816 return SCIP_OKAY;
817
818 /* add rows with no matrix, and then the columns, first ensure space */
819 SCIP_CALL( ensureRowMem(lpi, nrows) );
820
821 /* convert lhs/rhs into sen/rhs/range tuples */
822 SCIP_CALL( convertSides(lpi, nrows, lhs, rhs) );
823
824 /* compute row count */
825 if( nnonz > 0 )
826 {
827 assert(beg != NULL);
828 assert(ind != NULL);
829 assert(val != NULL);
830
831#ifndef NDEBUG
832 {
833 /* perform check that no new cols are added - this is forbidden */
834 int ncols;
835
836 ncols = QSget_colcount(lpi->prob);
837 for (i = 0; i < nnonz; ++i)
838 {
839 assert( val[i] != 0.0 );
840 assert( 0 <= ind[i] && ind[i] < ncols );
841 }
842 }
843#endif
844
845 for( i = 0 ; i < nrows -1 ; i++ )
846 {
847 lpi->ircnt[i] = beg[i+1] - beg[i];
848 assert(lpi->ircnt[i] >= 0);
849 }
850 assert( nrows > 0 );
851 lpi->ircnt[nrows-1] = nnonz - beg[nrows-1];
852 assert(lpi->ircnt[nrows-1] >= 0);
853
854 /* now we add the rows */
855 QS_CONDRET( QSadd_ranged_rows(lpi->prob, nrows, lpi->ircnt, (int*) beg, (int*) ind, (SCIP_Real*) val, lpi->irhs,
856 lpi->isen, lpi->irng, (const char**)rownames) );
857 }
858 else
859 {
860 for( i = 0; i < nrows -1; ++i )
861 {
862 lpi->ircnt[i] = 0;
863 lpi->irbeg[i] = 0;
864 }
865
866 /* now we add the rows */
867 QS_CONDRET( QSadd_ranged_rows(lpi->prob, nrows, lpi->ircnt, lpi->irbeg, (int*) ind, (SCIP_Real*) val, lpi->irhs,
868 lpi->isen, lpi->irng, (const char**)rownames) );
869 }
870
871 return SCIP_OKAY;
872}
873
874/** gets column names */
876 SCIP_LPI* lpi, /**< LP interface structure */
877 int firstcol, /**< first column to get name from LP */
878 int lastcol, /**< last column to get name from LP */
879 char** colnames, /**< pointers to column names (of size at least lastcol-firstcol+1) or NULL if namestoragesize is zero */
880 char* namestorage, /**< storage for col names or NULL if namestoragesize is zero */
881 int namestoragesize, /**< size of namestorage (if 0, storageleft returns the storage needed) */
882 int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */
883 )
884{
885 char** cnames;
886 char* s;
887 int ncols;
888 int rval;
889 int j;
890 int sizeleft;
891
892 assert(lpi != NULL);
893 assert(lpi->prob != NULL);
894 assert(colnames != NULL || namestoragesize == 0);
895 assert(namestorage != NULL || namestoragesize == 0);
896 assert(namestoragesize >= 0);
897 assert(storageleft != NULL);
898 assert(0 <= firstcol && firstcol <= lastcol && lastcol < QSget_colcount(lpi->prob));
899
900 SCIPdebugMessage("getting column names %d to %d\n", firstcol, lastcol);
901
902 ncols = QSget_colcount(lpi->prob);
903 SCIP_ALLOC( BMSallocMemoryArray(&cnames, ncols) );
904
905 rval = QSget_colnames(lpi->prob, cnames);
906 QS_ERROR(rval, "failed getting column names");
907
908 /* copy column names */
909 s = namestorage;
910 sizeleft = namestoragesize;
911 for( j = firstcol; j <= lastcol; ++j )
912 {
913 const char* t;
914
915 assert( s != NULL );
916
917 t = cnames[j];
918 if( colnames != NULL )
919 colnames[j-firstcol] = s;
920 while( *t != '\0' )
921 {
922 if( sizeleft > 0 )
923 *(s++) = *(t++);
924 --sizeleft;
925 }
926 *(s++) = '\0';
927 }
928 *storageleft = sizeleft;
929
930 /* free space */
931 for( j = 0; j < ncols; ++j )
932 free(cnames[j]);
933
934 return SCIP_OKAY;
935}
936
937/** gets row names */
939 SCIP_LPI* lpi, /**< LP interface structure */
940 int firstrow, /**< first row to get name from LP */
941 int lastrow, /**< last row to get name from LP */
942 char** rownames, /**< pointers to row names (of size at least lastrow-firstrow+1) or NULL if namestoragesize is zero */
943 char* namestorage, /**< storage for row names or NULL if namestoragesize is zero */
944 int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */
945 int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */
946 )
947{
948 char** rnames;
949 char* s;
950 int nrows;
951 int rval;
952 int i;
953 int sizeleft;
954
955 assert(lpi != NULL);
956 assert(lpi->prob != NULL);
957 assert(rownames != NULL || namestoragesize == 0);
958 assert(namestorage != NULL || namestoragesize == 0);
959 assert(namestoragesize >= 0);
960 assert(storageleft != NULL);
961 assert(0 <= firstrow && firstrow <= lastrow && lastrow < QSget_rowcount(lpi->prob));
962
963 SCIPdebugMessage("getting row names %d to %d\n", firstrow, lastrow);
964
965 nrows = QSget_rowcount(lpi->prob);
966 SCIP_ALLOC( BMSallocMemoryArray(&rnames, nrows) );
967
968 rval = QSget_rownames(lpi->prob, rnames);
969 QS_ERROR(rval, "failed getting row names");
970
971 s = namestorage;
972 sizeleft = namestoragesize;
973 for( i = firstrow; i <= lastrow; ++i )
974 {
975 const char* t;
976
977 assert( s != NULL );
978
979 t = rnames[i];
980 if( rownames != NULL )
981 rownames[i-firstrow] = s;
982 while( *t != '\0' )
983 {
984 if( sizeleft > 0 )
985 *(s++) = *(t++);
986 --sizeleft;
987 }
988 *(s++) = '\0';
989 }
990 *storageleft = sizeleft;
991
992 /* free space */
993 for( i = 0; i < nrows; ++i )
994 free(rnames[i]);
995
996 return SCIP_OKAY;
997}
998
999/** deletes all rows in the given range from LP */
1001 SCIP_LPI* lpi, /**< LP interface structure */
1002 int firstrow, /**< first row to be deleted */
1003 int lastrow /**< last row to be deleted */
1004 )
1005{
1006 const int len = lastrow - firstrow +1;
1007 register int i;
1008
1009 assert(lpi != NULL);
1010 assert(lpi->prob != NULL);
1011
1012 lpi->solstat = 0;
1013
1014 assert(0 <= firstrow && len > 0 && lastrow < QSget_rowcount (lpi->prob));
1015
1016 SCIPdebugMessage("deleting %d rows from QSopt\n", len);
1017
1018 SCIP_CALL( ensureRowMem(lpi, len) );
1019 for( i = firstrow; i <= lastrow; i++ )
1020 lpi->ircnt[i-firstrow] = i;
1021 QS_CONDRET( QSdelete_rows(lpi->prob, len, lpi->ircnt) );
1022
1023 return SCIP_OKAY;
1024}
1025
1026
1027/** deletes rows from SCIP_LP; the new position of a row must not be greater that its old position */
1029 SCIP_LPI* lpi, /**< LP interface structure */
1030 int* dstat /**< deletion status of rows
1031 * input: 1 if row should be deleted, 0 if not
1032 * output: new position of row, -1 if row was deleted */
1033 )
1034{
1035 int nrows;
1036 int ccnt;
1037 int ndel = 0;
1038 register int i;
1039
1040 assert(lpi != NULL);
1041 assert(lpi->prob != NULL);
1042
1043 nrows = QSget_rowcount(lpi->prob);
1044 lpi->solstat = 0;
1045
1046 for( i = 0; i < nrows; ++i )
1047 {
1048 if( dstat[i] == 1 )
1049 ndel++;
1050 }
1051
1052 SCIPdebugMessage("deleting a row set from QSopt (%d)\n", ndel);
1053
1054 QS_CONDRET( QSdelete_setrows(lpi->prob,dstat) );
1055
1056 for( i=0, ccnt=0; i < nrows; i++ )
1057 {
1058 if( dstat[i] )
1059 dstat[i] = -1;
1060 else
1061 dstat[i] = ccnt++;
1062 }
1063
1064 return SCIP_OKAY;
1065}
1066
1067/** clears the whole LP */
1069 SCIP_LPI* lpi /**< LP interface structure */
1070 )
1071{
1072 char savename[1024];
1073 char* name;
1074 int objsen;
1075
1076 assert(lpi != NULL);
1077 assert(lpi->prob != NULL);
1078
1079 SCIPdebugMessage("clearing QSopt LP\n");
1080 lpi->solstat = 0;
1081
1082 /* save sense and name of problem */
1083 QS_CONDRET( QSget_objsense(lpi->prob, &objsen) );
1084
1085 name = QSget_probname(lpi->prob);
1086 (void)strncpy(savename, name, 1023);
1087 name[1023] = '\0';
1088
1089 QSfree_prob(lpi->prob);
1090 lpi->prob = QScreate_prob(savename, objsen);
1091
1092 return SCIP_OKAY;
1093}
1094
1095
1096/** changes lower and upper bounds of columns */
1098 SCIP_LPI* lpi, /**< LP interface structure */
1099 int ncols, /**< number of columns to change bounds for */
1100 const int* ind, /**< column indices or NULL if ncols is zero */
1101 const SCIP_Real* lb, /**< values for the new lower bounds or NULL if ncols is zero */
1102 const SCIP_Real* ub /**< values for the new upper bounds or NULL if ncols is zero */
1103 )
1104{
1105 register int i;
1106
1107 assert(lpi != NULL);
1108 assert(lpi->prob != NULL);
1109 assert(ncols == 0 || (ind != NULL && lb != NULL && ub != NULL));
1110 if( ncols <= 0 )
1111 return SCIP_OKAY;
1112
1113 lpi->solstat = 0;
1114
1115 SCIPdebugMessage("changing %d bounds in QSopt\n", ncols);
1116
1117 for (i = 0; i < ncols; ++i)
1118 {
1119 SCIPdebugPrintf(" col %d: [%g,%g]\n", ind[i], lb[i], ub[i]);
1120
1121 if ( SCIPlpiIsInfinity(lpi, lb[i]) )
1122 {
1123 SCIPerrorMessage("LP Error: fixing lower bound for variable %d to infinity.\n", ind[i]);
1124 return SCIP_LPERROR;
1125 }
1126 if ( SCIPlpiIsInfinity(lpi, -ub[i]) )
1127 {
1128 SCIPerrorMessage("LP Error: fixing upper bound for variable %d to -infinity.\n", ind[i]);
1129 return SCIP_LPERROR;
1130 }
1131 }
1132
1133 SCIP_CALL(ensureColMem(lpi, ncols));
1134 for( i = 0; i < ncols; ++i )
1135 lpi->iccha[i] = 'L';
1136
1137 QS_CONDRET( QSchange_bounds(lpi->prob, ncols, (int*) ind, lpi->iccha, (SCIP_Real*) lb) );
1138
1139 for( i = 0; i < ncols; ++i )
1140 lpi->iccha[i] = 'U';
1141
1142 QS_CONDRET( QSchange_bounds(lpi->prob, ncols, (int*) ind, lpi->iccha, (SCIP_Real*) ub) );
1143
1144 return SCIP_OKAY;
1145}
1146
1147/** changes left and right hand sides of rows */
1149 SCIP_LPI* lpi, /**< LP interface structure */
1150 int nrows, /**< number of rows to change sides for */
1151 const int* ind, /**< row indices */
1152 const SCIP_Real* lhs, /**< new values for left hand sides */
1153 const SCIP_Real* rhs /**< new values for right hand sides */
1154 )
1155{
1156 register int i;
1157
1158 assert(lpi != NULL);
1159 assert(lpi->prob != NULL);
1160 assert(ind != NULL);
1161 if( nrows <= 0 )
1162 return SCIP_OKAY;
1163
1164 lpi->solstat = 0;
1165
1166 SCIPdebugMessage("changing %d sides in QSopt\n", nrows);
1167
1168 SCIP_CALL( ensureRowMem(lpi, nrows) );
1169
1170 /* convert lhs/rhs into sen/rhs/range tuples */
1171 SCIP_CALL( convertSides(lpi, nrows, lhs, rhs) );
1172
1173 /* now we change all rows */
1174 for( i = 0; i < nrows; ++i )
1175 {
1176 QS_CONDRET( QSchange_sense(lpi->prob, ind[i], lpi->isen[i]) );
1177
1178 QS_CONDRET( QSchange_rhscoef(lpi->prob, ind[i], lpi->irhs[i]) );
1179
1180 if( lpi->isen[i] == 'R' )
1181 {
1182 QS_CONDRET( QSchange_range(lpi->prob, ind[i], lpi->irng[i]) );
1183 }
1184 }
1185
1186 return SCIP_OKAY;
1187}
1188
1189/** changes a single coefficient */
1191 SCIP_LPI* lpi, /**< LP interface structure */
1192 int row, /**< row number of coefficient to change */
1193 int col, /**< column number of coefficient to change */
1194 SCIP_Real newval /**< new value of coefficient */
1195 )
1196{
1197 assert(lpi != NULL);
1198 assert(lpi->prob != NULL);
1199
1200 lpi->solstat = 0;
1201
1202 SCIPdebugMessage("changing coefficient row %d, column %d in QSopt to %g\n", row, col, newval);
1203
1204 QS_CONDRET( QSchange_coef(lpi->prob, row, col, newval) );
1205
1206 return SCIP_OKAY;
1207}
1208
1209/** changes the objective sense */
1211 SCIP_LPI* lpi, /**< LP interface structure */
1212 SCIP_OBJSEN objsen /**< new objective sense */
1213 )
1214{
1215 assert(lpi != NULL);
1216 assert(lpi->prob != NULL);
1217
1218 lpi->solstat = 0;
1219 SCIPdebugMessage("changing objective sense in QSopt to %d\n", objsen);
1220
1221 /* set sense */
1222 if( objsen == SCIP_OBJSEN_MAXIMIZE )
1223 {
1224 QS_CONDRET( QSchange_objsense(lpi->prob, QS_MAX) );
1225 }
1226 else
1227 {
1228 QS_CONDRET( QSchange_objsense(lpi->prob, QS_MIN) );
1229 }
1230
1231 return SCIP_OKAY;
1232}
1233
1234/** changes objective values of columns in the LP */
1236 SCIP_LPI* lpi, /**< LP interface structure */
1237 int ncols, /**< number of columns to change objective value for */
1238 const int* ind, /**< column indices to change objective value for */
1239 const SCIP_Real* obj /**< new objective values for columns */
1240 )
1241{
1242 register int i;
1243
1244 assert(lpi != NULL);
1245 assert(lpi->prob != NULL);
1246 assert(ind != NULL);
1247 assert(obj != NULL);
1248
1249 lpi->solstat = 0;
1250
1251 SCIPdebugMessage("changing %d objective values in QSopt\n", ncols);
1252
1253 for( i = 0; i < ncols; ++i )
1254 {
1255 QS_CONDRET( QSchange_objcoef(lpi->prob, ind[i], obj[i]) );
1256 }
1257
1258 return SCIP_OKAY;
1259}
1260
1261/** multiplies a row with a non-zero scalar; for negative scalars, the row's sense is switched accordingly */
1263 SCIP_LPI* lpi, /**< LP interface structure */
1264 int row, /**< row number to scale */
1265 SCIP_Real scaleval /**< scaling multiplier */
1266 )
1267{
1268 register int i;
1269 int rowlist[1];
1270 int* rowcnt = NULL, *rowbeg = NULL, *rowind = NULL;
1271 double* rowval = NULL, *rhs = NULL, *range = NULL;
1272 char* sense = NULL;
1273 int rval;
1274
1275 assert(lpi != NULL);
1276 assert(lpi->prob != NULL);
1277
1278 lpi->solstat = 0;
1279
1280 SCIPdebugMessage("scaling row %d with factor %g in QSopt\n", row, scaleval);
1281
1282 rowlist[0] = row;
1283 /* get row */
1284 rval = QSget_ranged_rows_list(lpi->prob, 1, rowlist, &rowcnt, &rowbeg, &rowind, &rowval, &rhs, &sense, &range, 0);
1285 QS_TESTG(rval, CLEANUP, " ");
1286
1287 /* change all coefficients in the constraint */
1288 for( i = 0; i < rowcnt[0]; ++i )
1289 {
1290 rval = QSchange_coef(lpi->prob, row, rowind[i], rowval[i] * scaleval);
1291 QS_TESTG(rval, CLEANUP, " ");
1292 }
1293
1294 /* if we have a positive scalar, we just scale rhs and range */
1295 if( scaleval >= 0 )
1296 {
1297 rval = QSchange_rhscoef(lpi->prob, row, rhs[0] * scaleval);
1298 QS_TESTG(rval, CLEANUP, " ");
1299 if( sense[0] == 'R' )
1300 {
1301 rval = QSchange_range(lpi->prob, row, range[0] * scaleval);
1302 QS_TESTG(rval, CLEANUP, " ");
1303 }
1304 }
1305 /* otherwise, we must change everything */
1306 else
1307 {
1308 switch( sense[0] )
1309 {
1310 case 'E':
1311 rval = QSchange_rhscoef(lpi->prob, row, rhs[0]*scaleval);
1312 QS_TESTG(rval, CLEANUP, " ");
1313 break;
1314 case 'L':
1315 rval = QSchange_rhscoef(lpi->prob, row, rhs[0]*scaleval);
1316 QS_TESTG(rval, CLEANUP, " ");
1317 rval = QSchange_sense(lpi->prob, row, 'G');
1318 QS_TESTG(rval, CLEANUP, " ");
1319 break;
1320 case 'G':
1321 rval = QSchange_rhscoef(lpi->prob, row, rhs[0]*scaleval);
1322 QS_TESTG(rval, CLEANUP, " ");
1323 rval = QSchange_sense(lpi->prob, row, 'L');
1324 QS_TESTG(rval, CLEANUP, " ");
1325 break;
1326 case 'R':
1327 rhs[0] = (rhs[0] + range[0]) * scaleval;
1328 range[0] = fabs(scaleval) * range[0];
1329 rval = QSchange_rhscoef(lpi->prob, row, rhs[0]);
1330 QS_TESTG(rval, CLEANUP, " ");
1331 rval = QSchange_range(lpi->prob, row, range[0]);
1332 QS_TESTG(rval, CLEANUP, " ");
1333 break;
1334 default:
1335 SCIPerrorMessage("Impossible! received sense %c (not E L G R)", sense[0]);
1336 rval = 1;
1337 goto CLEANUP;
1338 }
1339 }
1340
1341 /* now we must free all received arrays */
1342 /* ending */
1343 CLEANUP:
1344 if( rowcnt != NULL )
1345 QSfree(rowcnt);
1346 if( rowbeg != NULL )
1347 QSfree(rowbeg);
1348 if( rowind != NULL )
1349 QSfree(rowind);
1350 if( rowval != NULL )
1351 QSfree(rowval);
1352 if( rhs != NULL )
1353 QSfree(rhs);
1354 if( sense != NULL )
1355 QSfree(sense);
1356 if( range != NULL )
1357 QSfree(range);
1358
1359 QS_RETURN(rval);
1360}
1361
1362/** multiplies a column with a non-zero scalar; the objective value is multiplied with the scalar, and the bounds
1363 * are divided by the scalar; for negative scalars, the column's bounds are switched
1364 */
1366 SCIP_LPI* lpi, /**< LP interface structure */
1367 int col, /**< column number to scale */
1368 SCIP_Real scaleval /**< scaling multiplier */
1369 )
1370{
1371 register int i;
1372 int collist[1];
1373 int* colcnt=0;
1374 int* colbeg=0;
1375 int* colind=0;
1376 double* colval=0;
1377 double* lb=0;
1378 double* ub=0;
1379 double* obj=0;
1380 int rval;
1381
1382 assert(lpi != NULL);
1383 assert(lpi->prob != NULL);
1384
1385 lpi->solstat = 0;
1386
1387 SCIPdebugMessage("scaling column %d with factor %g in QSopt\n", col, scaleval);
1388
1389 /* get the column */
1390 collist[0] = col;
1391 rval = QSget_columns_list(lpi->prob, 1, collist, &colcnt, &colbeg, &colind, &colval, &obj, &lb, &ub, 0);
1392 QS_TESTG(rval, CLEANUP, " ");
1393
1394 /* scale column coefficients */
1395 for( i = 0; i < colcnt[0]; ++i )
1396 {
1397 rval = QSchange_coef(lpi->prob, colind[i], col, colval[i]*scaleval);
1398 QS_TESTG(rval, CLEANUP, " ");
1399 }
1400
1401 /* scale objective value */
1402 rval = QSchange_objcoef(lpi->prob, col, obj[0]*scaleval);
1403 QS_TESTG(rval, CLEANUP, " ");
1404
1405 /* scale column bounds */
1406 if( scaleval < 0 )
1407 {
1408 scaleval = -scaleval;
1409 obj[0] = lb[0];
1410 lb[0] = -ub[0];
1411 ub[0] = -obj[0];
1412 }
1413 if( lb[0] > -QS_MAXDOUBLE )
1414 lb[0] *= scaleval;
1415 if( ub[0] < QS_MAXDOUBLE )
1416 ub[0] *= scaleval;
1417
1418 if( lb[0] < -QS_MAXDOUBLE )
1419 lb[0] = -QS_MAXDOUBLE;
1420 if( ub[0] > QS_MAXDOUBLE )
1421 ub[0] = QS_MAXDOUBLE;
1422
1423 rval = QSchange_bound(lpi->prob, col, 'L', lb[0]);
1424 QS_TESTG(rval, CLEANUP, " ");
1425 rval = QSchange_bound(lpi->prob, col, 'U', ub[0]);
1426 QS_TESTG(rval, CLEANUP, " ");
1427
1428 /* ending */
1429 CLEANUP:
1430 if( colcnt != NULL )
1431 QSfree(colcnt);
1432 if( colbeg != NULL )
1433 QSfree(colbeg);
1434 if( colind != NULL )
1435 QSfree(colind);
1436 if( colval != NULL )
1437 QSfree(colval);
1438 if( obj != NULL )
1439 QSfree(obj);
1440 if( lb != NULL )
1441 QSfree(lb);
1442 if( ub != NULL )
1443 QSfree(ub);
1444
1445 QS_RETURN(rval);
1446}
1447/**@} */
1448
1449
1450
1451
1452/*
1453 * Data Accessing Methods
1454 */
1455
1456/**@name Data Accessing Methods */
1457/**@{ */
1458
1459/** gets the number of rows in the LP */
1461 SCIP_LPI* lpi, /**< LP interface structure */
1462 int* nrows /**< pointer to store the number of rows */
1463 )
1464{
1465 assert(lpi != NULL);
1466 assert(lpi->prob != NULL);
1467 assert(nrows != NULL);
1468
1469 SCIPdebugMessage("getting number of rows\n");
1470
1471 *nrows = QSget_rowcount(lpi->prob);
1472
1473 return SCIP_OKAY;
1474}
1475
1476/** gets the number of columns in the LP */
1478 SCIP_LPI* lpi, /**< LP interface structure */
1479 int* ncols /**< pointer to store the number of cols */
1480 )
1481{
1482 assert(lpi != NULL);
1483 assert(lpi->prob != NULL);
1484 assert(ncols != NULL);
1485
1486 SCIPdebugMessage("getting number of columns\n");
1487
1488 *ncols = QSget_colcount(lpi->prob);
1489
1490 return SCIP_OKAY;
1491}
1492
1493/** gets the number of nonzero elements in the LP constraint matrix */
1495 SCIP_LPI* lpi, /**< LP interface structure */
1496 int* nnonz /**< pointer to store the number of nonzeros */
1497 )
1498{
1499 assert(lpi != NULL);
1500 assert(lpi->prob != NULL);
1501 assert(nnonz != NULL);
1502
1503 SCIPdebugMessage("getting number of columns\n");
1504
1505 *nnonz = QSget_nzcount(lpi->prob);
1506
1507 return SCIP_OKAY;
1508}
1509
1510/** gets columns from LP problem object; the arrays have to be large enough to store all values
1511 * Either both, lb and ub, have to be NULL, or both have to be non-NULL,
1512 * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
1513 */
1515 SCIP_LPI* lpi, /**< LP interface structure */
1516 int firstcol, /**< first column to get from LP */
1517 int lastcol, /**< last column to get from LP */
1518 SCIP_Real* lb, /**< buffer to store the lower bound vector, or NULL */
1519 SCIP_Real* ub, /**< buffer to store the upper bound vector, or NULL */
1520 int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
1521 int* beg, /**< buffer to store start index of each column in ind- and val-array, or NULL */
1522 int* ind, /**< buffer to store row indices of constraint matrix entries, or NULL */
1523 SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
1524 )
1525{
1526 int len;
1527 register int i;
1528 double* lval = NULL;
1529 double* llb = NULL;
1530 double* lub = NULL;
1531 int rval;
1532 int* lcnt = NULL;
1533 int* lbeg = NULL;
1534 int* lind = NULL;
1535
1536 assert(lpi != NULL);
1537 assert(lpi->prob != NULL);
1538 assert(0 <= firstcol && firstcol <= lastcol && lastcol < QSget_colcount(lpi->prob));
1539 assert((lb == NULL && ub == NULL) || (lb != NULL && ub != NULL));
1540 assert((nnonz != NULL && beg != NULL && ind != NULL && val != NULL) || (nnonz == NULL && beg == NULL && ind == NULL && val == NULL));
1541
1542 SCIPdebugMessage("getting columns %d to %d\n", firstcol, lastcol);
1543
1544 /* build col-list */
1545 len = lastcol - firstcol + 1;
1546 assert( len > 0 );
1547 SCIP_CALL( ensureColMem(lpi, len) );
1548 for( i = 0; i < len; ++i )
1549 lpi->iccnt[i] = i + firstcol;
1550
1551 /* get data from qsopt */
1552 if ( nnonz != NULL )
1553 rval = QSget_columns_list(lpi->prob, len, lpi->iccnt, &lcnt, &lbeg, &lind, &lval, NULL, lb ? (&llb) : NULL, ub ? (&lub) : NULL, NULL); /*lint !e826*/
1554 else
1555 rval = QSget_columns_list(lpi->prob, len, lpi->iccnt, NULL, NULL, NULL, NULL, NULL, lb ? (&llb) : NULL, ub ? (&lub) : NULL, NULL); /*lint !e826*/
1556
1557 QS_TESTG(rval, CLEANUP, " ");
1558
1559 /* store in the user-provided data */
1560 if( nnonz != NULL )
1561 {
1562 assert(beg != NULL && ind != NULL && val != NULL); /* for lint */
1563
1564 if( lcnt == NULL || lbeg == NULL || lind == NULL || lval == NULL )
1565 {
1566 SCIPerrorMessage("QSget_columns_list() failed to allocate memory.\n");
1567 return SCIP_LPERROR;
1568 }
1569
1570 *nnonz = lbeg[len-1] + lcnt[len-1];
1571 for( i = 0 ; i < len ; i++ )
1572 beg[i] = lbeg[i];
1573 for( i = 0; i < *nnonz; ++i )
1574 {
1575 ind[i] = lind[i];
1576 val[i] = lval[i];
1577 }
1578 }
1579
1580 if( lb != NULL )
1581 {
1582 assert( ub != NULL ); /* for lint */
1583
1584 if( llb == NULL || lub == NULL ) /*lint !e774*/
1585 {
1586 SCIPerrorMessage("QSget_columns_list() failed to allocate memory.\n");
1587 return SCIP_LPERROR;
1588 }
1589
1590 for( i = 0; i < len; ++i )
1591 {
1592 lb[i] = llb[i];
1593 ub[i] = lub[i];
1594 }
1595 }
1596
1597 CLEANUP:
1598 if( lval != NULL )
1599 QSfree(lval);
1600 if( lub != NULL ) /*lint !e831 !e774*/
1601 QSfree(lub);
1602 if( llb != NULL ) /*lint !e831 !e774*/
1603 QSfree(llb);
1604 if( lind != NULL )
1605 QSfree(lind);
1606 if( lbeg != NULL )
1607 QSfree(lbeg);
1608 if( lcnt != NULL )
1609 QSfree(lcnt);
1610
1611 QS_RETURN(rval);
1612}
1613
1614/** gets rows from LP problem object; the arrays have to be large enough to store all values.
1615 * Either both, lhs and rhs, have to be NULL, or both have to be non-NULL,
1616 * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
1617 */
1619 SCIP_LPI* lpi, /**< LP interface structure */
1620 int firstrow, /**< first row to get from LP */
1621 int lastrow, /**< last row to get from LP */
1622 SCIP_Real* lhs, /**< buffer to store left hand side vector, or NULL */
1623 SCIP_Real* rhs, /**< buffer to store right hand side vector, or NULL */
1624 int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
1625 int* beg, /**< buffer to store start index of each row in ind- and val-array, or NULL */
1626 int* ind, /**< buffer to store column indices of constraint matrix entries, or NULL */
1627 SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
1628 )
1629{
1630 const int len = lastrow - firstrow + 1;
1631 register int i;
1632 double* lval = NULL;
1633 double* lrhs = NULL;
1634 double* lrng = NULL;
1635 int rval;
1636 int* lcnt = NULL;
1637 int* lbeg = NULL;
1638 int* lind = NULL;
1639 char* lsense = NULL;
1640
1641 assert(lpi != NULL);
1642 assert(lpi->prob != NULL);
1643 assert(0 <= firstrow && firstrow <= lastrow && lastrow < QSget_rowcount (lpi->prob));
1644 assert((lhs == NULL && rhs == NULL) || (rhs != NULL && lhs != NULL));
1645 assert((nnonz != NULL && beg != NULL && ind != NULL && val != NULL) || (nnonz == NULL && beg == NULL && ind == NULL && val == NULL));
1646
1647 SCIPdebugMessage("getting rows %d to %d\n", firstrow, lastrow);
1648
1649 /* build row-list */
1650 SCIP_CALL( ensureRowMem(lpi, len) );
1651 for( i = 0; i < len; ++i )
1652 lpi->ircnt[i] = i + firstrow;
1653
1654 /* get data from qsopt */
1655 if ( nnonz != NULL )
1656 rval = QSget_ranged_rows_list(lpi->prob, len, lpi->ircnt, &lcnt, &lbeg, &lind, &lval, rhs ? (&lrhs) : NULL, rhs ? (&lsense) : NULL, rhs ? (&lrng) : NULL, NULL); /*lint !e826*/
1657 else
1658 rval = QSget_ranged_rows_list(lpi->prob, len, lpi->ircnt, NULL, NULL, NULL, NULL, rhs ? (&lrhs) : NULL, rhs ? (&lsense) : NULL, rhs ? (&lrng) : NULL, NULL); /*lint !e826*/
1659
1660 QS_TESTG(rval, CLEANUP, " ");
1661
1662 /* store in the user-provided data */
1663 if( nnonz != NULL )
1664 {
1665 assert( beg != NULL && ind != NULL && val != NULL ); /* for lint */
1666
1667 if( lcnt == NULL || lbeg == NULL || lind == NULL || lval == NULL )
1668 {
1669 SCIPerrorMessage("QSget_ranged_rows_list() failed to allocate memory.\n");
1670 return SCIP_LPERROR;
1671 }
1672
1673 *nnonz = lbeg[len-1] + lcnt[len-1];
1674 for( i = 0 ; i < len; i++ )
1675 beg[i] = lbeg[i];
1676 for( i = 0; i < *nnonz; ++i )
1677 {
1678 ind[i] = lind[i];
1679 val[i] = lval[i];
1680 }
1681 }
1682
1683 if( rhs != NULL )
1684 {
1685 if( lrhs == NULL || lrng == NULL || lsense == NULL ) /*lint !e774*/
1686 {
1687 SCIPerrorMessage("QSget_ranged_rows_list() failed to allocate memory.\n");
1688 return SCIP_LPERROR;
1689 }
1690
1691 assert( lhs != NULL ); /* for lint */
1692
1693 for( i = 0; i < len; ++i )
1694 {
1695 switch( lsense[i] )
1696 {
1697 case 'R':
1698 lhs[i] = lrhs[i];
1699 rhs[i] = lrhs[i] + lrng[i];
1700 break;
1701 case 'E':
1702 lhs[i] = lrhs[i];
1703 rhs[i] = lrhs[i];
1704 break;
1705 case 'L':
1706 rhs[i] = lrhs[i];
1707 lhs[i] = -QS_MAXDOUBLE;
1708 break;
1709 case 'G':
1710 lhs[i] = lrhs[i];
1711 rhs[i] = QS_MAXDOUBLE;
1712 break;
1713 default:
1714 SCIPerrorMessage("Unknown sense %c from QSopt", lsense[i]);
1715 SCIPABORT();
1716 return SCIP_INVALIDDATA; /*lint !e527*/
1717 }
1718 }
1719 }
1720
1721 CLEANUP:
1722 if( lsense != NULL ) /*lint !e774*/
1723 QSfree(lsense);
1724 if( lrng != NULL ) /*lint !e774*/
1725 QSfree(lrng);
1726 if( lrhs != NULL ) /*lint !e774*/
1727 QSfree(lrhs);
1728 if( lval != NULL )
1729 QSfree(lval);
1730 if( lind != NULL )
1731 QSfree(lind);
1732 if( lbeg != NULL )
1733 QSfree(lbeg);
1734 if( lcnt != NULL )
1735 QSfree(lcnt);
1736
1737 QS_RETURN(rval);
1738}
1739
1740/** gets the objective sense of the LP */
1742 SCIP_LPI* lpi, /**< LP interface structure */
1743 SCIP_OBJSEN* objsen /**< pointer to store objective sense */
1744 )
1745{
1746 int sense;
1747
1748 assert(lpi != NULL);
1749 assert(lpi->prob != NULL);
1750 assert( objsen != NULL );
1751
1752 QS_CONDRET( QSget_objsense(lpi->prob, &sense) );
1753 if ( sense == QS_MIN )
1754 *objsen = SCIP_OBJSEN_MINIMIZE;
1755 else
1756 *objsen = SCIP_OBJSEN_MAXIMIZE;
1757
1758 return SCIP_OKAY;
1759}
1760
1761/** gets objective coefficients from LP problem object */
1763 SCIP_LPI* lpi, /**< LP interface structure */
1764 int firstcol, /**< first column to get objective coefficient for */
1765 int lastcol, /**< last column to get objective coefficient for */
1766 SCIP_Real* vals /**< array to store objective coefficients */
1767 )
1768{ /*lint --e{715}*/
1769 int len;
1770 register int i;
1771 double* qsoptvals;
1772
1773 assert(lpi != NULL);
1774 assert(lpi->prob != NULL);
1775 assert(vals != NULL);
1776 assert(0 <= firstcol && firstcol <= lastcol && lastcol < QSget_colcount (lpi->prob));
1777
1778 SCIPdebugMessage("getting objective values %d to %d\n", firstcol, lastcol);
1779
1780 /* build col-list */
1781 len = lastcol - firstcol + 1;
1782 SCIP_CALL(ensureColMem(lpi,len));
1783 for( i = 0; i < len; ++i )
1784 lpi->iccnt[i] = i + firstcol;
1785
1786 /* get data from qsopt */
1787
1788 /* There seems to be a bug in qsopt: The function QSget_obj_list might return values for slack variables. We
1789 * therefore have to use a workarround. */
1790#ifdef SCIP_DISABLED_CODE
1791 QS_CONDRET( QSget_obj_list(lpi->prob, len, lpi->iccnt, vals) );
1792#endif
1793
1794 QS_CONDRET( QSget_columns_list(lpi->prob, len, lpi->iccnt, NULL, NULL, NULL, NULL, &qsoptvals, NULL, NULL, NULL) );
1795 for (i = 0; i < len; ++i)
1796 vals[i] = qsoptvals[i];
1797 free( qsoptvals );
1798
1799 return SCIP_OKAY;
1800}
1801
1802/** gets current bounds from LP problem object */
1804 SCIP_LPI* lpi, /**< LP interface structure */
1805 int firstcol, /**< first column to get objective value for */
1806 int lastcol, /**< last column to get objective value for */
1807 SCIP_Real* lbs, /**< array to store lower bound values, or NULL */
1808 SCIP_Real* ubs /**< array to store upper bound values, or NULL */
1809 )
1810{
1811 const int len = lastcol - firstcol + 1;
1812 register int i;
1813
1814 assert(lpi != NULL);
1815 assert(lpi->prob != NULL);
1816 assert(0 <= firstcol && firstcol <= lastcol&& lastcol < QSget_colcount (lpi->prob));
1817
1818 SCIPdebugMessage("getting bound values %d to %d\n", firstcol, lastcol);
1819
1820 /* build col-list */
1821 SCIP_CALL(ensureColMem(lpi,len));
1822 for( i = 0; i < len; ++i )
1823 lpi->iccnt[i] = i + firstcol;
1824
1825 /* get data from qsopt */
1826 QS_CONDRET( QSget_bounds_list(lpi->prob, len, lpi->iccnt, lbs, ubs) );
1827
1828 return SCIP_OKAY;
1829}
1830
1831/** gets current row sides from LP problem object */
1833 SCIP_LPI* lpi, /**< LP interface structure */
1834 int firstrow, /**< first row to get sides for */
1835 int lastrow, /**< last row to get sides for */
1836 SCIP_Real* lhss, /**< array to store left hand side values, or NULL */
1837 SCIP_Real* rhss /**< array to store right hand side values, or NULL */
1838 )
1839{
1840 const int len = lastrow - firstrow + 1;
1841 register int i;
1842 double* lrhs=0, *lrng=0;
1843 int rval;
1844 char* lsense=0;
1845
1846 assert(lpi != NULL);
1847 assert(lpi->prob != NULL);
1848 assert(0 <= firstrow && firstrow <= lastrow && lastrow < QSget_rowcount (lpi->prob));
1849 assert(rhss != NULL);
1850 assert(lhss != NULL);
1851
1852 SCIPdebugMessage("getting row sides %d to %d\n", firstrow, lastrow);
1853
1854 /* build row-list */
1855 SCIP_CALL( ensureRowMem(lpi, len) );
1856 for( i = 0; i < len; ++i )
1857 lpi->ircnt[i] = i + firstrow;
1858
1859 /* get data from qsopt */
1860 rval = QSget_ranged_rows_list(lpi->prob, len, lpi->ircnt, 0, 0, 0, 0, &lrhs, &lsense, &lrng, 0);
1861 QS_TESTG(rval, CLEANUP, " ");
1862
1863 /* store in the user-provided data */
1864 for( i = 0; i < len; ++i )
1865 {
1866 switch( lsense[i] )
1867 {
1868 case 'R':
1869 lhss[i] = lrhs[i];
1870 rhss[i] = lrhs[i] + lrng[i];
1871 break;
1872 case 'E':
1873 lhss[i] = rhss[i] = lrhs[i];
1874 break;
1875 case 'L':
1876 rhss[i] = lrhs[i];
1877 lhss[i] = -QS_MAXDOUBLE;
1878 break;
1879 case 'G':
1880 lhss[i] = lrhs[i];
1881 rhss[i] = QS_MAXDOUBLE;
1882 break;
1883 default:
1884 SCIPerrorMessage("Unknown sense %c from QSopt", lsense[i]);
1885 SCIPABORT();
1886 return SCIP_INVALIDDATA; /*lint !e527*/
1887 }
1888 }
1889
1890 CLEANUP:
1891 if( lsense != NULL )
1892 QSfree(lsense);
1893 if( lrng != NULL )
1894 QSfree(lrng);
1895 if( lrhs != NULL )
1896 QSfree(lrhs);
1897
1898 QS_RETURN(rval);
1899}
1900
1901/** gets a single coefficient */
1903 SCIP_LPI* lpi, /**< LP interface structure */
1904 int row, /**< row number of coefficient */
1905 int col, /**< column number of coefficient */
1906 SCIP_Real* val /**< pointer to store the value of the coefficient */
1907 )
1908{
1909 assert(lpi != NULL);
1910 assert(lpi->prob != NULL);
1911 assert(val != NULL);
1912
1913 SCIPdebugMessage("getting coefficient of row %d col %d\n", row, col);
1914
1915 QS_CONDRET( QSget_coef(lpi->prob, row, col, val) );
1916
1917 return SCIP_OKAY;
1918}
1919
1920/**@} */
1921
1922
1923
1924
1925/*
1926 * Solving Methods
1927 */
1928
1929/**@name Solving Methods */
1930/**@{ */
1931
1932/** calls primal simplex to solve the LP */
1934 SCIP_LPI* lpi /**< LP interface structure */
1935 )
1936{
1937 assert(lpi != NULL);
1938 assert(lpi->prob != NULL);
1939
1940 SCIPdebugMessage("calling QSopt primal simplex: %d cols, %d rows, %d nz\n", QSget_colcount(lpi->prob),
1941 QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob));
1942
1943 QS_CONDRET( QSopt_primal(lpi->prob, &(lpi->solstat)) );
1945
1946 return SCIP_OKAY;
1947}
1948
1949/** calls dual simplex to solve the LP */
1951 SCIP_LPI* lpi /**< LP interface structure */
1952 )
1953{
1954 assert(lpi != NULL);
1955 assert(lpi->prob != NULL);
1956
1957 SCIPdebugMessage("calling QSopt dual simplex: %d cols, %d rows, %d nz\n", QSget_colcount(lpi->prob),
1958 QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob));
1959
1960 QS_CONDRET( QSopt_dual(lpi->prob, &(lpi->solstat)) );
1962
1963 return SCIP_OKAY;
1964}
1965
1966/** calls barrier or interior point algorithm to solve the LP with crossover to simplex basis */
1968 SCIP_LPI* lpi, /**< LP interface structure */
1969 SCIP_Bool crossover /**< perform crossover */
1970 )
1971{ /*lint --e{715}*/
1972 assert(lpi != NULL);
1973 assert(lpi->prob != NULL);
1974 SCIP_UNUSED( crossover );
1975
1976 return SCIPlpiSolveDual(lpi);
1977}
1978
1979/** start strong branching - call before any strong branching */
1981 SCIP_LPI* lpi /**< LP interface structure */
1982 )
1983{ /*lint --e{715}*/
1984 assert(lpi != NULL);
1985 assert(lpi->prob != NULL);
1986
1987 /* currently do nothing */
1988 return SCIP_OKAY;
1989}
1990
1991/** end strong branching - call after any strong branching */
1993 SCIP_LPI* lpi /**< LP interface structure */
1994 )
1995{ /*lint --e{715}*/
1996 assert(lpi != NULL);
1997 assert(lpi->prob != NULL);
1998
1999 /* currently do nothing */
2000 return SCIP_OKAY;
2001}
2002
2003/** performs strong branching iterations on one @b fractional candidate */
2005 SCIP_LPI* lpi, /**< LP interface structure */
2006 int col, /**< column to apply strong branching on */
2007 SCIP_Real psol, /**< fractional current primal solution value of column */
2008 int itlim, /**< iteration limit for strong branchings */
2009 SCIP_Real* down, /**< stores dual bound after branching column down */
2010 SCIP_Real* up, /**< stores dual bound after branching column up */
2011 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
2012 * otherwise, it can only be used as an estimate value */
2013 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
2014 * otherwise, it can only be used as an estimate value */
2015 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2016 )
2017{
2018 int nit;
2019
2020 assert(lpi != NULL);
2021 assert(lpi->prob != NULL);
2022 assert(down != NULL);
2023 assert(up != NULL);
2024 assert(downvalid != NULL);
2025 assert(upvalid != NULL);
2026
2027 SCIPdebugMessage("calling QSopt strong branching on variable %d with fractional value (%d it lim)\n", col, itlim);
2028
2029 /* results of QSopt are valid in any case */
2030 *downvalid = TRUE;
2031 *upvalid = TRUE;
2032
2033 assert( ! EPSISINT(psol, FEASTOL) );
2034
2035 /* call QSopt */
2036 QS_CONDRET( QSopt_strongbranch(lpi->prob, 1, &col, &psol, down, up, itlim, QS_MAXDOUBLE) );
2037
2038 QS_CONDRET( QSget_itcnt(lpi->prob, 0, 0, 0, 0, &nit) );
2039
2040 if( iter )
2041 *iter = nit - lpi->previt;
2042 lpi->previt = nit;
2043
2044 return SCIP_OKAY;
2045}
2046
2047/** performs strong branching iterations on given @b fractional candidates */
2049 SCIP_LPI* lpi, /**< LP interface structure */
2050 int* cols, /**< columns to apply strong branching on */
2051 int ncols, /**< number of columns */
2052 SCIP_Real* psols, /**< fractional current primal solution values of columns */
2053 int itlim, /**< iteration limit for strong branchings */
2054 SCIP_Real* down, /**< stores dual bounds after branching columns down */
2055 SCIP_Real* up, /**< stores dual bounds after branching columns up */
2056 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
2057 * otherwise, they can only be used as an estimate values */
2058 SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
2059 * otherwise, they can only be used as an estimate values */
2060 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2061 )
2062{
2063 int nit;
2064 int j;
2065
2066 assert(lpi != NULL);
2067 assert(lpi->prob != NULL);
2068 assert(cols != NULL);
2069 assert(psols != NULL);
2070 assert(down != NULL);
2071 assert(up != NULL);
2072 assert(downvalid != NULL);
2073 assert(upvalid != NULL);
2074
2075 SCIPdebugMessage("calling QSopt strong branching on %d variables with fractional value (%d it lim)\n", ncols, itlim);
2076
2077 /* results of QSopt are valid in any case */
2078 for( j = 0; j < ncols; ++j )
2079 {
2080 downvalid[j] = TRUE;
2081 upvalid[j] = TRUE;
2082 assert( ! EPSISINT(psols[j], FEASTOL) );
2083 }
2084
2085 /* call QSopt */
2086 QS_CONDRET( QSopt_strongbranch(lpi->prob, ncols, cols, psols, down, up, itlim, QS_MAXDOUBLE) );
2087
2088 QS_CONDRET( QSget_itcnt(lpi->prob, 0, 0, 0, 0, &nit) );
2089
2090 if( iter )
2091 *iter = nit - lpi->previt;
2092 lpi->previt = nit;
2093
2094 return SCIP_OKAY;
2095}
2096
2097/** performs strong branching iterations on one candidate with @b integral value */
2099 SCIP_LPI* lpi, /**< LP interface structure */
2100 int col, /**< column to apply strong branching on */
2101 SCIP_Real psol, /**< current integral primal solution value of column */
2102 int itlim, /**< iteration limit for strong branchings */
2103 SCIP_Real* down, /**< stores dual bound after branching column down */
2104 SCIP_Real* up, /**< stores dual bound after branching column up */
2105 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
2106 * otherwise, it can only be used as an estimate value */
2107 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
2108 * otherwise, it can only be used as an estimate value */
2109 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2110 )
2111{
2112 SCIP_Real objval;
2113
2114 assert(lpi != NULL);
2115 assert(lpi->prob != NULL);
2116 assert(down != NULL);
2117 assert(up != NULL);
2118 assert(downvalid != NULL);
2119 assert(upvalid != NULL);
2120
2121 SCIPdebugMessage("calling QSopt strong branching on variable %d with integral value (%d it lim)\n", col, itlim);
2122
2123 assert(EPSISINT(psol, FEASTOL));
2124
2125 /* QSopt cannot directly strong branch on integral values! We thus return the current objective
2126 * value for both cases. Could also implement a manual search as in lpi_cpx.c
2127 */
2128 QS_CONDRET( QSget_objval(lpi->prob, &objval) );
2129
2130 *down = objval;
2131 *up = objval;
2132 *downvalid = TRUE;
2133 *upvalid = TRUE;
2134
2135 if( iter )
2136 *iter = 0;
2137
2138 return SCIP_OKAY;
2139}
2140
2141/** performs strong branching iterations on given candidates with @b integral values */
2143 SCIP_LPI* lpi, /**< LP interface structure */
2144 int* cols, /**< columns to apply strong branching on */
2145 int ncols, /**< number of columns */
2146 SCIP_Real* psols, /**< current integral primal solution values of columns */
2147 int itlim, /**< iteration limit for strong branchings */
2148 SCIP_Real* down, /**< stores dual bounds after branching columns down */
2149 SCIP_Real* up, /**< stores dual bounds after branching columns up */
2150 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
2151 * otherwise, they can only be used as an estimate values */
2152 SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
2153 * otherwise, they can only be used as an estimate values */
2154 int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2155 )
2156{ /*lint --e{715}*/
2157 SCIP_Real objval;
2158 int j;
2159
2160 assert(lpi != NULL);
2161 assert(lpi->prob != NULL);
2162 assert(down != NULL);
2163 assert(up != NULL);
2164 assert(downvalid != NULL);
2165 assert(upvalid != NULL);
2166 SCIP_UNUSED( cols );
2167
2168 SCIPdebugMessage("calling QSopt strong branching on %d variables with integral value (%d it lim)\n", ncols, itlim);
2169
2170 /* QSopt cannot directly strong branch on integral values! We thus return the current objective
2171 * value for all cases. Could also implement a manual search as in lpi_cpx.c. */
2172 QS_CONDRET( QSget_objval(lpi->prob, &objval) );
2173
2174 for( j = 0; j < ncols; ++j )
2175 {
2176 assert(EPSISINT(psols[j], FEASTOL));
2177 down[j] = objval;
2178 up[j] = objval;
2179 downvalid[j] = TRUE;
2180 upvalid[j] = TRUE;
2181 }
2182
2183 if( iter )
2184 *iter = 0;
2185
2186 return SCIP_OKAY;
2187}
2188/**@} */
2189
2190
2191
2192
2193/*
2194 * Solution Information Methods
2195 */
2196
2197/**@name Solution Information Methods */
2198/**@{ */
2199
2200/** returns whether a solve method was called after the last modification of the LP */
2202 SCIP_LPI* lpi /**< LP interface structure */
2203 )
2204{
2205 assert(lpi!=NULL);
2206 assert(lpi->prob!=NULL);
2207
2208 return (lpi->solstat != 0 && lpi->solstat != QS_LP_MODIFIED);
2209}
2210
2211/** gets information about primal and dual feasibility of the current LP solution
2212 *
2213 * The feasibility information is with respect to the last solving call and it is only relevant if SCIPlpiWasSolved()
2214 * returns true. If the LP is changed, this information might be invalidated.
2215 *
2216 * Note that @a primalfeasible and @a dualfeasible should only return true if the solver has proved the respective LP to
2217 * be feasible. Thus, the return values should be equal to the values of SCIPlpiIsPrimalFeasible() and
2218 * SCIPlpiIsDualFeasible(), respectively. Note that if feasibility cannot be proved, they should return false (even if
2219 * the problem might actually be feasible).
2220 */
2222 SCIP_LPI* lpi, /**< LP interface structure */
2223 SCIP_Bool* primalfeasible, /**< pointer to store primal feasibility status */
2224 SCIP_Bool* dualfeasible /**< pointer to store dual feasibility status */
2225 )
2226{
2227 assert(lpi != NULL);
2228 assert(lpi->prob != NULL);
2229 assert(lpi->solstat != 0);
2230 assert(primalfeasible != NULL);
2231 assert(dualfeasible != NULL);
2232
2233 SCIPdebugMessage("getting solution feasibility\n");
2234
2235 if( lpi->solstat == QS_LP_OPTIMAL || (lpi->algo == LPI_QSOPT_ALGO_PRIMAL && lpi->solstat == QS_LP_UNBOUNDED) )
2236 *primalfeasible = TRUE;
2237 else
2238 *primalfeasible = FALSE;
2239
2240 if( lpi->solstat == QS_LP_OPTIMAL || (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE) || lpi->solstat == QS_LP_OBJ_LIMIT )
2241 *dualfeasible = TRUE;
2242 else
2243 *dualfeasible = FALSE;
2244
2245 return SCIP_OKAY;
2246}
2247
2248/** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point);
2249 * this does not necessarily mean, that the solver knows and can return the primal ray
2250 */
2252 SCIP_LPI* lpi /**< LP interface structure */
2253 )
2254{
2255 assert(lpi != NULL);
2256 assert(lpi->prob != NULL);
2257
2258 SCIPdebugMessage("checking primal ray existence\n");
2259
2260 return (lpi->solstat == QS_LP_UNBOUNDED);
2261}
2262
2263/** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point),
2264 * and the solver knows and can return the primal ray
2265 */
2267 SCIP_LPI* lpi /**< LP interface structure */
2268 )
2269{
2270 assert(lpi != NULL);
2271 assert(lpi->prob != NULL);
2272
2273 SCIPdebugMessage("checking for primal ray\n");
2274
2275 /* the current version of QSopt cannot give a primal certificate of unboundedness */
2276 return FALSE;
2277}
2278
2279/** returns TRUE iff LP is proven to be primal unbounded */
2281 SCIP_LPI* lpi /**< LP interface structure */
2282 )
2283{
2284 assert(lpi != NULL);
2285 assert(lpi->prob != NULL);
2286
2287 SCIPdebugMessage("checking for primal unboundedness\n");
2288
2289 return (lpi->algo == LPI_QSOPT_ALGO_PRIMAL && lpi->solstat == QS_LP_UNBOUNDED);
2290}
2291
2292/** returns TRUE iff LP is proven to be primal infeasible */
2294 SCIP_LPI* lpi /**< LP interface structure */
2295 )
2296{
2297 assert(lpi != NULL);
2298 assert(lpi->prob != NULL);
2299
2300 SCIPdebugMessage("checking for primal infeasibility\n");
2301
2302 (void) QSget_status(lpi->prob, &(lpi->solstat));
2303
2304 return (lpi->solstat == QS_LP_INFEASIBLE);
2305}
2306
2307/** returns TRUE iff LP is proven to be primal feasible */
2309 SCIP_LPI* lpi /**< LP interface structure */
2310 )
2311{
2312 assert(lpi != NULL);
2313 assert(lpi->prob != NULL);
2314
2315 SCIPdebugMessage("checking for primal feasibility\n");
2316
2317 return (lpi->solstat == QS_LP_OPTIMAL || lpi->solstat == QS_LP_UNBOUNDED);
2318}
2319
2320/** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point);
2321 * this does not necessarily mean, that the solver knows and can return the dual ray
2322 */
2324 SCIP_LPI* lpi /**< LP interface structure */
2325 )
2326{
2327 assert(lpi != NULL);
2328 assert(lpi->prob != NULL);
2329
2330 SCIPdebugMessage("checking for dual ray availability\n");
2331
2332 return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE);
2333}
2334
2335/** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point),
2336 * and the solver knows and can return the dual ray
2337 */
2339 SCIP_LPI* lpi /**< LP interface structure */
2340 )
2341{
2342 assert(lpi != NULL);
2343 assert(lpi->prob != NULL);
2344
2345 SCIPdebugMessage("checking for dual ray availability\n");
2346
2347 return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE);
2348}
2349
2350/** returns TRUE iff LP is dual unbounded */
2352 SCIP_LPI* lpi /**< LP interface structure */
2353 )
2354{
2355 assert(lpi != NULL);
2356 assert(lpi->prob != NULL);
2357
2358 SCIPdebugMessage("checking for dual unboundedness\n");
2359
2360 return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE);
2361}
2362
2363/** returns TRUE iff LP is dual infeasible */
2365 SCIP_LPI* lpi /**< LP interface structure */
2366 )
2367{
2368 assert(lpi != NULL);
2369 assert(lpi->prob != NULL);
2370
2371 SCIPdebugMessage("checking for dual infeasibility\n");
2372
2373 return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE);
2374}
2375
2376/** returns TRUE iff LP is proven to be dual feasible */
2378 SCIP_LPI* lpi /**< LP interface structure */
2379 )
2380{
2381 assert(lpi != NULL);
2382 assert(lpi->prob != NULL);
2383
2384 SCIPdebugMessage("checking for dual feasibility\n");
2385
2386 return ( lpi->solstat == QS_LP_OPTIMAL || (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE) || lpi->solstat == QS_LP_OBJ_LIMIT );
2387}
2388
2389/** returns TRUE iff LP was solved to optimality */
2391 SCIP_LPI* lpi /**< LP interface structure */
2392 )
2393{
2394 assert(lpi != NULL);
2395 assert(lpi->prob != NULL);
2396
2397 SCIPdebugMessage("checking for optimality\n");
2398
2399 return (lpi->solstat == QS_LP_OPTIMAL);
2400}
2401
2402/** returns TRUE iff current LP solution is stable
2403 *
2404 * This function should return true if the solution is reliable, i.e., feasible and optimal (or proven
2405 * infeasible/unbounded) with respect to the original problem. The optimality status might be with respect to a scaled
2406 * version of the problem, but the solution might not be feasible to the unscaled original problem; in this case,
2407 * SCIPlpiIsStable() should return false.
2408 */
2410 SCIP_LPI* lpi /**< LP interface structure */
2411 )
2412{
2413 assert(lpi != NULL);
2414 assert(lpi->prob != NULL);
2415
2416 SCIPdebugMessage("checking for numerical stability\n");
2417
2418 return (lpi->solstat != QS_LP_NUMERR);
2419}
2420
2421/** returns TRUE iff the objective limit was reached */
2423 SCIP_LPI* lpi /**< LP interface structure */
2424 )
2425{
2426 assert(lpi != NULL);
2427 assert(lpi->prob != NULL);
2428
2429 SCIPdebugMessage("checking for objective limit exceeded\n");
2430
2431 return (lpi->solstat == QS_LP_OBJ_LIMIT);
2432}
2433
2434/** returns TRUE iff the iteration limit was reached */
2436 SCIP_LPI* lpi /**< LP interface structure */
2437 )
2438{
2439 assert(lpi != NULL);
2440 assert(lpi->prob != NULL);
2441
2442 SCIPdebugMessage("checking for iteration limit exceeded\n");
2443
2444 return (lpi->solstat == QS_LP_ITER_LIMIT);
2445}
2446
2447/** returns TRUE iff the time limit was reached */
2449 SCIP_LPI* lpi /**< LP interface structure */
2450 )
2451{
2452 assert(lpi != NULL);
2453 assert(lpi->prob != NULL);
2454
2455 SCIPdebugMessage("checking for time limit exceeded\n");
2456
2457 return (lpi->solstat == QS_LP_TIME_LIMIT);
2458}
2459
2460/** returns the internal solution status of the solver */
2462 SCIP_LPI* lpi /**< LP interface structure */
2463 )
2464{
2465 assert(lpi != NULL);
2466 assert(lpi->prob != NULL);
2467
2468 SCIPdebugMessage("getting internal solution status\n");
2469
2470 return lpi->solstat;
2471}
2472
2473/** tries to reset the internal status of the LP solver in order to ignore an instability of the last solving call */
2475 SCIP_LPI* lpi, /**< LP interface structure */
2476 SCIP_Bool* success /**< pointer to store, whether the instability could be ignored */
2477 )
2478{
2479 assert(lpi != NULL);
2480 assert(lpi->prob != NULL);
2481 assert(success != NULL);
2482
2483 SCIPdebugMessage("ignore instability (will fail)\n");
2484
2485 /* it seems that in QSopt this does not make much sense */
2486 *success = FALSE;
2487
2488 return SCIP_OKAY;
2489}
2490
2491/** gets objective value of solution */
2493 SCIP_LPI* lpi, /**< LP interface structure */
2494 SCIP_Real* objval /**< stores the objective value */
2495 )
2496{
2497 assert(lpi != NULL);
2498 assert(lpi->prob != NULL);
2499 assert(objval != NULL);
2500
2501 SCIPdebugMessage("getting solution's objective value\n");
2502
2503 QS_CONDRET( QSget_objval(lpi->prob, objval) );
2504
2505 return SCIP_OKAY;
2506}
2507
2508/** gets primal and dual solution vectors for feasible LPs
2509 *
2510 * Before calling this function, the caller must ensure that the LP has been solved to optimality, i.e., that
2511 * SCIPlpiIsOptimal() returns true.
2512 */
2514 SCIP_LPI* lpi, /**< LP interface structure */
2515 SCIP_Real* objval, /**< stores the objective value, may be NULL if not needed */
2516 SCIP_Real* primsol, /**< primal solution vector, may be NULL if not needed */
2517 SCIP_Real* dualsol, /**< dual solution vector, may be NULL if not needed */
2518 SCIP_Real* activity, /**< row activity vector, may be NULL if not needed */
2519 SCIP_Real* redcost /**< reduced cost vector, may be NULL if not needed */
2520 )
2521{
2522 int nrows;
2523 register int i;
2524
2525 assert(lpi != NULL);
2526 assert(lpi->prob != NULL);
2527
2528 SCIPdebugMessage("getting solution\n");
2529
2530 /* Do nothing if the status is not optimal, e.g., if we reached the objective limit or the problem is
2531 * infeasible. QSopt cannot return a solution in this case.*/
2532 if ( lpi->solstat != QS_LP_OPTIMAL )
2533 return SCIP_OKAY;
2534
2535 nrows = QSget_rowcount(lpi->prob);
2536 SCIP_CALL( ensureRowMem(lpi, nrows) );
2537
2538 QS_CONDRET( QSget_solution(lpi->prob, objval, primsol, dualsol, lpi->irng, redcost) );
2539
2540 /* build back the activity */
2541 if( activity )
2542 {
2543 QS_CONDRET( QSget_rhs(lpi->prob, lpi->irhs) );
2544 QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) );
2545
2546 for( i = 0; i < nrows; ++i )
2547 {
2548 switch( lpi->isen[i] )
2549 {
2550 case 'R':
2551 case 'E':
2552 case 'G':
2553 activity[i] = lpi->irhs[i] + lpi->irng[i];
2554 break;
2555 case 'L':
2556 activity[i] = lpi->irhs[i] - lpi->irng[i];
2557 break;
2558 default:
2559 SCIPerrorMessage("unknown sense %c\n", lpi->isen[i]);
2560 SCIPABORT();
2561 return SCIP_INVALIDDATA; /*lint !e527*/
2562 }
2563 }
2564 }
2565
2566#ifdef SCIP_DISABLED_CODE
2567 {
2568 int stat;
2569 int ncols;
2570 int sense;
2571 char* icstat;
2572 char* irstat;
2573
2574 QSget_status(lpi->prob, &stat);
2575 if( stat == QS_LP_OPTIMAL )
2576 {
2577 QS_CONDRET( QSget_objsense(lpi->prob, &sense) );
2578 ncols = QSget_colcount(lpi->prob);
2579
2580 SCIP_CALL(ensureTabMem(lpi, nrows + ncols));
2581 icstat = lpi->ibas;
2582 irstat = lpi->ibas + ncols;
2583
2584 QS_CONDRET( QSget_basis_array(lpi->prob,icstat, irstat) );
2585
2586 for( i = ncols ; i-- ; )
2587 {
2588 switch( icstat[i] )
2589 {
2590 case QS_COL_BSTAT_BASIC:
2591 case QS_COL_BSTAT_FREE:
2592 if( fabs(redcost[i])> FEASTOL )
2593 {
2594 SCIPerrorMessage("stat col[%d] = %c, rd[%d] = %lg sense %d\n", i, icstat[i], i, redcost[i] * sense, sense);
2595 SCIPABORT();
2596 return SCIP_INVALIDDATA; /*lint !e527*/
2597 }
2598 break;
2599 case QS_COL_BSTAT_UPPER:
2600 if( redcost[i] * sense > FEASTOL )
2601 {
2602 SCIPerrorMessage("stat col[%d] = %c, rd[%d] = %lg sense %d\n", i, icstat[i], i, redcost[i] * sense, sense);
2603 SCIPABORT();
2604 return SCIP_INVALIDDATA; /*lint !e527*/
2605 }
2606 break;
2607 case QS_COL_BSTAT_LOWER:
2608 if( redcost[i] * sense < -FEASTOL )
2609 {
2610 SCIPerrorMessage("stat col[%d] = %c, rd[%d] = %lg sense %d\n", i, icstat[i], i, redcost[i] * sense, sense);
2611 SCIPABORT();
2612 return SCIP_INVALIDDATA; /*lint !e527*/
2613 }
2614 break;
2615 default:
2616 SCIPerrorMessage("unknown stat col[%d] = %c, rd[%d] = %lg\n", i, icstat[i], i, redcost[i] * sense);
2617 SCIPABORT();
2618 return SCIP_INVALIDDATA; /*lint !e527*/
2619 }
2620 }
2621 }
2622 }
2623#endif
2624
2625 return SCIP_OKAY;
2626}
2627
2628/** gets primal ray for unbounded LPs */
2630 SCIP_LPI* lpi, /**< LP interface structure */
2631 SCIP_Real* ray /**< primal ray */
2632 )
2633{ /*lint --e{715}*/
2634 assert(lpi != NULL);
2635 assert(lpi->prob != NULL);
2636 assert(ray != NULL);
2637
2638 SCIPerrorMessage("SCIPlpiGetPrimalRay() not supported by QSopt.\n");
2639
2640 return SCIP_LPERROR;
2641}
2642
2643/** gets dual Farkas proof for infeasibility */
2645 SCIP_LPI* lpi, /**< LP interface structure */
2646 SCIP_Real* dualfarkas /**< dual Farkas row multipliers */
2647 )
2648{
2649 assert(lpi != NULL);
2650 assert(lpi->prob != NULL);
2651 assert(dualfarkas != NULL);
2652
2653 SCIPdebugMessage("calling QSopt dual Farkas: %d cols, %d rows, %d non zeros\n", QSget_colcount (lpi->prob),
2654 QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob));
2655
2656 QS_CONDRET( QSget_infeas_array(lpi->prob, dualfarkas) );
2657
2658 return SCIP_OKAY;
2659}
2660
2661/** gets the number of LP iterations of the last solve call */
2663 SCIP_LPI* lpi, /**< LP interface structure */
2664 int* iterations /**< pointer to store the number of iterations of the last solve call */
2665 )
2666{
2667 int nit;
2668
2669 assert(lpi != NULL);
2670 assert(lpi->prob != NULL);
2671 assert(iterations != NULL);
2672
2673 QS_CONDRET( QSget_itcnt(lpi->prob, 0, 0, 0, 0, &nit) );
2674
2675 *iterations = nit - lpi->previt;
2676 lpi->previt = nit;
2677
2678 return SCIP_OKAY;
2679}
2680
2681/** gets information about the quality of an LP solution
2682 *
2683 * Such information is usually only available, if also a (maybe not optimal) solution is available.
2684 * The LPI should return SCIP_INVALID for @p quality, if the requested quantity is not available.
2685 */
2687 SCIP_LPI* lpi, /**< LP interface structure */
2688 SCIP_LPSOLQUALITY qualityindicator, /**< indicates which quality should be returned */
2689 SCIP_Real* quality /**< pointer to store quality number */
2690 )
2691{ /*lint --e{715}*/
2692 assert(lpi != NULL);
2693 assert(quality != NULL);
2694 SCIP_UNUSED( qualityindicator );
2695
2696 *quality = SCIP_INVALID;
2697
2698 return SCIP_OKAY;
2699}
2700
2701/**@} */
2702
2703
2704
2705
2706/*
2707 * LP Basis Methods
2708 */
2709
2710/**@name LP Basis Methods */
2711/**@{ */
2712
2713/** gets current basis status for columns and rows; arrays must be large enough to store the basis status */
2715 SCIP_LPI* lpi, /**< LP interface structure */
2716 int* cstat, /**< array to store column basis status, or NULL */
2717 int* rstat /**< array to store row basis status, or NULL */
2718 )
2719{
2720 int ncols;
2721 int nrows;
2722 char* icstat;
2723 char* irstat;
2724 register int i;
2725
2726 assert(lpi != NULL);
2727 assert(lpi->prob != NULL);
2728
2729 SCIPdebugMessage("saving QSopt basis into %p/%p\n", (void*)cstat, (void*)rstat);
2730
2731 ncols = QSget_colcount(lpi->prob);
2732 nrows = QSget_rowcount(lpi->prob);
2733
2734 SCIP_CALL( ensureTabMem(lpi, nrows + ncols) );
2735 SCIP_CALL( ensureRowMem(lpi, nrows) );
2736
2737 /* get senses */
2738 QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) );
2739
2740 /* get basis */
2741 icstat = lpi->ibas;
2742 irstat = lpi->ibas + ncols;
2743 QS_CONDRET( QSget_basis_array(lpi->prob, icstat, irstat) );
2744
2745 /* Now we must transform QSopt codes into SCIP codes.
2746 * We have the following cases:
2747 * 'G': b <= ax -> b = ax - s, s >= 0
2748 * 'L': ax <= b -> b = ax + s, s >= 0
2749 * 'R': b <= ax <= c -> c - b = ax + s, 0 <= s <= c - b
2750 */
2751 for( i = 0; i < nrows; ++i )
2752 {
2753 switch( irstat[i] )
2754 {
2755 case QS_ROW_BSTAT_LOWER:
2756 if ( lpi->isen[i] == 'L' )
2757 rstat[i] = (char) SCIP_BASESTAT_UPPER;
2758 else
2759 rstat[i] = (char) SCIP_BASESTAT_LOWER;
2760 break;
2761 case QS_ROW_BSTAT_BASIC:
2762 rstat[i] = (char) SCIP_BASESTAT_BASIC;
2763 break;
2764 case QS_ROW_BSTAT_UPPER:
2765 rstat[i] = (char) SCIP_BASESTAT_UPPER;
2766 break;
2767 default:
2768 SCIPerrorMessage("Unknown row basic status %c", rstat[i]);
2769 SCIPABORT();
2770 return SCIP_INVALIDDATA; /*lint !e527*/
2771 }
2772 }
2773 for( i = 0; i < ncols; ++i )
2774 {
2775 switch( icstat[i] )
2776 {
2777 case QS_COL_BSTAT_LOWER:
2778 cstat[i] = (char) SCIP_BASESTAT_LOWER;
2779 break;
2780 case QS_COL_BSTAT_BASIC:
2781 cstat[i] = (char) SCIP_BASESTAT_BASIC;
2782 break;
2783 case QS_COL_BSTAT_UPPER:
2784 cstat[i] = (char) SCIP_BASESTAT_UPPER;
2785 break;
2786 case QS_COL_BSTAT_FREE:
2787 cstat[i] = (char) SCIP_BASESTAT_ZERO;
2788 break;
2789 default:
2790 SCIPerrorMessage("Unknown column basic status %c", cstat[i]);
2791 SCIPABORT();
2792 return SCIP_INVALIDDATA; /*lint !e527*/
2793 }
2794 }
2795 return SCIP_OKAY;
2796}
2797
2798/** sets current basis status for columns and rows */
2800 SCIP_LPI* lpi, /**< LP interface structure */
2801 const int* cstat, /**< array with column basis status */
2802 const int* rstat /**< array with row basis status */
2803 )
2804{
2805 int ncols;
2806 int nrows;
2807 register int i;
2808 char* icstat;
2809 char* irstat;
2810
2811 assert(lpi != NULL);
2812 assert(lpi->prob != NULL);
2813
2814 SCIP_CALL( SCIPlpiGetNRows(lpi, &nrows) );
2815 SCIP_CALL( SCIPlpiGetNCols(lpi, &ncols) );
2816
2817 assert(cstat != NULL || ncols == 0);
2818 assert(rstat != NULL || nrows == 0);
2819
2820 SCIPdebugMessage("loading basis %p/%p into QSopt\n", (void*)cstat, (void*)rstat);
2821
2822 SCIP_CALL( ensureTabMem(lpi, ncols) );
2823 SCIP_CALL( ensureRowMem(lpi, nrows) );
2824
2825 /* get senses */
2826 QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) );
2827
2828 icstat = lpi->ibas;
2829 irstat = lpi->ibas + ncols;
2830
2831 /* now we must transform QSopt codes into SCIP codes */
2832 for( i = 0; i < nrows; ++i )
2833 {
2834 switch( rstat[i] ) /*lint !e613*/
2835 {
2837 irstat[i] = QS_ROW_BSTAT_LOWER;
2838 break;
2840 irstat[i] = QS_ROW_BSTAT_BASIC;
2841 break;
2843 if ( lpi->isen[i] == 'L' )
2844 irstat[i] = QS_ROW_BSTAT_LOWER;
2845 else
2846 irstat[i] = QS_ROW_BSTAT_UPPER;
2847 break;
2848 default:
2849 SCIPerrorMessage("Unknown row basic status %d", rstat[i]); /*lint !e613*/
2850 SCIPABORT();
2851 return SCIP_INVALIDDATA; /*lint !e527*/
2852 }
2853 }
2854 for( i = 0; i < ncols; ++i )
2855 {
2856 switch( cstat[i] ) /*lint !e613*/
2857 {
2859 icstat[i] = QS_COL_BSTAT_LOWER;
2860 break;
2862 icstat[i] = QS_COL_BSTAT_BASIC;
2863 break;
2865 icstat[i] = QS_COL_BSTAT_UPPER;
2866 break;
2867 case SCIP_BASESTAT_ZERO:
2868 icstat[i] = QS_COL_BSTAT_FREE;
2869 break;
2870 default:
2871 SCIPerrorMessage("Unknown column basic status %d", cstat[i]); /*lint !e613*/
2872 SCIPABORT();
2873 return SCIP_INVALIDDATA; /*lint !e527*/
2874 }
2875 }
2876
2877 /* set the basis */
2878 QS_CONDRET( QSload_basis_array(lpi->prob, icstat, irstat) );
2879
2880 return SCIP_OKAY;
2881}
2882
2883/** returns the indices of the basic columns and rows; basic column n gives value n, basic row m gives value -1-m */
2885 SCIP_LPI* lpi, /**< LP interface structure */
2886 int* bind /**< pointer to store basis indices ready to keep number of rows entries */
2887 )
2888{
2889 int nrows;
2890 int ncols;
2891 int stat;
2892 register int i;
2893
2894 assert(lpi!=NULL);
2895 assert(lpi->prob!=NULL);
2896 assert(bind != NULL);
2897
2898 SCIPdebugMessage("getting basis information\n");
2899
2900 nrows = QSget_rowcount(lpi->prob);
2901 ncols = QSget_colcount(lpi->prob);
2902
2903 QS_CONDRET( QSget_status(lpi->prob, &stat) );
2904 if ( stat == QS_LP_UNSOLVED || stat == QS_LP_MODIFIED || stat == QS_LP_NUMERR )
2905 {
2906 QS_CONDRET( QSopt_dual(lpi->prob, &(lpi->solstat)) );
2907 }
2908
2909 QS_CONDRET( QSget_basis_order(lpi->prob, bind) );
2910
2911 /* transform QSopt basis header into SCIP format */
2912 for( i = 0; i < nrows; ++i )
2913 {
2914 if( bind[i] >= ncols )
2915 bind[i] = -(bind[i] - ncols) - 1;
2916 }
2917
2918 return SCIP_OKAY;
2919}
2920
2921/** get row of inverse basis matrix B^-1
2922 *
2923 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2924 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2925 * see also the explanation in lpi.h.
2926 *
2927 * @todo check that the result is in terms of the LP interface definition
2928 */
2930 SCIP_LPI* lpi, /**< LP interface structure */
2931 int r, /**< row number */
2932 SCIP_Real* coef, /**< pointer to store the coefficients of the row */
2933 int* inds, /**< array to store the non-zero indices, or NULL */
2934 int* ninds /**< pointer to store the number of non-zero indices, or NULL
2935 * (-1: if we do not store sparsity information) */
2936 )
2937{ /*lint --e{715} */
2938 int nrows;
2939 int i;
2940
2941 assert(lpi!=NULL);
2942 assert(lpi->prob!=NULL);
2943 assert(coef != NULL);
2944 SCIP_UNUSED( inds );
2945
2946 nrows = QSget_rowcount(lpi->prob);
2947 assert( 0 <= r && r < nrows );
2948
2949 SCIPdebugMessage("getting binv-row %d from Qsopt %d cols, %d rows, %d nonz\n", r, QSget_colcount(lpi->prob),
2950 QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob));
2951
2952 /* can only return dense result */
2953 if ( ninds != NULL )
2954 *ninds = -1;
2955
2956 QS_CONDRET( QSget_binv_row(lpi->prob, r, coef) );
2957
2958 for (i = 0; i < nrows; i++)
2959 coef[i] *= -1.0;
2960
2961 return SCIP_OKAY;
2962}
2963
2964/** get column of inverse basis matrix B^-1
2965 *
2966 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2967 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2968 * see also the explanation in lpi.h.
2969 *
2970 * @todo check that the result is in terms of the LP interface definition
2971 */
2973 SCIP_LPI* lpi, /**< LP interface structure */
2974 int c, /**< column number of B^-1; this is NOT the number of the column in the LP;
2975 * you have to call SCIPlpiGetBasisInd() to get the array which links the
2976 * B^-1 column numbers to the row and column numbers of the LP!
2977 * c must be between 0 and nrows-1, since the basis has the size
2978 * nrows * nrows */
2979 SCIP_Real* coef, /**< pointer to store the coefficients of the column */
2980 int* inds, /**< array to store the non-zero indices, or NULL */
2981 int* ninds /**< pointer to store the number of non-zero indices, or NULL
2982 * (-1: if we do not store sparsity information) */
2983 )
2984{ /*lint --e{715} */
2985 assert(lpi!=NULL);
2986 assert(lpi->prob!=NULL);
2987 assert(coef != NULL);
2988 SCIP_UNUSED( c );
2989 SCIP_UNUSED( inds );
2990 SCIP_UNUSED( ninds );
2991
2992 SCIPerrorMessage("SCIPlpiGetBInvCol() not supported by QSopt.\n");
2993
2994 /* QSopt does not provide an interface for this yet */
2995 return SCIP_LPERROR;
2996}
2997
2998/** get row of inverse basis matrix times constraint matrix B^-1 * A
2999 *
3000 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
3001 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
3002 * see also the explanation in lpi.h.
3003 *
3004 * @todo check that the result is in terms of the LP interface definition
3005 */
3007 SCIP_LPI* lpi, /**< LP interface structure */
3008 int r, /**< row number */
3009 const SCIP_Real* binvrow, /**< row in (A_B)^-1 from prior call to SCIPlpiGetBInvRow(), or NULL */
3010 SCIP_Real* coef, /**< vector to return coefficients of the row */
3011 int* inds, /**< array to store the non-zero indices, or NULL */
3012 int* ninds /**< pointer to store the number of non-zero indices, or NULL
3013 * (-1: if we do not store sparsity information) */
3014 )
3015{ /*lint --e{715} */
3016 int ncols;
3017 int nrows;
3018 int i;
3019
3020 assert(lpi != NULL);
3021 assert(lpi->prob != NULL);
3022 assert(coef != NULL);
3023 SCIP_UNUSED( binvrow );
3024 SCIP_UNUSED( inds );
3025
3026 SCIPdebugMessage("getting binva-row %d\n", r);
3027
3028 /* can only return dense result */
3029 if ( ninds != NULL )
3030 *ninds = -1;
3031
3032 ncols = QSget_colcount(lpi->prob);
3033 nrows = QSget_rowcount(lpi->prob);
3034
3035 SCIP_CALL( ensureTabMem(lpi, nrows + ncols) );
3036
3037 QS_CONDRET( QSget_tableau_row(lpi->prob, r, lpi->itab) );
3038
3039 /* copy local information to the outside */
3040 BMScopyMemoryArray(coef, lpi->itab, ncols);
3041
3042 for (i = 0; i < ncols; ++i)
3043 coef[i] *= -1.0;
3044
3045 return SCIP_OKAY;
3046}
3047
3048/** get column of inverse basis matrix times constraint matrix B^-1 * A
3049 *
3050 * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
3051 * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
3052 * see also the explanation in lpi.h.
3053 *
3054 * @todo check that the result is in terms of the LP interface definition
3055 */
3057 SCIP_LPI* lpi, /**< LP interface structure */
3058 int c, /**< column number */
3059 SCIP_Real* coef, /**< vector to return coefficients of the column */
3060 int* inds, /**< array to store the non-zero indices, or NULL */
3061 int* ninds /**< pointer to store the number of non-zero indices, or NULL
3062 * (-1: if we do not store sparsity information) */
3063 )
3064{ /*lint --e{715} */
3065 assert(lpi!=NULL);
3066 assert(lpi->prob!=NULL);
3067 assert(coef != NULL);
3068 assert(c >= 0);
3069 SCIP_UNUSED( inds );
3070 SCIP_UNUSED( ninds );
3071
3072 SCIPerrorMessage("SCIPlpiGetBInvACol() not supported by QSopt.\n");
3073
3074 /* QSopt does not provide an interface for this yet */
3075 return SCIP_LPERROR;
3076}
3077
3078/**@} */
3079
3080
3081
3082
3083/*
3084 * LP State Methods
3085 */
3086
3087/**@name LP State Methods */
3088/**@{ */
3089
3090/** stores LPi state (like basis information) into lpistate object */
3092 SCIP_LPI* lpi, /**< LP interface structure */
3093 BMS_BLKMEM* blkmem, /**< block memory */
3094 SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
3095 )
3096{
3097 int ncols, nrows;
3098
3099 assert(lpi != NULL);
3100 assert(lpi->prob != NULL);
3101 assert(blkmem != NULL);
3102 assert(lpistate != NULL);
3103
3104 ncols = QSget_colcount(lpi->prob);
3105 nrows = QSget_rowcount(lpi->prob);
3106
3107 assert(ncols >= 0);
3108 assert(nrows >= 0);
3109
3110 /* allocate lpistate data */
3111 SCIP_CALL( lpistateCreate(lpistate, blkmem, ncols, nrows));
3112 SCIPdebugMessage("storing QSopt LPI state in %p (%d cols, %d rows)\n", (void*)*lpistate, ncols, nrows);
3113
3114 /* get unpacked basis information from QSopt */
3115 SCIP_CALL( ensureColMem(lpi, ncols) );
3116 SCIP_CALL( ensureRowMem(lpi, nrows) );
3117 SCIP_CALL( SCIPlpiGetBase(lpi, lpi->iccnt, lpi->ircnt) );
3118
3119 /* pack LPi state data */
3120 (*lpistate)->ncols = ncols;
3121 (*lpistate)->nrows = nrows;
3122 lpistatePack(*lpistate, lpi->iccnt, lpi->ircnt);
3123
3124 return SCIP_OKAY;
3125}
3126
3127/** loads LPi state (like basis information) into solver; note that the LP might have been extended with additional
3128 * columns and rows since the state was stored with SCIPlpiGetState()
3129 */
3131 SCIP_LPI* lpi, /**< LP interface structure */
3132 BMS_BLKMEM* blkmem, /**< block memory */
3133 const SCIP_LPISTATE* lpistate /**< LPi state information (like basis information), or NULL */
3134 )
3135{ /*lint --e{715} */
3136 char* icstat;
3137 char* irstat;
3138 int i;
3139 int ncols;
3140 int nrows;
3141
3142 assert(lpi != NULL);
3143 assert(lpi->prob != NULL);
3144 assert(blkmem != NULL);
3145
3146 /* if there was no basis information available, LPI state was not stored */
3147 if( lpistate == NULL )
3148 return SCIP_OKAY;
3149
3150 /* continue test */
3151 ncols = QSget_colcount(lpi->prob);
3152 nrows = QSget_rowcount(lpi->prob);
3153
3154 assert(ncols >= 0);
3155 assert(nrows >= 0);
3156 assert(lpistate->ncols <= ncols);
3157 assert(lpistate->nrows <= nrows);
3158
3159 SCIPdebugMessage("loading LPI state %p (%d cols, %d rows) into QSopt LP with %d cols and %d rows\n", (void*)lpistate, lpistate->ncols,
3160 lpistate->nrows, ncols, nrows);
3161
3162 if( lpistate->ncols == 0 || lpistate->nrows == 0 )
3163 return SCIP_OKAY;
3164
3165 /* allocate enough memory for storing uncompressed basis information */
3166 SCIP_CALL( ensureColMem(lpi, ncols) );
3167 SCIP_CALL( ensureRowMem(lpi, nrows) );
3168 SCIP_CALL( ensureTabMem(lpi, nrows + ncols) );
3169
3170 icstat = lpi->ibas;
3171 irstat = lpi->ibas + ncols;
3172
3173 /* get senses */
3174 QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) );
3175
3176 /* unpack LPi state data */
3177 lpistateUnpack(lpistate, lpi->iccnt, lpi->ircnt);
3178
3179 /* extend the basis to the current LP beyond the previously existing columns */
3180 for( i = lpistate->ncols; i < ncols; ++i )
3181 {
3182 SCIP_Real lb;
3183 SCIP_Real ub;
3184
3185 /* get bounds from qsopt */
3186 QS_CONDRET( QSget_bounds_list(lpi->prob, 1, &i, &lb, &ub) );
3187 if ( SCIPlpiIsInfinity(lpi, REALABS(lb)) )
3188 {
3189 /* if lower bound is +/- infinity -> try upper bound */
3190 if ( SCIPlpiIsInfinity(lpi, REALABS(ub)) )
3191 lpi->iccnt[i] = (int) SCIP_BASESTAT_ZERO; /* variable is free */
3192 else
3193 lpi->iccnt[i] = (int) SCIP_BASESTAT_UPPER; /* use finite upper bound */
3194 }
3195 else
3196 lpi->iccnt[i] = (int) SCIP_BASESTAT_LOWER; /* use finite lower bound */
3197 }
3198 for( i = lpistate->nrows; i < nrows; ++i ) /*lint !e850*/
3199 lpi->ircnt[i] = (int) SCIP_BASESTAT_BASIC;
3200
3201 /* convert the loaded basis into QSopt format */
3202 for( i = 0; i < nrows; ++i )
3203 {
3204 switch( lpi->ircnt[i] )
3205 {
3207 irstat[i] = QS_ROW_BSTAT_LOWER;
3208 break;
3210 irstat[i] = QS_ROW_BSTAT_BASIC;
3211 break;
3213 if ( lpi->isen[i] == 'L' )
3214 irstat[i] = QS_ROW_BSTAT_LOWER;
3215 else
3216 irstat[i] = QS_ROW_BSTAT_UPPER;
3217 break;
3218 default:
3219 SCIPerrorMessage("Unknown row basic status %d", lpi->ircnt[i]);
3220 SCIPABORT();
3221 return SCIP_INVALIDDATA; /*lint !e527*/
3222 }
3223 }
3224
3225 for( i = 0; i < ncols; ++i )
3226 {
3227 switch( lpi->iccnt[i] )
3228 {
3230 icstat[i] = QS_COL_BSTAT_LOWER;
3231 break;
3233 icstat[i] = QS_COL_BSTAT_BASIC;
3234 break;
3236 icstat[i] = QS_COL_BSTAT_UPPER;
3237 break;
3238 case SCIP_BASESTAT_ZERO:
3239 icstat[i] = QS_COL_BSTAT_FREE;
3240 break;
3241 default:
3242 SCIPerrorMessage("Unknown column basic status %d", lpi->iccnt[i]);
3243 SCIPABORT();
3244 return SCIP_INVALIDDATA; /*lint !e527*/
3245 }
3246 }
3247
3248 /* set the basis */
3249 QS_CONDRET( QSload_basis_array(lpi->prob, icstat, irstat) );
3250
3251 return SCIP_OKAY;
3252}
3253
3254/** clears current LPi state (like basis information) of the solver */
3256 SCIP_LPI* lpi /**< LP interface structure */
3257 )
3258{
3259 int ncols;
3260 int nrows;
3261 int* cstat;
3262 int* rstat;
3263 int i;
3264
3265 assert( lpi != NULL );
3266 assert( lpi->prob != NULL );
3267
3268 SCIPdebugMessage("SCIPlpiClearState()\n");
3269
3270 ncols = QSget_colcount(lpi->prob);
3271 nrows = QSget_rowcount(lpi->prob);
3272
3273 if ( ncols == 0 || nrows == 0 )
3274 return SCIP_OKAY;
3275
3276 SCIP_ALLOC( BMSallocMemoryArray(&cstat, ncols) );
3277 SCIP_ALLOC( BMSallocMemoryArray(&rstat, nrows) );
3278
3279 for (i = 0; i < ncols; ++i)
3280 cstat[i] = (char) SCIP_BASESTAT_LOWER;
3281 for (i = 0; i < nrows; ++i)
3282 rstat[i] = (char) SCIP_BASESTAT_BASIC;
3283
3284 SCIP_CALL( SCIPlpiSetBase(lpi, cstat, rstat) );
3285
3286 BMSfreeMemoryArray(&cstat);
3287 BMSfreeMemoryArray(&rstat);
3288
3289 return SCIP_OKAY;
3290}
3291
3292/** frees LPi state information */
3294 SCIP_LPI* lpi, /**< LP interface structure */
3295 BMS_BLKMEM* blkmem, /**< block memory */
3296 SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
3297 )
3298{
3299 assert(lpi != NULL);
3300 assert(lpistate != NULL);
3301 assert(blkmem != NULL);
3302
3303 if( *lpistate != NULL )
3304 lpistateFree(lpistate, blkmem);
3305
3306 return SCIP_OKAY;
3307}
3308
3309/** checks, whether the given LP state contains simplex basis information */
3311 SCIP_LPI* lpi, /**< LP interface structure */
3312 SCIP_LPISTATE* lpistate /**< LP state information (like basis information), or NULL */
3313 )
3314{ /*lint --e{715} */
3315 assert(lpi != NULL);
3316 return (lpistate != NULL);
3317}
3318
3319/** reads LP state (like basis information from a file */
3321 SCIP_LPI* lpi, /**< LP interface structure */
3322 const char* fname /**< file name */
3323 )
3324{
3325 int rval;
3326
3327 assert(lpi != NULL);
3328 assert(lpi->prob != NULL);
3329 assert(fname != NULL);
3330
3331 SCIPdebugMessage("reading QSopt LP state from file <%s>\n", fname);
3332
3333 rval = QSread_and_load_basis(lpi->prob, fname);
3334 if( rval )
3335 {
3336 SCIPerrorMessage("Error while loading basis from file <%s>.\n", fname);
3337 return SCIP_READERROR;
3338 }
3339
3340 return SCIP_OKAY;
3341}
3342
3343/** writes LPi state (i.e. basis information) to a file */
3345 SCIP_LPI* lpi, /**< LP interface structure */
3346 const char* fname /**< file name */
3347 )
3348{
3349 QSbas bas;
3350 int rval;
3351
3352 assert(lpi != NULL);
3353 assert(lpi->prob != NULL);
3354 assert(fname != NULL);
3355
3356 SCIPdebugMessage("writing QSopt LP state to file <%s>\n", fname);
3357
3358 bas = QSget_basis(lpi->prob);
3359 QS_ERROR(bas == 0, "Could not get basis from problem."); /*lint !e820*/
3360 assert(bas);
3361
3362 rval = QSwrite_basis(lpi->prob, bas, fname);
3363 QSfree(bas);
3364 if( rval )
3365 {
3366 SCIPerrorMessage("Could not write basis to file <%s>.\n", fname);
3367 return SCIP_WRITEERROR;
3368 }
3369
3370 return SCIP_OKAY;
3371}
3372
3373/**@} */
3374
3375
3376
3377
3378/*
3379 * LP Pricing Norms Methods
3380 */
3381
3382/**@name LP Pricing Norms Methods */
3383/**@{ */
3384
3385/** stores LPi pricing norms information
3386 * @todo should we store norm information?
3387 */
3389 SCIP_LPI* lpi, /**< LP interface structure */
3390 BMS_BLKMEM* blkmem, /**< block memory */
3391 SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
3392 )
3393{ /*lint --e{715} */
3394 int ncols;
3395 int nrows;
3396
3397 assert( lpi != NULL );
3398 assert( lpi->prob != NULL );
3399 assert( lpinorms != NULL );
3400 assert( blkmem != NULL );
3401
3402 ncols = QSget_colcount(lpi->prob);
3403 nrows = QSget_rowcount(lpi->prob);
3404
3405 /* allocate lpinorms data */
3406 SCIP_ALLOC( BMSallocBlockMemory(blkmem, lpinorms) );
3407 (*lpinorms)->ncols = ncols;
3408 (*lpinorms)->nrows = nrows;
3409
3410 if ( QStest_row_norms(lpi->prob) )
3411 {
3412 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->cstat, ncols) );
3413 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->rstat, nrows) );
3414 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->norms, nrows) );
3415
3416 QS_CONDRET( QSget_basis_and_row_norms_array(lpi->prob, (*lpinorms)->cstat, (*lpinorms)->rstat, (*lpinorms)->norms) );
3417 }
3418 else
3419 {
3420 (*lpinorms)->cstat = NULL;
3421 (*lpinorms)->rstat = NULL;
3422 (*lpinorms)->norms = NULL;
3423 }
3424
3425 return SCIP_OKAY;
3426}
3427
3428/** loads LPi pricing norms into solver; note that the LP might have been extended with additional
3429 * columns and rows since the state was stored with SCIPlpiGetNorms()
3430 */
3432 SCIP_LPI* lpi, /**< LP interface structure */
3433 BMS_BLKMEM* blkmem, /**< block memory */
3434 const SCIP_LPINORMS* lpinorms /**< LPi pricing norms information, or NULL */
3435 )
3436{ /*lint --e{715} */
3437 int ncols;
3438 int nrows;
3439
3440 assert( lpi != NULL );
3441 assert( lpi->prob != NULL );
3442 SCIP_UNUSED( blkmem );
3443
3444 if ( lpinorms->norms == NULL )
3445 return SCIP_OKAY;
3446
3447 ncols = QSget_colcount(lpi->prob);
3448 nrows = QSget_rowcount(lpi->prob);
3449 if ( nrows != lpinorms->nrows || ncols != lpinorms->ncols )
3450 return SCIP_OKAY;
3451
3452 /* load row norms */
3453 assert( lpinorms->cstat != NULL && lpinorms->rstat != NULL && lpinorms->norms != NULL );
3454 QS_CONDRET( QSload_basis_and_row_norms_array(lpi->prob, lpinorms->cstat, lpinorms->rstat, lpinorms->norms) );
3455
3456 return SCIP_OKAY;
3457}
3458
3459/** frees pricing norms information */
3461 SCIP_LPI* lpi, /**< LP interface structure */
3462 BMS_BLKMEM* blkmem, /**< block memory */
3463 SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information, or NULL */
3464 )
3465{ /*lint --e{715} */
3466 assert( lpinorms != NULL );
3467 assert( lpi != NULL );
3468
3469 if ( (*lpinorms)->norms != NULL )
3470 {
3471 assert( (*lpinorms)->cstat != NULL && (*lpinorms)->rstat != NULL );
3472 BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->norms, (*lpinorms)->nrows);
3473 BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->rstat, (*lpinorms)->nrows);
3474 BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->cstat, (*lpinorms)->ncols);
3475 }
3476 BMSfreeBlockMemory(blkmem, lpinorms);
3477
3478 return SCIP_OKAY;
3479}
3480
3481/**@} */
3482
3483
3484
3485
3486/*
3487 * Parameter Methods
3488 */
3489
3490/**@name Parameter Methods */
3491/**@{ */
3492
3493/** gets integer parameter of LP */
3495 SCIP_LPI* lpi, /**< LP interface structure */
3496 SCIP_LPPARAM type, /**< parameter number */
3497 int* ival /**< buffer to store the parameter value */
3498 )
3499{
3500 assert(lpi != NULL);
3501 assert(lpi->prob != NULL);
3502 assert(ival != NULL);
3503
3504 SCIPdebugMessage("getting int parameter %d\n", type);
3505
3506 switch( type )
3507 {
3509 case SCIP_LPPAR_FASTMIP:
3511 return SCIP_PARAMETERUNKNOWN;
3512 case SCIP_LPPAR_SCALING:
3513 QS_CONDRET( QSget_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, ival) );
3514 assert((*ival) == 0 || (*ival) == 1);
3515
3516 break;
3517 case SCIP_LPPAR_PRICING:
3518 *ival = lpi->pricing;
3519 break;
3520 case SCIP_LPPAR_LPINFO:
3521 QS_CONDRET( QSget_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, ival) );
3522 if( *ival )
3523 *ival = TRUE;
3524 else
3525 *ival = FALSE;
3526 break;
3527 case SCIP_LPPAR_LPITLIM:
3528 QS_CONDRET( QSget_param(lpi->prob, QS_PARAM_SIMPLEX_MAX_ITERATIONS, ival) );
3529 break;
3530 default:
3531 return SCIP_PARAMETERUNKNOWN;
3532 } /*lint !e788*/
3533
3534 return SCIP_OKAY;
3535}
3536
3537/** sets integer parameter of LP */
3539 SCIP_LPI* lpi, /**< LP interface structure */
3540 SCIP_LPPARAM type, /**< parameter number */
3541 int ival /**< parameter value */
3542 )
3543{
3544 assert(lpi != NULL);
3545 assert(lpi->prob != NULL);
3546
3547 SCIPdebugMessage("setting int parameter %d to %d\n", type, ival);
3548
3549 switch( type )
3550 {
3551 case SCIP_LPPAR_SCALING:
3552 if( ival == 0 )
3553 QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, 0) );
3554 else
3555 QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, 1) );
3556 break;
3557 case SCIP_LPPAR_PRICING:
3558 lpi->pricing = ival;
3559 switch( ival )
3560 {
3561 case SCIP_PRICING_AUTO:
3563 case SCIP_PRICING_FULL:
3564 case SCIP_PRICING_STEEP:
3566 QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_PRIMAL_PRICING, QS_PRICE_PSTEEP) );
3567 QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_DUAL_PRICING, QS_PRICE_DSTEEP) );
3568 break;
3570 QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_PRIMAL_PRICING,QS_PRICE_PMULTPARTIAL) );
3571 QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_DUAL_PRICING,QS_PRICE_DMULTPARTIAL) );
3572 break;
3573 case SCIP_PRICING_DEVEX:
3574 QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_PRIMAL_PRICING,QS_PRICE_PDEVEX) );
3575 QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_DUAL_PRICING,QS_PRICE_DDEVEX) );
3576 break;
3577 default:
3578 return SCIP_LPERROR;
3579 }
3580 break;
3581 case SCIP_LPPAR_LPINFO:
3582 if( ival )
3583 QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, 1) );
3584 else
3585 QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, 0) );
3586 break;
3587 case SCIP_LPPAR_LPITLIM:
3588 /* The maximum number of pivots allowed in the algorithm can be set with the QS_PARAM_SIMPLEX_MAX_ITERATIONS parameter.
3589 * ival can be any positive integer, 0 stopping immediately */
3590 assert( ival >= 0 );
3591 QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_MAX_ITERATIONS, ival) );
3592 break;
3593 default:
3594 return SCIP_PARAMETERUNKNOWN;
3595 } /*lint !e788*/
3596
3597 return SCIP_OKAY;
3598}
3599
3600/** gets floating point parameter of LP */
3602 SCIP_LPI* lpi, /**< LP interface structure */
3603 SCIP_LPPARAM type, /**< parameter number */
3604 SCIP_Real* dval /**< buffer to store the parameter value */
3605 )
3606{
3607 assert(lpi != NULL);
3608 assert(lpi->prob != NULL);
3609 assert(dval != NULL);
3610
3611 SCIPdebugMessage("getting real parameter %d\n", type);
3612
3613 switch( type )
3614 {
3615 case SCIP_LPPAR_OBJLIM:
3616 {
3617 int sense;
3618 QS_CONDRET( QSget_objsense(lpi->prob, &sense) );
3619 if ( sense == QS_MIN )
3620 {
3621 QS_CONDRET( QSget_param_double(lpi->prob, QS_PARAM_OBJULIM, dval) );
3622 }
3623 else
3624 {
3625 QS_CONDRET( QSget_param_double(lpi->prob, QS_PARAM_OBJLLIM, dval) );
3626 }
3627 break;
3628 }
3629 case SCIP_LPPAR_LPTILIM:
3630 QS_CONDRET( QSget_param_double(lpi->prob, QS_PARAM_SIMPLEX_MAX_TIME, dval) );
3631 break;
3632 default:
3636 case SCIP_LPPAR_FEASTOL:
3637 return SCIP_PARAMETERUNKNOWN;
3638 } /*lint !e788*/
3639
3640 return SCIP_OKAY;
3641}
3642
3643/** sets floating point parameter of LP */
3645 SCIP_LPI* lpi, /**< LP interface structure */
3646 SCIP_LPPARAM type, /**< parameter number */
3647 SCIP_Real dval /**< parameter value */
3648 )
3649{
3650 assert(lpi != NULL);
3651 assert(lpi->prob != NULL);
3652
3653 SCIPdebugMessage("setting real parameter %d to %g\n", type, dval);
3654
3655 switch( type )
3656 {
3657 case SCIP_LPPAR_LPTILIM:
3658 assert( dval > 0.0 );
3659
3660 /* qso requires dval >= 0
3661 *
3662 * However for consistency we assert the timelimit to be strictly positive.
3663 */
3664 QS_CONDRET( QSset_param_double(lpi->prob, QS_PARAM_SIMPLEX_MAX_TIME, dval) );
3665 break;
3666 case SCIP_LPPAR_OBJLIM:
3667 {
3668 int sense;
3669 QS_CONDRET( QSget_objsense(lpi->prob, &sense) );
3670 if ( sense == QS_MIN )
3671 {
3672 QS_CONDRET( QSset_param_double(lpi->prob, QS_PARAM_OBJULIM, dval) );
3673 }
3674 else
3675 {
3676 QS_CONDRET( QSset_param_double(lpi->prob, QS_PARAM_OBJLLIM, dval) );
3677 }
3678 break;
3679 }
3680 case SCIP_LPPAR_FEASTOL:
3684 default:
3685 return SCIP_PARAMETERUNKNOWN;
3686 } /*lint !e788*/
3687
3688 return SCIP_OKAY;
3689}
3690
3691/** interrupts the currently ongoing lp solve or disables the interrupt */
3693 SCIP_LPI* lpi, /**< LP interface structure */
3694 SCIP_Bool interrupt /**< TRUE if interrupt should be set, FALSE if it should be disabled */
3695 )
3696{
3697 /*lint --e{715}*/
3698 assert(lpi != NULL);
3699
3700 return SCIP_OKAY;
3701}
3702
3703/**@} */
3704
3705
3706
3707
3708/*
3709 * Numerical Methods
3710 */
3711
3712/**@name Numerical Methods */
3713/**@{ */
3714
3715/** returns value treated as infinity in the LP solver */
3717 SCIP_LPI* lpi /**< LP interface structure */
3718 )
3719{ /*lint --e{715} */
3720 assert(lpi != NULL);
3721 return QS_MAXDOUBLE;
3722}
3723
3724/** checks if given value is treated as infinity in the LP solver */
3726 SCIP_LPI* lpi, /**< LP interface structure */
3727 SCIP_Real val /**< value to be checked for infinity */
3728 )
3729{ /*lint --e{715} */
3730 assert(lpi != NULL);
3731 return (val >= QS_MAXDOUBLE);
3732}
3733
3734/**@} */
3735
3736
3737
3738
3739/*
3740 * File Interface Methods
3741 */
3742
3743/**@name File Interface Methods */
3744/**@{ */
3745
3746/** reads LP from a file */
3748 SCIP_LPI* lpi, /**< LP interface structure */
3749 const char* fname /**< file name */
3750 )
3751{
3752 assert(lpi != NULL);
3753 assert(lpi->prob != NULL);
3754 assert(fname != NULL);
3755
3756 SCIPdebugMessage("reading LP from file <%s>\n", fname);
3757
3758 if( lpi->prob != NULL )
3759 QSfree_prob(lpi->prob);
3760
3761 lpi->solstat = 0;
3762 lpi->previt = 0;
3763
3764 lpi->prob = QSread_prob(fname, "LP");
3765 if( lpi->prob == 0 )
3766 return SCIP_READERROR;
3767
3768 return SCIP_OKAY;
3769}
3770
3771/** writes LP to a file */
3773 SCIP_LPI* lpi, /**< LP interface structure */
3774 const char* fname /**< file name */
3775 )
3776{
3777 assert(lpi != NULL);
3778 assert(lpi->prob != NULL);
3779 assert(fname != NULL);
3780
3781 SCIPdebugMessage("writing LP to file <%s>\n", fname);
3782
3783 if( QSwrite_prob (lpi->prob, fname, "LP") )
3784 return SCIP_WRITEERROR;
3785
3786 return SCIP_OKAY;
3787}
3788
3789/**@} */
void SCIPdecodeDualBit(const SCIP_DUALPACKET *inp, int *out, int count)
Definition: bitencode.c:308
void SCIPencodeDualBit(const int *inp, SCIP_DUALPACKET *out, int count)
Definition: bitencode.c:238
packing single and dual bit values
unsigned int SCIP_DUALPACKET
Definition: bitencode.h:42
SCIP_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_UNUSED(x)
Definition: def.h:428
#define EPSISINT(x, eps)
Definition: def.h:210
#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 EPSEQ(x, y, eps)
Definition: def.h:198
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPlpiChgSides(SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
Definition: lpi_qso.c:1148
SCIP_RETCODE SCIPlpiSetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPISTATE *lpistate)
Definition: lpi_qso.c:3130
SCIP_RETCODE SCIPlpiGetBInvACol(SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:3056
SCIP_RETCODE SCIPlpiGetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real *dval)
Definition: lpi_qso.c:3601
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition: lpi_qso.c:3716
SCIP_Bool SCIPlpiIsObjlimExc(SCIP_LPI *lpi)
Definition: lpi_qso.c:2422
SCIP_RETCODE SCIPlpiChgObjsen(SCIP_LPI *lpi, SCIP_OBJSEN objsen)
Definition: lpi_qso.c:1210
SCIP_Bool SCIPlpiIsInfinity(SCIP_LPI *lpi, SCIP_Real val)
Definition: lpi_qso.c:3725
SCIP_RETCODE SCIPlpiClear(SCIP_LPI *lpi)
Definition: lpi_qso.c:1068
SCIP_RETCODE SCIPlpiClearState(SCIP_LPI *lpi)
Definition: lpi_qso.c:3255
SCIP_Bool SCIPlpiExistsDualRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2323
SCIP_Bool SCIPlpiExistsPrimalRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2251
SCIP_RETCODE SCIPlpiGetBase(SCIP_LPI *lpi, int *cstat, int *rstat)
Definition: lpi_qso.c:2714
SCIP_RETCODE SCIPlpiReadState(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3320
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_qso.c:791
SCIP_RETCODE SCIPlpiGetPrimalRay(SCIP_LPI *lpi, SCIP_Real *ray)
Definition: lpi_qso.c:2629
SCIP_RETCODE SCIPlpiGetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int *ival)
Definition: lpi_qso.c:3494
SCIP_RETCODE SCIPlpiWriteLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3772
SCIP_RETCODE SCIPlpiSetIntegralityInformation(SCIP_LPI *lpi, int ncols, int *intInfo)
Definition: lpi_qso.c:410
SCIP_Bool SCIPlpiIsDualInfeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2364
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
Definition: lpi_qso.c:3644
SCIP_RETCODE SCIPlpiStrongbranchFrac(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_qso.c:2004
SCIP_RETCODE SCIPlpiSetNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPINORMS *lpinorms)
Definition: lpi_qso.c:3431
SCIP_RETCODE SCIPlpiGetNNonz(SCIP_LPI *lpi, int *nnonz)
Definition: lpi_qso.c:1494
SCIP_Bool SCIPlpiHasPrimalSolve(void)
Definition: lpi_qso.c:425
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_qso.c:2098
SCIP_RETCODE SCIPlpiGetBounds(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *lbs, SCIP_Real *ubs)
Definition: lpi_qso.c:1803
SCIP_Bool SCIPlpiHasBarrierSolve(void)
Definition: lpi_qso.c:441
SCIP_RETCODE SCIPlpiGetDualfarkas(SCIP_LPI *lpi, SCIP_Real *dualfarkas)
Definition: lpi_qso.c:2644
SCIP_RETCODE SCIPlpiGetObjval(SCIP_LPI *lpi, SCIP_Real *objval)
Definition: lpi_qso.c:2492
SCIP_RETCODE SCIPlpiScaleCol(SCIP_LPI *lpi, int col, SCIP_Real scaleval)
Definition: lpi_qso.c:1365
int SCIPlpiGetInternalStatus(SCIP_LPI *lpi)
Definition: lpi_qso.c:2461
SCIP_RETCODE SCIPlpiStartStrongbranch(SCIP_LPI *lpi)
Definition: lpi_qso.c:1980
SCIP_RETCODE SCIPlpiGetSolFeasibility(SCIP_LPI *lpi, SCIP_Bool *primalfeasible, SCIP_Bool *dualfeasible)
Definition: lpi_qso.c:2221
SCIP_RETCODE SCIPlpiFreeNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
Definition: lpi_qso.c:3460
SCIP_Bool SCIPlpiIsIterlimExc(SCIP_LPI *lpi)
Definition: lpi_qso.c:2435
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_qso.c:1097
SCIP_Bool SCIPlpiIsPrimalUnbounded(SCIP_LPI *lpi)
Definition: lpi_qso.c:2280
SCIP_RETCODE SCIPlpiIgnoreInstability(SCIP_LPI *lpi, SCIP_Bool *success)
Definition: lpi_qso.c:2474
SCIP_RETCODE SCIPlpiWriteState(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3344
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
Definition: lpi_qso.c:509
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_qso.c:2048
SCIP_RETCODE SCIPlpiGetCoef(SCIP_LPI *lpi, int row, int col, SCIP_Real *val)
Definition: lpi_qso.c:1902
SCIP_Bool SCIPlpiIsPrimalFeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2308
SCIP_RETCODE SCIPlpiReadLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3747
SCIP_RETCODE SCIPlpiGetRealSolQuality(SCIP_LPI *lpi, SCIP_LPSOLQUALITY qualityindicator, SCIP_Real *quality)
Definition: lpi_qso.c:2686
SCIP_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2377
SCIP_RETCODE SCIPlpiGetNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
Definition: lpi_qso.c:3388
SCIP_Bool SCIPlpiIsTimelimExc(SCIP_LPI *lpi)
Definition: lpi_qso.c:2448
SCIP_Bool SCIPlpiHasStateBasis(SCIP_LPI *lpi, SCIP_LPISTATE *lpistate)
Definition: lpi_qso.c:3310
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_qso.c:3538
const char * SCIPlpiGetSolverName(void)
Definition: lpi_qso.c:376
SCIP_RETCODE SCIPlpiSetBase(SCIP_LPI *lpi, const int *cstat, const int *rstat)
Definition: lpi_qso.c:2799
SCIP_Bool SCIPlpiHasPrimalRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2266
SCIP_RETCODE SCIPlpiGetBInvRow(SCIP_LPI *lpi, int r, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:2929
SCIP_RETCODE SCIPlpiDelRows(SCIP_LPI *lpi, int firstrow, int lastrow)
Definition: lpi_qso.c:1000
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_qso.c:1514
SCIP_RETCODE SCIPlpiGetBInvCol(SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:2972
SCIP_RETCODE SCIPlpiGetColNames(SCIP_LPI *lpi, int firstcol, int lastcol, char **colnames, char *namestorage, int namestoragesize, int *storageleft)
Definition: lpi_qso.c:875
SCIP_RETCODE SCIPlpiGetBInvARow(SCIP_LPI *lpi, int r, const SCIP_Real *binvrow, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:3006
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_qso.c:1618
SCIP_Bool SCIPlpiWasSolved(SCIP_LPI *lpi)
Definition: lpi_qso.c:2201
const char * SCIPlpiGetSolverDesc(void)
Definition: lpi_qso.c:393
SCIP_RETCODE SCIPlpiSolveBarrier(SCIP_LPI *lpi, SCIP_Bool crossover)
Definition: lpi_qso.c:1967
SCIP_Bool SCIPlpiIsOptimal(SCIP_LPI *lpi)
Definition: lpi_qso.c:2390
SCIP_RETCODE SCIPlpiGetRowNames(SCIP_LPI *lpi, int firstrow, int lastrow, char **rownames, char *namestorage, int namestoragesize, int *storageleft)
Definition: lpi_qso.c:938
SCIP_Bool SCIPlpiHasDualSolve(void)
Definition: lpi_qso.c:433
SCIP_RETCODE SCIPlpiEndStrongbranch(SCIP_LPI *lpi)
Definition: lpi_qso.c:1992
SCIP_RETCODE SCIPlpiGetSides(SCIP_LPI *lpi, int firstrow, int lastrow, SCIP_Real *lhss, SCIP_Real *rhss)
Definition: lpi_qso.c:1832
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_qso.c:2142
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
Definition: lpi_qso.c:2513
SCIP_Bool SCIPlpiHasDualRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2338
SCIP_RETCODE SCIPlpiDelColset(SCIP_LPI *lpi, int *dstat)
Definition: lpi_qso.c:756
SCIP_RETCODE SCIPlpiGetObj(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *vals)
Definition: lpi_qso.c:1762
SCIP_RETCODE SCIPlpiFreeState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition: lpi_qso.c:3293
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2293
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_qso.c:1950
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_qso.c:639
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
Definition: lpi_qso.c:1933
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_qso.c:549
SCIP_Bool SCIPlpiIsDualUnbounded(SCIP_LPI *lpi)
Definition: lpi_qso.c:2351
SCIP_RETCODE SCIPlpiGetIterations(SCIP_LPI *lpi, int *iterations)
Definition: lpi_qso.c:2662
SCIP_RETCODE SCIPlpiGetBasisInd(SCIP_LPI *lpi, int *bind)
Definition: lpi_qso.c:2884
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
Definition: lpi_qso.c:461
void * SCIPlpiGetSolverPointer(SCIP_LPI *lpi)
Definition: lpi_qso.c:401
SCIP_RETCODE SCIPlpiChgObj(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *obj)
Definition: lpi_qso.c:1235
SCIP_RETCODE SCIPlpiGetObjsen(SCIP_LPI *lpi, SCIP_OBJSEN *objsen)
Definition: lpi_qso.c:1741
SCIP_Bool SCIPlpiIsStable(SCIP_LPI *lpi)
Definition: lpi_qso.c:2409
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
Definition: lpi_qso.c:1477
SCIP_RETCODE SCIPlpiInterrupt(SCIP_LPI *lpi, SCIP_Bool interrupt)
Definition: lpi_qso.c:3692
SCIP_RETCODE SCIPlpiDelCols(SCIP_LPI *lpi, int firstcol, int lastcol)
Definition: lpi_qso.c:727
SCIP_RETCODE SCIPlpiDelRowset(SCIP_LPI *lpi, int *dstat)
Definition: lpi_qso.c:1028
SCIP_RETCODE SCIPlpiScaleRow(SCIP_LPI *lpi, int row, SCIP_Real scaleval)
Definition: lpi_qso.c:1262
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
Definition: lpi_qso.c:1460
SCIP_RETCODE SCIPlpiGetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition: lpi_qso.c:3091
SCIP_RETCODE SCIPlpiChgCoef(SCIP_LPI *lpi, int row, int col, SCIP_Real newval)
Definition: lpi_qso.c:1190
interface methods for specific LP solvers
SCIP_DUALPACKET ROWPACKET
Definition: lpi_clp.cpp:128
SCIP_DUALPACKET COLPACKET
Definition: lpi_clp.cpp:126
#define EPSILON
Definition: lpi_qso.c:102
static void lpistatePack(SCIP_LPISTATE *lpistate, const int *cstat, const int *rstat)
Definition: lpi_qso.c:178
static void lpistateUnpack(const SCIP_LPISTATE *lpistate, int *cstat, int *rstat)
Definition: lpi_qso.c:194
static int rowpacketNum(int nrows)
Definition: lpi_qso.c:169
SCIP_DUALPACKET ROWPACKET
Definition: lpi_qso.c:43
static SCIP_RETCODE ensureTabMem(SCIP_LPI *const lpi, int sz)
Definition: lpi_qso.c:253
#define COLS_PER_PACKET
Definition: lpi_qso.c:42
#define FEASTOL
Definition: lpi_qso.c:99
enum LPI_QSOPT_Algo LPI_QSOPT_ALGO
Definition: lpi_qso.c:52
static void lpistateFree(SCIP_LPISTATE **lpistate, BMS_BLKMEM *blkmem)
Definition: lpi_qso.c:231
LPI_QSOPT_Algo
Definition: lpi_qso.c:47
@ LPI_QSOPT_ALGO_UNKNOWN
Definition: lpi_qso.c:48
@ LPI_QSOPT_ALGO_DUAL
Definition: lpi_qso.c:50
@ LPI_QSOPT_ALGO_PRIMAL
Definition: lpi_qso.c:49
#define QS_TESTG(A, B, C)
Definition: lpi_qso.c:109
SCIP_DUALPACKET COLPACKET
Definition: lpi_qso.c:41
static int colpacketNum(int ncols)
Definition: lpi_qso.c:160
#define QS_CONDRET(A)
Definition: lpi_qso.c:134
static SCIP_RETCODE ensureRowMem(SCIP_LPI *const lpi, int nrows)
Definition: lpi_qso.c:287
static SCIP_RETCODE convertSides(SCIP_LPI *const lpi, int nrows, const double *const lhs, const double *const rhs)
Definition: lpi_qso.c:307
#define QS_RETURN(A)
Definition: lpi_qso.c:124
static SCIP_RETCODE ensureColMem(SCIP_LPI *const lpi, int ncols)
Definition: lpi_qso.c:270
static SCIP_RETCODE lpistateCreate(SCIP_LPISTATE **lpistate, BMS_BLKMEM *blkmem, int ncols, int nrows)
Definition: lpi_qso.c:210
#define ROWS_PER_PACKET
Definition: lpi_qso.c:44
#define QS_ERROR(A,...)
Definition: lpi_qso.c:116
#define BMSfreeMemory(ptr)
Definition: memory.h:145
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:465
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:451
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:127
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:123
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:147
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition: memory.h:454
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition: memory.h:467
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define BMSallocMemory(ptr)
Definition: memory.h:118
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebugMessage
Definition: pub_message.h:96
#define SCIPdebugPrintf
Definition: pub_message.h:99
public data structures and miscellaneous methods
SCIP_Real * norms
Definition: lpi_qso.c:85
char * cstat
Definition: lpi_qso.c:83
char * rstat
Definition: lpi_qso.c:84
COLPACKET * packcstat
Definition: lpi_clp.cpp:136
ROWPACKET * packrstat
Definition: lpi_clp.cpp:137
int tbsz
Definition: lpi_qso.c:71
int * ircnt
Definition: lpi_qso.c:66
char * isen
Definition: lpi_qso.c:63
double * irhs
Definition: lpi_qso.c:64
double * irng
Definition: lpi_qso.c:65
QSprob prob
Definition: lpi_qso.c:58
double * itab
Definition: lpi_qso.c:72
int previt
Definition: lpi_qso.c:61
LPI_QSOPT_ALGO algo
Definition: lpi_qso.c:60
int solstat
Definition: lpi_cpx.c:149
int colspace
Definition: lpi_qso.c:68
int * irbeg
Definition: lpi_qso.c:67
int * iccnt
Definition: lpi_qso.c:69
SCIP_PRICING pricing
Definition: lpi_clp.cpp:112
int rowspace
Definition: lpi_qso.c:62
SCIP_MESSAGEHDLR * messagehdlr
Definition: lpi_cpx.c:185
char * iccha
Definition: lpi_qso.c:70
int pricing
Definition: lpi_qso.c:74
char * ibas
Definition: lpi_qso.c:73
@ 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_LPParam SCIP_LPPARAM
Definition: type_lpi.h:73
@ SCIP_LPPAR_PRICING
Definition: type_lpi.h:54
@ SCIP_LPPAR_LPINFO
Definition: type_lpi.h:55
@ SCIP_LPPAR_SCALING
Definition: type_lpi.h:52
@ SCIP_LPPAR_LPTILIM
Definition: type_lpi.h:61
@ SCIP_LPPAR_BARRIERCONVTOL
Definition: type_lpi.h:58
@ SCIP_LPPAR_PRESOLVING
Definition: type_lpi.h:53
@ SCIP_LPPAR_FASTMIP
Definition: type_lpi.h:51
@ 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
@ 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_WRITEERROR
Definition: type_retcode.h:46
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63