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