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-2015 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
123 int colpacketNum(
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
132 int rowpacketNum(
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
141 void lpistatePack(
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
157 void lpistateUnpack(
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
173 SCIP_RETCODE lpistateCreate(
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
194 void lpistateFree(
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
216 SCIP_RETCODE ensureTabMem(
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
232 SCIP_RETCODE ensureColMem(
233  SCIP_LPI* const lpi,
234  int const ncols
235  )
236 {
237  if( lpi->colspace < ncols )
238  {
239  lpi->colspace = ncols*2;
240  SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->iccnt), lpi->colspace) );
241  SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->iccha), lpi->colspace) );
242  }
243  return SCIP_OKAY;
244 }
245 
246 /** ensure size of row-related arrays */
247 static
248 SCIP_RETCODE ensureRowMem(
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) );
259  SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->ircnt), lpi->rowspace) );
260  SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->irbeg), lpi->rowspace) );
261  }
262  return SCIP_OKAY;
263 }
264 
265 /** transform lhs/rhs into qsopt format */
266 static
267 SCIP_RETCODE convertSides(
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 nrows;
2659  int ncols;
2660  int stat;
2661  register int i;
2662 
2663  assert(lpi!=NULL);
2664  assert(lpi->prob!=NULL);
2665 
2666  SCIPdebugMessage("getting basis information\n");
2667 
2668  nrows = QSget_rowcount(lpi->prob);
2669  ncols = QSget_colcount(lpi->prob);
2670 
2671  QS_CONDRET( QSget_status(lpi->prob, &stat) );
2672  if ( stat == QS_LP_UNSOLVED || stat == QS_LP_MODIFIED || stat == QS_LP_NUMERR )
2673  {
2674  QS_CONDRET( QSopt_dual(lpi->prob, &(lpi->solstat)) );
2675  }
2676 
2677  QS_CONDRET( QSget_basis_order( lpi->prob, bind) );
2678 
2679  /* transform QSopt basis header into SCIP format */
2680  for( i = 0; i < nrows; ++i )
2681  {
2682  if( bind[i] >= ncols )
2683  bind[i] = -(bind[i] - ncols - 1);
2684  }
2685 
2686  return SCIP_OKAY;
2687 }
2688 
2689 /** get dense row of inverse basis matrix B^-1
2690  *
2691  * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2692  * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2693  * see also the explanation in lpi.h.
2694  *
2695  * @todo check that the result is in terms of the LP interface definition
2696  */
2698  SCIP_LPI* lpi, /**< LP interface structure */
2699  int r, /**< row number */
2700  SCIP_Real* coef, /**< pointer to store the coefficients of the row */
2701  int* inds, /**< array to store the non-zero indices */
2702  int* ninds /**< pointer to store the number of non-zero indices
2703  * (-1: if we do not store sparsity informations) */
2704  )
2705 {
2706  int rval = 0;
2707 
2708  assert(lpi!=NULL);
2709  assert(lpi->prob!=NULL);
2710  SCIPdebugMessage("getting binv-row %d from Qsopt %d cols, %d rows, %d nonz\n", r, QSget_colcount(lpi->prob),
2711  QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob));
2712 
2713  /* can only return dense result */
2714  if ( ninds != NULL )
2715  *ninds = -1;
2716 
2717  rval = QSget_binv_row(lpi->prob, r, coef);
2718  QS_RETURN(rval);
2719 }
2720 
2721 /** get dense column of inverse basis matrix B^-1
2722  *
2723  * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2724  * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2725  * see also the explanation in lpi.h.
2726  *
2727  * @todo check that the result is in terms of the LP interface definition
2728  */
2730  SCIP_LPI* lpi, /**< LP interface structure */
2731  int c, /**< column number of B^-1; this is NOT the number of the column in the LP;
2732  * you have to call SCIPlpiGetBasisInd() to get the array which links the
2733  * B^-1 column numbers to the row and column numbers of the LP!
2734  * c must be between 0 and nrows-1, since the basis has the size
2735  * nrows * nrows */
2736  SCIP_Real* coef, /**< pointer to store the coefficients of the column */
2737  int* inds, /**< array to store the non-zero indices */
2738  int* ninds /**< pointer to store the number of non-zero indices
2739  * (-1: if we do not store sparsity informations) */
2740  )
2741 { /*lint --e{715} */
2742  assert(lpi!=NULL);
2743  assert(lpi->prob!=NULL);
2744 
2745  SCIPerrorMessage("SCIPlpiGetBInvCol() not supported by QSopt.\n");
2746 
2747  /* QSopt does not provide an interface for this yet */
2748  return SCIP_LPERROR;
2749 }
2750 
2751 /** get dense row of inverse basis matrix times constraint matrix B^-1 * A
2752  *
2753  * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2754  * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2755  * see also the explanation in lpi.h.
2756  *
2757  * @todo check that the result is in terms of the LP interface definition
2758  */
2760  SCIP_LPI* lpi, /**< LP interface structure */
2761  int r, /**< row number */
2762  const SCIP_Real* binvrow, /**< row in (A_B)^-1 from prior call to SCIPlpiGetBInvRow(), or NULL */
2763  SCIP_Real* coef, /**< vector to return coefficients */
2764  int* inds, /**< array to store the non-zero indices */
2765  int* ninds /**< pointer to store the number of non-zero indices
2766  * (-1: if we do not store sparsity informations) */
2767  )
2768 { /*lint --e{715} */
2769  int rval = 0;
2770  int ncols;
2771  int nrows;
2772 
2773  assert(lpi != NULL);
2774  assert(lpi->prob != NULL);
2775 
2776  SCIPdebugMessage("getting binva-row %d\n", r);
2777 
2778  /* can only return dense result */
2779  if ( ninds != NULL )
2780  *ninds = -1;
2781 
2782  ncols = QSget_colcount(lpi->prob);
2783  nrows = QSget_rowcount(lpi->prob);
2784 
2785  SCIP_CALL(ensureTabMem(lpi, nrows+ncols));
2786 
2787  rval = QSget_tableau_row(lpi->prob, r, lpi->itab);
2788  QS_CONDRET(rval);
2789 
2790  /* copy local information to the outside */
2791  memcpy(coef, lpi->itab, sizeof(double)*ncols);
2792 
2793  return SCIP_OKAY;
2794 }
2795 
2796 /** get dense column of inverse basis matrix times constraint matrix B^-1 * A
2797  *
2798  * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver
2799  * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated;
2800  * see also the explanation in lpi.h.
2801  *
2802  * @todo check that the result is in terms of the LP interface definition
2803  */
2805  SCIP_LPI* lpi, /**< LP interface structure */
2806  int c, /**< column number */
2807  SCIP_Real* coef, /**< vector to return coefficients */
2808  int* inds, /**< array to store the non-zero indices */
2809  int* ninds /**< pointer to store the number of non-zero indices
2810  * (-1: if we do not store sparsity informations) */
2811  )
2812 { /*lint --e{715} */
2813  assert(lpi!=NULL);
2814  assert(lpi->prob!=NULL);
2815 
2816  SCIPerrorMessage("SCIPlpiGetBInvACol() not supported by QSopt.\n");
2817 
2818  /* QSopt does not provide an interface for this yet */
2819  return SCIP_LPERROR;
2820 }
2821 
2822 /**@} */
2823 
2824 
2825 
2826 
2827 /*
2828  * LP State Methods
2829  */
2830 
2831 /**@name LP State Methods */
2832 /**@{ */
2833 
2834 /** stores LPi state (like basis information) into lpistate object */
2836  SCIP_LPI* lpi, /**< LP interface structure */
2837  BMS_BLKMEM* blkmem, /**< block memory */
2838  SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
2839  )
2840 {
2841  int ncols, nrows;
2842 
2843  assert(lpi != NULL);
2844  assert(lpi->prob != NULL);
2845  assert(blkmem != NULL);
2846  assert(lpistate != NULL);
2847 
2848  ncols = QSget_colcount(lpi->prob);
2849  nrows = QSget_rowcount(lpi->prob);
2850 
2851  assert(ncols >= 0);
2852  assert(nrows >= 0);
2853 
2854  /* allocate lpistate data */
2855  SCIP_CALL( lpistateCreate(lpistate, blkmem, ncols, nrows));
2856  SCIPdebugMessage("storing QSopt LPI state in %p (%d cols, %d rows)\n", (void*)*lpistate, ncols, nrows);
2857 
2858  /* get unpacked basis information from QSopt */
2859  SCIP_CALL( ensureColMem(lpi, ncols) );
2860  SCIP_CALL( ensureRowMem(lpi, nrows) );
2861  SCIP_CALL( SCIPlpiGetBase(lpi, lpi->iccnt, lpi->ircnt) );
2862 
2863  /* pack LPi state data */
2864  (*lpistate)->ncols = ncols;
2865  (*lpistate)->nrows = nrows;
2866  lpistatePack(*lpistate, lpi->iccnt, lpi->ircnt);
2867 
2868  return SCIP_OKAY;
2869 }
2870 
2871 /** loads LPi state (like basis information) into solver; note that the LP might have been extended with additional
2872  * columns and rows since the state was stored with SCIPlpiGetState()
2873  */
2875  SCIP_LPI* lpi, /**< LP interface structure */
2876  BMS_BLKMEM* blkmem, /**< block memory */
2877  SCIP_LPISTATE* lpistate /**< LPi state information (like basis information) */
2878  )
2879 { /*lint --e{715} */
2880  char* icstat = 0;
2881  char* irstat = 0;
2882  int i;
2883  int ncols;
2884  int nrows;
2885  int rval = 0;
2886 
2887  assert(lpi != NULL);
2888  assert(lpi->prob != NULL);
2889 
2890  /* if there was no basis information available, LPI state was not stored */
2891  if( lpistate == NULL )
2892  return SCIP_OKAY;
2893 
2894  /* continue test */
2895  ncols = QSget_colcount(lpi->prob);
2896  nrows = QSget_rowcount(lpi->prob);
2897 
2898  assert(ncols >= 0);
2899  assert(nrows >= 0);
2900  assert(lpistate->ncols <= ncols);
2901  assert(lpistate->nrows <= nrows);
2902 
2903  SCIPdebugMessage("loading LPI state %p (%d cols, %d rows) into QSopt LP with %d cols and %d rows\n", (void*)lpistate, lpistate->ncols,
2904  lpistate->nrows, ncols, nrows);
2905 
2906  if( lpistate->ncols == 0 || lpistate->nrows == 0 )
2907  return SCIP_OKAY;
2908 
2909  /* allocate enough memory for storing uncompressed basis information */
2910  SCIP_CALL( ensureColMem(lpi, ncols) );
2911  SCIP_CALL( ensureRowMem(lpi, nrows) );
2912  SCIP_CALL( ensureTabMem(lpi, nrows + ncols) );
2913 
2914  icstat = lpi->ibas;
2915  irstat = lpi->ibas + ncols;
2916 
2917  /* unpack LPi state data */
2918  lpistateUnpack(lpistate, lpi->iccnt, lpi->ircnt);
2919 
2920  /* extend the basis to the current LP beyond the previously existing columns */
2921  for( i = lpistate->ncols; i < ncols; ++i )
2922  {
2923  SCIP_Real lb;
2924  SCIP_Real ub;
2925 
2926  /* get bounds from qsopt */
2927  rval = QSget_bounds_list(lpi->prob, 1, &i, &lb, &ub);
2928  if ( SCIPlpiIsInfinity(lpi, REALABS(lb)) )
2929  {
2930  /* if lower bound is +/- infinity -> try upper bound */
2931  if ( SCIPlpiIsInfinity(lpi, REALABS(ub)) )
2932  lpi->iccnt[i] = SCIP_BASESTAT_ZERO; /* variable is free */
2933  else
2934  lpi->iccnt[i] = SCIP_BASESTAT_UPPER; /* use finite upper bound */
2935  }
2936  else
2937  lpi->iccnt[i] = SCIP_BASESTAT_LOWER; /* use finite lower bound */
2938  }
2939  for( i = lpistate->nrows; i < nrows; ++i )
2940  lpi->ircnt[i] = SCIP_BASESTAT_BASIC; /*lint !e641*/
2941 
2942  /* convert the loaded basis into QSopt format */
2943  for( i = 0; i < nrows; ++i )
2944  {
2945  switch( lpi->ircnt[i] )
2946  {
2947  case SCIP_BASESTAT_LOWER:
2948  irstat[i] = QS_ROW_BSTAT_LOWER;
2949  break;
2950  case SCIP_BASESTAT_BASIC:
2951  irstat[i] = QS_ROW_BSTAT_BASIC;
2952  break;
2953  case SCIP_BASESTAT_UPPER:
2954  irstat[i] = QS_ROW_BSTAT_UPPER;
2955  break;
2956  default:
2957  SCIPerrorMessage("Unknown row basic status %d", lpi->ircnt[i]);
2958  SCIPABORT();
2959  return SCIP_INVALIDDATA; /*lint !e527*/
2960  }
2961  }
2962  for( i = 0; i < ncols; ++i )
2963  {
2964  switch( lpi->iccnt[i] )
2965  {
2966  case SCIP_BASESTAT_LOWER:
2967  icstat[i] = QS_COL_BSTAT_LOWER;
2968  break;
2969  case SCIP_BASESTAT_BASIC:
2970  icstat[i] = QS_COL_BSTAT_BASIC;
2971  break;
2972  case SCIP_BASESTAT_UPPER:
2973  icstat[i] = QS_COL_BSTAT_UPPER;
2974  break;
2975  case SCIP_BASESTAT_ZERO:
2976  icstat[i] = QS_COL_BSTAT_FREE;
2977  break;
2978  default:
2979  SCIPerrorMessage("Unknown column basic status %d", lpi->iccnt[i]);
2980  SCIPABORT();
2981  return SCIP_INVALIDDATA; /*lint !e527*/
2982  }
2983  }
2984 
2985  /* set the basis */
2986  rval = QSload_basis_array(lpi->prob, icstat, irstat);
2987  QS_RETURN(rval);
2988 }
2989 
2990 /** clears current LPi state (like basis information) of the solver */
2992  SCIP_LPI* lpi /**< LP interface structure */
2993  )
2994 {
2995  assert(lpi != NULL);
2996 
2997  /**@todo implement SCIPlpiClearState() for QSopt */
2998  SCIPerrorMessage("QSopt interface does not implement SCIPlpiClearState()\n");
2999 
3000  return SCIP_OKAY;
3001 }
3002 
3003 /** frees LPi state information */
3005  SCIP_LPI* lpi, /**< LP interface structure */
3006  BMS_BLKMEM* blkmem, /**< block memory */
3007  SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
3008  )
3009 {
3010  assert(lpi != NULL);
3011  assert(lpistate != NULL);
3012 
3013  if( *lpistate != NULL )
3014  lpistateFree(lpistate, blkmem);
3015 
3016  return SCIP_OKAY;
3017 }
3018 
3019 /** checks, whether the given LP state contains simplex basis information */
3021  SCIP_LPI* lpi, /**< LP interface structure */
3022  SCIP_LPISTATE* lpistate /**< LP state information (like basis information) */
3023  )
3024 { /*lint --e{715} */
3025  return (lpistate != NULL);
3026 }
3027 
3028 /** reads LP state (like basis information from a file */
3030  SCIP_LPI* lpi, /**< LP interface structure */
3031  const char* fname /**< file name */
3032  )
3033 {
3034  int rval = 0;
3035 
3036  assert(lpi != NULL);
3037  assert(lpi->prob != NULL);
3038 
3039  SCIPdebugMessage("reading QSopt LP state from file <%s>\n", fname);
3040 
3041  rval = QSread_and_load_basis(lpi->prob, fname);
3042  if( rval )
3043  {
3044  SCIPerrorMessage("Error while loading basis from file <%s>.\n", fname);
3045  return SCIP_READERROR;
3046  }
3047 
3048  return SCIP_OKAY;
3049 }
3050 
3051 /** writes LP state (like basis information) to a file */
3053  SCIP_LPI* lpi, /**< LP interface structure */
3054  const char* fname /**< file name */
3055  )
3056 {
3057  QSbas bas = 0;
3058  int rval = 0;
3059 
3060  assert(lpi != NULL);
3061  assert(lpi->prob != NULL);
3062 
3063  SCIPdebugMessage("writing QSopt LP state to file <%s>\n", fname);
3064 
3065  bas = QSget_basis(lpi->prob);
3066  QS_ERROR(bas == 0, "Could not get basis from problem."); /*lint !e820*/
3067  assert(bas);
3068 
3069  rval = QSwrite_basis(lpi->prob, bas, fname);
3070  QSfree(bas);
3071  if( rval )
3072  {
3073  SCIPerrorMessage("Could not write basis to file <%s>.\n", fname);
3074  return SCIP_WRITEERROR;
3075  }
3076 
3077  return SCIP_OKAY;
3078 }
3079 
3080 /**@} */
3081 
3082 
3083 
3084 
3085 /*
3086  * LP Pricing Norms Methods
3087  */
3088 
3089 /**@name LP Pricing Norms Methods */
3090 /**@{ */
3091 
3092 /** stores LPi pricing norms information
3093  * @todo should we store norm information?
3094  */
3096  SCIP_LPI* lpi, /**< LP interface structure */
3097  BMS_BLKMEM* blkmem, /**< block memory */
3098  SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
3099  )
3100 {
3101  assert(lpinorms != NULL);
3102 
3103  (*lpinorms) = NULL;
3104 
3105  return SCIP_OKAY;
3106 }
3107 
3108 /** loads LPi pricing norms into solver; note that the LP might have been extended with additional
3109  * columns and rows since the state was stored with SCIPlpiGetNorms()
3110  */
3112  SCIP_LPI* lpi, /**< LP interface structure */
3113  BMS_BLKMEM* blkmem, /**< block memory */
3114  SCIP_LPINORMS* lpinorms /**< LPi pricing norms information */
3115  )
3116 {
3117  assert(lpinorms == NULL);
3118 
3119  /* no work necessary */
3120  return SCIP_OKAY;
3121 }
3122 
3123 /** frees pricing norms information */
3125  SCIP_LPI* lpi, /**< LP interface structure */
3126  BMS_BLKMEM* blkmem, /**< block memory */
3127  SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
3128  )
3129 {
3130  assert(lpinorms == NULL);
3131 
3132  /* no work necessary */
3133  return SCIP_OKAY;
3134 }
3135 
3136 /**@} */
3137 
3138 
3139 
3140 
3141 /*
3142  * Parameter Methods
3143  */
3144 
3145 /**@name Parameter Methods */
3146 /**@{ */
3147 
3148 /** gets integer parameter of LP */
3150  SCIP_LPI* lpi, /**< LP interface structure */
3151  SCIP_LPPARAM type, /**< parameter number */
3152  int* ival /**< buffer to store the parameter value */
3153  )
3154 {
3155  int rval = 0;
3156 
3157  assert(lpi != NULL);
3158  assert(lpi->prob != NULL);
3159  assert(ival != NULL);
3160 
3161  SCIPdebugMessage("getting int parameter %d\n", type);
3162 
3163  switch( type )
3164  {
3166  case SCIP_LPPAR_FASTMIP:
3167  case SCIP_LPPAR_PRESOLVING:
3168  return SCIP_PARAMETERUNKNOWN;
3169  case SCIP_LPPAR_SCALING:
3170  rval = QSget_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING,ival);
3171  if( *ival )
3172  *ival = TRUE;
3173  else
3174  *ival = FALSE;
3175  break;
3176  case SCIP_LPPAR_PRICING:
3177  *ival = lpi->pricing;
3178  break;
3179  case SCIP_LPPAR_LPINFO:
3180  rval = QSget_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, ival);
3181  if( *ival )
3182  *ival = TRUE;
3183  else
3184  *ival = FALSE;
3185  break;
3186  case SCIP_LPPAR_LPITLIM:
3187  rval = QSget_param(lpi->prob, QS_PARAM_SIMPLEX_MAX_ITERATIONS, ival);
3188  break;
3189  default:
3190  return SCIP_PARAMETERUNKNOWN;
3191  } /*lint !e788*/
3192 
3193  QS_RETURN(rval);
3194 }
3195 
3196 /** sets integer parameter of LP */
3198  SCIP_LPI* lpi, /**< LP interface structure */
3199  SCIP_LPPARAM type, /**< parameter number */
3200  int ival /**< parameter value */
3201  )
3202 {
3203  int rval = 0;
3204 
3205  assert(lpi != NULL);
3206  assert(lpi->prob != NULL);
3207 
3208  SCIPdebugMessage("setting int parameter %d to %d\n", type, ival);
3209 
3210  switch( type )
3211  {
3212  case SCIP_LPPAR_SCALING:
3213  if( ival == TRUE )
3214  rval = QSset_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, 1);
3215  else
3216  rval = QSset_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, 0);
3217  break;
3218  case SCIP_LPPAR_PRICING:
3219  lpi->pricing = ival;
3220  switch( ival )
3221  {
3222  case SCIP_PRICING_AUTO:
3224  case SCIP_PRICING_FULL:
3225  case SCIP_PRICING_STEEP:
3227  rval = QSset_param(lpi->prob, QS_PARAM_PRIMAL_PRICING, QS_PRICE_PSTEEP);
3228  rval += QSset_param(lpi->prob, QS_PARAM_DUAL_PRICING, QS_PRICE_DSTEEP);
3229  break;
3230  case SCIP_PRICING_PARTIAL:
3231  rval = QSset_param(lpi->prob,QS_PARAM_PRIMAL_PRICING,QS_PRICE_PMULTPARTIAL);
3232  rval += QSset_param(lpi->prob,QS_PARAM_DUAL_PRICING,QS_PRICE_DMULTPARTIAL);
3233  break;
3234  case SCIP_PRICING_DEVEX:
3235  rval = QSset_param(lpi->prob,QS_PARAM_PRIMAL_PRICING,QS_PRICE_PDEVEX);
3236  rval += QSset_param(lpi->prob,QS_PARAM_DUAL_PRICING,QS_PRICE_DDEVEX);
3237  break;
3238  default:
3239  return SCIP_LPERROR;
3240  }
3241  break;
3242  case SCIP_LPPAR_LPINFO:
3243  if( ival )
3244  rval = QSset_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, 1);
3245  else
3246  rval = QSset_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, 0);
3247  break;
3248  case SCIP_LPPAR_LPITLIM:
3249  rval = QSset_param(lpi->prob, QS_PARAM_SIMPLEX_MAX_ITERATIONS, ival);
3250  break;
3251  default:
3252  return SCIP_PARAMETERUNKNOWN;
3253  } /*lint !e788*/
3254 
3255  QS_RETURN(rval);
3256 }
3257 
3258 /** gets floating point parameter of LP */
3260  SCIP_LPI* lpi, /**< LP interface structure */
3261  SCIP_LPPARAM type, /**< parameter number */
3262  SCIP_Real* dval /**< buffer to store the parameter value */
3263  )
3264 {
3265  int rval = 0;
3266 
3267  assert(lpi != NULL);
3268  assert(lpi->prob != NULL);
3269  assert(dval != NULL);
3270 
3271  SCIPdebugMessage("getting real parameter %d\n", type);
3272 
3273  switch( type )
3274  {
3275  case SCIP_LPPAR_LOBJLIM:
3276  rval = QSget_param_double(lpi->prob, QS_PARAM_OBJLLIM, dval);
3277  break;
3278  case SCIP_LPPAR_UOBJLIM:
3279  rval = QSget_param_double(lpi->prob, QS_PARAM_OBJULIM, dval);
3280  break;
3281  case SCIP_LPPAR_LPTILIM:
3282  rval = QSget_param_double(lpi->prob, QS_PARAM_SIMPLEX_MAX_TIME, dval);
3283  break;
3284  default:
3285  case SCIP_LPPAR_MARKOWITZ:
3288  case SCIP_LPPAR_FEASTOL:
3289  return SCIP_PARAMETERUNKNOWN;
3290  } /*lint !e788*/
3291 
3292  QS_RETURN(rval);
3293 }
3294 
3295 /** sets floating point parameter of LP */
3297  SCIP_LPI* lpi, /**< LP interface structure */
3298  SCIP_LPPARAM type, /**< parameter number */
3299  SCIP_Real dval /**< parameter value */
3300  )
3301 {
3302  int rval = 0;
3303 
3304  assert(lpi != NULL);
3305  assert(lpi->prob != NULL);
3306 
3307  SCIPdebugMessage("setting real parameter %d to %g\n", type, dval);
3308 
3309  switch( type )
3310  {
3311  case SCIP_LPPAR_LPTILIM:
3312  rval = QSset_param_double(lpi->prob, QS_PARAM_SIMPLEX_MAX_TIME, dval);
3313  break;
3314  case SCIP_LPPAR_LOBJLIM:
3315  rval = QSset_param_double(lpi->prob, QS_PARAM_OBJLLIM, dval);
3316  break;
3317  case SCIP_LPPAR_UOBJLIM:
3318  rval = QSset_param_double(lpi->prob, QS_PARAM_OBJULIM, dval);
3319  break;
3320  case SCIP_LPPAR_FEASTOL:
3323  case SCIP_LPPAR_MARKOWITZ:
3324  default:
3325  return SCIP_PARAMETERUNKNOWN;
3326  } /*lint !e788*/
3327 
3328  QS_RETURN(rval);
3329 }
3330 
3331 /**@} */
3332 
3333 
3334 
3335 
3336 /*
3337  * Numerical Methods
3338  */
3339 
3340 /**@name Numerical Methods */
3341 /**@{ */
3342 
3343 /** returns value treated as infinity in the LP solver */
3345  SCIP_LPI* lpi /**< LP interface structure */
3346  )
3347 { /*lint --e{715} */
3348  return QS_MAXDOUBLE;
3349 }
3350 
3351 /** checks if given value is treated as infinity in the LP solver */
3353  SCIP_LPI* lpi, /**< LP interface structure */
3354  SCIP_Real val /**< value to be checked for infinity */
3355  )
3356 { /*lint --e{715} */
3357  return (val >= QS_MAXDOUBLE);
3358 }
3359 
3360 /**@} */
3361 
3362 
3363 
3364 
3365 /*
3366  * File Interface Methods
3367  */
3368 
3369 /**@name File Interface Methods */
3370 /**@{ */
3371 
3372 /** reads LP from a file */
3374  SCIP_LPI* lpi, /**< LP interface structure */
3375  const char* fname /**< file name */
3376  )
3377 {
3378  assert(lpi != NULL);
3379  assert(lpi->prob != NULL);
3380 
3381  SCIPdebugMessage("reading LP from file <%s>\n", fname);
3382 
3383  if( lpi->prob != NULL )
3384  QSfree_prob(lpi->prob);
3385 
3386  lpi->solstat = 0;
3387  lpi->previt = 0;
3388 
3389  lpi->prob = QSread_prob(fname, "LP");
3390  if( lpi->prob == 0 )
3391  return SCIP_READERROR;
3392 
3393  return SCIP_OKAY;
3394 }
3395 
3396 /** writes LP to a file */
3398  SCIP_LPI* lpi, /**< LP interface structure */
3399  const char* fname /**< file name */
3400  )
3401 {
3402  assert(lpi != NULL);
3403  assert(lpi->prob != NULL);
3404 
3405  SCIPdebugMessage("writing LP to file <%s>\n", fname);
3406 
3407  if( QSwrite_prob (lpi->prob, fname, "LP") )
3408  return SCIP_WRITEERROR;
3409 
3410  return SCIP_OKAY;
3411 }
3412 
3413 /**@} */
SCIP_RETCODE SCIPlpiGetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real *dval)
Definition: lpi_qso.c:3259
SCIP_Bool SCIPlpiIsPrimalFeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2084
SCIP_RETCODE SCIPlpiGetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int *ival)
Definition: lpi_qso.c:3149
enum SCIP_LPSolQuality SCIP_LPSOLQUALITY
Definition: type_lpi.h:92
SCIP_RETCODE SCIPlpiEndStrongbranch(SCIP_LPI *lpi)
Definition: lpi_qso.c:1769
SCIP_RETCODE SCIPlpiGetBInvRow(SCIP_LPI *lpi, int r, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:2697
SCIP_RETCODE SCIPlpiGetRowNames(SCIP_LPI *lpi, int firstrow, int lastrow, char **rownames, char *namestorage, int namestoragesize, int *storageleft)
Definition: lpi_qso.c:771
SCIP_Bool SCIPlpiIsTimelimExc(SCIP_LPI *lpi)
Definition: lpi_qso.c:2238
SCIP_Bool SCIPlpiExistsDualRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2101
SCIP_RETCODE SCIPlpiDelCols(SCIP_LPI *lpi, int firstcol, int lastcol)
Definition: lpi_qso.c:582
unsigned int SCIP_DUALPACKET
Definition: lpi_grb.c:83
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_qso.c:3197
enum SCIP_ObjSen SCIP_OBJSEN
Definition: type_lpi.h:36
SCIP_RETCODE SCIPlpiGetRows(SCIP_LPI *lpi, int firstrow, int lastrow, SCIP_Real *lhs, SCIP_Real *rhs, int *nnonz, int *beg, int *ind, SCIP_Real *val)
Definition: lpi_qso.c:1433
#define NULL
Definition: lpi_spx.cpp:130
SCIP_RETCODE SCIPlpiChgSides(SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
Definition: lpi_qso.c:974
#define QS_ERROR(A,...)
Definition: lpi_qso.c:79
SCIP_RETCODE SCIPlpiGetPrimalRay(SCIP_LPI *lpi, SCIP_Real *ray)
Definition: lpi_qso.c:2422
interface methods for specific LP solvers
struct SCIP_Messagehdlr SCIP_MESSAGEHDLR
Definition: type_message.h:50
#define FALSE
Definition: def.h:53
SCIP_Bool SCIPlpiIsOptimal(SCIP_LPI *lpi)
Definition: lpi_qso.c:2178
#define EPSISINT(x, eps)
Definition: def.h:161
SCIP_RETCODE SCIPlpiReadLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3373
#define TRUE
Definition: def.h:52
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_DUALPACKET COLPACKET
Definition: lpi_qso.c:31
enum SCIP_LPParam SCIP_LPPARAM
Definition: type_lpi.h:61
SCIP_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2163
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_RETCODE SCIPlpiStartStrongbranch(SCIP_LPI *lpi)
Definition: lpi_qso.c:1760
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_qso.c:933
SCIP_RETCODE SCIPlpiGetRealSolQuality(SCIP_LPI *lpi, SCIP_LPSOLQUALITY qualityindicator, SCIP_Real *quality)
Definition: lpi_qso.c:2481
SCIP_RETCODE SCIPlpiChgObj(SCIP_LPI *lpi, int ncols, int *ind, SCIP_Real *obj)
Definition: lpi_qso.c:1066
SCIP_RETCODE SCIPlpiGetIterations(SCIP_LPI *lpi, int *iterations)
Definition: lpi_qso.c:2456
SCIP_RETCODE SCIPlpiChgCoef(SCIP_LPI *lpi, int row, int col, SCIP_Real newval)
Definition: lpi_qso.c:1016
SCIP_RETCODE SCIPlpiGetSides(SCIP_LPI *lpi, int firstrow, int lastrow, SCIP_Real *lhss, SCIP_Real *rhss)
Definition: lpi_qso.c:1613
SCIP_RETCODE SCIPlpiScaleCol(SCIP_LPI *lpi, int col, SCIP_Real scaleval)
Definition: lpi_qso.c:1193
SCIP_DUALPACKET COLPACKET
Definition: lpi_clp.cpp:115
SCIP_RETCODE SCIPlpiAddCols(SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_qso.c:536
SCIP_RETCODE SCIPlpiGetBase(SCIP_LPI *lpi, int *cstat, int *rstat)
Definition: lpi_qso.c:2508
SCIP_RETCODE SCIPlpiFreeNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
Definition: lpi_qso.c:3124
SCIP_RETCODE SCIPlpiStrongbranchInt(SCIP_LPI *lpi, int col, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_qso.c:1878
SCIP_RETCODE SCIPlpiGetObjval(SCIP_LPI *lpi, SCIP_Real *objval)
Definition: lpi_qso.c:2285
SCIP_RETCODE SCIPlpiGetBounds(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *lbs, SCIP_Real *ubs)
Definition: lpi_qso.c:1583
SCIP_RETCODE SCIPlpiSetBase(SCIP_LPI *lpi, int *cstat, int *rstat)
Definition: lpi_qso.c:2580
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
Definition: lpi_qso.c:1715
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPlpiDelRowset(SCIP_LPI *lpi, int *dstat)
Definition: lpi_qso.c:858
SCIP_RETCODE SCIPlpiGetNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
Definition: lpi_qso.c:3095
#define SCIPdebugPrintf
Definition: pub_message.h:80
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_qso.c:1733
SCIP_RETCODE SCIPlpiClearState(SCIP_LPI *lpi)
Definition: lpi_qso.c:2991
SCIP_RETCODE SCIPlpiClear(SCIP_LPI *lpi)
Definition: lpi_qso.c:896
SCIP_RETCODE SCIPlpiGetCoef(SCIP_LPI *lpi, int row, int col, SCIP_Real *val)
Definition: lpi_qso.c:1683
SCIP_Bool SCIPlpiHasPrimalRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2040
SCIP_Bool SCIPlpiIsStable(SCIP_LPI *lpi)
Definition: lpi_qso.c:2193
SCIP_RETCODE SCIPlpiReadState(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3029
SCIP_DUALPACKET ROWPACKET
Definition: lpi_clp.cpp:117
struct SCIP_LPiState SCIP_LPISTATE
Definition: type_lpi.h:95
SCIP_Bool SCIPlpiIsPrimalUnbounded(SCIP_LPI *lpi)
Definition: lpi_qso.c:2054
SCIP_Bool SCIPlpiIsDualInfeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2148
#define REALABS(x)
Definition: def.h:148
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
Definition: lpi_qso.c:420
SCIP_RETCODE SCIPlpiGetObj(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *vals)
Definition: lpi_qso.c:1554
#define SCIP_CALL(x)
Definition: def.h:263
SCIP_RETCODE SCIPlpiWriteState(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3052
SCIP_RETCODE SCIPlpiGetBasisInd(SCIP_LPI *lpi, int *bind)
Definition: lpi_qso.c:2653
SCIP_Bool SCIPlpiIsInfinity(SCIP_LPI *lpi, SCIP_Real val)
Definition: lpi_qso.c:3352
SCIP_RETCODE SCIPlpiStrongbranchesFrac(SCIP_LPI *lpi, int *cols, int ncols, SCIP_Real *psols, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_qso.c:1825
SCIP_Bool SCIPlpiHasStateBasis(SCIP_LPI *lpi, SCIP_LPISTATE *lpistate)
Definition: lpi_qso.c:3020
SCIP_RETCODE SCIPlpiDelRows(SCIP_LPI *lpi, int firstrow, int lastrow)
Definition: lpi_qso.c:830
SCIP_RETCODE SCIPlpiLoadColLP(SCIP_LPI *lpi, SCIP_OBJSEN objsen, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_qso.c:460
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
Definition: lpi_qso.c:1305
public data structures and miscellaneous methods
SCIP_RETCODE SCIPlpiChgObjsen(SCIP_LPI *lpi, SCIP_OBJSEN objsen)
Definition: lpi_qso.c:1038
SCIP_RETCODE SCIPlpiFreeState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition: lpi_qso.c:3004
#define SCIP_Bool
Definition: def.h:50
SCIP_Bool SCIPlpiHasDualRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2118
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
Definition: lpi_qso.c:1288
#define QS_CONDRET(A)
Definition: lpi_qso.c:97
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
Definition: lpi_qso.c:3296
#define QS_TESTG(A, B,...)
Definition: lpi_qso.c:72
SCIP_RETCODE SCIPlpiGetBInvARow(SCIP_LPI *lpi, int r, const SCIP_Real *binvrow, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:2759
SCIP_RETCODE SCIPlpiGetSolFeasibility(SCIP_LPI *lpi, SCIP_Bool *primalfeasible, SCIP_Bool *dualfeasible)
Definition: lpi_qso.c:1998
void * SCIPlpiGetSolverPointer(SCIP_LPI *lpi)
Definition: lpi_qso.c:352
SCIP_Bool SCIPlpiWasSolved(SCIP_LPI *lpi)
Definition: lpi_qso.c:1985
SCIP_RETCODE SCIPlpiScaleRow(SCIP_LPI *lpi, int row, SCIP_Real scaleval)
Definition: lpi_qso.c:1091
#define ROWS_PER_PACKET
Definition: lpi_qso.c:34
SCIP_RETCODE SCIPlpiAddRows(SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_qso.c:643
SCIP_RETCODE SCIPlpiGetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition: lpi_qso.c:2835
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
Definition: lpi_qso.c:374
SCIP_RETCODE SCIPlpiStrongbranchFrac(SCIP_LPI *lpi, int col, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_qso.c:1778
#define COLS_PER_PACKET
Definition: lpi_qso.c:32
SCIP_Bool SCIPlpiExistsPrimalRay(SCIP_LPI *lpi)
Definition: lpi_qso.c:2023
SCIP_RETCODE SCIPlpiIgnoreInstability(SCIP_LPI *lpi, SCIP_Bool *success)
Definition: lpi_qso.c:2268
SCIP_RETCODE SCIPlpiSolveBarrier(SCIP_LPI *lpi, SCIP_Bool crossover)
Definition: lpi_qso.c:1751
SCIP_RETCODE SCIPlpiGetColNames(SCIP_LPI *lpi, int firstcol, int lastcol, char **colnames, char *namestorage, int namestoragesize, int *storageleft)
Definition: lpi_qso.c:711
SCIP_RETCODE SCIPlpiStrongbranchesInt(SCIP_LPI *lpi, int *cols, int ncols, SCIP_Real *psols, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
Definition: lpi_qso.c:1924
#define QS_RETURN(A)
Definition: lpi_qso.c:87
SCIP_RETCODE SCIPlpiDelColset(SCIP_LPI *lpi, int *dstat)
Definition: lpi_qso.c:610
SCIP_Bool SCIPlpiIsDualUnbounded(SCIP_LPI *lpi)
Definition: lpi_qso.c:2133
const char * SCIPlpiGetSolverDesc(void)
Definition: lpi_qso.c:344
public methods for message output
SCIP_RETCODE SCIPlpiSetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE *lpistate)
Definition: lpi_qso.c:2874
SCIP_RETCODE SCIPlpiGetObjsen(SCIP_LPI *lpi, SCIP_OBJSEN *objsen)
Definition: lpi_qso.c:1544
struct SCIP_LPi SCIP_LPI
Definition: type_lpi.h:94
int SCIPlpiGetInternalStatus(SCIP_LPI *lpi)
Definition: lpi_qso.c:2253
#define SCIP_Real
Definition: def.h:124
SCIP_RETCODE SCIPlpiSetNorms(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS *lpinorms)
Definition: lpi_qso.c:3111
SCIP_RETCODE SCIPlpiGetNNonz(SCIP_LPI *lpi, int *nnonz)
Definition: lpi_qso.c:1322
SCIP_RETCODE SCIPlpiGetCols(SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *lb, SCIP_Real *ub, int *nnonz, int *beg, int *ind, SCIP_Real *val)
Definition: lpi_qso.c:1341
#define SCIP_INVALID
Definition: def.h:144
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_qso.c:2069
SCIP_RETCODE SCIPlpiGetBInvACol(SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:2804
SCIP_RETCODE SCIPlpiWriteLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_qso.c:3397
SCIP_Bool SCIPlpiIsObjlimExc(SCIP_LPI *lpi)
Definition: lpi_qso.c:2208
SCIP_RETCODE SCIPlpiGetDualfarkas(SCIP_LPI *lpi, SCIP_Real *dualfarkas)
Definition: lpi_qso.c:2436
#define SCIP_ALLOC(x)
Definition: def.h:274
#define SCIPABORT()
Definition: def.h:235
SCIP_DUALPACKET ROWPACKET
Definition: lpi_qso.c:33
SCIP_Bool SCIPlpiIsIterlimExc(SCIP_LPI *lpi)
Definition: lpi_qso.c:2223
SCIP_RETCODE SCIPlpiGetBInvCol(SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
Definition: lpi_qso.c:2729
const char * SCIPlpiGetSolverName(void)
Definition: lpi_qso.c:332
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition: lpi_qso.c:3344
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
Definition: lpi_qso.c:2303