Scippy

SCIP

Solving Constraint Integer Programs

lpi_cpx.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file lpi_cpx.c
17  * @ingroup LPIS
18  * @brief LP interface for CPLEX >= 8.0
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Stefan Heinz
22  * @author Gerald Gamrath
23  * @author Ambrox Gleixner
24  * @author Marc Pfetsch
25  * @author Stefan Vigerske
26  * @author Michael Winkler
27  * @author Kati Wolter
28  */
29 
30 /* CPLEX supports FASTMIP which fastens the lp solving process but therefor it might happen that there will be a loss in
31  * precision (because e.g. the optimal basis will not be factorized again)
32  */
33 
34 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 
38 #include "cplex.h"
39 #ifndef CPX_SUBVERSION
40 #define CPX_SUBVERSION 0
41 #endif
42 #include "scip/bitencode.h"
43 #include "lpi/lpi.h"
44 #include "scip/pub_message.h"
45 
46 
47 
48 #define CHECK_ZERO(messagehdlr, x) { int _restat_; \
49  if( (_restat_ = (x)) != 0 ) \
50  { \
51  SCIPmessagePrintWarning((messagehdlr), "LP Error: CPLEX returned %d\n", _restat_); \
52  return SCIP_LPERROR; \
53  } \
54  }
55 
56 /* this macro is only called in functions returning SCIP_Bool; thus, we return FALSE if there is an error in optimized mode */
57 #define ABORT_ZERO(x) { int _restat_; \
58  if( (_restat_ = (x)) != 0 ) \
59  { \
60  SCIPerrorMessage("LP Error: CPLEX returned %d\n", _restat_); \
61  SCIPABORT(); \
62  return FALSE; \
63  } \
64  }
65 
66 #define CPX_INT_MAX 2100000000 /* CPLEX doesn't accept larger values in integer parameters */
67 
68 /* At several places we need to guarantee to have a factorization of an optimal basis and call the simplex to produce
69  * it. In a numerical perfect world, this should need no iterations. However, due to numerical inaccuracies after
70  * refactorization, it might be necessary to do a few extra pivot steps, in particular if FASTMIP is used. */
71 #define CPX_REFACTORMAXITERS 50 /* maximal number of iterations allowed for producing a refactorization of the basis */
72 
73 /* CPLEX seems to ignore bounds with absolute value less than 1e-10. There is no interface define for this constant yet,
74  * so we define it here. */
75 #define CPX_MAGICZEROCONSTANT 1e-10
76 
77 typedef SCIP_DUALPACKET COLPACKET; /* each column needs two bits of information (basic/on_lower/on_upper) */
78 #define COLS_PER_PACKET SCIP_DUALPACKETSIZE
79 typedef SCIP_DUALPACKET ROWPACKET; /* each row needs two bit of information (basic/on_lower/on_upper) */
80 #define ROWS_PER_PACKET SCIP_DUALPACKETSIZE
81 
82 /* CPLEX parameter lists which can be changed */
83 #define NUMINTPARAM 10
84 static const int intparam[NUMINTPARAM] =
85 {
86  CPX_PARAM_ADVIND,
87  CPX_PARAM_ITLIM,
88  CPX_PARAM_FASTMIP,
89  CPX_PARAM_SCAIND,
90  CPX_PARAM_PREIND,
91  CPX_PARAM_PPRIIND,
92  CPX_PARAM_DPRIIND,
93  CPX_PARAM_SIMDISPLAY,
94  CPX_PARAM_SCRIND,
95  CPX_PARAM_THREADS
96 };
97 
98 #define NUMDBLPARAM 7
99 static const int dblparam[NUMDBLPARAM] =
100 {
101  CPX_PARAM_EPRHS,
102  CPX_PARAM_EPOPT,
103  CPX_PARAM_BAREPCOMP,
104  CPX_PARAM_OBJLLIM,
105  CPX_PARAM_OBJULIM,
106  CPX_PARAM_TILIM,
107  CPX_PARAM_EPMRK
108 };
109 
110 static const double dblparammin[NUMDBLPARAM] =
111 {
112  +1e-09, /*CPX_PARAM_EPRHS*/
113  +1e-09, /*CPX_PARAM_EPOPT*/
114  +1e-12, /*CPX_PARAM_BAREPCOMP*/
115  -1e+99, /*CPX_PARAM_OBJLLIM*/
116  -1e+99, /*CPX_PARAM_OBJULIM*/
117  -1e+99, /*CPX_PARAM_TILIM*/
118  0.0001 /*CPX_PARAM_EPMRK*/
119 };
120 
121 /** CPLEX parameter settings */
122 struct SCIP_CPXParam
123 {
124  int intparval[NUMINTPARAM]; /**< integer parameter values */
125  double dblparval[NUMDBLPARAM]; /**< double parameter values */
126 };
127 typedef struct SCIP_CPXParam SCIP_CPXPARAM;
128 
129 /** LP interface */
130 struct SCIP_LPi
131 {
132  CPXENVptr cpxenv; /**< CPLEX environment */
133  SCIP_CPXPARAM defparam; /**< default CPLEX parameters */
134  SCIP_CPXPARAM curparam; /**< current CPLEX parameters in the environment */
135  CPXLPptr cpxlp; /**< CPLEX LP pointer */
136  int solstat; /**< solution status of last optimization call */
137  SCIP_CPXPARAM cpxparam; /**< current parameter values for this LP */
138  char* larray; /**< array with 'L' entries for changing lower bounds */
139  char* uarray; /**< array with 'U' entries for changing upper bounds */
140  char* senarray; /**< array for storing row senses */
141  SCIP_Real* rhsarray; /**< array for storing rhs values */
142  SCIP_Real* rngarray; /**< array for storing range values */
143  SCIP_Real* valarray; /**< array for storing coefficient values */
144  int* rngindarray; /**< array for storing row indices with range values */
145  int* cstat; /**< array for storing column basis status */
146  int* rstat; /**< array for storing row basis status */
147  int* indarray; /**< array for storing coefficient indices */
148  int boundchgsize; /**< size of larray and uarray */
149  int sidechgsize; /**< size of senarray, rngarray, and rngindarray */
150  int valsize; /**< size of valarray and indarray */
151  int cstatsize; /**< size of cstat array */
152  int rstatsize; /**< size of rstat array */
153  int iterations; /**< number of iterations used in the last solving call */
154  SCIP_PRICING pricing; /**< SCIP pricing setting */
155  SCIP_Bool solisbasic; /**< is current LP solution a basic solution? */
156  SCIP_Bool instabilityignored; /**< was the instability of the last LP ignored? */
157  SCIP_Bool fromscratch; /**< shall solves be performed with CPX_PARAM_ADVIND turned off? */
158  SCIP_Bool clearstate; /**< shall next solve be performed with CPX_PARAM_ADVIND turned off? */
159  SCIP_Real feastol; /**< feasibility tolerance for integrality */
160  SCIP_Real conditionlimit; /**< maximum condition number of LP basis counted as stable (-1.0: no limit) */
161  SCIP_Bool checkcondition; /**< should condition number of LP basis be checked for stability? */
162 #if (CPX_VERSION <= 1100)
163  SCIP_Bool rngfound; /**< was ranged row found; scaling is disabled, because there is a bug
164  * in the scaling algorithm for ranged rows in CPLEX up to version 11.0 */
165 #endif
166 #if (CPX_VERSION == 1100 || (CPX_VERSION == 1220 && (CPX_SUBVERSION == 0 || CPX_SUBVERSION == 2)))
167  int pseudonthreads; /**< number of threads that SCIP set for the LP solver, but due to CPLEX bug,
168  * we set the thread count to 1. In order to fulfill assert in lp.c,
169  * we have to return the value set by SCIP and not the real thread count */
170 #endif
171  SCIP_MESSAGEHDLR* messagehdlr; /**< messagehdlr handler to printing messages, or NULL */
172 };
173 
174 /** LPi state stores basis information */
175 struct SCIP_LPiState
176 {
177  int ncols; /**< number of LP columns */
178  int nrows; /**< number of LP rows */
179  COLPACKET* packcstat; /**< column basis status in compressed form */
180  ROWPACKET* packrstat; /**< row basis status in compressed form */
181 };
182 
183 /** LPi norms stores pricing norms */
184 struct SCIP_LPiNorms
185 {
186  int normlen; /**< number of rows for which dual norm is stored */
187  double* norm; /**< dual norms */
188  int* head; /**< row/column indices corresponding to norms */
189 };
190 
191 
192 /*
193  * dynamic memory arrays
194  */
195 
196 /** resizes larray and uarray to have at least num entries */
197 static
198 SCIP_RETCODE ensureBoundchgMem(
199  SCIP_LPI* lpi, /**< LP interface structure */
200  int num /**< minimal number of entries in array */
201  )
202 {
203  assert(lpi != NULL);
204 
205  if( num > lpi->boundchgsize )
206  {
207  int newsize;
208  int i;
209 
210  newsize = MAX(2*lpi->boundchgsize, num);
211  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->larray, newsize) );
212  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->uarray, newsize) );
213  for( i = lpi->boundchgsize; i < newsize; ++i )
214  {
215  lpi->larray[i] = 'L';
216  lpi->uarray[i] = 'U';
217  }
218  lpi->boundchgsize = newsize;
219  }
220  assert(num <= lpi->boundchgsize);
221 
222  return SCIP_OKAY;
223 }
224 
225 /** resizes senarray, rngarray, and rngindarray to have at least num entries */
226 static
227 SCIP_RETCODE ensureSidechgMem(
228  SCIP_LPI* lpi, /**< LP interface structure */
229  int num /**< minimal number of entries in array */
230  )
231 {
232  assert(lpi != NULL);
233 
234  if( num > lpi->sidechgsize )
235  {
236  int newsize;
237 
238  newsize = MAX(2*lpi->sidechgsize, num);
239  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->senarray, newsize) );
240  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->rhsarray, newsize) );
241  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->rngarray, newsize) );
242  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->rngindarray, newsize) );
243  lpi->sidechgsize = newsize;
244  }
245  assert(num <= lpi->sidechgsize);
246 
247  return SCIP_OKAY;
248 }
249 
250 /** resizes valarray and indarray to have at least num entries */
251 static
252 SCIP_RETCODE ensureValMem(
253  SCIP_LPI* lpi, /**< LP interface structure */
254  int num /**< minimal number of entries in array */
255  )
256 {
257  assert(lpi != NULL);
258 
259  if( num > lpi->valsize )
260  {
261  int newsize;
262 
263  newsize = MAX(2*lpi->valsize, num);
264  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->valarray, newsize) );
265  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->indarray, newsize) );
266  lpi->valsize = newsize;
267  }
268  assert(num <= lpi->valsize);
269 
270  return SCIP_OKAY;
271 }
272 
273 /** resizes cstat array to have at least num entries */
274 static
275 SCIP_RETCODE ensureCstatMem(
276  SCIP_LPI* lpi, /**< LP interface structure */
277  int num /**< minimal number of entries in array */
278  )
279 {
280  assert(lpi != NULL);
281 
282  if( num > lpi->cstatsize )
283  {
284  int newsize;
285 
286  newsize = MAX(2*lpi->cstatsize, num);
287  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->cstat, newsize) );
288  lpi->cstatsize = newsize;
289  }
290  assert(num <= lpi->cstatsize);
291 
292  return SCIP_OKAY;
293 }
294 
295 /** resizes rstat array to have at least num entries */
296 static
297 SCIP_RETCODE ensureRstatMem(
298  SCIP_LPI* lpi, /**< LP interface structure */
299  int num /**< minimal number of entries in array */
300  )
301 {
302  assert(lpi != NULL);
303 
304  if( num > lpi->rstatsize )
305  {
306  int newsize;
307 
308  newsize = MAX(2*lpi->rstatsize, num);
309  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->rstat, newsize) );
310  lpi->rstatsize = newsize;
311  }
312  assert(num <= lpi->rstatsize);
313 
314  return SCIP_OKAY;
315 }
316 
317 /** stores current basis in internal arrays of LPI data structure */
318 static
319 SCIP_RETCODE getBase(
320  SCIP_LPI* lpi /**< LP interface structure */
321  )
322 {
323  int ncols;
324  int nrows;
325 
326  assert(lpi != NULL);
327  assert(lpi->cpxenv != NULL);
328 
329  SCIPdebugMessage("getBase()\n");
330 
331  ncols = CPXgetnumcols(lpi->cpxenv, lpi->cpxlp);
332  nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
333 
334  /* allocate enough memory for storing uncompressed basis information */
335  SCIP_CALL( ensureCstatMem(lpi, ncols) );
336  SCIP_CALL( ensureRstatMem(lpi, nrows) );
337 
338  /* get unpacked basis information from CPLEX */
339  CHECK_ZERO( lpi->messagehdlr, CPXgetbase(lpi->cpxenv, lpi->cpxlp, lpi->cstat, lpi->rstat) );
340 
341  return SCIP_OKAY;
342 }
343 
344 /** loads basis stored in internal arrays of LPI data structure into CPLEX */
345 static
346 SCIP_RETCODE setBase(
347  SCIP_LPI* lpi /**< LP interface structure */
348  )
349 {
350  assert(lpi != NULL);
351  assert(lpi->cpxenv != NULL);
352 
353  SCIPdebugMessage("setBase()\n");
354 
355  /* load basis information into CPLEX */
356  CHECK_ZERO( lpi->messagehdlr, CPXcopybase(lpi->cpxenv, lpi->cpxlp, lpi->cstat, lpi->rstat) );
357 
358  /* because the basis status values are equally defined in SCIP and CPLEX, they don't need to be transformed */
359  assert((int)SCIP_BASESTAT_LOWER == CPX_AT_LOWER);
360  assert((int)SCIP_BASESTAT_BASIC == CPX_BASIC);
361  assert((int)SCIP_BASESTAT_UPPER == CPX_AT_UPPER);
362  assert((int)SCIP_BASESTAT_ZERO == CPX_FREE_SUPER);
363 
364  return SCIP_OKAY;
365 }
366 
367 
368 
369 
370 /*
371  * LPi state methods
372  */
373 
374 /** returns the number of packets needed to store column packet information */
375 static
376 int colpacketNum(
377  int ncols /**< number of columns to store */
378  )
379 {
380  return (ncols+(int)COLS_PER_PACKET-1)/(int)COLS_PER_PACKET;
381 }
382 
383 /** returns the number of packets needed to store row packet information */
384 static
385 int rowpacketNum(
386  int nrows /**< number of rows to store */
387  )
388 {
389  return (nrows+(int)ROWS_PER_PACKET-1)/(int)ROWS_PER_PACKET;
390 }
391 
392 /** store row and column basis status in a packed LPi state object */
393 static
394 void lpistatePack(
395  SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */
396  const int* cstat, /**< basis status of columns in unpacked format */
397  const int* rstat /**< basis status of rows in unpacked format */
398  )
399 {
400  assert(lpistate != NULL);
401  assert(lpistate->packcstat != NULL);
402  assert(lpistate->packrstat != NULL);
403 
404  SCIPencodeDualBit(cstat, lpistate->packcstat, lpistate->ncols);
405  SCIPencodeDualBit(rstat, lpistate->packrstat, lpistate->nrows);
406 }
407 
408 /** unpacks row and column basis status from a packed LPi state object */
409 static
410 void lpistateUnpack(
411  const SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */
412  int* cstat, /**< buffer for storing basis status of columns in unpacked format */
413  int* rstat /**< buffer for storing basis status of rows in unpacked format */
414  )
415 {
416  assert(lpistate != NULL);
417  assert(lpistate->packcstat != NULL);
418  assert(lpistate->packrstat != NULL);
419 
420  SCIPdecodeDualBit(lpistate->packcstat, cstat, lpistate->ncols);
421  SCIPdecodeDualBit(lpistate->packrstat, rstat, lpistate->nrows);
422 }
423 
424 /** creates LPi state information object */
425 static
426 SCIP_RETCODE lpistateCreate(
427  SCIP_LPISTATE** lpistate, /**< pointer to LPi state */
428  BMS_BLKMEM* blkmem, /**< block memory */
429  int ncols, /**< number of columns to store */
430  int nrows /**< number of rows to store */
431  )
432 {
433  assert(lpistate != NULL);
434  assert(blkmem != NULL);
435  assert(ncols >= 0);
436  assert(nrows >= 0);
437 
438  SCIP_ALLOC( BMSallocBlockMemory(blkmem, lpistate) );
439  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum(ncols)) );
440  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum(nrows)) );
441 
442  return SCIP_OKAY;
443 }
444 
445 /** frees LPi state information */
446 static
447 void lpistateFree(
448  SCIP_LPISTATE** lpistate, /**< pointer to LPi state information (like basis information) */
449  BMS_BLKMEM* blkmem /**< block memory */
450  )
451 {
452  assert(blkmem != NULL);
453  assert(lpistate != NULL);
454  assert(*lpistate != NULL);
455 
456  BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum((*lpistate)->ncols));
457  BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum((*lpistate)->nrows));
458  BMSfreeBlockMemory(blkmem, lpistate);
459 }
460 
461 
462 
463 /*
464  * local methods
465  */
466 
467 /** gets all CPLEX parameters used in LPI */
468 static
469 SCIP_RETCODE getParameterValues(
470  SCIP_LPI* lpi, /**< LP interface structure */
471  SCIP_CPXPARAM* cpxparam /**< current parameter values for this LP */
472  )
473 {
474  int i;
475 
476  assert(lpi != NULL);
477  assert(cpxparam != NULL);
478 
479  SCIPdebugMessage("getParameterValues()\n");
480 
481  for( i = 0; i < NUMINTPARAM; ++i )
482  {
483  CHECK_ZERO( lpi->messagehdlr, CPXgetintparam(lpi->cpxenv, intparam[i], &(cpxparam->intparval[i])) );
484  }
485  for( i = 0; i < NUMDBLPARAM; ++i )
486  {
487  CHECK_ZERO( lpi->messagehdlr, CPXgetdblparam(lpi->cpxenv, dblparam[i], &(cpxparam->dblparval[i])) );
488  }
489 
490  return SCIP_OKAY;
491 }
492 
493 /** in debug mode, checks validity of CPLEX parameters */
494 static
495 SCIP_RETCODE checkParameterValues(
496  SCIP_LPI*const lpi /**< LP interface structure */
497  )
498 {
499 #ifndef NDEBUG
500  SCIP_CPXPARAM par;
501  int i;
502 
503  assert(lpi != NULL);
504  assert(lpi->cpxenv != NULL);
505 
506  SCIP_CALL( getParameterValues(lpi, &par) );
507  for( i = 0; i < NUMINTPARAM; ++i )
508  assert(lpi->curparam.intparval[i] == par.intparval[i]
509  || (lpi->curparam.intparval[i] == CPX_INT_MAX && par.intparval[i] >= CPX_INT_MAX));
510  for( i = 0; i < NUMDBLPARAM; ++i )
511  assert(MAX(lpi->curparam.dblparval[i], dblparammin[i]) == par.dblparval[i]); /*lint !e777*/
512 #endif
513 
514  return SCIP_OKAY;
515 }
516 
517 /** sets all CPLEX parameters used in LPI */
518 static
519 SCIP_RETCODE setParameterValues(
520  SCIP_LPI*const lpi, /**< LP interface structure */
521  SCIP_CPXPARAM*const cpxparam /**< current parameter values for this LP */
522  )
523 {
524  int i;
525 
526  assert(lpi != NULL);
527  assert(lpi->cpxenv != NULL);
528  assert(cpxparam != NULL);
529 
530  SCIPdebugMessage("setParameterValues()\n");
531 
532  for( i = 0; i < NUMINTPARAM; ++i )
533  {
534  if( lpi->curparam.intparval[i] != cpxparam->intparval[i] )
535  {
536  SCIPdebugMessage("setting CPLEX int parameter %d from %d to %d\n",
537  intparam[i], lpi->curparam.intparval[i], cpxparam->intparval[i]);
538  lpi->curparam.intparval[i] = cpxparam->intparval[i];
539  CHECK_ZERO( lpi->messagehdlr, CPXsetintparam(lpi->cpxenv, intparam[i], lpi->curparam.intparval[i]) );
540  }
541  }
542  for( i = 0; i < NUMDBLPARAM; ++i )
543  {
544  if( lpi->curparam.dblparval[i] != cpxparam->dblparval[i] ) /*lint !e777*/
545  {
546  SCIPdebugMessage("setting CPLEX dbl parameter %d from %g to %g\n",
547  dblparam[i], lpi->curparam.dblparval[i], MAX(cpxparam->dblparval[i], dblparammin[i]));
548  lpi->curparam.dblparval[i] = MAX(cpxparam->dblparval[i], dblparammin[i]);
549  CHECK_ZERO( lpi->messagehdlr, CPXsetdblparam(lpi->cpxenv, dblparam[i], lpi->curparam.dblparval[i]) );
550  }
551  }
552 
553  SCIP_CALL( checkParameterValues(lpi) );
554 
555  return SCIP_OKAY;
556 }
557 
558 /** copies CPLEX parameters from source to dest */
559 static
560 void copyParameterValues(
561  SCIP_CPXPARAM* dest, /**< CPLEX parameters to copy to */
562  SCIP_CPXPARAM*const source /**< CPLEX parameters which will be copied */
563  )
564 {
565  int i;
566 
567  for( i = 0; i < NUMINTPARAM; ++i )
568  dest->intparval[i] = source->intparval[i];
569  for( i = 0; i < NUMDBLPARAM; ++i )
570  dest->dblparval[i] = source->dblparval[i];
571 }
572 
573 /** gets a single integer parameter value */
574 static
575 int getIntParam(
576  SCIP_LPI* lpi, /**< LP interface structure */
577  int const param /**< parameter to get value for */
578  )
579 {
580  int i;
581 
582  assert(lpi != NULL);
583 
584  for( i = 0; i < NUMINTPARAM; ++i )
585  {
586  if( intparam[i] == param )
587  return lpi->cpxparam.intparval[i];
588  }
589 
590  SCIPerrorMessage("unknown CPLEX integer parameter\n");
591  SCIPABORT();
592  return 0; /*lint !e527*/
593 }
594 
595 /** gets a single double parameter value */
596 static
597 double getDblParam(
598  SCIP_LPI* lpi, /**< LP interface structure */
599  int const param /**< parameter to get value for */
600  )
601 {
602  SCIP_Real val;
603  int i;
604 
605  assert(lpi != NULL);
606 
607  for( i = 0; i < NUMDBLPARAM; ++i )
608  {
609  if( dblparam[i] == param )
610  {
611  val = lpi->cpxparam.dblparval[i];
612  if( val >= CPX_INFBOUND )
613  return CPX_INFBOUND;
614  else if( val <= -CPX_INFBOUND )
615  return -CPX_INFBOUND;
616  else
617  return val;
618  }
619  }
620 
621  SCIPerrorMessage("unknown CPLEX double parameter\n");
622  SCIPABORT();
623  return 0.0; /*lint !e527*/
624 }
625 
626 /** sets a single integer parameter value */
627 static
628 void setIntParam(
629  SCIP_LPI* lpi, /**< LP interface structure */
630  int const param, /**< parameter to set value */
631  int const parval /**< new value for parameter */
632  )
633 {
634  int i;
635 
636  assert(lpi != NULL);
637 
638  for( i = 0; i < NUMINTPARAM; ++i )
639  {
640  if( intparam[i] == param )
641  {
642  lpi->cpxparam.intparval[i] = parval;
643  return;
644  }
645  }
646 
647  SCIPerrorMessage("unknown CPLEX integer parameter\n");
648  SCIPABORT();
649 }
650 
651 /** sets a single double parameter value */
652 static
653 void setDblParam(
654  SCIP_LPI* lpi, /**< LP interface structure */
655  int const param, /**< parameter to set value */
656  double parval /**< new value for parameter */
657  )
658 {
659  int i;
660 
661  assert(lpi != NULL);
662 
663  if( parval >= CPX_INFBOUND )
664  parval = 1e+75;
665  else if( parval <= -CPX_INFBOUND )
666  parval = -1e+75;
667 
668  for( i = 0; i < NUMDBLPARAM; ++i )
669  {
670  if( dblparam[i] == param )
671  {
672  lpi->cpxparam.dblparval[i] = parval;
673  return;
674  }
675  }
676 
677  SCIPerrorMessage("unknown CPLEX double parameter\n");
678  SCIPABORT();
679 }
680 
681 /** marks the current LP to be unsolved */
682 static
683 void invalidateSolution(
684  SCIP_LPI* const lpi /**< LP interface structure */
685  )
686 {
687  assert(lpi != NULL);
688  lpi->solstat = -1;
689  lpi->instabilityignored = FALSE;
690 }
691 
692 /** converts SCIP's objective sense into CPLEX's objective sense */
693 static
694 int cpxObjsen(
695  SCIP_OBJSEN const objsen /**< objective sense */
696  )
697 {
698  switch( objsen )
699  {
700  case SCIP_OBJSEN_MAXIMIZE:
701  return CPX_MAX;
702  case SCIP_OBJSEN_MINIMIZE:
703  return CPX_MIN;
704  default:
705  SCIPerrorMessage("invalid objective sense\n");
706  SCIPABORT();
707  return 0; /*lint !e527*/
708  }
709 }
710 
711 /** converts SCIP's lhs/rhs pairs into CPLEX's sen/rhs/rng */
712 static
713 void convertSides(
714  SCIP_LPI* lpi, /**< LP interface structure */
715  int nrows, /**< number of rows */
716  const SCIP_Real* lhs, /**< left hand side vector */
717  const SCIP_Real* rhs, /**< right hand side vector */
718  int indoffset, /**< index of first row in LP */
719  int* rngcount /**< pointer to store the number of range rows */
720  )
721 {
722  int i;
723 
724  assert(lpi != NULL);
725  assert(nrows >= 0);
726  assert(lhs != NULL);
727  assert(rhs != NULL);
728  assert(rngcount != NULL);
729 
730  /* convert lhs/rhs into sen/rhs/rng */
731  *rngcount = 0;
732  for( i = 0; i < nrows; ++i )
733  {
734  assert(lhs[i] <= rhs[i]);
735  if( lhs[i] == rhs[i] ) /*lint !e777*/
736  {
737  assert(-CPX_INFBOUND < rhs[i] && rhs[i] < CPX_INFBOUND);
738  lpi->senarray[i] = 'E';
739  lpi->rhsarray[i] = rhs[i];
740  }
741  else if( lhs[i] <= -CPX_INFBOUND )
742  {
743  assert(-CPX_INFBOUND < rhs[i] && rhs[i] < CPX_INFBOUND);
744  lpi->senarray[i] = 'L';
745  lpi->rhsarray[i] = rhs[i];
746  }
747  else if( rhs[i] >= CPX_INFBOUND )
748  {
749  assert(-CPX_INFBOUND < lhs[i] && lhs[i] < CPX_INFBOUND);
750  lpi->senarray[i] = 'G';
751  lpi->rhsarray[i] = lhs[i];
752  }
753  else
754  {
755  /* CPLEX defines a ranged row to be within rhs and rhs+rng.
756  * -> To keep SCIP's meaning of the rhs value, we would like to use negative range values: rng := lhs - rhs,
757  * but there seems to be a bug in CPLEX's presolve with negative range values:
758  * the ranged row
759  * 0 <= -x <= 100000 with x >= 0 (rhs=0, rng=-100000)
760  * would lead to the CPLEX row
761  * -x -Rg = 100000
762  * Rg = 0
763  * instead of the correct presolving implication Rg = -100000.
764  * -> Because of this bug, we have to use an additional rhsarray[] for the converted right hand sides and
765  * use rhsarray[i] = lhs[i] and rngarray[i] = rhs[i] - lhs[i] for ranged rows to keep the range values
766  * non-negative.
767  */
768  lpi->senarray[i] = 'R';
769  lpi->rhsarray[i] = lhs[i];
770  lpi->rngarray[*rngcount] = rhs[i] - lhs[i];
771  lpi->rngindarray[*rngcount] = i + indoffset;
772  (*rngcount)++;
773  }
774  }
775 }
776 
777 /** converts CPLEX's sen/rhs/rng triplets into SCIP's lhs/rhs pairs */
778 static
779 void reconvertBothSides(
780  SCIP_LPI* lpi, /**< LP interface structure */
781  int nrows, /**< number of rows */
782  SCIP_Real* lhs, /**< buffer to store the left hand side vector */
783  SCIP_Real* rhs /**< buffer to store the right hand side vector */
784  )
785 {
786  int i;
787 
788  assert(lpi != NULL);
789  assert(nrows >= 0);
790  assert(lhs != NULL);
791  assert(rhs != NULL);
792 
793  for( i = 0; i < nrows; ++i )
794  {
795  switch( lpi->senarray[i] )
796  {
797  case 'E':
798  lhs[i] = lpi->rhsarray[i];
799  rhs[i] = lpi->rhsarray[i];
800  break;
801 
802  case 'L':
803  lhs[i] = -CPX_INFBOUND;
804  rhs[i] = lpi->rhsarray[i];
805  break;
806 
807  case 'G':
808  lhs[i] = lpi->rhsarray[i];
809  rhs[i] = CPX_INFBOUND;
810  break;
811 
812  case 'R':
813  assert(lpi->rngarray[i] != 0.0);
814  if( lpi->rngarray[i] > 0.0 )
815  {
816  lhs[i] = lpi->rhsarray[i];
817  rhs[i] = lpi->rhsarray[i] + lpi->rngarray[i];
818  }
819  else
820  {
821  lhs[i] = lpi->rhsarray[i] + lpi->rngarray[i];
822  rhs[i] = lpi->rhsarray[i];
823  }
824  break;
825 
826  default:
827  SCIPerrorMessage("invalid row sense\n");
828  SCIPABORT();
829  }
830  assert(lhs[i] <= rhs[i]);
831  }
832 }
833 
834 /** converts CPLEX's sen/rhs/rng triplets into SCIP's lhs/rhs pairs, only storing the left hand side */
835 static
836 void reconvertLhs(
837  SCIP_LPI* lpi, /**< LP interface structure */
838  int nrows, /**< number of rows */
839  SCIP_Real* lhs /**< buffer to store the left hand side vector */
840  )
841 {
842  int i;
843 
844  assert(lpi != NULL);
845  assert(nrows >= 0);
846  assert(lhs != NULL);
847 
848  for( i = 0; i < nrows; ++i )
849  {
850  switch( lpi->senarray[i] )
851  {
852  case 'E':
853  assert(lpi->rngarray[i] == 0.0);
854  lhs[i] = lpi->rhsarray[i];
855  break;
856 
857  case 'L':
858  assert(lpi->rngarray[i] == 0.0);
859  lhs[i] = -CPX_INFBOUND;
860  break;
861 
862  case 'G':
863  assert(lpi->rngarray[i] == 0.0);
864  lhs[i] = lpi->rhsarray[i];
865  break;
866 
867  case 'R':
868  assert(lpi->rngarray[i] != 0.0);
869  if( lpi->rngarray[i] > 0.0 )
870  lhs[i] = lpi->rhsarray[i];
871  else
872  lhs[i] = lpi->rhsarray[i] + lpi->rngarray[i];
873  break;
874 
875  default:
876  SCIPerrorMessage("invalid row sense\n");
877  SCIPABORT();
878  }
879  }
880 }
881 
882 /** converts CPLEX's sen/rhs/rng triplets into SCIP's lhs/rhs pairs, only storing the right hand side */
883 static
884 void reconvertRhs(
885  SCIP_LPI* lpi, /**< LP interface structure */
886  int nrows, /**< number of rows */
887  SCIP_Real* rhs /**< buffer to store the right hand side vector */
888  )
889 {
890  int i;
891 
892  assert(lpi != NULL);
893  assert(nrows >= 0);
894  assert(rhs != NULL);
895 
896  for( i = 0; i < nrows; ++i )
897  {
898  switch( lpi->senarray[i] )
899  {
900  case 'E':
901  assert(lpi->rngarray[i] == 0.0);
902  rhs[i] = lpi->rhsarray[i];
903  break;
904 
905  case 'L':
906  assert(lpi->rngarray[i] == 0.0);
907  rhs[i] = lpi->rhsarray[i];
908  break;
909 
910  case 'G':
911  assert(lpi->rngarray[i] == 0.0);
912  rhs[i] = CPX_INFBOUND;
913  break;
914 
915  case 'R':
916  assert(lpi->rngarray[i] != 0.0);
917  if( lpi->rngarray[i] > 0.0 )
918  rhs[i] = lpi->rhsarray[i] + lpi->rngarray[i];
919  else
920  rhs[i] = lpi->rhsarray[i];
921  break;
922 
923  default:
924  SCIPerrorMessage("invalid row sense\n");
925  SCIPABORT();
926  }
927  }
928 }
929 
930 /** converts CPLEX's sen/rhs/rng triplets into SCIP's lhs/rhs pairs */
931 static
932 void reconvertSides(
933  SCIP_LPI* lpi, /**< LP interface structure */
934  int nrows, /**< number of rows */
935  SCIP_Real* lhs, /**< buffer to store the left hand side vector, or NULL */
936  SCIP_Real* rhs /**< buffer to store the right hand side vector, or NULL */
937  )
938 {
939  if( lhs != NULL && rhs != NULL )
940  reconvertBothSides(lpi, nrows, lhs, rhs);
941  else if( lhs != NULL )
942  reconvertLhs(lpi, nrows, lhs);
943  else if( rhs != NULL )
944  reconvertRhs(lpi, nrows, rhs);
945 }
946 
947 
948 /** after restoring the old lp data in CPLEX we need to resolve the lp to be able to retrieve correct information */
949 static
950 SCIP_RETCODE restoreLPData(
951  SCIP_LPI* lpi /**< LP interface structure */
952  )
953 {
954  assert(lpi != NULL);
955 
956  /* modifying the LP, restoring the old LP, and loading the old basis is not enough for CPLEX to be able to return the
957  * basis -> we have to resolve the LP;
958  *
959  * this may happen after manual strong branching on an integral variable, or after conflict analysis on a strong
960  * branching conflict created a constraint that is not able to modify the LP but trigger the additional call of the
961  * separators, in particular, the Gomory separator
962  *
963  * In a numerical perfect world, CPX_REFACTORMAXITERS below should be zero. However, due to numerical inaccuracies
964  * after refactorization, it might be necessary to do a few extra pivot steps.
965  */
966  CHECK_ZERO( lpi->messagehdlr, CPXdualopt(lpi->cpxenv, lpi->cpxlp) );
967 #ifndef NDEBUG
968  if ( CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp) > CPX_REFACTORMAXITERS )
969  SCIPmessagePrintWarning(lpi->messagehdlr, "CPLEX needed %d phase 1 iterations to restore optimal basis.\n", CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp));
970  if ( CPXgetitcnt(lpi->cpxenv, lpi->cpxlp) > CPX_REFACTORMAXITERS )
971  SCIPmessagePrintWarning(lpi->messagehdlr, "CPLEX needed %d iterations to restore optimal basis.\n", CPXgetitcnt(lpi->cpxenv, lpi->cpxlp));
972 #endif
973 
974  return SCIP_OKAY;
975 }
976 
977 
978 /*
979  * LP Interface Methods
980  */
981 
982 
983 /*
984  * Miscellaneous Methods
985  */
986 
987 static char cpxname[100];
988 
989 /**@name Miscellaneous Methods */
990 /**@{ */
991 
992 /** gets name and version of LP solver */
993 const char* SCIPlpiGetSolverName(
994  void
995  )
996 {
997 #ifdef CPX_VERSION_VERSION
998  sprintf(cpxname, "CPLEX %d.%d.%d.%d", CPX_VERSION_VERSION, CPX_VERSION_RELEASE, CPX_VERSION_MODIFICATION, CPX_VERSION_FIX);
999 #else
1000  sprintf(cpxname, "CPLEX %d.%d.%d.%d", CPX_VERSION/100, (CPX_VERSION%100)/10, CPX_VERSION%10, CPX_SUBVERSION);
1001 #endif
1002  return cpxname;
1003 }
1004 
1005 /** gets description of LP solver (developer, webpage, ...) */
1006 const char* SCIPlpiGetSolverDesc(
1007  void
1008  )
1009 {
1010  return "Linear Programming Solver developed by IBM (www.cplex.com)";
1011 }
1012 
1013 /** gets pointer for LP solver - use only with great care
1014  *
1015  * Here we return the pointer to the LP environment.
1016  */
1017 void* SCIPlpiGetSolverPointer(
1018  SCIP_LPI* lpi /**< pointer to an LP interface structure */
1019  )
1020 {
1021  return (void*) lpi->cpxlp;
1022 }
1023 /**@} */
1024 
1025 
1026 
1027 
1028 /*
1029  * LPI Creation and Destruction Methods
1030  */
1031 
1032 /**@name LPI Creation and Destruction Methods */
1033 /**@{ */
1034 
1035 /** creates an LP problem object */
1036 SCIP_RETCODE SCIPlpiCreate(
1037  SCIP_LPI** lpi, /**< pointer to an LP interface structure */
1038  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler to use for printing messages, or NULL */
1039  const char* name, /**< problem name */
1040  SCIP_OBJSEN objsen /**< objective sense */
1041  )
1042 {
1043  int restat;
1044 
1045  assert(sizeof(SCIP_Real) == sizeof(double)); /* CPLEX only works with doubles as floating points */
1046  assert(sizeof(SCIP_Bool) == sizeof(int)); /* CPLEX only works with ints as bools */
1047  assert(lpi != NULL);
1048 
1049  SCIPdebugMessage("SCIPlpiCreate()\n");
1050 
1051  SCIP_ALLOC( BMSallocMemory(lpi) );
1052 
1053  /* create environment */
1054  (*lpi)->cpxenv = CPXopenCPLEX(&restat);
1055  CHECK_ZERO( messagehdlr, restat );
1056 
1057 #if (CPX_VERSION == 1100 || (CPX_VERSION == 1220 && (CPX_SUBVERSION == 0 || CPX_SUBVERSION == 2)))
1058  /* manually set number of threads to 1 to avoid huge system load due to CPLEX bug (version 1100) or segmentation fault (version 1220) */
1059  CHECK_ZERO( messagehdlr, CPXsetintparam((*lpi)->cpxenv, CPX_PARAM_THREADS, 1) );
1060 #endif
1061 
1062 #if 0 /* turning presolve off seems to be faster than turning it off on demand (if presolve detects infeasibility) */
1063  /* turn presolve off, s.t. for an infeasible problem, a ray is always available */
1064  CHECK_ZERO( messagehdlr, CPXsetintparam((*lpi)->cpxenv, CPX_PARAM_PREIND, CPX_OFF) );
1065 #endif
1066 
1067  /* get default parameter values */
1068  SCIP_CALL( getParameterValues((*lpi), &((*lpi)->defparam)) );
1069  copyParameterValues(&((*lpi)->curparam), &((*lpi)->defparam));
1070 
1071  /* create LP */
1072  (*lpi)->larray = NULL;
1073  (*lpi)->uarray = NULL;
1074  (*lpi)->senarray = NULL;
1075  (*lpi)->rhsarray = NULL;
1076  (*lpi)->rngarray = NULL;
1077  (*lpi)->valarray = NULL;
1078  (*lpi)->rngindarray = NULL;
1079  (*lpi)->cstat = NULL;
1080  (*lpi)->rstat = NULL;
1081  (*lpi)->indarray = NULL;
1082  (*lpi)->boundchgsize = 0;
1083  (*lpi)->sidechgsize = 0;
1084  (*lpi)->valsize = 0;
1085  (*lpi)->cstatsize = 0;
1086  (*lpi)->rstatsize = 0;
1087  (*lpi)->iterations = 0;
1088  (*lpi)->pricing = SCIP_PRICING_LPIDEFAULT;
1089  (*lpi)->solisbasic = FALSE;
1090  (*lpi)->cpxlp = CPXcreateprob((*lpi)->cpxenv, &restat, name);
1091  (*lpi)->instabilityignored = FALSE;
1092  (*lpi)->fromscratch = FALSE;
1093  (*lpi)->clearstate = FALSE;
1094  (*lpi)->feastol = 1e-06;
1095  (*lpi)->conditionlimit = -1.0;
1096  (*lpi)->checkcondition = FALSE;
1097 #if (CPX_VERSION <= 1100)
1098  (*lpi)->rngfound = FALSE;
1099 #endif
1100  (*lpi)->messagehdlr = messagehdlr;
1101 
1102  CHECK_ZERO( messagehdlr, restat );
1103  invalidateSolution(*lpi);
1104  copyParameterValues(&((*lpi)->cpxparam), &((*lpi)->defparam));
1105 
1106  /* set objective sense */
1107  SCIP_CALL( SCIPlpiChgObjsen(*lpi, objsen) );
1108 
1109  /* set default pricing */
1110  SCIP_CALL( SCIPlpiSetIntpar(*lpi, SCIP_LPPAR_PRICING, (int)(*lpi)->pricing) );
1111 
1112  return SCIP_OKAY;
1113 }
1114 
1115 /** deletes an LP problem object */
1116 SCIP_RETCODE SCIPlpiFree(
1117  SCIP_LPI** lpi /**< pointer to an LP interface structure */
1118  )
1119 {
1120  assert(lpi != NULL);
1121  assert(*lpi != NULL);
1122  assert((*lpi)->cpxenv != NULL);
1123 
1124  SCIPdebugMessage("SCIPlpiFree()\n");
1125 
1126  /* free LP */
1127  CHECK_ZERO( (*lpi)->messagehdlr, CPXfreeprob((*lpi)->cpxenv, &((*lpi)->cpxlp)) );
1128 
1129  /* free memory */
1130  BMSfreeMemoryArrayNull(&(*lpi)->larray);
1131  BMSfreeMemoryArrayNull(&(*lpi)->uarray);
1132  BMSfreeMemoryArrayNull(&(*lpi)->senarray);
1133  BMSfreeMemoryArrayNull(&(*lpi)->rhsarray);
1134  BMSfreeMemoryArrayNull(&(*lpi)->rngarray);
1135  BMSfreeMemoryArrayNull(&(*lpi)->rngindarray);
1136  BMSfreeMemoryArrayNull(&(*lpi)->cstat);
1137  BMSfreeMemoryArrayNull(&(*lpi)->rstat);
1138 
1139  /* free environment */
1140  CHECK_ZERO( (*lpi)->messagehdlr, CPXcloseCPLEX(&((*lpi)->cpxenv)) );
1141 
1142  BMSfreeMemory(lpi);
1143 
1144  return SCIP_OKAY;
1145 }
1146 
1147 /**@} */
1148 
1149 
1150 
1151 
1152 /*
1153  * Modification Methods
1154  */
1155 
1156 /**@name Modification Methods */
1157 /**@{ */
1158 
1159 /** copies LP data with column matrix into LP solver */
1160 SCIP_RETCODE SCIPlpiLoadColLP(
1161  SCIP_LPI* lpi, /**< LP interface structure */
1162  SCIP_OBJSEN objsen, /**< objective sense */
1163  int ncols, /**< number of columns */
1164  const SCIP_Real* obj, /**< objective function values of columns */
1165  const SCIP_Real* lb, /**< lower bounds of columns */
1166  const SCIP_Real* ub, /**< upper bounds of columns */
1167  char** colnames, /**< column names, or NULL */
1168  int nrows, /**< number of rows */
1169  const SCIP_Real* lhs, /**< left hand sides of rows */
1170  const SCIP_Real* rhs, /**< right hand sides of rows */
1171  char** rownames, /**< row names, or NULL */
1172  int nnonz, /**< number of nonzero elements in the constraint matrix */
1173  const int* beg, /**< start index of each column in ind- and val-array */
1174  const int* ind, /**< row indices of constraint matrix entries */
1175  const SCIP_Real* val /**< values of constraint matrix entries */
1176  )
1177 {
1178  int* cnt;
1179  int rngcount;
1180  int c;
1181 
1182  assert(lpi != NULL);
1183  assert(lpi->cpxlp != NULL);
1184  assert(lpi->cpxenv != NULL);
1185 
1186  SCIPdebugMessage("loading LP in column format into CPLEX: %d cols, %d rows\n", ncols, nrows);
1187 
1188  invalidateSolution(lpi);
1189 
1190  SCIP_CALL( ensureSidechgMem(lpi, nrows) );
1191 
1192  /* convert lhs/rhs into sen/rhs/range tuples */
1193  convertSides(lpi, nrows, lhs, rhs, 0, &rngcount);
1194 
1195  /* calculate column lengths */
1196  SCIP_ALLOC( BMSallocMemoryArray(&cnt, ncols) );
1197  for( c = 0; c < ncols-1; ++c )
1198  {
1199  cnt[c] = beg[c+1] - beg[c];
1200  assert(cnt[c] >= 0);
1201  }
1202  cnt[ncols-1] = nnonz - beg[ncols-1];
1203  assert(cnt[ncols-1] >= 0);
1204 
1205  /* copy data into CPLEX */
1206  CHECK_ZERO( lpi->messagehdlr, CPXcopylpwnames(lpi->cpxenv, lpi->cpxlp, ncols, nrows, cpxObjsen(objsen), obj,
1207  lpi->rhsarray, lpi->senarray, beg, cnt, ind, val, lb, ub, lpi->rngarray, colnames, rownames) );
1208 
1209  /* free temporary memory */
1210  BMSfreeMemoryArray(&cnt);
1211 
1212  assert(CPXgetnumcols(lpi->cpxenv, lpi->cpxlp) == ncols);
1213  assert(CPXgetnumrows(lpi->cpxenv, lpi->cpxlp) == nrows);
1214  assert(CPXgetnumnz(lpi->cpxenv, lpi->cpxlp) == nnonz);
1215 
1216  return SCIP_OKAY;
1217 }
1218 
1219 /** adds columns to the LP */
1220 SCIP_RETCODE SCIPlpiAddCols(
1221  SCIP_LPI* lpi, /**< LP interface structure */
1222  int ncols, /**< number of columns to be added */
1223  const SCIP_Real* obj, /**< objective function values of new columns */
1224  const SCIP_Real* lb, /**< lower bounds of new columns */
1225  const SCIP_Real* ub, /**< upper bounds of new columns */
1226  char** colnames, /**< column names, or NULL */
1227  int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
1228  const int* beg, /**< start index of each column in ind- and val-array, or NULL if nnonz == 0 */
1229  const int* ind, /**< row indices of constraint matrix entries, or NULL if nnonz == 0 */
1230  const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
1231  )
1232 {
1233  assert(lpi != NULL);
1234  assert(lpi->cpxlp != NULL);
1235  assert(lpi->cpxenv != NULL);
1236 
1237  SCIPdebugMessage("adding %d columns with %d nonzeros to CPLEX\n", ncols, nnonz);
1238 
1239  invalidateSolution(lpi);
1240 
1241  if( nnonz > 0 )
1242  {
1243  CHECK_ZERO( lpi->messagehdlr, CPXaddcols(lpi->cpxenv, lpi->cpxlp, ncols, nnonz, obj, beg, ind, val, lb, ub, colnames) );
1244  }
1245  else
1246  {
1247  CHECK_ZERO( lpi->messagehdlr, CPXnewcols(lpi->cpxenv, lpi->cpxlp, ncols, obj, lb, ub, NULL, colnames) );
1248  }
1249 
1250  return SCIP_OKAY;
1251 }
1252 
1253 /** deletes all columns in the given range from LP */
1254 SCIP_RETCODE SCIPlpiDelCols(
1255  SCIP_LPI* lpi, /**< LP interface structure */
1256  int firstcol, /**< first column to be deleted */
1257  int lastcol /**< last column to be deleted */
1258  )
1259 {
1260  assert(lpi != NULL);
1261  assert(lpi->cpxlp != NULL);
1262  assert(lpi->cpxenv != NULL);
1263  assert(0 <= firstcol && firstcol <= lastcol && lastcol < CPXgetnumcols(lpi->cpxenv, lpi->cpxlp));
1264 
1265  SCIPdebugMessage("deleting %d columns from CPLEX\n", lastcol - firstcol + 1);
1266 
1267  invalidateSolution(lpi);
1268 
1269  CHECK_ZERO( lpi->messagehdlr, CPXdelcols(lpi->cpxenv, lpi->cpxlp, firstcol, lastcol) );
1270 
1271  return SCIP_OKAY;
1272 }
1273 
1274 /** deletes columns from SCIP_LP; the new position of a column must not be greater that its old position */
1275 SCIP_RETCODE SCIPlpiDelColset(
1276  SCIP_LPI* lpi, /**< LP interface structure */
1277  int* dstat /**< deletion status of columns
1278  * input: 1 if column should be deleted, 0 if not
1279  * output: new position of column, -1 if column was deleted */
1280  )
1281 {
1282  assert(lpi != NULL);
1283  assert(lpi->cpxlp != NULL);
1284  assert(lpi->cpxenv != NULL);
1285 
1286  SCIPdebugMessage("deleting a column set from CPLEX\n");
1287 
1288  invalidateSolution(lpi);
1289 
1290  CHECK_ZERO( lpi->messagehdlr, CPXdelsetcols(lpi->cpxenv, lpi->cpxlp, dstat) );
1291 
1292  return SCIP_OKAY;
1293 }
1294 
1295 /** adds rows to the LP */
1296 SCIP_RETCODE SCIPlpiAddRows(
1297  SCIP_LPI* lpi, /**< LP interface structure */
1298  int nrows, /**< number of rows to be added */
1299  const SCIP_Real* lhs, /**< left hand sides of new rows */
1300  const SCIP_Real* rhs, /**< right hand sides of new rows */
1301  char** rownames, /**< row names, or NULL */
1302  int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
1303  const int* beg, /**< start index of each row in ind- and val-array, or NULL if nnonz == 0 */
1304  const int* ind, /**< column indices of constraint matrix entries, or NULL if nnonz == 0 */
1305  const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
1306  )
1307 {
1308  int rngcount;
1309 
1310  assert(lpi != NULL);
1311  assert(lpi->cpxlp != NULL);
1312  assert(lpi->cpxenv != NULL);
1313 
1314  SCIPdebugMessage("adding %d rows with %d nonzeros to CPLEX\n", nrows, nnonz);
1315 
1316  invalidateSolution(lpi);
1317 
1318  SCIP_CALL( ensureSidechgMem(lpi, nrows) );
1319 
1320  /* convert lhs/rhs into sen/rhs/range tuples */
1321  convertSides(lpi, nrows, lhs, rhs, CPXgetnumrows(lpi->cpxenv, lpi->cpxlp), &rngcount);
1322 
1323  /* add rows to LP */
1324  if( nnonz > 0 )
1325  {
1326  CHECK_ZERO( lpi->messagehdlr, CPXaddrows(lpi->cpxenv, lpi->cpxlp, 0, nrows, nnonz, lpi->rhsarray, lpi->senarray, beg, ind, val, NULL,
1327  rownames) );
1328  }
1329  else
1330  {
1331  CHECK_ZERO( lpi->messagehdlr, CPXnewrows(lpi->cpxenv, lpi->cpxlp, nrows, lpi->rhsarray, lpi->senarray, NULL, rownames) );
1332  }
1333  if( rngcount > 0 )
1334  {
1335 #if (CPX_VERSION <= 1100)
1336  if( lpi->rngfound == FALSE )
1337  {
1338  SCIP_CALL( SCIPlpiSetIntpar(lpi, SCIP_LPPAR_SCALING, FALSE) );
1339  lpi->rngfound = TRUE;
1340  }
1341 #endif
1342  CHECK_ZERO( lpi->messagehdlr, CPXchgrngval(lpi->cpxenv, lpi->cpxlp, rngcount, lpi->rngindarray, lpi->rngarray) );
1343  }
1344 
1345  return SCIP_OKAY;
1346 }
1347 
1348 /** deletes all rows in the given range from LP */
1349 SCIP_RETCODE SCIPlpiDelRows(
1350  SCIP_LPI* lpi, /**< LP interface structure */
1351  int firstrow, /**< first row to be deleted */
1352  int lastrow /**< last row to be deleted */
1353  )
1354 {
1355  assert(lpi != NULL);
1356  assert(lpi->cpxlp != NULL);
1357  assert(lpi->cpxenv != NULL);
1358  assert(0 <= firstrow && firstrow <= lastrow && lastrow < CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
1359 
1360  SCIPdebugMessage("deleting %d rows from CPLEX\n", lastrow - firstrow + 1);
1361 
1362  invalidateSolution(lpi);
1363 
1364  CHECK_ZERO( lpi->messagehdlr, CPXdelrows(lpi->cpxenv, lpi->cpxlp, firstrow, lastrow) );
1365 
1366  return SCIP_OKAY;
1367 }
1368 
1369 /** deletes rows from SCIP_LP; the new position of a row must not be greater that its old position */
1370 SCIP_RETCODE SCIPlpiDelRowset(
1371  SCIP_LPI* lpi, /**< LP interface structure */
1372  int* dstat /**< deletion status of rows
1373  * input: 1 if row should be deleted, 0 if not
1374  * output: new position of row, -1 if row was deleted */
1375  )
1376 {
1377  assert(lpi != NULL);
1378  assert(lpi->cpxlp != NULL);
1379  assert(lpi->cpxenv != NULL);
1380 
1381  SCIPdebugMessage("deleting a row set from CPLEX\n");
1382 
1383  invalidateSolution(lpi);
1384 
1385  CHECK_ZERO( lpi->messagehdlr, CPXdelsetrows(lpi->cpxenv, lpi->cpxlp, dstat) );
1386 
1387  return SCIP_OKAY;
1388 }
1389 
1390 /** clears the whole LP */
1391 SCIP_RETCODE SCIPlpiClear(
1392  SCIP_LPI* lpi /**< LP interface structure */
1393  )
1394 {
1395  int ncols;
1396  int nrows;
1397 
1398  assert(lpi != NULL);
1399  assert(lpi->cpxlp != NULL);
1400  assert(lpi->cpxenv != NULL);
1401 
1402  SCIPdebugMessage("clearing CPLEX LP\n");
1403 
1404  invalidateSolution(lpi);
1405 
1406  ncols = CPXgetnumcols(lpi->cpxenv, lpi->cpxlp);
1407  nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
1408  if( ncols >= 1 )
1409  {
1410  CHECK_ZERO( lpi->messagehdlr, CPXdelcols(lpi->cpxenv, lpi->cpxlp, 0, ncols-1) );
1411  }
1412  if( nrows >= 1 )
1413  {
1414  CHECK_ZERO( lpi->messagehdlr, CPXdelrows(lpi->cpxenv, lpi->cpxlp, 0, nrows-1) );
1415  }
1416 
1417  return SCIP_OKAY;
1418 }
1419 
1420 /** changes lower and upper bounds of columns */
1421 SCIP_RETCODE SCIPlpiChgBounds(
1422  SCIP_LPI* lpi, /**< LP interface structure */
1423  int ncols, /**< number of columns to change bounds for */
1424  const int* ind, /**< column indices */
1425  const SCIP_Real* lb, /**< values for the new lower bounds */
1426  const SCIP_Real* ub /**< values for the new upper bounds */
1427  )
1428 {
1429  assert(lpi != NULL);
1430  assert(lpi->cpxlp != NULL);
1431  assert(lpi->cpxenv != NULL);
1432 
1433  SCIPdebugMessage("changing %d bounds in CPLEX\n", ncols);
1434 #ifdef SCIP_DEBUG
1435  {
1436  int i;
1437  for( i = 0; i < ncols; ++i )
1438  SCIPdebugPrintf(" col %d: [%g,%g]\n", ind[i], lb[i], ub[i]);
1439  }
1440 #endif
1441 
1442  invalidateSolution(lpi);
1443 
1444  SCIP_CALL( ensureBoundchgMem(lpi, ncols) );
1445 
1446  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, ncols, ind, lpi->larray, (SCIP_Real*)lb) );
1447  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, ncols, ind, lpi->uarray, (SCIP_Real*)ub) );
1448 
1449 #ifndef NDEBUG
1450  {
1451  int i;
1452  for( i = 0; i < ncols; ++i )
1453  {
1454  SCIP_Real cpxlb;
1455  SCIP_Real cpxub;
1456 
1457  CHECK_ZERO( lpi->messagehdlr, CPXgetlb(lpi->cpxenv, lpi->cpxlp, &cpxlb, ind[i], ind[i]) );
1458  CHECK_ZERO( lpi->messagehdlr, CPXgetub(lpi->cpxenv, lpi->cpxlp, &cpxub, ind[i], ind[i]) );
1459 
1460  /* Note that CPLEX seems to set bounds below 1e-10 in absolute value to 0.*/
1461  assert( EPSZ(cpxlb, CPX_MAGICZEROCONSTANT) || cpxlb == lb[i] );
1462  assert( EPSZ(cpxub, CPX_MAGICZEROCONSTANT) || cpxub == ub[i] );
1463  }
1464  }
1465 #endif
1466 
1467  return SCIP_OKAY;
1468 }
1469 
1470 /** changes left and right hand sides of rows */
1471 SCIP_RETCODE SCIPlpiChgSides(
1472  SCIP_LPI* lpi, /**< LP interface structure */
1473  int nrows, /**< number of rows to change sides for */
1474  const int* ind, /**< row indices */
1475  const SCIP_Real* lhs, /**< new values for left hand sides */
1476  const SCIP_Real* rhs /**< new values for right hand sides */
1477  )
1478 {
1479  int rngcount;
1480  int i;
1481 
1482  assert(lpi != NULL);
1483  assert(lpi->cpxlp != NULL);
1484  assert(lpi->cpxenv != NULL);
1485 
1486  SCIPdebugMessage("changing %d sides in CPLEX\n", nrows);
1487 
1488  invalidateSolution(lpi);
1489 
1490  SCIP_CALL( ensureSidechgMem(lpi, nrows) );
1491 
1492  /* convert lhs/rhs into sen/rhs/range tuples */
1493  convertSides(lpi, nrows, lhs, rhs, 0, &rngcount);
1494 
1495  /* change row sides */
1496  CHECK_ZERO( lpi->messagehdlr, CPXchgsense(lpi->cpxenv, lpi->cpxlp, nrows, ind, lpi->senarray) );
1497  CHECK_ZERO( lpi->messagehdlr, CPXchgrhs(lpi->cpxenv, lpi->cpxlp, nrows, ind, lpi->rhsarray) );
1498  if( rngcount > 0 )
1499  {
1500  /* adjust the range count indices to the correct row indices */
1501  for( i = 0; i < rngcount; ++i )
1502  {
1503  assert(0 <= lpi->rngindarray[i] && lpi->rngindarray[i] < nrows);
1504  assert(lpi->senarray[lpi->rngindarray[i]] == 'R');
1505  lpi->rngindarray[i] = ind[lpi->rngindarray[i]];
1506  }
1507 
1508  /* change the range values in CPLEX */
1509  CHECK_ZERO( lpi->messagehdlr, CPXchgrngval(lpi->cpxenv, lpi->cpxlp, rngcount, lpi->rngindarray, lpi->rngarray) );
1510  }
1511 
1512  return SCIP_OKAY;
1513 }
1514 
1515 /** changes a single coefficient */
1516 SCIP_RETCODE SCIPlpiChgCoef(
1517  SCIP_LPI* lpi, /**< LP interface structure */
1518  int row, /**< row number of coefficient to change */
1519  int col, /**< column number of coefficient to change */
1520  SCIP_Real newval /**< new value of coefficient */
1521  )
1522 {
1523  assert(lpi != NULL);
1524  assert(lpi->cpxlp != NULL);
1525  assert(lpi->cpxenv != NULL);
1526 
1527  SCIPdebugMessage("changing coefficient row %d, column %d in CPLEX to %g\n", row, col, newval);
1528 
1529  invalidateSolution(lpi);
1530 
1531  CHECK_ZERO( lpi->messagehdlr, CPXchgcoef(lpi->cpxenv, lpi->cpxlp, row, col, newval) );
1532 
1533  return SCIP_OKAY;
1534 }
1535 
1536 /** changes the objective sense */
1537 SCIP_RETCODE SCIPlpiChgObjsen(
1538  SCIP_LPI* lpi, /**< LP interface structure */
1539  SCIP_OBJSEN objsen /**< new objective sense */
1540  )
1541 {
1542  assert(lpi != NULL);
1543  assert(lpi->cpxlp != NULL);
1544  assert(lpi->cpxenv != NULL);
1545 
1546  SCIPdebugMessage("changing objective sense in CPLEX to %d\n", objsen);
1547 
1548  invalidateSolution(lpi);
1549 
1550  CPXchgobjsen(lpi->cpxenv, lpi->cpxlp, cpxObjsen(objsen));
1551 
1552  return SCIP_OKAY;
1553 }
1554 
1555 /** changes objective values of columns in the LP */
1556 SCIP_RETCODE SCIPlpiChgObj(
1557  SCIP_LPI* lpi, /**< LP interface structure */
1558  int ncols, /**< number of columns to change objective value for */
1559  int* ind, /**< column indices to change objective value for */
1560  SCIP_Real* obj /**< new objective values for columns */
1561  )
1562 {
1563  assert(lpi != NULL);
1564  assert(lpi->cpxlp != NULL);
1565  assert(lpi->cpxenv != NULL);
1566 
1567  SCIPdebugMessage("changing %d objective values in CPLEX\n", ncols);
1568 
1569  CHECK_ZERO( lpi->messagehdlr, CPXchgobj(lpi->cpxenv, lpi->cpxlp, ncols, ind, obj) );
1570 
1571  return SCIP_OKAY;
1572 }
1573 
1574 /** multiplies a row with a non-zero scalar; for negative scalars, the row's sense is switched accordingly */
1575 SCIP_RETCODE SCIPlpiScaleRow(
1576  SCIP_LPI* lpi, /**< LP interface structure */
1577  int row, /**< row number to scale */
1578  SCIP_Real scaleval /**< scaling multiplier */
1579  )
1580 {
1581  SCIP_Real lhs;
1582  SCIP_Real rhs;
1583  int nnonz;
1584  int beg;
1585  int i;
1586 
1587  assert(lpi != NULL);
1588  assert(lpi->cpxlp != NULL);
1589  assert(lpi->cpxenv != NULL);
1590  assert(scaleval != 0.0);
1591 
1592  SCIPdebugMessage("scaling row %d with factor %g in CPLEX\n", row, scaleval);
1593 
1594  invalidateSolution(lpi);
1595 
1596  SCIP_CALL( ensureValMem(lpi, CPXgetnumcols(lpi->cpxenv, lpi->cpxlp)) );
1597 
1598  /* get the row */
1599  SCIP_CALL( SCIPlpiGetRows(lpi, row, row, &lhs, &rhs, &nnonz, &beg, lpi->indarray, lpi->valarray) );
1600 
1601  /* scale row coefficients */
1602  for( i = 0; i < nnonz; ++i )
1603  {
1604  SCIP_CALL( SCIPlpiChgCoef(lpi, row, lpi->indarray[i], lpi->valarray[i] * scaleval) );
1605  }
1606 
1607  /* scale row sides */
1608  if( lhs > -CPX_INFBOUND )
1609  lhs *= scaleval;
1610  else if( scaleval < 0.0 )
1611  lhs = CPX_INFBOUND;
1612  if( rhs < CPX_INFBOUND )
1613  rhs *= scaleval;
1614  else if( scaleval < 0.0 )
1615  rhs = -CPX_INFBOUND;
1616  if( scaleval > 0.0 )
1617  {
1618  SCIP_CALL( SCIPlpiChgSides(lpi, 1, &row, &lhs, &rhs) );
1619  }
1620  else
1621  {
1622  SCIP_CALL( SCIPlpiChgSides(lpi, 1, &row, &rhs, &lhs) );
1623  }
1624 
1625  return SCIP_OKAY;
1626 }
1627 
1628 /** multiplies a column with a non-zero scalar; the objective value is multiplied with the scalar, and the bounds
1629  * are divided by the scalar; for negative scalars, the column's bounds are switched
1630  */
1631 SCIP_RETCODE SCIPlpiScaleCol(
1632  SCIP_LPI* lpi, /**< LP interface structure */
1633  int col, /**< column number to scale */
1634  SCIP_Real scaleval /**< scaling multiplier */
1635  )
1636 {
1637  SCIP_Real lb;
1638  SCIP_Real ub;
1639  SCIP_Real obj;
1640  int nnonz;
1641  int beg;
1642  int i;
1643 
1644  assert(lpi != NULL);
1645  assert(lpi->cpxlp != NULL);
1646  assert(lpi->cpxenv != NULL);
1647  assert(scaleval != 0.0);
1648 
1649  SCIPdebugMessage("scaling column %d with factor %g in CPLEX\n", col, scaleval);
1650 
1651  invalidateSolution(lpi);
1652 
1653  SCIP_CALL( ensureValMem(lpi, CPXgetnumrows(lpi->cpxenv, lpi->cpxlp)) );
1654 
1655  /* get the column */
1656  SCIP_CALL( SCIPlpiGetCols(lpi, col, col, &lb, &ub, &nnonz, &beg, lpi->indarray, lpi->valarray) );
1657 
1658  /* get objective coefficient */
1659  SCIP_CALL( SCIPlpiGetObj(lpi, col, col, &obj) );
1660 
1661  /* scale column coefficients */
1662  for( i = 0; i < nnonz; ++i )
1663  {
1664  SCIP_CALL( SCIPlpiChgCoef(lpi, lpi->indarray[i], col, lpi->valarray[i] * scaleval) );
1665  }
1666 
1667  /* scale objective value */
1668  obj *= scaleval;
1669  SCIP_CALL( SCIPlpiChgObj(lpi, 1, &col, &obj) );
1670 
1671  /* scale column bounds */
1672  if( lb > -CPX_INFBOUND )
1673  lb /= scaleval;
1674  else if( scaleval < 0.0 )
1675  lb = CPX_INFBOUND;
1676  if( ub < CPX_INFBOUND )
1677  ub /= scaleval;
1678  else if( scaleval < 0.0 )
1679  ub = -CPX_INFBOUND;
1680  if( scaleval > 0.0 )
1681  {
1682  SCIP_CALL( SCIPlpiChgBounds(lpi, 1, &col, &lb, &ub) );
1683  }
1684  else
1685  {
1686  SCIP_CALL( SCIPlpiChgBounds(lpi, 1, &col, &ub, &lb) );
1687  }
1688 
1689  return SCIP_OKAY;
1690 }
1691 
1692 /**@} */
1693 
1694 
1695 
1696 
1697 /*
1698  * Data Accessing Methods
1699  */
1700 
1701 /**@name Data Accessing Methods */
1702 /**@{ */
1703 
1704 /** gets the number of rows in the LP */
1705 SCIP_RETCODE SCIPlpiGetNRows(
1706  SCIP_LPI* lpi, /**< LP interface structure */
1707  int* nrows /**< pointer to store the number of rows */
1708  )
1709 {
1710  assert(lpi != NULL);
1711  assert(lpi->cpxenv != NULL);
1712  assert(nrows != NULL);
1713 
1714  SCIPdebugMessage("getting number of rows\n");
1715 
1716  *nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
1717 
1718  return SCIP_OKAY;
1719 }
1720 
1721 /** gets the number of columns in the LP */
1722 SCIP_RETCODE SCIPlpiGetNCols(
1723  SCIP_LPI* lpi, /**< LP interface structure */
1724  int* ncols /**< pointer to store the number of cols */
1725  )
1726 {
1727  assert(lpi != NULL);
1728  assert(lpi->cpxenv != NULL);
1729  assert(ncols != NULL);
1730 
1731  SCIPdebugMessage("getting number of columns\n");
1732 
1733  *ncols = CPXgetnumcols(lpi->cpxenv, lpi->cpxlp);
1734 
1735  return SCIP_OKAY;
1736 }
1737 
1738 /** gets the number of nonzero elements in the LP constraint matrix */
1739 SCIP_RETCODE SCIPlpiGetNNonz(
1740  SCIP_LPI* lpi, /**< LP interface structure */
1741  int* nnonz /**< pointer to store the number of nonzeros */
1742  )
1743 {
1744  assert(lpi != NULL);
1745  assert(lpi->cpxenv != NULL);
1746  assert(nnonz != NULL);
1747 
1748  SCIPdebugMessage("getting number of non-zeros\n");
1749 
1750  *nnonz = CPXgetnumnz(lpi->cpxenv, lpi->cpxlp);
1751 
1752  return SCIP_OKAY;
1753 }
1754 
1755 /** gets columns from LP problem object; the arrays have to be large enough to store all values
1756  * Either both, lb and ub, have to be NULL, or both have to be non-NULL,
1757  * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
1758  */
1759 SCIP_RETCODE SCIPlpiGetCols(
1760  SCIP_LPI* lpi, /**< LP interface structure */
1761  int firstcol, /**< first column to get from LP */
1762  int lastcol, /**< last column to get from LP */
1763  SCIP_Real* lb, /**< buffer to store the lower bound vector, or NULL */
1764  SCIP_Real* ub, /**< buffer to store the upper bound vector, or NULL */
1765  int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
1766  int* beg, /**< buffer to store start index of each column in ind- and val-array, or NULL */
1767  int* ind, /**< buffer to store column indices of constraint matrix entries, or NULL */
1768  SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
1769  )
1770 {
1771  assert(lpi != NULL);
1772  assert(lpi->cpxlp != NULL);
1773  assert(lpi->cpxenv != NULL);
1774  assert(0 <= firstcol && firstcol <= lastcol && lastcol < CPXgetnumcols(lpi->cpxenv, lpi->cpxlp));
1775 
1776  SCIPdebugMessage("getting columns %d to %d\n", firstcol, lastcol);
1777 
1778  if( lb != NULL )
1779  {
1780  assert(ub != NULL);
1781 
1782  CHECK_ZERO( lpi->messagehdlr, CPXgetlb(lpi->cpxenv, lpi->cpxlp, lb, firstcol, lastcol) );
1783  CHECK_ZERO( lpi->messagehdlr, CPXgetub(lpi->cpxenv, lpi->cpxlp, ub, firstcol, lastcol) );
1784  }
1785  else
1786  assert(ub == NULL);
1787 
1788  if( nnonz != NULL )
1789  {
1790  int surplus;
1791 
1792  assert(beg != NULL);
1793  assert(ind != NULL);
1794  assert(val != NULL);
1795 
1796  /* get matrix entries */
1797  CHECK_ZERO( lpi->messagehdlr, CPXgetcols(lpi->cpxenv, lpi->cpxlp, nnonz, beg, ind, val,
1798  CPXgetnumnz(lpi->cpxenv, lpi->cpxlp), &surplus, firstcol, lastcol) );
1799  assert(surplus >= 0);
1800  }
1801  else
1802  {
1803  assert(beg == NULL);
1804  assert(ind == NULL);
1805  assert(val == NULL);
1806  }
1807 
1808  return SCIP_OKAY;
1809 }
1810 
1811 /** gets rows from LP problem object; the arrays have to be large enough to store all values.
1812  * Either both, lhs and rhs, have to be NULL, or both have to be non-NULL,
1813  * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
1814  */
1815 SCIP_RETCODE SCIPlpiGetRows(
1816  SCIP_LPI* lpi, /**< LP interface structure */
1817  int firstrow, /**< first row to get from LP */
1818  int lastrow, /**< last row to get from LP */
1819  SCIP_Real* lhs, /**< buffer to store left hand side vector, or NULL */
1820  SCIP_Real* rhs, /**< buffer to store right hand side vector, or NULL */
1821  int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
1822  int* beg, /**< buffer to store start index of each row in ind- and val-array, or NULL */
1823  int* ind, /**< buffer to store row indices of constraint matrix entries, or NULL */
1824  SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
1825  )
1826 {
1827  int retcode;
1828 
1829  assert(lpi != NULL);
1830  assert(lpi->cpxlp != NULL);
1831  assert(lpi->cpxenv != NULL);
1832  assert(0 <= firstrow && firstrow <= lastrow && lastrow < CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
1833 
1834  SCIPdebugMessage("getting rows %d to %d\n", firstrow, lastrow);
1835 
1836  if( lhs != NULL || rhs != NULL )
1837  {
1838  /* get row sense, rhs, and ranges */
1839  SCIP_CALL( ensureSidechgMem(lpi, lastrow - firstrow + 1) );
1840  CHECK_ZERO( lpi->messagehdlr, CPXgetsense(lpi->cpxenv, lpi->cpxlp, lpi->senarray, firstrow, lastrow) );
1841  CHECK_ZERO( lpi->messagehdlr, CPXgetrhs(lpi->cpxenv, lpi->cpxlp, lpi->rhsarray, firstrow, lastrow) );
1842  retcode = CPXgetrngval(lpi->cpxenv, lpi->cpxlp, lpi->rngarray, firstrow, lastrow);
1843  if( retcode != CPXERR_NO_RNGVAL ) /* ignore "No range values" error */
1844  {
1845  CHECK_ZERO( lpi->messagehdlr, retcode );
1846  }
1847  else
1848  BMSclearMemoryArray(lpi->rngarray, lastrow-firstrow+1);
1849 
1850  /* convert sen/rhs/range into lhs/rhs tuples */
1851  reconvertSides(lpi, lastrow - firstrow + 1, lhs, rhs);
1852  }
1853 
1854  if( nnonz != NULL )
1855  {
1856  int surplus;
1857 
1858  assert(beg != NULL);
1859  assert(ind != NULL);
1860  assert(val != NULL);
1861 
1862  /* get matrix entries */
1863  CHECK_ZERO( lpi->messagehdlr, CPXgetrows(lpi->cpxenv, lpi->cpxlp, nnonz, beg, ind, val,
1864  CPXgetnumnz(lpi->cpxenv, lpi->cpxlp), &surplus, firstrow, lastrow) );
1865  assert(surplus >= 0);
1866  }
1867  else
1868  {
1869  assert(beg == NULL);
1870  assert(ind == NULL);
1871  assert(val == NULL);
1872  }
1873 
1874  return SCIP_OKAY;
1875 }
1876 
1877 /** gets column names */
1878 SCIP_RETCODE SCIPlpiGetColNames(
1879  SCIP_LPI* lpi, /**< LP interface structure */
1880  int firstcol, /**< first column to get name from LP */
1881  int lastcol, /**< last column to get name from LP */
1882  char** colnames, /**< pointers to column names (of size at least lastcol-firstcol+1) */
1883  char* namestorage, /**< storage for col names */
1884  int namestoragesize, /**< size of namestorage (if 0, storageleft returns the storage needed) */
1885  int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) */
1886  )
1887 {
1888  int retcode;
1889 
1890  assert(lpi != NULL);
1891  assert(lpi->cpxlp != NULL);
1892  assert(lpi->cpxenv != NULL);
1893  assert(colnames != NULL || namestoragesize == 0);
1894  assert(namestorage != NULL || namestoragesize == 0);
1895  assert(namestoragesize >= 0);
1896  assert(storageleft != NULL);
1897  assert(0 <= firstcol && firstcol <= lastcol && lastcol < CPXgetnumcols(lpi->cpxenv, lpi->cpxlp));
1898 
1899  SCIPdebugMessage("getting column names %d to %d\n", firstcol, lastcol);
1900 
1901  retcode = CPXgetcolname(lpi->cpxenv, lpi->cpxlp, colnames, namestorage, namestoragesize, storageleft, firstcol, lastcol);
1902  assert( namestoragesize != 0 || retcode == CPXERR_NEGATIVE_SURPLUS );
1903  if( namestoragesize != 0 )
1904  {
1905  CHECK_ZERO( lpi->messagehdlr, retcode );
1906  }
1907 
1908  return SCIP_OKAY;
1909 }
1910 
1911 /** gets row names */
1912 SCIP_RETCODE SCIPlpiGetRowNames(
1913  SCIP_LPI* lpi, /**< LP interface structure */
1914  int firstrow, /**< first row to get name from LP */
1915  int lastrow, /**< last row to get name from LP */
1916  char** rownames, /**< pointers to row names (of size at least lastrow-firstrow+1) */
1917  char* namestorage, /**< storage for row names */
1918  int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */
1919  int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) */
1920  )
1921 {
1922  int retcode;
1923 
1924  assert(lpi != NULL);
1925  assert(lpi->cpxlp != NULL);
1926  assert(lpi->cpxenv != NULL);
1927  assert(rownames != NULL || namestoragesize == 0);
1928  assert(namestorage != NULL || namestoragesize == 0);
1929  assert(namestoragesize >= 0);
1930  assert(storageleft != NULL);
1931  assert(0 <= firstrow && firstrow <= lastrow && lastrow < CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
1932 
1933  SCIPdebugMessage("getting row names %d to %d\n", firstrow, lastrow);
1934 
1935  retcode = CPXgetrowname(lpi->cpxenv, lpi->cpxlp, rownames, namestorage, namestoragesize, storageleft, firstrow, lastrow);
1936  assert( namestoragesize != 0 || retcode == CPXERR_NEGATIVE_SURPLUS );
1937  if( namestoragesize != 0 )
1938  {
1939  CHECK_ZERO( lpi->messagehdlr, retcode );
1940  }
1941 
1942  return SCIP_OKAY;
1943 }
1944 
1945 /** gets objective sense of the LP */
1946 SCIP_RETCODE SCIPlpiGetObjsen(
1947  SCIP_LPI* lpi, /**< LP interface structure */
1948  SCIP_OBJSEN* objsen /**< pointer to store objective sense */
1949  )
1950 {
1951  assert(lpi != NULL);
1952  assert(objsen != NULL);
1953  assert(CPXgetobjsen(lpi->cpxenv, lpi->cpxlp) == CPX_MIN || CPXgetobjsen(lpi->cpxenv, lpi->cpxlp) == CPX_MAX);
1954 
1955  SCIPdebugMessage("getting objective sense\n");
1956 
1957  *objsen = (CPXgetobjsen(lpi->cpxenv, lpi->cpxlp) == CPX_MIN) ? SCIP_OBJSEN_MINIMIZE : SCIP_OBJSEN_MAXIMIZE;
1958 
1959  return SCIP_OKAY;
1960 }
1961 
1962 /** gets objective coefficients from LP problem object */
1963 SCIP_RETCODE SCIPlpiGetObj(
1964  SCIP_LPI* lpi, /**< LP interface structure */
1965  int firstcol, /**< first column to get objective coefficient for */
1966  int lastcol, /**< last column to get objective coefficient for */
1967  SCIP_Real* vals /**< array to store objective coefficients */
1968  )
1969 {
1970  assert(lpi != NULL);
1971  assert(lpi->cpxlp != NULL);
1972  assert(lpi->cpxenv != NULL);
1973  assert(firstcol <= lastcol);
1974  assert(vals != NULL);
1975 
1976  SCIPdebugMessage("getting objective values %d to %d\n", firstcol, lastcol);
1977 
1978  CHECK_ZERO( lpi->messagehdlr, CPXgetobj(lpi->cpxenv, lpi->cpxlp, vals, firstcol, lastcol) );
1979 
1980  return SCIP_OKAY;
1981 }
1982 
1983 /** gets current bounds from LP problem object */
1984 SCIP_RETCODE SCIPlpiGetBounds(
1985  SCIP_LPI* lpi, /**< LP interface structure */
1986  int firstcol, /**< first column to get bounds for */
1987  int lastcol, /**< last column to get bounds for */
1988  SCIP_Real* lbs, /**< array to store lower bound values, or NULL */
1989  SCIP_Real* ubs /**< array to store upper bound values, or NULL */
1990  )
1991 {
1992  assert(lpi != NULL);
1993  assert(lpi->cpxlp != NULL);
1994  assert(lpi->cpxenv != NULL);
1995  assert(firstcol <= lastcol);
1996 
1997  SCIPdebugMessage("getting bounds %d to %d\n", firstcol, lastcol);
1998 
1999  if( lbs != NULL )
2000  {
2001  CHECK_ZERO( lpi->messagehdlr, CPXgetlb(lpi->cpxenv, lpi->cpxlp, lbs, firstcol, lastcol) );
2002  }
2003 
2004  if( ubs != NULL )
2005  {
2006  CHECK_ZERO( lpi->messagehdlr, CPXgetub(lpi->cpxenv, lpi->cpxlp, ubs, firstcol, lastcol) );
2007  }
2008 
2009  return SCIP_OKAY;
2010 }
2011 
2012 /** gets current row sides from LP problem object */
2013 SCIP_RETCODE SCIPlpiGetSides(
2014  SCIP_LPI* lpi, /**< LP interface structure */
2015  int firstrow, /**< first row to get sides for */
2016  int lastrow, /**< last row to get sides for */
2017  SCIP_Real* lhss, /**< array to store left hand side values, or NULL */
2018  SCIP_Real* rhss /**< array to store right hand side values, or NULL */
2019  )
2020 {
2021  int retval;
2022 
2023  assert(lpi != NULL);
2024  assert(lpi->cpxlp != NULL);
2025  assert(lpi->cpxenv != NULL);
2026  assert(firstrow <= lastrow);
2027 
2028  SCIPdebugMessage("getting row sides %d to %d\n", firstrow, lastrow);
2029 
2030  /* get row sense, rhs, and ranges */
2031  SCIP_CALL( ensureSidechgMem(lpi, lastrow - firstrow + 1) );
2032  CHECK_ZERO( lpi->messagehdlr, CPXgetsense(lpi->cpxenv, lpi->cpxlp, lpi->senarray, firstrow, lastrow) );
2033  CHECK_ZERO( lpi->messagehdlr, CPXgetrhs(lpi->cpxenv, lpi->cpxlp, lpi->rhsarray, firstrow, lastrow) );
2034  retval = CPXgetrngval(lpi->cpxenv, lpi->cpxlp, lpi->rngarray, firstrow, lastrow);
2035  if( retval != CPXERR_NO_RNGVAL ) /* ignore "No range values" error */
2036  {
2037  CHECK_ZERO( lpi->messagehdlr, retval );
2038  }
2039  else
2040  BMSclearMemoryArray(lpi->rngarray, lastrow-firstrow+1);
2041 
2042  /* convert sen/rhs/range into lhs/rhs tuples */
2043  reconvertSides(lpi, lastrow - firstrow + 1, lhss, rhss);
2044 
2045  return SCIP_OKAY;
2046 }
2047 
2048 /** gets a single coefficient */
2049 SCIP_RETCODE SCIPlpiGetCoef(
2050  SCIP_LPI* lpi, /**< LP interface structure */
2051  int row, /**< row number of coefficient */
2052  int col, /**< column number of coefficient */
2053  SCIP_Real* val /**< pointer to store the value of the coefficient */
2054  )
2055 {
2056  assert(lpi != NULL);
2057  assert(lpi->cpxlp != NULL);
2058  assert(lpi->cpxenv != NULL);
2059 
2060  SCIPdebugMessage("getting coefficient of row %d col %d\n", row, col);
2061 
2062  CHECK_ZERO( lpi->messagehdlr, CPXgetcoef(lpi->cpxenv, lpi->cpxlp, row, col, val) );
2063 
2064  return SCIP_OKAY;
2065 }
2066 
2067 /**@} */
2068 
2069 
2070 
2071 
2072 /*
2073  * Solving Methods
2074  */
2075 
2076 /**@name Solving Methods */
2077 /**@{ */
2078 
2079 /** calls primal simplex to solve the LP */
2080 SCIP_RETCODE SCIPlpiSolvePrimal(
2081  SCIP_LPI* lpi /**< LP interface structure */
2082  )
2083 {
2084  int retval;
2085  int primalfeasible;
2086  int dualfeasible;
2087  int solntype;
2088 
2089  assert(lpi != NULL);
2090  assert(lpi->cpxlp != NULL);
2091  assert(lpi->cpxenv != NULL);
2092 
2093  SCIPdebugMessage("calling CPLEX primal simplex: %d cols, %d rows\n",
2094  CPXgetnumcols(lpi->cpxenv, lpi->cpxlp), CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
2095 
2096  invalidateSolution(lpi);
2097 
2098  setIntParam(lpi, CPX_PARAM_ADVIND, lpi->fromscratch || lpi->clearstate ? CPX_OFF : CPX_ON);
2099  lpi->clearstate = FALSE;
2100 
2101  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2102 
2103  SCIPdebugMessage("calling CPXprimopt()\n");
2104  retval = CPXprimopt(lpi->cpxenv, lpi->cpxlp);
2105  lpi->iterations = CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp) + CPXgetitcnt(lpi->cpxenv, lpi->cpxlp);
2106  switch( retval )
2107  {
2108  case 0:
2109  break;
2110  case CPXERR_NO_MEMORY:
2111  return SCIP_NOMEMORY;
2112  default:
2113  return SCIP_LPERROR;
2114  }
2115 
2116  lpi->solstat = CPXgetstat(lpi->cpxenv, lpi->cpxlp);
2117  lpi->instabilityignored = FALSE;
2118  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &primalfeasible, &dualfeasible) );
2119  SCIPdebugMessage(" -> CPLEX returned solstat=%d, pfeas=%d, dfeas=%d (%d iterations)\n",
2120  lpi->solstat, primalfeasible, dualfeasible, lpi->iterations);
2121 
2122  if( lpi->solstat == CPX_STAT_INForUNBD
2123  || (lpi->solstat == CPX_STAT_INFEASIBLE && !dualfeasible)
2124  || (lpi->solstat == CPX_STAT_UNBOUNDED && !primalfeasible) )
2125  {
2126  if( getIntParam(lpi, CPX_PARAM_PREIND) == CPX_ON )
2127  {
2128  /* maybe the preprocessor solved the problem; but we need a solution, so solve again without preprocessing */
2129  SCIPdebugMessage("presolver may have solved the problem -> calling CPLEX primal simplex again without presolve\n");
2130 
2131  /* switch off preprocessing */
2132  setIntParam(lpi, CPX_PARAM_PREIND, CPX_OFF);
2133  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2134 
2135  retval = CPXprimopt(lpi->cpxenv, lpi->cpxlp);
2136  switch( retval )
2137  {
2138  case 0:
2139  break;
2140  case CPXERR_NO_MEMORY:
2141  return SCIP_NOMEMORY;
2142  default:
2143  return SCIP_LPERROR;
2144  }
2145 
2146  lpi->iterations += CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp) + CPXgetitcnt(lpi->cpxenv, lpi->cpxlp);
2147  lpi->solstat = CPXgetstat(lpi->cpxenv, lpi->cpxlp);
2148  lpi->instabilityignored = FALSE;
2149  SCIPdebugMessage(" -> CPLEX returned solstat=%d (%d iterations)\n", lpi->solstat, lpi->iterations);
2150 
2151  /* switch on preprocessing again */
2152  setIntParam(lpi, CPX_PARAM_PREIND, CPX_ON);
2153  }
2154 
2155  if( lpi->solstat == CPX_STAT_INForUNBD )
2156  {
2157  /* preprocessing was not the problem; issue a warning message and treat LP as infeasible */
2158  SCIPerrorMessage("CPLEX primal simplex returned CPX_STAT_INForUNBD after presolving was turned off\n");
2159  }
2160  }
2161 
2162  /* check whether the solution is basic: if Cplex, e.g., hits a time limit in data setup, this might not be the case,
2163  * also for some pathological cases of infeasibility, e.g., contradictory bounds
2164  */
2165  if( lpi->solstat == CPX_STAT_OPTIMAL )
2166  {
2167 #ifdef NDEBUG
2168  lpi->solisbasic = TRUE;
2169 #else
2170  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
2171  lpi->solisbasic = (solntype == CPX_BASIC_SOLN);
2172  assert(lpi->solisbasic);
2173 #endif
2174  }
2175  else
2176  {
2177  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
2178  lpi->solisbasic = (solntype == CPX_BASIC_SOLN);
2179  }
2180 
2181  return SCIP_OKAY;
2182 }
2183 
2184 /** calls dual simplex to solve the LP */
2185 SCIP_RETCODE SCIPlpiSolveDual(
2186  SCIP_LPI* lpi /**< LP interface structure */
2187  )
2188 {
2189  int retval;
2190  int primalfeasible;
2191  int dualfeasible;
2192  int solntype;
2193 
2194  assert(lpi != NULL);
2195  assert(lpi->cpxlp != NULL);
2196  assert(lpi->cpxenv != NULL);
2197 
2198  SCIPdebugMessage("calling CPLEX dual simplex: %d cols, %d rows\n",
2199  CPXgetnumcols(lpi->cpxenv, lpi->cpxlp), CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
2200 
2201  invalidateSolution(lpi);
2202 
2203  setIntParam(lpi, CPX_PARAM_ADVIND, lpi->fromscratch || lpi->clearstate ? CPX_OFF : CPX_ON);
2204  lpi->clearstate = FALSE;
2205 
2206  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2207 
2208  SCIPdebugMessage("calling CPXdualopt()\n");
2209  retval = CPXdualopt(lpi->cpxenv, lpi->cpxlp);
2210  lpi->iterations = CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp) + CPXgetitcnt(lpi->cpxenv, lpi->cpxlp);
2211  switch( retval )
2212  {
2213  case 0:
2214  break;
2215  case CPXERR_NO_MEMORY:
2216  return SCIP_NOMEMORY;
2217  default:
2218  return SCIP_LPERROR;
2219  }
2220 
2221  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
2222 
2223  lpi->solstat = CPXgetstat(lpi->cpxenv, lpi->cpxlp);
2224  lpi->instabilityignored = FALSE;
2225  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &primalfeasible, &dualfeasible) );
2226  SCIPdebugMessage(" -> CPLEX returned solstat=%d, pfeas=%d, dfeas=%d (%d iterations)\n",
2227  lpi->solstat, primalfeasible, dualfeasible, lpi->iterations);
2228 
2229  if( lpi->solstat == CPX_STAT_INForUNBD
2230  || (lpi->solstat == CPX_STAT_INFEASIBLE && !dualfeasible)
2231  || (lpi->solstat == CPX_STAT_UNBOUNDED && !primalfeasible) )
2232  {
2233  if( getIntParam(lpi, CPX_PARAM_PREIND) == CPX_ON )
2234  {
2235  /* maybe the preprocessor solved the problem; but we need a solution, so solve again without preprocessing */
2236  SCIPdebugMessage("presolver may have solved the problem -> calling CPLEX dual simplex again without presolve\n");
2237 
2238  /* switch off preprocessing */
2239  setIntParam(lpi, CPX_PARAM_PREIND, CPX_OFF);
2240  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2241 
2242  retval = CPXdualopt(lpi->cpxenv, lpi->cpxlp);
2243  switch( retval )
2244  {
2245  case 0:
2246  break;
2247  case CPXERR_NO_MEMORY:
2248  return SCIP_NOMEMORY;
2249  default:
2250  return SCIP_LPERROR;
2251  }
2252 
2253  lpi->iterations += CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp) + CPXgetitcnt(lpi->cpxenv, lpi->cpxlp);
2254  lpi->solstat = CPXgetstat(lpi->cpxenv, lpi->cpxlp);
2255  lpi->instabilityignored = FALSE;
2256  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &primalfeasible, &dualfeasible) );
2257  SCIPdebugMessage(" -> CPLEX returned solstat=%d (%d iterations)\n", lpi->solstat, lpi->iterations);
2258 
2259  /* switch on preprocessing again */
2260  setIntParam(lpi, CPX_PARAM_PREIND, CPX_ON);
2261  }
2262 
2263  if( lpi->solstat == CPX_STAT_INForUNBD )
2264  {
2265  /* preprocessing was not the problem; issue a warning message and treat LP as infeasible */
2266  SCIPerrorMessage("CPLEX dual simplex returned CPX_STAT_INForUNBD after presolving was turned off\n");
2267  }
2268  }
2269 
2270  /* check whether the solution is basic: if Cplex, e.g., hits a time limit in data setup, this might not be the case,
2271  * also for some pathological cases of infeasibility, e.g., contradictory bounds
2272  */
2273  if( lpi->solstat == CPX_STAT_OPTIMAL )
2274  {
2275 #ifdef NDEBUG
2276  lpi->solisbasic = TRUE;
2277 #else
2278  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
2279  lpi->solisbasic = (solntype == CPX_BASIC_SOLN);
2280  assert(lpi->solisbasic);
2281 #endif
2282  }
2283  else
2284  {
2285  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
2286  lpi->solisbasic = (solntype == CPX_BASIC_SOLN);
2287  }
2288 
2289 #if 0
2290  /* this fixes the strange behavior of CPLEX, that in case of the objective limit exceedance, it returns the
2291  * solution for the basis preceeding the one with exceeding objective limit
2292  * (using this "wrong" dual solution can cause column generation algorithms to fail to find an improving column)
2293  */
2294  if( SCIPlpiIsObjlimExc(lpi) )
2295  {
2296  SCIP_Real objval;
2297  SCIP_Real llim;
2298  SCIP_Real ulim;
2299  SCIP_Real eps;
2300 
2301  /* check, if the dual solution returned by CPLEX really exceeds the objective limit;
2302  * CPLEX usually returns the basis one iteration before the one that exceeds the limit
2303  */
2304  SCIP_CALL( SCIPlpiGetObjval(lpi, &objval) );
2305  llim = getDblParam(lpi, CPX_PARAM_OBJLLIM);
2306  ulim = getDblParam(lpi, CPX_PARAM_OBJULIM);
2307  eps = getDblParam(lpi, CPX_PARAM_EPOPT);
2308  if( objval >= llim - eps && objval <= ulim + eps )
2309  {
2310  int itlim;
2311  int advind;
2312 
2313  /* perform one additional simplex iteration without objective limit */
2314  SCIPdebugMessage("dual solution %g does not exceed objective limit [%g,%g] (%d iterations) -> calling CPLEX dual simplex again for one iteration\n",
2315  objval, llim, ulim, lpi->iterations);
2316  itlim = getIntParam(lpi, CPX_PARAM_ITLIM);
2317  setIntParam(lpi, CPX_PARAM_ITLIM, 1);
2318  advind = getIntParam(lpi, CPX_PARAM_ADVIND);
2319  setIntParam(lpi, CPX_PARAM_ADVIND, CPX_ON);
2320  setDblParam(lpi, CPX_PARAM_OBJLLIM, -CPX_INFBOUND);
2321  setDblParam(lpi, CPX_PARAM_OBJULIM, CPX_INFBOUND);
2322  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2323  CHECK_ZERO( lpi->messagehdlr, CPXsetintparam(lpi->cpxenv, CPX_PARAM_FINALFACTOR, FALSE) );
2324 
2325  retval = CPXdualopt(lpi->cpxenv, lpi->cpxlp);
2326  switch( retval )
2327  {
2328  case 0:
2329  break;
2330  case CPXERR_NO_MEMORY:
2331  return SCIP_NOMEMORY;
2332  default:
2333  return SCIP_LPERROR;
2334  }
2335 
2336  lpi->iterations += CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp) + CPXgetitcnt(lpi->cpxenv, lpi->cpxlp);
2337 
2338  /* reset the iteration limit and objective bounds */
2339  setIntParam(lpi, CPX_PARAM_ITLIM, itlim);
2340  setIntParam(lpi, CPX_PARAM_ADVIND, advind);
2341  setDblParam(lpi, CPX_PARAM_OBJLLIM, llim);
2342  setDblParam(lpi, CPX_PARAM_OBJULIM, ulim);
2343  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2344  CHECK_ZERO( lpi->messagehdlr, CPXsetintparam(lpi->cpxenv, CPX_PARAM_FINALFACTOR, TRUE) );
2345 
2346  /* resolve LP again in order to restore the status of exceeded objective limit */
2347  retval = CPXdualopt(lpi->cpxenv, lpi->cpxlp);
2348  switch( retval )
2349  {
2350  case 0:
2351  break;
2352  case CPXERR_NO_MEMORY:
2353  return SCIP_NOMEMORY;
2354  default:
2355  return SCIP_LPERROR;
2356  }
2357 
2358  lpi->iterations += CPXgetphase1cnt(lpi->cpxenv, lpi->cpxlp) + CPXgetitcnt(lpi->cpxenv, lpi->cpxlp);
2359  lpi->solstat = CPXgetstat(lpi->cpxenv, lpi->cpxlp);
2360  lpi->instabilityignored = FALSE;
2361  SCIPdebugMessage(" -> CPLEX returned solstat=%d (%d iterations)\n", lpi->solstat, lpi->iterations);
2362  }
2363  }
2364 #endif
2365 
2366  return SCIP_OKAY;
2367 }
2368 
2369 /** calls barrier or interior point algorithm to solve the LP with crossover to simplex basis */
2370 SCIP_RETCODE SCIPlpiSolveBarrier(
2371  SCIP_LPI* lpi, /**< LP interface structure */
2372  SCIP_Bool crossover /**< perform crossover */
2373  )
2374 {
2375  int solntype;
2376  int retval;
2377 
2378  assert(lpi != NULL);
2379  assert(lpi->cpxlp != NULL);
2380  assert(lpi->cpxenv != NULL);
2381 
2382  SCIPdebugMessage("calling CPLEX barrier: %d cols, %d rows\n",
2383  CPXgetnumcols(lpi->cpxenv, lpi->cpxlp), CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
2384 
2385  invalidateSolution(lpi);
2386 
2387  setIntParam(lpi, CPX_PARAM_ADVIND, lpi->fromscratch || lpi->clearstate ? CPX_OFF : CPX_ON);
2388  lpi->clearstate = FALSE;
2389 
2390  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2391 
2392  SCIPdebugMessage("calling CPXhybaropt()\n");
2393  retval = CPXhybbaropt(lpi->cpxenv, lpi->cpxlp, crossover ? 0 : CPX_ALG_NONE);
2394  lpi->iterations = CPXgetbaritcnt(lpi->cpxenv, lpi->cpxlp);
2395  switch( retval )
2396  {
2397  case 0:
2398  break;
2399  case CPXERR_NO_MEMORY:
2400  return SCIP_NOMEMORY;
2401  default:
2402  return SCIP_LPERROR;
2403  }
2404 
2405  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
2406 
2407  lpi->solisbasic = (solntype == CPX_BASIC_SOLN);
2408  lpi->solstat = CPXgetstat(lpi->cpxenv, lpi->cpxlp);
2409  lpi->instabilityignored = FALSE;
2410  SCIPdebugMessage(" -> CPLEX returned solstat=%d (%d iterations)\n", lpi->solstat, lpi->iterations);
2411 
2412  if( lpi->solstat == CPX_STAT_INForUNBD )
2413  {
2414  /* maybe the preprocessor solved the problem; but we need a solution, so solve again without preprocessing */
2415  SCIPdebugMessage("CPLEX returned INForUNBD -> calling CPLEX barrier again without presolve\n");
2416 
2417  /* switch off preprocessing */
2418  setIntParam(lpi, CPX_PARAM_PREIND, CPX_OFF);
2419  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2420 
2421  retval = CPXhybbaropt(lpi->cpxenv, lpi->cpxlp, crossover ? 0 : CPX_ALG_NONE);
2422  switch( retval )
2423  {
2424  case 0:
2425  break;
2426  case CPXERR_NO_MEMORY:
2427  return SCIP_NOMEMORY;
2428  default:
2429  return SCIP_LPERROR;
2430  }
2431 
2432  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
2433 
2434  lpi->solisbasic = (solntype == CPX_BASIC_SOLN);
2435  lpi->iterations += CPXgetbaritcnt(lpi->cpxenv, lpi->cpxlp);
2436  lpi->solstat = CPXgetstat(lpi->cpxenv, lpi->cpxlp);
2437  lpi->instabilityignored = FALSE;
2438  SCIPdebugMessage(" -> CPLEX returned solstat=%d\n", lpi->solstat);
2439 
2440  if( lpi->solstat == CPX_STAT_INForUNBD )
2441  {
2442  /* preprocessing was not the problem; issue a warning message and treat LP as infeasible */
2443  SCIPerrorMessage("CPLEX barrier returned CPX_STAT_INForUNBD after presolving was turned off\n");
2444  }
2445 
2446  setIntParam(lpi, CPX_PARAM_PREIND, CPX_ON);
2447  }
2448 
2449  return SCIP_OKAY;
2450 }
2451 
2452 /** manually performs strong branching on one integral variable */
2453 static
2454 SCIP_RETCODE lpiStrongbranchIntegral(
2455  SCIP_LPI* lpi, /**< LP interface structure */
2456  int col, /**< column to apply strong branching on */
2457  SCIP_Real psol, /**< current integral primal solution value of column */
2458  int itlim, /**< iteration limit for strong branchings */
2459  SCIP_Real* down, /**< stores dual bound after branching column down */
2460  SCIP_Real* up, /**< stores dual bound after branching column up */
2461  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
2462  * otherwise, it can only be used as an estimate value */
2463  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
2464  * otherwise, it can only be used as an estimate value */
2465  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2466  )
2467 {
2468  const char lbound = 'L';
2469  const char ubound = 'U';
2470  SCIP_Real oldlb;
2471  SCIP_Real oldub;
2472  SCIP_Real newlb;
2473  SCIP_Real newub;
2474  int objsen;
2475  int olditlim;
2476  int it;
2477 
2478  SCIPdebugMessage(" -> strong branching on integral variable %d\n", col);
2479 
2480  assert( EPSISINT(psol, lpi->feastol) );
2481 
2482  objsen = CPXgetobjsen(lpi->cpxenv, lpi->cpxlp);
2483 
2484  /* results of CPLEX are valid in any case */
2485  *downvalid = TRUE;
2486  *upvalid = TRUE;
2487 
2488  /* save current LP basis and bounds*/
2489  SCIP_CALL( getBase(lpi) );
2490  CHECK_ZERO( lpi->messagehdlr, CPXgetlb(lpi->cpxenv, lpi->cpxlp, &oldlb, col, col) );
2491  CHECK_ZERO( lpi->messagehdlr, CPXgetub(lpi->cpxenv, lpi->cpxlp, &oldub, col, col) );
2492 
2493  /* save old iteration limit and set iteration limit to strong branching limit */
2494  if( itlim > CPX_INT_MAX )
2495  itlim = CPX_INT_MAX;
2496  olditlim = getIntParam(lpi, CPX_PARAM_ITLIM);
2497  setIntParam(lpi, CPX_PARAM_ITLIM, itlim);
2498 
2499  /* down branch */
2500  newub = EPSCEIL(psol-1.0, lpi->feastol);
2501  if( newub >= oldlb - 0.5 )
2502  {
2503  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &ubound, &newub) );
2504  SCIP_CALL( SCIPlpiSolveDual(lpi) );
2505  if( SCIPlpiIsPrimalInfeasible(lpi) || SCIPlpiIsObjlimExc(lpi) )
2506  *down = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJULIM) : getDblParam(lpi, CPX_PARAM_OBJLLIM);
2507  else if( SCIPlpiIsOptimal(lpi) || SCIPlpiIsIterlimExc(lpi) )
2508  {
2509  SCIP_CALL( SCIPlpiGetObjval(lpi, down) );
2510  }
2511  else
2512  *down = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJLLIM) : getDblParam(lpi, CPX_PARAM_OBJULIM);
2513  if( iter != NULL )
2514  {
2515  SCIP_CALL( SCIPlpiGetIterations(lpi, &it) );
2516  *iter += it;
2517  }
2518  SCIPdebugMessage(" -> down (x%d <= %g): %g\n", col, newub, *down);
2519 
2520  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &ubound, &oldub) );
2521  SCIP_CALL( setBase(lpi) );
2522  }
2523  else
2524  *down = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJULIM) : getDblParam(lpi, CPX_PARAM_OBJLLIM);
2525 
2526  /* up branch */
2527  newlb = EPSFLOOR(psol+1.0, lpi->feastol);
2528  if( newlb <= oldub + 0.5 )
2529  {
2530  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &lbound, &newlb) );
2531  SCIP_CALL( SCIPlpiSolveDual(lpi) );
2532  if( SCIPlpiIsPrimalInfeasible(lpi) || SCIPlpiIsObjlimExc(lpi) )
2533  *up = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJULIM) : getDblParam(lpi, CPX_PARAM_OBJLLIM);
2534  else if( SCIPlpiIsOptimal(lpi) || SCIPlpiIsIterlimExc(lpi) )
2535  {
2536  SCIP_CALL( SCIPlpiGetObjval(lpi, up) );
2537  }
2538  else
2539  *up = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJLLIM) : getDblParam(lpi, CPX_PARAM_OBJULIM);
2540  if( iter != NULL )
2541  {
2542  SCIP_CALL( SCIPlpiGetIterations(lpi, &it) );
2543  *iter += it;
2544  }
2545  SCIPdebugMessage(" -> up (x%d >= %g): %g\n", col, newlb, *up);
2546 
2547  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &lbound, &oldlb) );
2548  SCIP_CALL( setBase(lpi) );
2549  }
2550  else
2551  *up = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJLLIM) : getDblParam(lpi, CPX_PARAM_OBJULIM);
2552 
2553  /* reset iteration limit */
2554  setIntParam(lpi, CPX_PARAM_ITLIM, olditlim);
2555 
2556  return SCIP_OKAY;
2557 }
2558 
2559 /** start strong branching */
2560 SCIP_RETCODE SCIPlpiStartStrongbranch(
2561  SCIP_LPI* lpi /**< LP interface structure */
2562  )
2563 { /* no work necessary */
2564  return SCIP_OKAY;
2565 }
2566 
2567 /** end strong branching */
2568 SCIP_RETCODE SCIPlpiEndStrongbranch(
2569  SCIP_LPI* lpi /**< LP interface structure */
2570  )
2571 { /* no work necessary */
2572  return SCIP_OKAY;
2573 }
2574 
2575 /** performs strong branching iterations on one @b fractional candidate */
2576 SCIP_RETCODE SCIPlpiStrongbranchFrac(
2577  SCIP_LPI* lpi, /**< LP interface structure */
2578  int col, /**< column to apply strong branching on */
2579  SCIP_Real psol, /**< fractional current primal solution value of column */
2580  int itlim, /**< iteration limit for strong branchings */
2581  SCIP_Real* down, /**< stores dual bound after branching column down */
2582  SCIP_Real* up, /**< stores dual bound after branching column up */
2583  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
2584  * otherwise, it can only be used as an estimate value */
2585  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
2586  * otherwise, it can only be used as an estimate value */
2587  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2588  )
2589 {
2590 #if 0
2591  const char lbound = 'L';
2592  const char ubound = 'U';
2593  SCIP_Real oldlb;
2594  SCIP_Real oldub;
2595  SCIP_Real newlb;
2596  SCIP_Real newub;
2597  double* norm;
2598  int* head;
2599  int nrows;
2600  int objsen;
2601  int olditlim;
2602  int it;
2603  int dnormlen;
2604 
2605  SCIPdebugMessage(" -> strong branching on integral variable %d\n", col);
2606 
2607  assert( !EPSISINT(psol, lpi->feastol) );
2608 
2609  objsen = CPXgetobjsen(lpi->cpxenv, lpi->cpxlp);
2610 
2611  /* results of CPLEX are valid in any case */
2612  *downvalid = TRUE;
2613  *upvalid = TRUE;
2614 
2615  if( iter != NULL )
2616  *iter = 0;
2617 
2618  nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
2619 
2620  SCIP_ALLOC( BMSallocMemoryArray(&norm, nrows) );
2621  SCIP_ALLOC( BMSallocMemoryArray(&head, nrows) );
2622 
2623  /* save current LP basis and bounds*/
2624  SCIP_CALL( getBase(lpi) );
2625  CHECK_ZERO( lpi->messagehdlr, CPXgetdnorms(lpi->cpxenv, lpi->cpxlp, norm, head, &dnormlen) );
2626  CHECK_ZERO( lpi->messagehdlr, CPXgetlb(lpi->cpxenv, lpi->cpxlp, &oldlb, col, col) );
2627  CHECK_ZERO( lpi->messagehdlr, CPXgetub(lpi->cpxenv, lpi->cpxlp, &oldub, col, col) );
2628 
2629  /* save old iteration limit and set iteration limit to strong branching limit */
2630  if( itlim > CPX_INT_MAX )
2631  itlim = CPX_INT_MAX;
2632  olditlim = getIntParam(lpi, CPX_PARAM_ITLIM);
2633  setIntParam(lpi, CPX_PARAM_ITLIM, itlim);
2634 
2635  /* down branch */
2636  newub = EPSFLOOR(psol, lpi->feastol);
2637  if( newub >= oldlb - 0.5 )
2638  {
2639  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &ubound, &newub) );
2640  SCIP_CALL( SCIPlpiSolveDual(lpi) );
2641  if( SCIPlpiIsPrimalInfeasible(lpi) || SCIPlpiIsObjlimExc(lpi) )
2642  *down = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJULIM) : getDblParam(lpi, CPX_PARAM_OBJLLIM);
2643  else if( SCIPlpiIsOptimal(lpi) || SCIPlpiIsIterlimExc(lpi) )
2644  {
2645  SCIP_CALL( SCIPlpiGetObjval(lpi, down) );
2646  }
2647  else
2648  *down = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJLLIM) : getDblParam(lpi, CPX_PARAM_OBJULIM);
2649  if( iter != NULL )
2650  {
2651  SCIP_CALL( SCIPlpiGetIterations(lpi, &it) );
2652  *iter += it;
2653  }
2654  SCIPdebugMessage(" -> down (x%d <= %g): %g\n", col, newub, *down);
2655 
2656  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &ubound, &oldub) );
2657  SCIP_CALL( setBase(lpi) );
2658  CHECK_ZERO( lpi->messagehdlr, CPXcopydnorms(lpi->cpxenv, lpi->cpxlp, norm, head, dnormlen) );
2659  }
2660  else
2661  *down = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJULIM) : getDblParam(lpi, CPX_PARAM_OBJLLIM);
2662 
2663  /* up branch */
2664  newlb = EPSCEIL(psol, lpi->feastol);
2665  if( newlb <= oldub + 0.5 )
2666  {
2667  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &lbound, &newlb) );
2668  SCIP_CALL( SCIPlpiSolveDual(lpi) );
2669  if( SCIPlpiIsPrimalInfeasible(lpi) || SCIPlpiIsObjlimExc(lpi) )
2670  *up = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJULIM) : getDblParam(lpi, CPX_PARAM_OBJLLIM);
2671  else if( SCIPlpiIsOptimal(lpi) || SCIPlpiIsIterlimExc(lpi) )
2672  {
2673  SCIP_CALL( SCIPlpiGetObjval(lpi, up) );
2674  }
2675  else
2676  *up = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJLLIM) : getDblParam(lpi, CPX_PARAM_OBJULIM);
2677  if( iter != NULL )
2678  {
2679  SCIP_CALL( SCIPlpiGetIterations(lpi, &it) );
2680  *iter += it;
2681  }
2682  SCIPdebugMessage(" -> up (x%d >= %g): %g\n", col, newlb, *up);
2683 
2684  CHECK_ZERO( lpi->messagehdlr, CPXchgbds(lpi->cpxenv, lpi->cpxlp, 1, &col, &lbound, &oldlb) );
2685  SCIP_CALL( setBase(lpi) );
2686  CHECK_ZERO( lpi->messagehdlr, CPXcopydnorms(lpi->cpxenv, lpi->cpxlp, norm, head, dnormlen) );
2687  }
2688  else
2689  *up = objsen == CPX_MIN ? getDblParam(lpi, CPX_PARAM_OBJLLIM) : getDblParam(lpi, CPX_PARAM_OBJULIM);
2690 
2691  if( iter != NULL )
2692  *iter = -1;
2693 
2694  BMSfreeMemoryArray(&norm);
2695  BMSfreeMemoryArray(&head);
2696 
2697  /* reset iteration limit */
2698  setIntParam(lpi, CPX_PARAM_ITLIM, olditlim);
2699 #else
2700  int retval;
2701 
2702  assert(lpi != NULL);
2703  assert(lpi->cpxlp != NULL);
2704  assert(lpi->cpxenv != NULL);
2705  assert(down != NULL);
2706  assert(up != NULL);
2707  assert(downvalid != NULL);
2708  assert(upvalid != NULL);
2709 
2710  SCIPdebugMessage("calling CPLEX strongbranching on fractional variable %d (%d iterations)\n", col, itlim);
2711 
2712  assert( !EPSISINT(psol, lpi->feastol) );
2713 
2714  /* results of CPLEX are valid in any case */
2715  *downvalid = TRUE;
2716  *upvalid = TRUE;
2717 
2718  setIntParam(lpi, CPX_PARAM_ADVIND, lpi->fromscratch || lpi->clearstate ? CPX_OFF : CPX_ON);
2719  lpi->clearstate = FALSE;
2720 
2721  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2722 
2723  retval = CPXstrongbranch(lpi->cpxenv, lpi->cpxlp, &col, 1, down, up, itlim);
2724  if( retval == CPXERR_NEED_OPT_SOLN )
2725  {
2726  SCIPdebugMessage(" -> no optimal solution available\n");
2727  return SCIP_LPERROR;
2728  }
2729  else if( retval == CPXERR_TILIM_STRONGBRANCH )
2730  {
2731  SCIPdebugMessage(" -> time limit exceeded during strong branching\n");
2732  return SCIP_LPERROR;
2733  }
2734  else if( retval == CPXERR_SINGULAR )
2735  {
2736  SCIPdebugMessage(" -> numerical troubles (basis singular)\n");
2737  return SCIP_LPERROR;
2738  }
2739  CHECK_ZERO( lpi->messagehdlr, retval );
2740  SCIPdebugMessage(" -> down: %g, up:%g\n", *down, *up);
2741 
2742  /* CPLEX is not able to return the iteration counts in strong branching */
2743  if( iter != NULL )
2744  *iter = -1;
2745 #endif
2746  return SCIP_OKAY;
2747 }
2748 
2749 /** performs strong branching iterations on given @b fractional candidates */
2750 SCIP_RETCODE SCIPlpiStrongbranchesFrac(
2751  SCIP_LPI* lpi, /**< LP interface structure */
2752  int* cols, /**< columns to apply strong branching on */
2753  int ncols, /**< number of columns */
2754  SCIP_Real* psols, /**< fractional current primal solution values of columns */
2755  int itlim, /**< iteration limit for strong branchings */
2756  SCIP_Real* down, /**< stores dual bounds after branching columns down */
2757  SCIP_Real* up, /**< stores dual bounds after branching columns up */
2758  SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
2759  * otherwise, they can only be used as an estimate values */
2760  SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
2761  * otherwise, they can only be used as an estimate values */
2762  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2763  )
2764 {
2765  int retval;
2766  int j;
2767 
2768  assert(lpi != NULL);
2769  assert(lpi->cpxlp != NULL);
2770  assert(lpi->cpxenv != NULL);
2771  assert(cols != NULL);
2772  assert(psols != NULL);
2773  assert(down != NULL);
2774  assert(up != NULL);
2775  assert(downvalid != NULL);
2776  assert(upvalid != NULL);
2777 
2778  SCIPdebugMessage("calling CPLEX strongbranching on %d fractional variables (%d iterations)\n", ncols, itlim);
2779 
2780  setIntParam(lpi, CPX_PARAM_ADVIND, lpi->fromscratch || lpi->clearstate ? CPX_OFF : CPX_ON);
2781  lpi->clearstate = FALSE;
2782 
2783  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
2784 
2785  /* initialize */
2786  for( j = 0; j < ncols; ++j )
2787  {
2788  /* results of CPLEX are valid in any case */
2789  *downvalid = TRUE;
2790  *upvalid = TRUE;
2791 
2792  assert( !EPSISINT(psols[j], lpi->feastol) );
2793  }
2794 
2795  retval = CPXstrongbranch(lpi->cpxenv, lpi->cpxlp, cols, ncols, down, up, itlim);
2796  if( retval == CPXERR_NEED_OPT_SOLN )
2797  {
2798  SCIPdebugMessage(" -> no optimal solution available\n");
2799  return SCIP_LPERROR;
2800  }
2801  else if( retval == CPXERR_TILIM_STRONGBRANCH )
2802  {
2803  SCIPdebugMessage(" -> time limit exceeded during strong branching\n");
2804  return SCIP_LPERROR;
2805  }
2806  CHECK_ZERO( lpi->messagehdlr, retval );
2807 
2808  /* CPLEX is not able to return the iteration counts in strong branching */
2809  if( iter != NULL )
2810  *iter = -1;
2811 
2812  return SCIP_OKAY;
2813 }
2814 
2815 /** performs strong branching iterations on one candidate with @b integral value */
2816 SCIP_RETCODE SCIPlpiStrongbranchInt(
2817  SCIP_LPI* lpi, /**< LP interface structure */
2818  int col, /**< column to apply strong branching on */
2819  SCIP_Real psol, /**< current integral primal solution value of column */
2820  int itlim, /**< iteration limit for strong branchings */
2821  SCIP_Real* down, /**< stores dual bound after branching column down */
2822  SCIP_Real* up, /**< stores dual bound after branching column up */
2823  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
2824  * otherwise, it can only be used as an estimate value */
2825  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
2826  * otherwise, it can only be used as an estimate value */
2827  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2828  )
2829 {
2830  assert(lpi != NULL);
2831  assert(lpi->cpxlp != NULL);
2832  assert(down != NULL);
2833  assert(up != NULL);
2834  assert(downvalid != NULL);
2835  assert(upvalid != NULL);
2836 
2837  SCIPdebugMessage("calling CPLEX strongbranching on variable %d with integral value (%d iterations)\n", col, itlim);
2838 
2839  assert( EPSISINT(psol, lpi->feastol) );
2840 
2841  if( iter != NULL )
2842  *iter = 0;
2843 
2844  SCIP_CALL( lpiStrongbranchIntegral(lpi, col, psol, itlim, down, up, downvalid, upvalid, iter) );
2845 
2846  return SCIP_OKAY;
2847 }
2848 
2849 /** performs strong branching iterations on given candidates with @b integral values */
2850 SCIP_RETCODE SCIPlpiStrongbranchesInt(
2851  SCIP_LPI* lpi, /**< LP interface structure */
2852  int* cols, /**< columns to apply strong branching on */
2853  int ncols, /**< number of columns */
2854  SCIP_Real* psols, /**< current integral primal solution values of columns */
2855  int itlim, /**< iteration limit for strong branchings */
2856  SCIP_Real* down, /**< stores dual bounds after branching columns down */
2857  SCIP_Real* up, /**< stores dual bounds after branching columns up */
2858  SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
2859  * otherwise, they can only be used as an estimate values */
2860  SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
2861  * otherwise, they can only be used as an estimate values */
2862  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2863  )
2864 {
2865  int j;
2866 
2867  assert(lpi != NULL);
2868  assert(lpi->cpxlp != NULL);
2869  assert(cols != NULL);
2870  assert(psols != NULL);
2871  assert(down != NULL);
2872  assert(up != NULL);
2873  assert(downvalid != NULL);
2874  assert(upvalid != NULL);
2875 
2876  SCIPdebugMessage("calling CPLEX strongbranching on %d variables with integer values (%d iterations)\n", ncols, itlim);
2877 
2878  if( iter != NULL )
2879  *iter = 0;
2880 
2881  /* initialize */
2882  for( j = 0; j < ncols; ++j )
2883  {
2884  assert( EPSISINT(psols[j], lpi->feastol) );
2885  SCIP_CALL( lpiStrongbranchIntegral(lpi, cols[j], psols[j], itlim, &(down[j]), &(up[j]), &(downvalid[j]), &(upvalid[j]), iter) );
2886  }
2887 
2888  return SCIP_OKAY;
2889 }
2890 /**@} */
2891 
2892 
2893 
2894 
2895 /*
2896  * Solution Information Methods
2897  */
2898 
2899 /**@name Solution Information Methods */
2900 /**@{ */
2901 
2902 /** returns whether a solve method was called after the last modification of the LP */
2903 SCIP_Bool SCIPlpiWasSolved(
2904  SCIP_LPI* lpi /**< LP interface structure */
2905  )
2906 {
2907  assert(lpi != NULL);
2908 
2909  return (lpi->solstat != -1);
2910 }
2911 
2912 /** gets information about primal and dual feasibility of the current LP solution */
2913 SCIP_RETCODE SCIPlpiGetSolFeasibility(
2914  SCIP_LPI* lpi, /**< LP interface structure */
2915  SCIP_Bool* primalfeasible, /**< stores primal feasibility status */
2916  SCIP_Bool* dualfeasible /**< stores dual feasibility status */
2917  )
2918 {
2919  int pfeas;
2920  int dfeas;
2921 
2922  assert(lpi != NULL);
2923  assert(lpi->cpxlp != NULL);
2924  assert(lpi->cpxenv != NULL);
2925  assert(primalfeasible != NULL);
2926  assert(dualfeasible != NULL);
2927 
2928  SCIPdebugMessage("getting solution feasibility\n");
2929 
2930  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &pfeas, &dfeas) );
2931  *primalfeasible = (SCIP_Bool)pfeas;
2932  *dualfeasible = (SCIP_Bool)dfeas;
2933 
2934  return SCIP_OKAY;
2935 }
2936 
2937 /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point);
2938  * this does not necessarily mean, that the solver knows and can return the primal ray
2939  */
2940 SCIP_Bool SCIPlpiExistsPrimalRay(
2941  SCIP_LPI* lpi /**< LP interface structure */
2942  )
2943 {
2944  assert(lpi != NULL);
2945  assert(lpi->cpxlp != NULL);
2946  assert(lpi->solstat >= 0);
2947 
2948  return (lpi->solstat == CPX_STAT_UNBOUNDED || lpi->solstat == CPX_STAT_OPTIMAL_FACE_UNBOUNDED);
2949 }
2950 
2951 /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point),
2952  * and the solver knows and can return the primal ray
2953  */
2954 SCIP_Bool SCIPlpiHasPrimalRay(
2955  SCIP_LPI* lpi /**< LP interface structure */
2956  )
2957 {
2958  assert(lpi != NULL);
2959  assert(lpi->cpxlp != NULL);
2960  assert(lpi->cpxenv != NULL);
2961  assert(lpi->solstat >= 0);
2962 
2963  return (lpi->solstat == CPX_STAT_UNBOUNDED && CPXgetmethod(lpi->cpxenv, lpi->cpxlp) == CPX_ALG_PRIMAL);
2964 }
2965 
2966 /** returns TRUE iff LP is proven to be primal unbounded */
2967 SCIP_Bool SCIPlpiIsPrimalUnbounded(
2968  SCIP_LPI* lpi /**< LP interface structure */
2969  )
2970 {
2971  int primalfeasible;
2972 
2973  assert(lpi != NULL);
2974  assert(lpi->cpxlp != NULL);
2975  assert(lpi->cpxenv != NULL);
2976  assert(lpi->solstat >= 0);
2977 
2978  SCIPdebugMessage("checking for primal unboundedness\n");
2979 
2980  ABORT_ZERO( CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &primalfeasible, NULL) );
2981 
2982  /* If the solution status of CPLEX is CPX_STAT_UNBOUNDED, it only means, there is an unbounded ray,
2983  * but not necessarily a feasible primal solution. If primalfeasible == FALSE, we cannot conclude,
2984  * that the problem is unbounded
2985  */
2986  return ((primalfeasible && (lpi->solstat == CPX_STAT_UNBOUNDED || lpi->solstat == CPX_STAT_INForUNBD))
2987  || lpi->solstat == CPX_STAT_OPTIMAL_FACE_UNBOUNDED);
2988 }
2989 
2990 /** returns TRUE iff LP is proven to be primal infeasible */
2991 SCIP_Bool SCIPlpiIsPrimalInfeasible(
2992  SCIP_LPI* lpi /**< LP interface structure */
2993  )
2994 {
2995  int dualfeasible;
2996 
2997  assert(lpi != NULL);
2998  assert(lpi->cpxlp != NULL);
2999  assert(lpi->cpxenv != NULL);
3000  assert(lpi->solstat >= 0);
3001 
3002  SCIPdebugMessage("checking for primal infeasibility\n");
3003 
3004  ABORT_ZERO( CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, NULL, &dualfeasible) );
3005 
3006  return (lpi->solstat == CPX_STAT_INFEASIBLE || (lpi->solstat == CPX_STAT_INForUNBD && dualfeasible));
3007 }
3008 
3009 /** returns TRUE iff LP is proven to be primal feasible */
3010 SCIP_Bool SCIPlpiIsPrimalFeasible(
3011  SCIP_LPI* lpi /**< LP interface structure */
3012  )
3013 {
3014  int primalfeasible;
3015 
3016  assert(lpi != NULL);
3017  assert(lpi->cpxlp != NULL);
3018  assert(lpi->cpxenv != NULL);
3019  assert(lpi->solstat >= 0);
3020 
3021  SCIPdebugMessage("checking for primal feasibility\n");
3022 
3023  ABORT_ZERO( CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &primalfeasible, NULL) );
3024 
3025  return (SCIP_Bool)primalfeasible;
3026 }
3027 
3028 /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point);
3029  * this does not necessarily mean, that the solver knows and can return the dual ray
3030  */
3031 SCIP_Bool SCIPlpiExistsDualRay(
3032  SCIP_LPI* lpi /**< LP interface structure */
3033  )
3034 {
3035  assert(lpi != NULL);
3036  assert(lpi->solstat >= 0);
3037 
3038  return (lpi->solstat == CPX_STAT_INFEASIBLE);
3039 }
3040 
3041 /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point),
3042  * and the solver knows and can return the dual ray
3043  */
3044 SCIP_Bool SCIPlpiHasDualRay(
3045  SCIP_LPI* lpi /**< LP interface structure */
3046  )
3047 {
3048  assert(lpi != NULL);
3049  assert(lpi->cpxlp != NULL);
3050  assert(lpi->cpxenv != NULL);
3051  assert(lpi->solstat >= 0);
3052 
3053  return (lpi->solstat == CPX_STAT_INFEASIBLE && CPXgetmethod(lpi->cpxenv, lpi->cpxlp) == CPX_ALG_DUAL);
3054 }
3055 
3056 /** returns TRUE iff LP is proven to be dual unbounded */
3057 SCIP_Bool SCIPlpiIsDualUnbounded(
3058  SCIP_LPI* lpi /**< LP interface structure */
3059  )
3060 {
3061  int dualfeasible;
3062 
3063  assert(lpi != NULL);
3064  assert(lpi->cpxlp != NULL);
3065  assert(lpi->cpxenv != NULL);
3066  assert(lpi->solstat >= 0);
3067 
3068  SCIPdebugMessage("checking for dual unboundedness\n");
3069 
3070  ABORT_ZERO( CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, NULL, &dualfeasible) );
3071 
3072  return (dualfeasible && (lpi->solstat == CPX_STAT_INFEASIBLE || lpi->solstat == CPX_STAT_INForUNBD));
3073 }
3074 
3075 /** returns TRUE iff LP is proven to be dual infeasible */
3076 SCIP_Bool SCIPlpiIsDualInfeasible(
3077  SCIP_LPI* lpi /**< LP interface structure */
3078  )
3079 {
3080  int primalfeasible;
3081 
3082  assert(lpi != NULL);
3083  assert(lpi->cpxlp != NULL);
3084  assert(lpi->cpxenv != NULL);
3085  assert(lpi->solstat >= 0);
3086 
3087  SCIPdebugMessage("checking for dual infeasibility\n");
3088 
3089  ABORT_ZERO( CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &primalfeasible, NULL) );
3090 
3091  return (lpi->solstat == CPX_STAT_UNBOUNDED
3092  || lpi->solstat == CPX_STAT_OPTIMAL_FACE_UNBOUNDED
3093  || (lpi->solstat == CPX_STAT_INForUNBD && primalfeasible));
3094 }
3095 
3096 /** returns TRUE iff LP is proven to be dual feasible */
3097 SCIP_Bool SCIPlpiIsDualFeasible(
3098  SCIP_LPI* lpi /**< LP interface structure */
3099  )
3100 {
3101  int dualfeasible;
3102 
3103  assert(lpi != NULL);
3104  assert(lpi->cpxlp != NULL);
3105  assert(lpi->cpxenv != NULL);
3106  assert(lpi->solstat >= 0);
3107 
3108  SCIPdebugMessage("checking for dual feasibility\n");
3109 
3110  ABORT_ZERO( CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, NULL, &dualfeasible) );
3111 
3112  return (SCIP_Bool)dualfeasible;
3113 }
3114 
3115 /** returns TRUE iff LP was solved to optimality */
3116 SCIP_Bool SCIPlpiIsOptimal(
3117  SCIP_LPI* lpi /**< LP interface structure */
3118  )
3119 {
3120  assert(lpi != NULL);
3121  assert(lpi->solstat >= 0);
3122 
3123  return (lpi->solstat == CPX_STAT_OPTIMAL);
3124 }
3125 
3126 /** returns TRUE iff current LP basis is stable */
3127 SCIP_Bool SCIPlpiIsStable(
3128  SCIP_LPI* lpi /**< LP interface structure */
3129  )
3130 {
3131  assert(lpi != NULL);
3132  assert(lpi->cpxlp != NULL);
3133  assert(lpi->cpxenv != NULL);
3134  assert(lpi->solstat >= 0);
3135 
3136  SCIPdebugMessage("checking for stability: CPLEX solstat = %d\n", lpi->solstat);
3137 
3138  /* If the solution status of CPLEX is CPX_STAT_UNBOUNDED, it only means, there is an unbounded ray,
3139  * but not necessarily a feasible primal solution. If primalfeasible == FALSE, we interpret this
3140  * result as instability, s.t. the problem is resolved from scratch
3141  */
3142  if( lpi->solstat == CPX_STAT_UNBOUNDED )
3143  {
3144  int primalfeasible;
3145 
3146  ABORT_ZERO( CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, NULL, &primalfeasible, NULL) );
3147 
3148  if( !primalfeasible )
3149  return FALSE;
3150  }
3151 
3152  /* If the condition number of the basis should be checked, everything above the specified threshold is counted
3153  * as instable.
3154  */
3155  if( lpi->checkcondition && (SCIPlpiIsOptimal(lpi) || SCIPlpiIsObjlimExc(lpi)) )
3156  {
3157  SCIP_Real kappa;
3158 
3159  SCIP_CALL_ABORT( SCIPlpiGetRealSolQuality(lpi, SCIP_LPSOLQUALITY_ESTIMCONDITION, &kappa) );
3160 
3161  /* if the kappa could not be computed (e.g., because we do not have a basis), we cannot check the condition */
3162  if( kappa != SCIP_INVALID || kappa > lpi->conditionlimit )
3163  return FALSE;
3164  }
3165 
3166  return (lpi->solstat != CPX_STAT_NUM_BEST && lpi->solstat != CPX_STAT_OPTIMAL_INFEAS);
3167 }
3168 
3169 /** returns TRUE iff the objective limit was reached */
3170 SCIP_Bool SCIPlpiIsObjlimExc(
3171  SCIP_LPI* lpi /**< LP interface structure */
3172  )
3173 {
3174  assert(lpi != NULL);
3175  assert(lpi->solstat >= 0);
3176 
3177  return (lpi->solstat == CPX_STAT_ABORT_OBJ_LIM
3178  || lpi->solstat == CPX_STAT_ABORT_DUAL_OBJ_LIM
3179  || lpi->solstat == CPX_STAT_ABORT_PRIM_OBJ_LIM);
3180 }
3181 
3182 /** returns TRUE iff the iteration limit was reached */
3183 SCIP_Bool SCIPlpiIsIterlimExc(
3184  SCIP_LPI* lpi /**< LP interface structure */
3185  )
3186 {
3187  assert(lpi != NULL);
3188  assert(lpi->solstat >= 0);
3189 
3190  return (lpi->solstat == CPX_STAT_ABORT_IT_LIM);
3191 }
3192 
3193 /** returns TRUE iff the time limit was reached */
3194 SCIP_Bool SCIPlpiIsTimelimExc(
3195  SCIP_LPI* lpi /**< LP interface structure */
3196  )
3197 {
3198  assert(lpi != NULL);
3199  assert(lpi->solstat >= 0);
3200 
3201  return (lpi->solstat == CPX_STAT_ABORT_TIME_LIM);
3202 }
3203 
3204 /** returns the internal solution status of the solver */
3205 int SCIPlpiGetInternalStatus(
3206  SCIP_LPI* lpi /**< LP interface structure */
3207  )
3208 {
3209  assert(lpi != NULL);
3210  assert(lpi->cpxlp != NULL);
3211 
3212  return lpi->solstat;
3213 }
3214 
3215 /** tries to reset the internal status of the LP solver in order to ignore an instability of the last solving call */
3216 SCIP_RETCODE SCIPlpiIgnoreInstability(
3217  SCIP_LPI* lpi, /**< LP interface structure */
3218  SCIP_Bool* success /**< pointer to store, whether the instability could be ignored */
3219  )
3220 {
3221  assert(lpi != NULL);
3222  assert(lpi->cpxlp != NULL);
3223  assert(success != NULL);
3224  assert(lpi->solstat == CPX_STAT_UNBOUNDED
3225  || lpi->solstat == CPX_STAT_NUM_BEST
3226  || lpi->solstat == CPX_STAT_OPTIMAL_INFEAS);
3227 
3228  /* replace instable status with optimal status */
3229  if( lpi->solstat == CPX_STAT_NUM_BEST || lpi->solstat == CPX_STAT_OPTIMAL_INFEAS )
3230  lpi->solstat = CPX_STAT_OPTIMAL;
3231 
3232  *success = TRUE;
3233  lpi->instabilityignored = TRUE;
3234 
3235  return SCIP_OKAY;
3236 }
3237 
3238 /** gets objective value of solution */
3239 SCIP_RETCODE SCIPlpiGetObjval(
3240  SCIP_LPI* lpi, /**< LP interface structure */
3241  SCIP_Real* objval /**< stores the objective value */
3242  )
3243 {
3244  int retcode;
3245 
3246  assert(lpi != NULL);
3247  assert(lpi->cpxlp != NULL);
3248  assert(lpi->cpxenv != NULL);
3249 
3250  SCIPdebugMessage("getting solution's objective value\n");
3251 
3252  retcode = CPXgetobjval(lpi->cpxenv, lpi->cpxlp, objval);
3253 
3254  /* if CPLEX has no solution, e.g., because of a reached time limit, we return -infinity */
3255  if( retcode == CPXERR_NO_SOLN )
3256  {
3257  *objval = -SCIPlpiInfinity(lpi);
3258  }
3259  else
3260  {
3261  CHECK_ZERO( lpi->messagehdlr, retcode );
3262  }
3263 
3264  return SCIP_OKAY;
3265 }
3266 
3267 /** gets primal and dual solution vectors */
3268 SCIP_RETCODE SCIPlpiGetSol(
3269  SCIP_LPI* lpi, /**< LP interface structure */
3270  SCIP_Real* objval, /**< stores the objective value, may be NULL if not needed */
3271  SCIP_Real* primsol, /**< primal solution vector, may be NULL if not needed */
3272  SCIP_Real* dualsol, /**< dual solution vector, may be NULL if not needed */
3273  SCIP_Real* activity, /**< row activity vector, may be NULL if not needed */
3274  SCIP_Real* redcost /**< reduced cost vector, may be NULL if not needed */
3275  )
3276 {
3277  int dummy;
3278 
3279  assert(lpi != NULL);
3280  assert(lpi->cpxlp != NULL);
3281  assert(lpi->cpxenv != NULL);
3282  assert(lpi->solstat >= 0);
3283 
3284  SCIPdebugMessage("getting solution\n");
3285 
3286  CHECK_ZERO( lpi->messagehdlr, CPXsolution(lpi->cpxenv, lpi->cpxlp, &dummy, objval, primsol, dualsol, NULL, redcost) );
3287  assert(dummy == lpi->solstat || lpi->instabilityignored);
3288 
3289  if( activity != NULL )
3290  {
3291  CHECK_ZERO( lpi->messagehdlr, CPXgetax(lpi->cpxenv, lpi->cpxlp, activity, 0, CPXgetnumrows(lpi->cpxenv, lpi->cpxlp)-1) );
3292  }
3293 
3294  return SCIP_OKAY;
3295 }
3296 
3297 /** gets primal ray for unbounded LPs */
3298 SCIP_RETCODE SCIPlpiGetPrimalRay(
3299  SCIP_LPI* lpi, /**< LP interface structure */
3300  SCIP_Real* ray /**< primal ray */
3301  )
3302 {
3303  assert(lpi != NULL);
3304  assert(lpi->cpxlp != NULL);
3305  assert(lpi->cpxenv != NULL);
3306  assert(lpi->solstat >= 0);
3307 
3308  SCIPdebugMessage("calling CPLEX get primal ray: %d cols, %d rows\n",
3309  CPXgetnumcols(lpi->cpxenv, lpi->cpxlp), CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
3310 
3311  CHECK_ZERO( lpi->messagehdlr, CPXgetray(lpi->cpxenv, lpi->cpxlp, ray) );
3312 
3313  return SCIP_OKAY;
3314 }
3315 
3316 /** gets dual Farkas proof for infeasibility */
3317 SCIP_RETCODE SCIPlpiGetDualfarkas(
3318  SCIP_LPI* lpi, /**< LP interface structure */
3319  SCIP_Real* dualfarkas /**< dual Farkas row multipliers */
3320  )
3321 {
3322  assert(lpi != NULL);
3323  assert(lpi->cpxlp != NULL);
3324  assert(lpi->cpxenv != NULL);
3325  assert(lpi->solstat >= 0);
3326  assert(dualfarkas != NULL);
3327 
3328  SCIPdebugMessage("calling CPLEX dual Farkas: %d cols, %d rows\n",
3329  CPXgetnumcols(lpi->cpxenv, lpi->cpxlp), CPXgetnumrows(lpi->cpxenv, lpi->cpxlp));
3330 
3331  CHECK_ZERO( lpi->messagehdlr, CPXdualfarkas(lpi->cpxenv, lpi->cpxlp, dualfarkas, NULL) );
3332 
3333  return SCIP_OKAY;
3334 }
3335 
3336 /** gets the number of LP iterations of the last solve call */
3337 SCIP_RETCODE SCIPlpiGetIterations(
3338  SCIP_LPI* lpi, /**< LP interface structure */
3339  int* iterations /**< pointer to store the number of iterations of the last solve call */
3340  )
3341 {
3342  assert(lpi != NULL);
3343  assert(iterations != NULL);
3344 
3345  *iterations = lpi->iterations;
3346 
3347  return SCIP_OKAY;
3348 }
3349 
3350 /** gets information about the quality of an LP solution
3351  *
3352  * Such information is usually only available, if also a (maybe not optimal) solution is available.
3353  * The LPI should return SCIP_INVALID for @p quality, if the requested quantity is not available.
3354  */
3355 SCIP_RETCODE SCIPlpiGetRealSolQuality(
3356  SCIP_LPI* lpi, /**< LP interface structure */
3357  SCIP_LPSOLQUALITY qualityindicator, /**< indicates which quality should be returned */
3358  SCIP_Real* quality /**< pointer to store quality number */
3359  )
3360 {
3361  int solntype;
3362  int what;
3363 
3364  assert(lpi != NULL);
3365  assert(quality != NULL);
3366 
3367  *quality = SCIP_INVALID;
3368 
3369  SCIPdebugMessage("requesting solution quality from CPLEX: quality %d\n", qualityindicator);
3370 
3371  switch( qualityindicator )
3372  {
3373  case SCIP_LPSOLQUALITY_ESTIMCONDITION:
3374  what = CPX_KAPPA;
3375  break;
3376 
3377  case SCIP_LPSOLQUALITY_EXACTCONDITION:
3378  what = CPX_EXACT_KAPPA;
3379  break;
3380 
3381  default:
3382  SCIPerrorMessage("Solution quality %d unknown.\n", qualityindicator);
3383  return SCIP_INVALIDDATA;
3384  }
3385 
3386  CHECK_ZERO( lpi->messagehdlr, CPXsolninfo(lpi->cpxenv, lpi->cpxlp, NULL, &solntype, NULL, NULL) );
3387 
3388  if( solntype == CPX_BASIC_SOLN )
3389  {
3390  CHECK_ZERO( lpi->messagehdlr, CPXgetdblquality(lpi->cpxenv, lpi->cpxlp, quality, what) );
3391  }
3392 
3393  return SCIP_OKAY;
3394 }
3395 
3396 /**@} */
3397 
3398 
3399 
3400 
3401 /*
3402  * LP Basis Methods
3403  */
3404 
3405 /**@name LP Basis Methods */
3406 /**@{ */
3407 
3408 /** gets current basis status for columns and rows; arrays must be large enough to store the basis status */
3409 SCIP_RETCODE SCIPlpiGetBase(
3410  SCIP_LPI* lpi, /**< LP interface structure */
3411  int* cstat, /**< array to store column basis status, or NULL */
3412  int* rstat /**< array to store row basis status, or NULL */
3413  )
3414 {
3415  int i;
3416  int nrows;
3417  char sense;
3418 
3419  assert(lpi != NULL);
3420  assert(lpi->cpxlp != NULL);
3421  assert(lpi->cpxenv != NULL);
3422 
3423  SCIPdebugMessage("saving CPLEX basis into %p/%p\n", (void *) cstat, (void *) rstat);
3424 
3425  CHECK_ZERO( lpi->messagehdlr, CPXgetbase(lpi->cpxenv, lpi->cpxlp, cstat, rstat) );
3426 
3427  /* correct rstat values for "<=" constraints: Here CPX_AT_LOWER bound means that the slack is 0, i.e., the upper bound is tight */
3428  nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
3429  for (i = 0; i < nrows; ++i)
3430  {
3431  if ( rstat[i] == CPX_AT_LOWER )
3432  {
3433  CHECK_ZERO( lpi->messagehdlr, CPXgetsense(lpi->cpxenv, lpi->cpxlp, &sense, i, i) );
3434  if ( sense == 'L' )
3435  rstat[i] = SCIP_BASESTAT_UPPER;
3436  }
3437  }
3438 
3439  /* because the basis status values are equally defined in SCIP and CPLEX, they don't need to be transformed */
3440  assert((int)SCIP_BASESTAT_LOWER == CPX_AT_LOWER);
3441  assert((int)SCIP_BASESTAT_BASIC == CPX_BASIC);
3442  assert((int)SCIP_BASESTAT_UPPER == CPX_AT_UPPER);
3443  assert((int)SCIP_BASESTAT_ZERO == CPX_FREE_SUPER);
3444 
3445  return SCIP_OKAY;
3446 }
3447 
3448 /** sets current basis status for columns and rows */
3449 SCIP_RETCODE SCIPlpiSetBase(
3450  SCIP_LPI* lpi, /**< LP interface structure */
3451  int* cstat, /**< array with column basis status */
3452  int* rstat /**< array with row basis status */
3453  )
3454 {
3455  int i;
3456  int nrows;
3457  char sense;
3458 
3459  assert(lpi != NULL);
3460  assert(lpi->cpxlp != NULL);
3461  assert(lpi->cpxenv != NULL);
3462  assert(cstat != NULL);
3463  assert(rstat != NULL);
3464 
3465  SCIPdebugMessage("loading basis %p/%p into CPLEX\n", (void *) cstat, (void *) rstat);
3466 
3467  invalidateSolution(lpi);
3468 
3469  /* because the basis status values are equally defined in SCIP and CPLEX, they don't need to be transformed */
3470  assert((int)SCIP_BASESTAT_LOWER == CPX_AT_LOWER);
3471  assert((int)SCIP_BASESTAT_BASIC == CPX_BASIC);
3472  assert((int)SCIP_BASESTAT_UPPER == CPX_AT_UPPER);
3473  assert((int)SCIP_BASESTAT_ZERO == CPX_FREE_SUPER);
3474 
3475  /* correct rstat values for ">=" constraints: Here CPX_AT_LOWER bound means that the slack is 0, i.e., the upper bound is tight */
3476  nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
3477  for (i = 0; i < nrows; ++i)
3478  {
3479  if ( rstat[i] == SCIP_BASESTAT_UPPER )
3480  {
3481  CHECK_ZERO( lpi->messagehdlr, CPXgetsense(lpi->cpxenv, lpi->cpxlp, &sense, i, i) );
3482  if ( sense == 'L' )
3483  rstat[i] = CPX_AT_LOWER;
3484  }
3485  }
3486 
3487  CHECK_ZERO( lpi->messagehdlr, CPXcopybase(lpi->cpxenv, lpi->cpxlp, cstat, rstat) );
3488 
3489  return SCIP_OKAY;
3490 }
3491 
3492 /** returns the indices of the basic columns and rows; basic column n gives value n, basic row m gives value -1-m */
3493 SCIP_RETCODE SCIPlpiGetBasisInd(
3494  SCIP_LPI* lpi, /**< LP interface structure */
3495  int* bind /**< pointer to store basis indices ready to keep number of rows entries */
3496  )
3497 {
3498  int retval;
3499 
3500  assert(lpi != NULL);
3501  assert(lpi->cpxlp != NULL);
3502  assert(lpi->cpxenv != NULL);
3503 
3504  SCIPdebugMessage("getting basis information\n");
3505 
3506  /* this might be turned off if the user as called SCIPlpiClearState() or set SCIP_LPPAR_FROMSCRATCH to TRUE */
3507  setIntParam(lpi, CPX_PARAM_ADVIND, CPX_ON);
3508  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
3509 
3510  retval = CPXgetbhead(lpi->cpxenv, lpi->cpxlp, bind, NULL);
3511  if( retval == CPXERR_NO_SOLN || retval == CPXERR_NO_LU_FACTOR || retval == CPXERR_NO_BASIC_SOLN || retval == CPXERR_NO_BASIS )
3512  {
3513  SCIP_CALL_QUIET( restoreLPData(lpi) );
3514  retval = CPXgetbhead(lpi->cpxenv, lpi->cpxlp, bind, NULL);
3515  }
3516  CHECK_ZERO( lpi->messagehdlr, retval );
3517 
3518  return SCIP_OKAY;
3519 }
3520 
3521 /** get dense row of inverse basis matrix B^-1 */
3522 SCIP_RETCODE SCIPlpiGetBInvRow(
3523  SCIP_LPI* lpi, /**< LP interface structure */
3524  int r, /**< row number */
3525  SCIP_Real* coef /**< pointer to store the coefficients of the row */
3526  )
3527 {
3528  int retval;
3529 
3530  assert(lpi != NULL);
3531  assert(lpi->cpxlp != NULL);
3532  assert(lpi->cpxenv != NULL);
3533 
3534  SCIPdebugMessage("getting binv-row %d\n", r);
3535 
3536  /* this might be turned off if the user as called SCIPlpiClearState() or set SCIP_LPPAR_FROMSCRATCH to TRUE */
3537  setIntParam(lpi, CPX_PARAM_ADVIND, CPX_ON);
3538  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
3539 
3540  retval = CPXbinvrow(lpi->cpxenv, lpi->cpxlp, r, coef);
3541  if( retval == CPXERR_NO_SOLN || retval == CPXERR_NO_LU_FACTOR || retval == CPXERR_NO_BASIC_SOLN || retval == CPXERR_NO_BASIS )
3542  {
3543  SCIP_CALL_QUIET( restoreLPData(lpi) );
3544  retval = CPXbinvrow(lpi->cpxenv, lpi->cpxlp, r, coef);
3545  }
3546  CHECK_ZERO( lpi->messagehdlr, retval );
3547 
3548  return SCIP_OKAY;
3549 }
3550 
3551 /** get dense column of inverse basis matrix B^-1 */
3552 SCIP_RETCODE SCIPlpiGetBInvCol(
3553  SCIP_LPI* lpi, /**< LP interface structure */
3554  int c, /**< column number of B^-1; this is NOT the number of the column in the LP;
3555  * you have to call SCIPlpiGetBasisInd() to get the array which links the
3556  * B^-1 column numbers to the row and column numbers of the LP!
3557  * c must be between 0 and nrows-1, since the basis has the size
3558  * nrows * nrows */
3559  SCIP_Real* coef /**< pointer to store the coefficients of the column */
3560  )
3561 {
3562  int retval;
3563 
3564  assert(lpi != NULL);
3565  assert(lpi->cpxlp != NULL);
3566  assert(lpi->cpxenv != NULL);
3567 
3568  SCIPdebugMessage("getting binv-col %d\n", c);
3569 
3570  /* this might be turned off if the user as called SCIPlpiClearState() or set SCIP_LPPAR_FROMSCRATCH to TRUE */
3571  setIntParam(lpi, CPX_PARAM_ADVIND, CPX_ON);
3572  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
3573 
3574  retval = CPXbinvcol(lpi->cpxenv, lpi->cpxlp, c, coef);
3575  if( retval == CPXERR_NO_SOLN || retval == CPXERR_NO_LU_FACTOR || retval == CPXERR_NO_BASIC_SOLN || retval == CPXERR_NO_BASIS )
3576  {
3577  SCIP_CALL_QUIET( restoreLPData(lpi) );
3578  retval = CPXbinvcol(lpi->cpxenv, lpi->cpxlp, c, coef);
3579  }
3580  CHECK_ZERO( lpi->messagehdlr, retval );
3581 
3582  return SCIP_OKAY;
3583 }
3584 
3585 /** get dense row of inverse basis matrix times constraint matrix B^-1 * A */
3586 SCIP_RETCODE SCIPlpiGetBInvARow(
3587  SCIP_LPI* lpi, /**< LP interface structure */
3588  int r, /**< row number */
3589  const SCIP_Real* binvrow, /**< row in (A_B)^-1 from prior call to SCIPlpiGetBInvRow(), or NULL */
3590  SCIP_Real* coef /**< vector to return coefficients */
3591  )
3592 { /*lint --e{715}*/
3593  int retval;
3594 
3595  assert(lpi != NULL);
3596  assert(lpi->cpxlp != NULL);
3597  assert(lpi->cpxenv != NULL);
3598 
3599  SCIPdebugMessage("getting binva-row %d\n", r);
3600 
3601  /* this might be turned off if the user as called SCIPlpiClearState() or set SCIP_LPPAR_FROMSCRATCH to TRUE */
3602  setIntParam(lpi, CPX_PARAM_ADVIND, CPX_ON);
3603  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
3604 
3605  retval = CPXbinvarow(lpi->cpxenv, lpi->cpxlp, r, coef);
3606  if( retval == CPXERR_NO_SOLN || retval == CPXERR_NO_LU_FACTOR || retval == CPXERR_NO_BASIC_SOLN || retval == CPXERR_NO_BASIS )
3607  {
3608  SCIP_CALL_QUIET( restoreLPData(lpi) );
3609  retval = CPXbinvarow(lpi->cpxenv, lpi->cpxlp, r, coef);
3610  }
3611  CHECK_ZERO( lpi->messagehdlr, retval );
3612 
3613  return SCIP_OKAY;
3614 }
3615 
3616 /** get dense column of inverse basis matrix times constraint matrix B^-1 * A */
3617 SCIP_RETCODE SCIPlpiGetBInvACol(
3618  SCIP_LPI* lpi, /**< LP interface structure */
3619  int c, /**< column number */
3620  SCIP_Real* coef /**< vector to return coefficients */
3621  )
3622 { /*lint --e{715}*/
3623  int retval;
3624 
3625  assert(lpi->cpxenv != NULL);
3626  assert(lpi != NULL);
3627  assert(lpi->cpxlp != NULL);
3628 
3629  SCIPdebugMessage("getting binva-col %d\n", c);
3630 
3631  /* this might be turned off if the user as called SCIPlpiClearState() or set SCIP_LPPAR_FROMSCRATCH to TRUE */
3632  setIntParam(lpi, CPX_PARAM_ADVIND, CPX_ON);
3633  SCIP_CALL( setParameterValues(lpi, &(lpi->cpxparam)) );
3634 
3635  retval = CPXbinvacol(lpi->cpxenv, lpi->cpxlp, c, coef);
3636  if( retval == CPXERR_NO_SOLN || retval == CPXERR_NO_LU_FACTOR || retval == CPXERR_NO_BASIC_SOLN || retval == CPXERR_NO_BASIS )
3637  {
3638  SCIP_CALL_QUIET( restoreLPData(lpi) );
3639  retval = CPXbinvacol(lpi->cpxenv, lpi->cpxlp, c, coef);
3640  }
3641  CHECK_ZERO( lpi->messagehdlr, retval );
3642 
3643  return SCIP_OKAY;
3644 }
3645 
3646 /**@} */
3647 
3648 
3649 
3650 
3651 /*
3652  * LP State Methods
3653  */
3654 
3655 /**@name LP State Methods */
3656 /**@{ */
3657 
3658 /** stores LPi state (like basis information) into lpistate object */
3659 SCIP_RETCODE SCIPlpiGetState(
3660  SCIP_LPI* lpi, /**< LP interface structure */
3661  BMS_BLKMEM* blkmem, /**< block memory */
3662  SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
3663  )
3664 {
3665  int ncols;
3666  int nrows;
3667 
3668  assert(blkmem != NULL);
3669  assert(lpi != NULL);
3670  assert(lpi->cpxlp != NULL);
3671  assert(lpi->cpxenv != NULL);
3672  assert(lpistate != NULL);
3673 
3674  /* if there is no basis information available (e.g. after barrier without crossover), or no state can be saved; if
3675  * SCIPlpiClearState() has been called, do not return the state
3676  */
3677  if( !lpi->solisbasic || lpi->clearstate )
3678  {
3679  *lpistate = NULL;
3680  return SCIP_OKAY;
3681  }
3682 
3683  ncols = CPXgetnumcols(lpi->cpxenv, lpi->cpxlp);
3684  nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
3685  assert(ncols >= 0);
3686  assert(nrows >= 0);
3687 
3688  /* allocate lpistate data */
3689  SCIP_CALL( lpistateCreate(lpistate, blkmem, ncols, nrows) );
3690 
3691  SCIPdebugMessage("storing CPLEX LPI state in %p (%d cols, %d rows)\n", (void *) *lpistate, ncols, nrows);
3692 
3693  /* get unpacked basis information from CPLEX */
3694  SCIP_CALL( getBase(lpi) );
3695 
3696  /* pack LPi state data */
3697  (*lpistate)->ncols = ncols;
3698  (*lpistate)->nrows = nrows;
3699  lpistatePack(*lpistate, lpi->cstat, lpi->rstat);
3700 
3701  return SCIP_OKAY;
3702 }
3703 
3704 /** loads LPi state (like basis information) into solver; note that the LP might have been extended with additional
3705  * columns and rows since the state was stored with SCIPlpiGetState()
3706  */
3707 SCIP_RETCODE SCIPlpiSetState(
3708  SCIP_LPI* lpi, /**< LP interface structure */
3709  BMS_BLKMEM* blkmem, /**< block memory */
3710  SCIP_LPISTATE* lpistate /**< LPi state information (like basis information) */
3711  )
3712 {
3713  int lpncols;
3714  int lpnrows;
3715  int i;
3716 
3717  assert(blkmem != NULL);
3718  assert(lpi != NULL);
3719  assert(lpi->cpxlp != NULL);
3720  assert(lpi->cpxenv != NULL);
3721 
3722  /* if there was no basis information available, the LPI state was not stored */
3723  if( lpistate == NULL )
3724  return SCIP_OKAY;
3725 
3726  lpncols = CPXgetnumcols(lpi->cpxenv, lpi->cpxlp);
3727  lpnrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
3728  assert(lpistate->ncols <= lpncols);
3729  assert(lpistate->nrows <= lpnrows);
3730 
3731  SCIPdebugMessage("loading LPI state %p (%d cols, %d rows) into CPLEX LP with %d cols and %d rows\n",
3732  (void *) lpistate, lpistate->ncols, lpistate->nrows, lpncols, lpnrows);
3733 
3734  if( lpistate->ncols == 0 || lpistate->nrows == 0 )
3735  return SCIP_OKAY;
3736 
3737  /* allocate enough memory for storing uncompressed basis information */
3738  SCIP_CALL( ensureCstatMem(lpi, lpncols) );
3739  SCIP_CALL( ensureRstatMem(lpi, lpnrows) );
3740 
3741  /* unpack LPi state data */
3742  lpistateUnpack(lpistate, lpi->cstat, lpi->rstat);
3743 
3744  /* extend the basis to the current LP beyond the previously existing columns */
3745  for( i = lpistate->ncols; i < lpncols; ++i )
3746  {
3747  SCIP_Real bnd;
3748  CHECK_ZERO( lpi->messagehdlr, CPXgetlb(lpi->cpxenv, lpi->cpxlp, &bnd, i, i) );
3749  if ( SCIPlpiIsInfinity(lpi, REALABS(bnd)) )
3750  {
3751  /* if lower bound is +/- infinity -> try upper bound */
3752  CHECK_ZERO( lpi->messagehdlr, CPXgetub(lpi->cpxenv, lpi->cpxlp, &bnd, i, i) );
3753  if ( SCIPlpiIsInfinity(lpi, REALABS(bnd)) )
3754  lpi->cstat[i] = SCIP_BASESTAT_ZERO; /* variable is free -> super basic */
3755  else
3756  lpi->cstat[i] = SCIP_BASESTAT_UPPER; /* use finite upper bound */
3757  }
3758  else
3759  lpi->cstat[i] = SCIP_BASESTAT_LOWER; /* use finite lower bound */
3760  }
3761  for( i = lpistate->nrows; i < lpnrows; ++i )
3762  lpi->rstat[i] = SCIP_BASESTAT_BASIC;
3763 
3764  /* load basis information into CPLEX */
3765  SCIP_CALL( setBase(lpi) );
3766 
3767  return SCIP_OKAY;
3768 }
3769 
3770 /** clears current LPi state (like basis information) of the solver */
3771 SCIP_RETCODE SCIPlpiClearState(
3772  SCIP_LPI* lpi /**< LP interface structure */
3773  )
3774 {
3775  assert(lpi != NULL);
3776 
3777  /* set CPX_PARAM_ADVIND to CPX_OFF for the next solve */
3778  lpi->clearstate = TRUE;
3779 
3780  return SCIP_OKAY;
3781 }
3782 
3783 /** frees LPi state information */
3784 SCIP_RETCODE SCIPlpiFreeState(
3785  SCIP_LPI* lpi, /**< LP interface structure */
3786  BMS_BLKMEM* blkmem, /**< block memory */
3787  SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
3788  )
3789 {
3790  assert(lpi != NULL);
3791  assert(lpistate != NULL);
3792 
3793  if( *lpistate != NULL )
3794  {
3795  lpistateFree(lpistate, blkmem);
3796  }
3797 
3798  return SCIP_OKAY;
3799 }
3800 
3801 /** checks, whether the given LP state contains simplex basis information */
3802 SCIP_Bool SCIPlpiHasStateBasis(
3803  SCIP_LPI* lpi, /**< LP interface structure */
3804  SCIP_LPISTATE* lpistate /**< LP state information (like basis information) */
3805  )
3806 { /*lint --e{715}*/
3807  return (lpistate != NULL);
3808 }
3809 
3810 /** reads LP state (like basis information from a file */
3811 SCIP_RETCODE SCIPlpiReadState(
3812  SCIP_LPI* lpi, /**< LP interface structure */
3813  const char* fname /**< file name */
3814  )
3815 {
3816  assert(lpi != NULL);
3817  assert(lpi->cpxlp != NULL);
3818  assert(lpi->cpxenv != NULL);
3819 
3820  SCIPdebugMessage("reading LP state from file <%s>\n", fname);
3821 
3822  CHECK_ZERO( lpi->messagehdlr, CPXreadcopybase(lpi->cpxenv, lpi->cpxlp, fname) );
3823 
3824  return SCIP_OKAY;
3825 }
3826 
3827 /** writes LP state (like basis information) to a file */
3828 SCIP_RETCODE SCIPlpiWriteState(
3829  SCIP_LPI* lpi, /**< LP interface structure */
3830  const char* fname /**< file name */
3831  )
3832 {
3833  assert(lpi != NULL);
3834  assert(lpi->cpxlp != NULL);
3835  assert(lpi->cpxenv != NULL);
3836 
3837  SCIPdebugMessage("writing LP state to file <%s>\n", fname);
3838 
3839  CHECK_ZERO( lpi->messagehdlr, CPXmbasewrite(lpi->cpxenv, lpi->cpxlp, fname) );
3840 
3841  return SCIP_OKAY;
3842 }
3843 
3844 /**@} */
3845 
3846 
3847 
3848 
3849 /*
3850  * LP Pricing Norms Methods
3851  */
3852 
3853 /**@name LP Pricing Norms Methods */
3854 /**@{ */
3855 
3856 /** stores LPi pricing norms information
3857  *
3858  * @todo store primal norms as well?
3859  */
3860 SCIP_RETCODE SCIPlpiGetNorms(
3861  SCIP_LPI* lpi, /**< LP interface structure */
3862  BMS_BLKMEM* blkmem, /**< block memory */
3863  SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
3864  )
3865 {
3866  int nrows;
3867  int retval;
3868 
3869  assert(blkmem != NULL);
3870  assert(lpi != NULL);
3871  assert(lpi->cpxlp != NULL);
3872  assert(lpi->cpxenv != NULL);
3873  assert(lpi->messagehdlr != NULL);
3874  assert(lpinorms != NULL);
3875 
3876  /* if there is no basis information available (e.g. after barrier without crossover), norms cannot be saved; if
3877  * SCIPlpiClearState() has been called, do not return the state
3878  */
3879  if( !lpi->solisbasic || lpi->clearstate )
3880  {
3881  *lpinorms = NULL;
3882  return SCIP_OKAY;
3883  }
3884 
3885  nrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
3886  assert(nrows >= 0);
3887 
3888  /* allocate lpinorms data */
3889  SCIP_ALLOC( BMSallocBlockMemory(blkmem, lpinorms) );
3890  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->norm, nrows) );
3891  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->head, nrows) );
3892  (*lpinorms)->normlen = 0;
3893 
3894  SCIPdebugMessage("storing CPLEX LPI pricing norms in %p (%d rows)\n", (void *) *lpinorms, nrows);
3895 
3896  /* get dual norms */
3897  retval = CPXgetdnorms(lpi->cpxenv, lpi->cpxlp, (*lpinorms)->norm, (*lpinorms)->head, &((*lpinorms)->normlen));
3898 
3899  /* if CPLEX used the primal simplex in the last optimization call, we do not have dual norms (error 1264) */
3900  if( retval == 1264 )
3901  {
3902  /* no norms available, free lpinorms data */
3903  BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->head, nrows);
3904  BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->norm, nrows);
3905  BMSfreeBlockMemory(blkmem, lpinorms);
3906  assert(*lpinorms == NULL);
3907  }
3908  else
3909  {
3910  assert((*lpinorms)->normlen == nrows);
3911  CHECK_ZERO( lpi->messagehdlr, retval );
3912  }
3913 
3914  return SCIP_OKAY;
3915 }
3916 
3917 /** loads LPi pricing norms into solver; note that the LP might have been extended with additional
3918  * columns and rows since the state was stored with SCIPlpiGetNorms()
3919  */
3920 SCIP_RETCODE SCIPlpiSetNorms(
3921  SCIP_LPI* lpi, /**< LP interface structure */
3922  BMS_BLKMEM* blkmem, /**< block memory */
3923  SCIP_LPINORMS* lpinorms /**< LPi pricing norms information */
3924  )
3925 {
3926  int lpnrows;
3927 
3928  assert(blkmem != NULL);
3929  assert(lpi != NULL);
3930  assert(lpi->cpxlp != NULL);
3931  assert(lpi->cpxenv != NULL);
3932 
3933  /* if there was no pricing norms information available, the LPI norms were not stored */
3934  if( lpinorms == NULL )
3935  return SCIP_OKAY;
3936 
3937  lpnrows = CPXgetnumrows(lpi->cpxenv, lpi->cpxlp);
3938  assert(lpinorms->normlen <= lpnrows);
3939 
3940  SCIPdebugMessage("loading LPI simplex norms %p (%d rows) into CPLEX LP with %d rows\n",
3941  (void *) lpinorms, lpinorms->normlen, lpnrows);
3942 
3943  if( lpinorms->normlen == 0 )
3944  return SCIP_OKAY;
3945 
3946  /* load pricing norms information into CPLEX */
3947  CHECK_ZERO( lpi->messagehdlr, CPXcopydnorms(lpi->cpxenv, lpi->cpxlp, lpinorms->norm, lpinorms->head, lpinorms->normlen) );
3948 
3949  return SCIP_OKAY;
3950 }
3951 
3952 /** frees pricing norms information */
3953 SCIP_RETCODE SCIPlpiFreeNorms(
3954  SCIP_LPI* lpi, /**< LP interface structure */
3955  BMS_BLKMEM* blkmem, /**< block memory */
3956  SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
3957  )
3958 {
3959  assert(lpi != NULL);
3960  assert(lpinorms != NULL);
3961 
3962  BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->head, (*lpinorms)->normlen);
3963  BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->norm, (*lpinorms)->normlen);
3964  BMSfreeBlockMemory(blkmem, lpinorms);
3965 
3966  return SCIP_OKAY;
3967 }
3968 
3969 /**@} */
3970 
3971 
3972 
3973 
3974 /*
3975  * Parameter Methods
3976  */
3977 
3978 /**@name Parameter Methods */
3979 /**@{ */
3980 
3981 /** gets integer parameter of LP */
3982 SCIP_RETCODE SCIPlpiGetIntpar(
3983  SCIP_LPI* lpi, /**< LP interface structure */
3984  SCIP_LPPARAM type, /**< parameter number */
3985  int* ival /**< buffer to store the parameter value */
3986  )
3987 {
3988  assert(lpi != NULL);
3989  assert(lpi->cpxlp != NULL);
3990  assert(ival != NULL);
3991 
3992  SCIPdebugMessage("getting int parameter %d\n", type);
3993 
3994  switch( type )
3995  {
3996  case SCIP_LPPAR_FROMSCRATCH:
3997  *ival = lpi->fromscratch;
3998  break;
3999  case SCIP_LPPAR_FASTMIP:
4000  *ival = getIntParam(lpi, CPX_PARAM_FASTMIP);
4001  break;
4002  case SCIP_LPPAR_SCALING:
4003 #if (CPX_VERSION <= 1100)
4004  if( lpi->rngfound )
4005  return SCIP_PARAMETERUNKNOWN;
4006 #endif
4007  *ival = (getIntParam(lpi, CPX_PARAM_SCAIND) == 0);
4008  break;
4009  case SCIP_LPPAR_PRESOLVING:
4010  *ival = (getIntParam(lpi, CPX_PARAM_PREIND) == CPX_ON);
4011  break;
4012  case SCIP_LPPAR_PRICING:
4013  *ival = (int)lpi->pricing; /* store pricing method in LPI struct */
4014  break;
4015 #if 0
4016  case SCIP_LPPAR_PRICING:
4017  switch( getIntParam(lpi, CPX_PARAM_PPRIIND) )
4018  {
4019  case CPX_PPRIIND_FULL:
4020  *ival = (int)SCIP_PRICING_FULL;
4021  break;
4022  case CPX_PPRIIND_PARTIAL:
4023  *ival = (int)SCIP_PRICING_PARTIAL;
4024  break;
4025  case CPX_PPRIIND_STEEP:
4026  *ival = (int)SCIP_PRICING_STEEP;
4027  break;
4028  case CPX_PPRIIND_STEEPQSTART:
4029  *ival = (int)SCIP_PRICING_STEEPQSTART;
4030  break;
4031 #if (CPX_VERSION >= 900)
4032  case CPX_PPRIIND_DEVEX:
4033  *ival = (int)SCIP_PRICING_DEVEX;
4034  break;
4035 #endif
4036  default:
4037  *ival = (int)SCIP_PRICING_AUTO;
4038  break;
4039  }
4040  break;
4041 #endif
4042  case SCIP_LPPAR_LPINFO:
4043  *ival = (getIntParam(lpi, CPX_PARAM_SCRIND) == CPX_ON);
4044  break;
4045  case SCIP_LPPAR_LPITLIM:
4046  *ival = getIntParam(lpi, CPX_PARAM_ITLIM);
4047 #if (CPX_VERSION <= 1230)
4048  if( *ival >= CPX_INT_MAX )
4049  *ival = INT_MAX;
4050 #endif
4051  break;
4052  case SCIP_LPPAR_THREADS:
4053 #if (CPX_VERSION == 1100 || (CPX_VERSION == 1220 && (CPX_SUBVERSION == 0 || CPX_SUBVERSION == 2)))
4054  /* Due to CPLEX bug, we always set the thread count to 1. In order to fulfill an assert in lp.c, we have to
4055  * return the value set by SCIP and not the real thread count */
4056  *ival = lpi->pseudonthreads;
4057  assert(getIntParam(lpi, CPX_PARAM_THREADS) == 1);
4058 #else
4059  *ival = getIntParam(lpi, CPX_PARAM_THREADS);
4060 #endif
4061  break;
4062  default:
4063  return SCIP_PARAMETERUNKNOWN;
4064  } /*lint !e788*/
4065 
4066  return SCIP_OKAY;
4067 }
4068 
4069 /** sets integer parameter of LP */
4070 SCIP_RETCODE SCIPlpiSetIntpar(
4071  SCIP_LPI* lpi, /**< LP interface structure */
4072  SCIP_LPPARAM type, /**< parameter number */
4073  int ival /**< parameter value */
4074  )
4075 {
4076  assert(lpi != NULL);
4077  assert(lpi->cpxlp != NULL);
4078 
4079  SCIPdebugMessage("setting int parameter %d to %d\n", type, ival);
4080 
4081  switch( type )
4082  {
4083  case SCIP_LPPAR_FROMSCRATCH:
4084  assert(ival == TRUE || ival == FALSE);
4085  lpi->fromscratch = ival;
4086  break;
4087  case SCIP_LPPAR_FASTMIP:
4088  assert(0 <= ival && ival <= 1);
4089  setIntParam(lpi, CPX_PARAM_FASTMIP, ival);
4090  break;
4091  case SCIP_LPPAR_SCALING:
4092  assert(ival == TRUE || ival == FALSE);
4093 #if (CPX_VERSION <= 1100)
4094  if( lpi->rngfound )
4095  return SCIP_PARAMETERUNKNOWN;
4096 #endif
4097  setIntParam(lpi, CPX_PARAM_SCAIND, ival == TRUE ? 0 : -1);
4098  break;
4099  case SCIP_LPPAR_PRESOLVING:
4100  assert(ival == TRUE || ival == FALSE);
4101  setIntParam(lpi, CPX_PARAM_PREIND, ival == TRUE ? CPX_ON : CPX_OFF);
4102  break;
4103  case SCIP_LPPAR_PRICING:
4104  lpi->pricing = (SCIP_PRICING)ival;
4105  switch( (SCIP_PRICING)ival )
4106  {
4107  case SCIP_PRICING_AUTO:
4108  setIntParam(lpi, CPX_PARAM_PPRIIND, CPX_PPRIIND_AUTO);
4109  setIntParam(lpi, CPX_PARAM_DPRIIND, CPX_DPRIIND_AUTO);
4110  break;
4111  case SCIP_PRICING_FULL:
4112  setIntParam(lpi, CPX_PARAM_PPRIIND, CPX_PPRIIND_FULL);
4113  setIntParam(lpi, CPX_PARAM_DPRIIND, CPX_DPRIIND_FULL);
4114  break;
4115  case SCIP_PRICING_PARTIAL:
4116  setIntParam(lpi, CPX_PARAM_PPRIIND, CPX_PPRIIND_PARTIAL);
4117  setIntParam(lpi, CPX_PARAM_DPRIIND, CPX_DPRIIND_AUTO);
4118  break;
4119  case SCIP_PRICING_LPIDEFAULT:
4120  case SCIP_PRICING_STEEP:
4121  setIntParam(lpi, CPX_PARAM_PPRIIND, CPX_PPRIIND_STEEP);
4122  setIntParam(lpi, CPX_PARAM_DPRIIND, CPX_DPRIIND_STEEP);
4123  break;
4124  case SCIP_PRICING_STEEPQSTART:
4125  setIntParam(lpi, CPX_PARAM_PPRIIND, CPX_PPRIIND_STEEPQSTART);
4126  setIntParam(lpi, CPX_PARAM_DPRIIND, CPX_DPRIIND_STEEPQSTART);
4127  break;
4128 #if (CPX_VERSION >= 900)
4129  case SCIP_PRICING_DEVEX:
4130  setIntParam(lpi, CPX_PARAM_PPRIIND, CPX_PPRIIND_DEVEX);
4131  setIntParam(lpi, CPX_PARAM_DPRIIND, CPX_DPRIIND_DEVEX);
4132  break;
4133 #endif
4134  default:
4135  return SCIP_LPERROR;
4136  }
4137  break;
4138  case SCIP_LPPAR_LPINFO:
4139  assert(ival == TRUE || ival == FALSE);
4140  if( ival )
4141  setIntParam(lpi, CPX_PARAM_SCRIND, CPX_ON);
4142  else
4143  setIntParam(lpi, CPX_PARAM_SCRIND, CPX_OFF);
4144  break;
4145  case SCIP_LPPAR_LPITLIM:
4146 #if (CPX_VERSION <= 1230)
4147  ival = MIN(ival, CPX_INT_MAX);
4148 #endif
4149  setIntParam(lpi, CPX_PARAM_ITLIM, ival);
4150  break;
4151  case SCIP_LPPAR_THREADS:
4152 #if (CPX_VERSION == 1100 || (CPX_VERSION == 1220 && (CPX_SUBVERSION == 0 || CPX_SUBVERSION == 2)))
4153  /* Due to CPLEX bug, we always set the thread count to 1. In order to fulfill an assert in lp.c, we have to
4154  * store the value set by SCIP and return it later instead of the real thread count */
4155  lpi->pseudonthreads = ival;
4156  ival = 1;
4157 #else
4158  ival = MIN(ival, CPX_INT_MAX);
4159 #endif
4160  setIntParam(lpi, CPX_PARAM_THREADS, ival);
4161  break;
4162  default:
4163  return SCIP_PARAMETERUNKNOWN;
4164  } /*lint !e788*/
4165 
4166  return SCIP_OKAY;
4167 }
4168 
4169 /** gets floating point parameter of LP */
4170 SCIP_RETCODE SCIPlpiGetRealpar(
4171  SCIP_LPI* lpi, /**< LP interface structure */
4172  SCIP_LPPARAM type, /**< parameter number */
4173  SCIP_Real* dval /**< buffer to store the parameter value */
4174  )
4175 {
4176  assert(lpi != NULL);
4177  assert(lpi->cpxlp != NULL);
4178  assert(dval != NULL);
4179 
4180  SCIPdebugMessage("getting real parameter %d\n", type);
4181 
4182  switch( type )
4183  {
4184  case SCIP_LPPAR_FEASTOL:
4185  *dval = getDblParam(lpi, CPX_PARAM_EPRHS);
4186  break;
4187  case SCIP_LPPAR_DUALFEASTOL:
4188  *dval = getDblParam(lpi, CPX_PARAM_EPOPT);
4189  break;
4190  case SCIP_LPPAR_BARRIERCONVTOL:
4191  *dval = getDblParam(lpi, CPX_PARAM_BAREPCOMP);
4192  break;
4193  case SCIP_LPPAR_LOBJLIM:
4194  *dval = getDblParam(lpi, CPX_PARAM_OBJLLIM);
4195  break;
4196  case SCIP_LPPAR_UOBJLIM:
4197  *dval = getDblParam(lpi, CPX_PARAM_OBJULIM);
4198  break;
4199  case SCIP_LPPAR_LPTILIM:
4200  *dval = getDblParam(lpi, CPX_PARAM_TILIM);
4201  break;
4202  case SCIP_LPPAR_MARKOWITZ:
4203  *dval = getDblParam(lpi, CPX_PARAM_EPMRK);
4204  break;
4205  case SCIP_LPPAR_CONDITIONLIMIT:
4206  *dval = lpi->conditionlimit;
4207  break;
4208  default:
4209  return SCIP_PARAMETERUNKNOWN;
4210  } /*lint !e788*/
4211 
4212  return SCIP_OKAY;
4213 }
4214 
4215 /** sets floating point parameter of LP */
4216 SCIP_RETCODE SCIPlpiSetRealpar(
4217  SCIP_LPI* lpi, /**< LP interface structure */
4218  SCIP_LPPARAM type, /**< parameter number */
4219  SCIP_Real dval /**< parameter value */
4220  )
4221 {
4222  assert(lpi != NULL);
4223  assert(lpi->cpxlp != NULL);
4224 
4225  SCIPdebugMessage("setting real parameter %d to %.15g\n", type, dval);
4226 
4227  switch( type )
4228  {
4229  case SCIP_LPPAR_FEASTOL:
4230  setDblParam(lpi, CPX_PARAM_EPRHS, dval);
4231  lpi->feastol = dval;
4232  break;
4233  case SCIP_LPPAR_DUALFEASTOL:
4234  setDblParam(lpi, CPX_PARAM_EPOPT, dval);
4235  break;
4236  case SCIP_LPPAR_BARRIERCONVTOL:
4237  setDblParam(lpi, CPX_PARAM_BAREPCOMP, dval);
4238  break;
4239  case SCIP_LPPAR_LOBJLIM:
4240  setDblParam(lpi, CPX_PARAM_OBJLLIM, dval);
4241  break;
4242  case SCIP_LPPAR_UOBJLIM:
4243  setDblParam(lpi, CPX_PARAM_OBJULIM, dval);
4244  break;
4245  case SCIP_LPPAR_LPTILIM:
4246  setDblParam(lpi, CPX_PARAM_TILIM, dval);
4247  break;
4248  case SCIP_LPPAR_MARKOWITZ:
4249  setDblParam(lpi, CPX_PARAM_EPMRK, dval);
4250  break;
4251  case SCIP_LPPAR_CONDITIONLIMIT:
4252  lpi->conditionlimit = dval;
4253  lpi->checkcondition = (dval >= 0);
4254  break;
4255  default:
4256  return SCIP_PARAMETERUNKNOWN;
4257  } /*lint !e788*/
4258 
4259  return SCIP_OKAY;
4260 }
4261 
4262 /**@} */
4263 
4264 
4265 
4266 
4267 /*
4268  * Numerical Methods
4269  */
4270 
4271 /**@name Numerical Methods */
4272 /**@{ */
4273 
4274 /** returns value treated as infinity in the LP solver */
4275 SCIP_Real SCIPlpiInfinity(
4276  SCIP_LPI* lpi /**< LP interface structure */
4277  )
4278 { /*lint --e{715}*/
4279  return CPX_INFBOUND;
4280 }
4281 
4282 /** checks if given value is treated as infinity in the LP solver */
4283 SCIP_Bool SCIPlpiIsInfinity(
4284  SCIP_LPI* lpi, /**< LP interface structure */
4285  SCIP_Real val /**< value to be checked for infinity */
4286  )
4287 { /*lint --e{715}*/
4288  return (val >= CPX_INFBOUND);
4289 }
4290 
4291 /**@} */
4292 
4293 
4294 
4295 
4296 /*
4297  * File Interface Methods
4298  */
4299 
4300 /**@name File Interface Methods */
4301 /**@{ */
4302 
4303 /** reads LP from a file */
4304 SCIP_RETCODE SCIPlpiReadLP(
4305  SCIP_LPI* lpi, /**< LP interface structure */
4306  const char* fname /**< file name */
4307  )
4308 {
4309  int restat;
4310 
4311  assert(lpi != NULL);
4312  assert(lpi->cpxlp != NULL);
4313  assert(lpi->cpxenv != NULL);
4314 
4315  SCIPdebugMessage("reading LP from file <%s>\n", fname);
4316 
4317  restat = CPXreadcopyprob(lpi->cpxenv, lpi->cpxlp, fname, NULL);
4318  if( restat != 0 )
4319  {
4320  SCIPerrorMessage("LP Error: CPLEX returned %d\n", restat);
4321  return SCIP_READERROR;
4322  }
4323 
4324  return SCIP_OKAY;
4325 }
4326 
4327 /** writes LP to a file */
4328 SCIP_RETCODE SCIPlpiWriteLP(
4329  SCIP_LPI* lpi, /**< LP interface structure */
4330  const char* fname /**< file name */
4331  )
4332 {
4333  int restat;
4334 
4335  assert(lpi != NULL);
4336  assert(lpi->cpxlp != NULL);
4337  assert(lpi->cpxenv != NULL);
4338 
4339  SCIPdebugMessage("writing LP to file <%s>\n", fname);
4340 
4341  restat = CPXwriteprob(lpi->cpxenv, lpi->cpxlp, fname, NULL);
4342  if( restat != 0 )
4343  {
4344  SCIPerrorMessage("LP Error: CPLEX returned %d\n", restat);
4345  return SCIP_READERROR;
4346  }
4347 
4348  return SCIP_OKAY;
4349 }
4350 
4351 /**@} */
4352