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