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