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