Scippy

SCIP

Solving Constraint Integer Programs

lpi_spx.cpp
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_spx.cpp
17  * @ingroup LPIS
18  * @brief LP interface for SoPlex version 1.4 and higher
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Ambros Gleixner
22  * @author Marc Pfetsch
23  *
24  * This is an implementation of SCIP's LP interface for SoPlex. While the ratio test is fixed to SoPlex's standard,
25  * different pricing methods can be chosen and an autopricing strategy (start with devex and switch to steepest edge
26  * after too many iterations) is implemented directly. Scaler and simplifier may be applied if solving from scratch.
27  *
28  * For debugging purposes, the SoPlex results can be double checked with CPLEX if WITH_LPSCHECK is defined. This may
29  * yield false positives, since the LP is dumped to a file for transfering it to CPLEX, hence, precision may be lost.
30  */
31 
32 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #define AUTOPRICING_ITERSWITCH 10000/**< start with devex and switch to steepest edge after this many iterations */
35 #define STRONGBRANCH_RESTOREBASIS /**< if defined then in SCIPlpiStrongbranch() we restore the basis after the
36  * down branch and after the up branch; if false only after the end of a
37  * strong branching phase, which however seems to mostly increase strong
38  * branching time and iterations */
39 
40 /* in this case the SoPlex results are double checked using CPLEX */
41 #ifdef WITH_LPSCHECK
42 #include <cplex.h>
43 
44 #define CHECK_SPXSOLVE true /**< shall the SoPlex results in spxSolve() be double checked using CPLEX? */
45 #define CHECK_SPXSTRONGBRANCH true /**< shall the SoPlex results in SCIPlpStrongbranch() be double checked using CPLEX? */
46 #define CHECK_START 0 /**< skip first CHECK_START number of checks */
47 #define EXIT_AT_WRONG_RESULT false/**< shall program be exited if CPLEX returns different result than SoPlex? */
48 #define EXIT_AT_CPXERROR false/**< shall program be exited if CPLEX returns an error? */
49 
50 #define CPX_CALL(x) do \
51  { \
52  int _cpxstat_; \
53  if( (_cpxstat_ = (x)) != 0 ) \
54  { \
55  SCIPmessagePrintWarning(m_messagehdlr, "CPLEX error <%d>; SoPlex result unchecked\n", _cpxstat_); \
56  if( EXIT_AT_CPXERROR ) \
57  { \
58  exit(1); \
59  } \
60  else \
61  { \
62  goto ENDCHECK; \
63  } \
64  } \
65  } \
66  while( false )
67 #endif
68 
69 /* remember the original value of the SCIP_DEBUG define and undefine it */
70 #ifdef SCIP_DEBUG
71 #define ___DEBUG
72 #undef SCIP_DEBUG
73 #endif
74 
75 /* include SoPlex solver */
76 #include "spxsolver.h"
77 
78 /* define subversion for versions <= 1.5.0.1 */
79 #ifndef SOPLEX_SUBVERSION
80 #define SOPLEX_SUBVERSION 0
81 #endif
82 
83 /* check version */
84 #if (SOPLEX_VERSION < 133)
85 #error "This interface is not compatible with SoPlex versions prior to 1.4"
86 #endif
87 
88 /* get githash of SoPlex */
89 #if (SOPLEX_VERSION >= 160)
90 #include "spxgithash.h"
91 #endif
92 
93 /* include SoPlex components */
94 #include "slufactor.h"
95 #include "spxsteeppr.h"
96 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 6) || SOPLEX_VERSION > 160)
97 #include "spxsteepexpr.h"
98 #endif
99 #include "spxparmultpr.h"
100 #include "spxdevexpr.h"
101 #include "spxfastrt.h"
102 #include "spxmainsm.h"
103 #include "spxequilisc.h"
104 
105 #ifdef WITH_BOUNDFLIPPING
106 #include "spxboundflippingrt.h"
107 #endif
108 
109 /* reset the SCIP_DEBUG define to its original SCIP value */
110 #undef SCIP_DEBUG
111 #ifdef ___DEBUG
112 #define SCIP_DEBUG
113 #undef ___DEBUG
114 #endif
115 
116 #define SOPLEX_VERBLEVEL 5 /**< verbosity level for LPINFO */
117 
118 #include "scip/pub_message.h"
119 
120 /********************************************************************/
121 /*----------------------------- C++ --------------------------------*/
122 /********************************************************************/
123 
124 /* in C++ we have to use "0" instead of "(void*)0" */
125 #undef NULL
126 #define NULL 0
127 
128 #include <cassert>
129 using namespace soplex;
130 
131 
132 /** Macro for a single SoPlex call for which exceptions have to be catched - return an LP error. We
133  * make no distinction between different exception types, e.g., between memory allocation and other
134  * exceptions.
135  */
136 #ifndef NDEBUG
137 #define SOPLEX_TRY(messagehdlr, x) do \
138  { \
139  try \
140  { \
141  (x); \
142  } \
143  catch(SPxException E) \
144  { \
145  std::string s = E.what(); \
146  SCIPmessagePrintWarning((messagehdlr), "SoPlex threw an exception: %s\n", s.c_str()); \
147  return SCIP_LPERROR; \
148  } \
149  } \
150  while( FALSE )
151 
152 #else
153 #define SOPLEX_TRY(messagehdlr, x) do \
154  { \
155  try \
156  { \
157  (x); \
158  } \
159  catch(SPxException E) \
160  { \
161  return SCIP_LPERROR; \
162  } \
163  } \
164  while( FALSE )
165 #endif
166 
167 #define SOPLEX_TRYLPI(x) SOPLEX_TRY(lpi->messagehdlr, x)
168 #define SOPLEX_TRYLPIPTR(x) SOPLEX_TRY((*lpi)->messagehdlr, x)
169 
170 /* Macro for a single SoPlex call for which exceptions have to be catched - abort if they
171  * arise. SCIP_ABORT() is not accessible here.
172  */
173 #define SOPLEX_TRY_ABORT(x) do \
174  { \
175  try \
176  { \
177  (x); \
178  } \
179  catch(SPxException E) \
180  { \
181  std::string s = E.what(); \
182  SCIPerrorMessage("SoPlex threw an exception: %s\n", s.c_str()); \
183  abort(); \
184  } \
185  } \
186  while( FALSE )
187 
188 
189 
190 /** SCIP's SoPlex class */
191 class SPxSCIP : public SPxSolver
192 {
193  SPxLP::SPxSense m_sense; /**< optimization sense */
194  SLUFactor m_slu; /**< sparse LU factorization */
195  SPxSteepPR m_price_steep; /**< steepest edge pricer */
196 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 6) || SOPLEX_VERSION > 160)
197  SPxSteepExPR m_price_steep_ex; /**< steepest edge with exact weight initialization */
198 #else
199  SPxSteepPR m_price_steep_ex; /**< fallback to quick start pricer */
200 #endif
201  SPxParMultPR m_price_parmult; /**< partial multiple pricer */
202  SPxDevexPR m_price_devex; /**< devex pricer */
203 #ifdef WITH_BOUNDFLIPPING
204  SPxBoundFlippingRT m_ratio; /**< Long step dual ratio tester */
205 #else
206  SPxFastRT m_ratio; /**< Harris fast ratio tester */
207 #endif
208  char* m_probname; /**< problem name */
209  bool m_fromscratch; /**< use old basis indicator */
210  bool m_scaling; /**< use lp scaling */
211  bool m_presolving; /**< use lp presolving */
212  Real m_lpifeastol; /**< feastol set by SCIPlpiSetRealpar() */
213  Real m_lpiopttol; /**< opttol set by SCIPlpiSetRealpar() */
214  Real m_objLoLimit; /**< lower objective limit */
215  Real m_objUpLimit; /**< upper objective limit */
216  Status m_stat; /**< solving status */
217  bool m_lpinfo; /**< storing whether output is turned on */
218  bool m_autopricing; /**< is automatic pricing selected? */
219  int m_itlim; /**< iteration limit (-1 for unbounded) */
220  int m_itused; /**< number of iterations spent in phase one of auto pricing */
221  SPxSolver::VarStatus* m_rowstat; /**< basis status of rows before starting strong branching (if available, 0 otherwise) */
222  SPxSolver::VarStatus* m_colstat; /**< basis status of columns before starting strong branching (if available, 0 otherwise) */
223  NameSet* m_rownames; /**< row names */
224  NameSet* m_colnames; /**< column names */
225 
226 #ifdef WITH_LPSCHECK
227  int m_checknum;
228  bool m_doublecheck;
229  CPXENVptr m_cpxenv; /**< CPLEX memory environment */
230  CPXLPptr m_cpxlp; /**< CPLEX lp structure */
231 #endif
232  SCIP_MESSAGEHDLR* m_messagehdlr; /**< messagehdlr handler to printing messages, or NULL */
233 
234 public:
235  SPxSCIP(
236  SCIP_MESSAGEHDLR* messagehdlr = NULL, /**< message handler */
237  const char* probname = NULL /**< name of problem */
238  )
239  : SPxSolver(LEAVE, COLUMN),
240  m_probname(0),
241  m_fromscratch(false),
242  m_scaling(true),
243  m_presolving(true),
244  m_objLoLimit(-soplex::infinity),
245  m_objUpLimit(soplex::infinity),
246  m_stat(NO_PROBLEM),
247  m_lpinfo(false),
248  m_autopricing(true),
249  m_itlim(-1),
250  m_itused(0),
251  m_rowstat(NULL),
252  m_colstat(NULL),
253  m_rownames(0),
254  m_colnames(0),
255  m_messagehdlr(messagehdlr)
256  {
257  m_sense = sense();
258  setSense(SPxLP::MINIMIZE);
259  setSolver(&m_slu);
260  setTester(&m_ratio);
261  setPricer(&m_price_steep);
262  /* no starter */
263 
264  if ( probname != NULL )
265  SOPLEX_TRY_ABORT( setProbname(probname) );
266 
267 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 160)
268  m_lpifeastol = SPxSolver::feastol();
269  m_lpiopttol = SPxSolver::opttol();
270 #else
271  m_lpifeastol = SPxSolver::delta();
272  m_lpiopttol = SPxSolver::delta();
273 #endif
274 
275 #ifdef WITH_LPSCHECK
276  int cpxstat;
277  m_cpxenv = CPXopenCPLEX(&cpxstat);
278  assert(m_cpxenv != NULL);
279  m_cpxlp = CPXcreateprob(m_cpxenv, &cpxstat, probname != NULL ? probname : "spxcheck");
280  (void) CPXsetintparam(m_cpxenv, CPX_PARAM_SCRIND, 0);
281  m_checknum = 0;
282  m_doublecheck = false;
283 #endif
284  }
285 
286  virtual ~SPxSCIP()
287  {
288  if( m_probname != NULL )
289  spx_free(m_probname); /*lint !e1551*/
290 
291  freePreStrongbranchingBasis();
292 
293  if( m_rownames != NULL )
294  {
295  m_rownames->~NameSet();
296  spx_free(m_rownames);
297  }
298  if( m_colnames != NULL )
299  {
300  m_colnames->~NameSet();
301  spx_free(m_colnames);
302  }
303 
304 #ifdef WITH_LPSCHECK
305  (void) CPXfreeprob(m_cpxenv, &m_cpxlp);
306  (void) CPXcloseCPLEX(&m_cpxenv);
307 #endif
308  }
309 
310  /**< return feastol set by SCIPlpiSetRealpar(), which might be tighter than what SoPlex accepted */
311  Real feastol()
312  {
313  return m_lpifeastol;
314  }
315 
316  /**< set feastol and store value in case SoPlex only accepts a larger tolerance */
317  void setFeastol(
318  const Real d
319  )
320  {
321  m_lpifeastol = d;
322 
323 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 160)
324  SPxSolver::setFeastol(d);
325 #else
326  SPxSolver::setDelta(d);
327 #endif
328  }
329 
330  /**< return opttol set by SCIPlpiSetRealpar(), which might be tighter than what SoPlex accepted */
331  Real opttol()
332  {
333  return m_lpiopttol;
334  }
335 
336  /**< set opttol and store value in case SoPlex only accepts a larger tolerance */
337  void setOpttol(
338  const Real d
339  )
340  {
341  m_lpiopttol = d;
342 
343 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 160)
344  SPxSolver::setOpttol(d);
345 #else
346  SPxSolver::setDelta(d);
347 #endif
348  }
349 
350  bool isPerturbed()
351  {
352  /* the epsilon is 1e-16; we add a factor of ten to account for numerics */
353  return (shift() >= 10.0 * epsilon());
354  }
355 
356  /** set iteration limit (-1 = unbounded) */
357  void setIterationLimit(
358  const int itlim
359  )
360  {
361  m_itlim = itlim;
362  }
363 
364  void setAutoPricer()
365  {
366  setPricer(&m_price_devex);
367  m_autopricing = true;
368  }
369 
370  void setFullPricer()
371  {
372  setPricer(&m_price_steep);
373  m_autopricing = false;
374  }
375 
376  void setSteepPricer()
377  {
378  setPricer(&m_price_steep_ex);
379  m_autopricing = false;
380  }
381 
382  void setSteepQStartPricer()
383  {
384  setPricer(&m_price_steep);
385  m_autopricing = false;
386  }
387 
388  void setParmultPricer()
389  {
390  setPricer(&m_price_parmult);
391  m_autopricing = false;
392  }
393 
394  void setDevexPricer()
395  {
396  setPricer(&m_price_devex);
397  m_autopricing = false;
398  }
399 
400  /** get iteration limit (-1 = unbounded) */
401  int getIterationLimit()
402  {
403  return m_itlim;
404  }
405 
406  bool getFromScratch() const
407  {
408  return m_fromscratch;
409  }
410 
411  void setFromScratch(bool fs)
412  {
413  m_fromscratch = fs;
414  }
415 
416  bool getScaling() const
417  {
418  return m_scaling;
419  }
420 
421  void setScaling(bool s)
422  {
423  m_scaling = s;
424  }
425 
426  bool getPresolving() const
427  {
428  return m_presolving;
429  }
430 
431  void setPresolving(bool p)
432  {
433  m_presolving = p;
434  }
435 
436  bool getLpInfo() const
437  {
438  return m_lpinfo;
439  }
440 
441  void setLpInfo(bool li)
442  {
443  m_lpinfo = li;
444  }
445 
446  SPxLP::SPxSense getSense() const
447  {
448  assert(m_sense == sense());
449 
450  return m_sense;
451  }
452 
453  void setSense(const SPxLP::SPxSense sen)
454  {
455  assert(m_sense == sense());
456 
457  if( m_sense != sen )
458  {
459  m_sense = sen;
460  changeSense(sen);
461 
462  /* if objective limit was set for the new sense previously, we have to apply it now */
463  if( m_sense == SPxLP::MINIMIZE && getObjUpLimit() < soplex::infinity )
464  {
465  SCIPdebugMessage("setting termination value to <%g>\n", getObjUpLimit());
466  SPxSolver::setTerminationValue(getObjUpLimit());
467  }
468  else if( m_sense == SPxLP::MAXIMIZE && getObjLoLimit() > -soplex::infinity )
469  {
470  SCIPdebugMessage("setting termination value to <%g>\n", getObjLoLimit());
471  SPxSolver::setTerminationValue(getObjLoLimit());
472  }
473  }
474  }
475 
476  void setProbname(const char* probname)
477  {
478  int len;
479 
480  assert(probname != NULL);
481  if( m_probname != NULL )
482  spx_free(m_probname);
483  len = (int)strlen(probname);
484  spx_alloc(m_probname, len + 1);
485  strncpy(m_probname, probname, len);
486  m_probname[len] = '\0';
487  }
488 
489  Real getObjLoLimit() const
490  {
491  return m_objLoLimit;
492  }
493 
494  void setObjLoLimit(Real limit)
495  {
496  if( getSense() == SPxLP::MAXIMIZE )
497  {
498  SCIPdebugMessage("setting termination value from <%g> to <%g>\n", m_objLoLimit, limit);
499  SPxSolver::setTerminationValue(limit);
500  }
501  m_objLoLimit = limit;
502  }
503 
504  Real getObjUpLimit() const
505  {
506  return m_objUpLimit;
507  }
508 
509  void setObjUpLimit(Real limit)
510  {
511  if( getSense() == SPxLP::MINIMIZE )
512  {
513  SCIPdebugMessage("setting termination value from <%g> to <%g>\n", m_objUpLimit, limit);
514  SPxSolver::setTerminationValue(limit);
515  }
516  m_objUpLimit = limit;
517  }
518 
519  void setRep(SPxSolver::Representation p_rep)
520  {
521  if( p_rep != rep() )
522  {
523  SCIPdebugMessage("switching to %s representation of the basis\n", p_rep == SPxSolver::ROW ? "row" : "column");
524  SPxSolver::setRep(p_rep);
525  }
526  }
527 
528 #ifdef WITH_LPSCHECK
529  bool getDoubleCheck()
530  {
531  m_checknum++;
532  return m_doublecheck && m_checknum + 1 >= CHECK_START;
533  }
534 
535  void setDoubleCheck(bool dc)
536  {
537  m_doublecheck = dc;
538  }
539 
540  const char* spxStatusString(const SPxSolver::Status stat)
541  {
542  switch( stat )
543  {
544  case SPxSolver::ABORT_TIME:
545  return "ABORT_TIME";
546  case SPxSolver::ABORT_ITER:
547  return "ABORT_ITER";
548  case SPxSolver::ABORT_VALUE:
549  return "ABORT_VALUE";
550  case SPxSolver::SINGULAR:
551  return "SINGULAR";
552  case SPxSolver::REGULAR:
553  return "REGULAR";
554  case SPxSolver::UNKNOWN:
555  return "UNKNOWN";
556  case SPxSolver::OPTIMAL:
557  return "OPTIMAL";
558  case SPxSolver::UNBOUNDED:
559  return "UNBOUNDED";
560  case SPxSolver::INFEASIBLE:
561  return "INFEASIBLE";
562  default:
563  return "UNKNOWN";
564  } /*lint !e788*/
565 
566  return "UNKNOWN";
567  }
568 
569  const char* cpxStatusString(const int stat)
570  {
571  switch( stat )
572  {
573  case CPX_STAT_ABORT_TIME_LIM:
574  return "ABORT_TIME";
575  case CPX_STAT_ABORT_IT_LIM:
576  return "ABORT_ITER";
577  case CPX_STAT_ABORT_OBJ_LIM:
578  return "ABORT_VALUE";
579  case CPX_STAT_OPTIMAL:
580  return "OPTIMAL";
581  case CPX_STAT_OPTIMAL_INFEAS:
582  return "CPX_STAT_OPTIMAL_INFEAS: OPT SOL INFEASIBLE AFTER UNSCALING";
583  case CPX_STAT_UNBOUNDED:
584  return "UNBOUNDED";
585  case CPX_STAT_INFEASIBLE:
586  return "INFEASIBLE";
587  case CPX_STAT_INForUNBD:
588  return "INFEASIBLE or UNBOUNDED";
589  case CPX_STAT_NUM_BEST:
590  return "CPX_STAT_NUM_BEST: SOL AVAILABLE BUT NOT PROVEN OPTIMAL DUE TO NUM TROUBLE";
591  default:
592  return "UNKNOWN";
593  } /*lint !e788*/
594 
595  return "UNKNOWN";
596  }
597 #endif
598 
599 #ifndef NDEBUG
600  bool checkConsistentBounds()
601  {
602  for( int i = 0; i < nCols(); ++i )
603  {
604  if( lower(i) > upper(i) )
605  {
606  SCIPerrorMessage("inconsistent bounds on column %d: lower=%.17g, upper=%.17g\n",
607  i, lower(i), upper(i));
608  return false;
609  }
610  }
611 
612  return true;
613  }
614 
615  bool checkConsistentSides()
616  {
617  for( int i = 0; i < nRows(); ++i )
618  {
619  if( lhs(i) > rhs(i) )
620  {
621  SCIPerrorMessage("inconsistent sides on row %d: lhs=%.17g, rhs=%.17g\n",
622  i, lhs(i), rhs(i));
623  return false;
624  }
625  }
626 
627  return true;
628  }
629 #endif
630 
631  void trySolve(bool printwarning = true)
632  {
633  Real timespent;
634  Real timelimit;
635  try
636  {
637  m_stat = SPxSolver::solve();
638  }
639  catch(SPxException x)
640  {
641  std::string s = x.what();
642  if( printwarning )
643  {
644  SCIPmessagePrintWarning(m_messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
645  }
646  m_stat = SPxSolver::status();
647 
648  /* since it is not clear if the status in SoPlex are set correctly
649  * we want to make sure that if an error is thrown the status is
650  * not OPTIMAL anymore.
651  */
652  assert( m_stat != SPxSolver::OPTIMAL );
653  }
654 
655  /* save iteration count */
656  m_itused += SPxSolver::iterations();
657  assert(m_itlim < 0 || m_itused <= m_itlim);
658 
659  /* update time limit */
660  timespent = SPxSolver::time();
661  if( timespent > 0 )
662  {
663  /* get current time limit */
664  timelimit = SPxSolver::terminationTime();
665  if( timelimit > timespent )
666  timelimit -= timespent;
667  else
668  timelimit = 0;
669  /* set new time limit */
670  assert(timelimit >= 0);
671  SPxSolver::setTerminationTime(timelimit);
672  }
673  }
674 
675  virtual Status doSolve(bool printwarning = true)
676  {
677  int verbosity;
678 
679  /* store and set verbosity */
680  verbosity = Param::verbose();
681  Param::setVerbose(getLpInfo() ? SOPLEX_VERBLEVEL : 0);
682 
683  assert(checkConsistentBounds());
684  assert(checkConsistentSides());
685 
686 #ifdef WITH_LPSCHECK
687  /* dump LP with current basis and settings saved in SoPlex */
688  if( getDoubleCheck() )
689  writeState("spxcheck", NULL, NULL);
690 #endif
691 
692  /* in auto pricing, do the first iterations with devex, then switch to steepest edge */
693  setTerminationIter(m_autopricing && (m_itlim < 0 || m_itlim - m_itused > AUTOPRICING_ITERSWITCH) ? AUTOPRICING_ITERSWITCH : m_itlim - m_itused);
694 
695  trySolve(printwarning);
696 
697  if( m_autopricing && m_stat == SPxSolver::ABORT_ITER && (m_itlim < 0 || m_itlim - m_itused > 0) )
698  {
699  setTerminationIter(m_itlim - m_itused);
700  setPricer(&m_price_steep_ex);
701 
702  trySolve(printwarning);
703 
704  setPricer(&m_price_devex);
705  }
706 
707  /* for safety reset iteration limit */
708  setTerminationIter(m_itlim);
709 
710  if( m_stat == OPTIMAL )
711  {
712  Real objval = value();
713 
714  if( (objval > m_objUpLimit) || (objval < m_objLoLimit) )
715  m_stat = ABORT_VALUE;
716  }
717 
718 #ifdef WITH_LPSCHECK
719  /* if SoPlex gave a definite answer, we double check if it is consistent with CPLEX's answer */
720  if( getDoubleCheck() && (m_stat == SPxSolver::OPTIMAL || m_stat == SPxSolver::UNBOUNDED || m_stat == SPxSolver::INFEASIBLE || m_stat == SPxSolver::ABORT_VALUE) )
721  {
722  SCIP_Real cpxobj;
723  int cpxstat;
724 
725  /* read LP with basis */
726  CPX_CALL( CPXreadcopyprob(m_cpxenv, m_cpxlp, "spxcheck.mps", NULL) );
727  CPX_CALL( CPXreadcopybase(m_cpxenv, m_cpxlp, "spxcheck.bas") );
728 
729  /* set tolerances */
730  CPX_CALL( CPXsetdblparam(m_cpxenv, CPX_PARAM_EPOPT, MAX(opttol(), 1e-9)) );
731  CPX_CALL( CPXsetdblparam(m_cpxenv, CPX_PARAM_EPRHS, MAX(feastol(), 1e-9)) );
732 
733  /* solve LP */
734  CPX_CALL( CPXlpopt(m_cpxenv, m_cpxlp) );
735 
736  /* get solution status and objective value */
737  CPX_CALL( CPXsolution(m_cpxenv, m_cpxlp, &cpxstat, &cpxobj, NULL, NULL, NULL, NULL) );
738  if( getSense() == SPxLP::MAXIMIZE )
739  cpxobj *= -1.0;
740 
741  /* check for inconsistent statuses */
742  if( cpxstat == CPX_STAT_OPTIMAL_INFEAS )
743  {
744  SCIPerrorMessage("In %s: SoPlex status=%d (%s) while CPLEX status=%d (%s)\n",
745  m_probname, m_stat, spxStatusString(m_stat), cpxstat, cpxStatusString(cpxstat));
746  if( EXIT_AT_CPXERROR )
747  exit(1);
748  }
749  else if( (m_stat == SPxSolver::OPTIMAL && cpxstat != CPX_STAT_OPTIMAL)
750  || (m_stat == SPxSolver::UNBOUNDED && cpxstat != CPX_STAT_UNBOUNDED)
751  || (m_stat == SPxSolver::INFEASIBLE && cpxstat != CPX_STAT_INFEASIBLE) )
752  {
753  SCIPerrorMessage("In %s: SoPlex status=%d (%s) while CPLEX status=%d (%s) (checknum=%d)\n",
754  m_probname, m_stat, spxStatusString(m_stat), cpxstat, cpxStatusString(cpxstat), m_checknum);
755  if( EXIT_AT_WRONG_RESULT )
756  exit(1);
757  }
758  else if( m_stat == SPxSolver::ABORT_VALUE )
759  {
760  switch( cpxstat )
761  {
762  case CPX_STAT_OPTIMAL:
763  if( (getSense() == SPxSolver::MINIMIZE && LTrel(cpxobj, getObjUpLimit(), 2*opttol()))
764  || (getSense() == SPxSolver::MAXIMIZE && GTrel(cpxobj, getObjLoLimit(), 2*opttol())) )
765  {
766  SCIPerrorMessage("In %s: SoPlex returned status=%d (%s) while CPLEX claims obj=%.10f %s %.10f=obj.limit (%s) (checknum=%d)\n",
767  m_probname, m_stat, spxStatusString(m_stat), cpxobj, getSense() == SPxSolver::MINIMIZE ? "<" : ">",
768  getSense() == SPxSolver::MINIMIZE ? getObjUpLimit() : getObjLoLimit(), cpxStatusString(cpxstat), m_checknum);
769  if( EXIT_AT_WRONG_RESULT )
770  exit(1);
771  }
772  else if( (getSense() == SPxSolver::MINIMIZE && cpxobj < getObjUpLimit())
773  || (getSense() == SPxSolver::MAXIMIZE && cpxobj > getObjLoLimit()) )
774  {
775  SCIPerrorMessage("In %s: SoPlex returned status=%d (%s) while CPLEX claims obj=%.10f %s %.10f=obj.limit (%s) (checknum=%d)\n",
776  m_probname, m_stat, spxStatusString(m_stat), cpxobj, getSense() == SPxSolver::MINIMIZE ? "<" : ">",
777  getSense() == SPxSolver::MINIMIZE ? getObjUpLimit() : getObjLoLimit(), cpxStatusString(cpxstat), m_checknum);
778  }
779  break;
780  case CPX_STAT_OPTIMAL_INFEAS:
781  case CPX_STAT_NUM_BEST:
782  if( (getSense() == SPxSolver::MINIMIZE && cpxobj < getObjUpLimit())
783  || (getSense() == SPxSolver::MAXIMIZE && cpxobj > getObjLoLimit()) )
784  {
785  SCIPerrorMessage("In %s: SoPlex returned status=%d (%s) while CPLEX claims obj=%.10f %s %.10f=obj.limit (%s) (checknum=%d)\n",
786  m_probname, m_stat, spxStatusString(m_stat), cpxobj, getSense() == SPxSolver::MINIMIZE ? "<" : ">",
787  getSense() == SPxSolver::MINIMIZE ? getObjUpLimit() : getObjLoLimit(), cpxStatusString(cpxstat), m_checknum);
788  }
789  break;
790  case CPX_STAT_INFEASIBLE:
791  break;
792  case CPX_STAT_UNBOUNDED:
793  SCIPerrorMessage("In %s: SoPlex status=%d (%s) while CPLEX status=%d (%s) (checknum=%d)\n",
794  m_probname, m_stat, spxStatusString(m_stat), cpxstat, cpxStatusString(cpxstat), m_checknum);
795  if( EXIT_AT_WRONG_RESULT )
796  exit(1);
797  break;
798  case CPX_STAT_INForUNBD:
799  default:
800  SCIPerrorMessage("In %s: SoPlex status=%d (%s) while CPLEX status=%d (%s) (checknum=%d)\n",
801  m_probname, m_stat, spxStatusString(m_stat), cpxstat, cpxStatusString(cpxstat), m_checknum);
802  break;
803  } /*lint !e788*/
804  }
805  /* check for same objective values */
806  else if( m_stat == SPxSolver::OPTIMAL )
807  {
808  if( (getSense() == SPxSolver::MINIMIZE && LTrel(value(), cpxobj, 2*opttol()))
809  || (getSense() == SPxSolver::MAXIMIZE && GTrel(value(), cpxobj, 2*opttol())) )
810  {
811  /* SCIPerrorMessage("In %s: LP optimal; SoPlex value=%.10f %s CPLEX value=%.10f too good (checknum=%d)\n", value(),
812  m_probname, getSense() == SPxSolver::MINIMIZE ? "<" : ">", cpxobj, m_checknum); */
813  }
814  else if( (getSense() == SPxSolver::MINIMIZE && GTrel(value(), cpxobj, 2*opttol()))
815  || (getSense() == SPxSolver::MAXIMIZE && LTrel(value(), cpxobj, 2*opttol())) )
816  {
817  SCIPerrorMessage("In %s: LP optimal; SoPlex value=%.10f %s CPLEX value=%.10f suboptimal (checknum=%d)\n", value(),
818  m_probname, getSense() == SPxSolver::MINIMIZE ? ">" : "<", cpxobj, m_checknum);
819  if( EXIT_AT_WRONG_RESULT )
820  exit(1);
821  }
822  }
823  }
824 
825  ENDCHECK:
826 #endif
827 
828  /* restore verbosity */
829  Param::setVerbose(verbosity);
830 
831  return m_stat;
832  }
833 
834  virtual Status solve()
835  {
836  assert(m_sense == sense());
837 
838  SPxEquiliSC* scaler = NULL;
839  SPxMainSM* simplifier = NULL;
840  SPxLP origlp;
841  SPxSimplifier::Result result = SPxSimplifier::OKAY;
842 
843  /* delete starting basis if solving from scratch */
844  if ( getFromScratch() )
845  {
846  try
847  {
848  SPxSolver::reLoad();
849  }
850  catch(SPxException x)
851  {
852  std::string s = x.what();
853  SCIPmessagePrintWarning(m_messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
854  m_stat = SPxSolver::status();
855  assert( m_stat != SPxSolver::OPTIMAL );
856  return m_stat;
857  }
858  }
859  assert(!getFromScratch() || getBasisStatus() == SPxBasis::NO_PROBLEM);
860 
861  /* use scaler and simplifier if no basis is loaded, i.e., if solving for the first time or from scratch */
862  if( SPxSolver::getBasisStatus() == SPxBasis::NO_PROBLEM && getScaling() && nCols() > 0 && nRows() > 0 )
863  {
864  spx_alloc(scaler, 1);
865  scaler = new (scaler) SPxEquiliSC();
866  assert(scaler != NULL);
867  }
868 
869  if( SPxSolver::getBasisStatus() == SPxBasis::NO_PROBLEM && getPresolving() && nCols() > 0 && nRows() > 0 )
870  {
871  spx_alloc(simplifier, 1);
872  simplifier = new (simplifier) SPxMainSM();
873  assert(simplifier != NULL);
874  }
875 
876  /* store original lp */
877  if( scaler != NULL || simplifier != NULL )
878  origlp = SPxLP(*this);
879 
880  SOLVEAGAIN:
881  /* perform scaling and presolving */
882  if( scaler != NULL )
883  {
884  SCIPdebugMessage("scaling LP\n");
885  scaler->scale(*this);
886  }
887 
888  if( simplifier != NULL )
889  {
890  int verbosity;
891 
892  /* store and set verbosity */
893  verbosity = Param::verbose();
894  Param::setVerbose(getLpInfo() ? SOPLEX_VERBLEVEL : 0);
895  SCIPdebugMessage("simplifying LP\n");
896 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 160)
897  result = simplifier->simplify(*this, epsilon(), feastol(), opttol());
898 #else
899  result = simplifier->simplify(*this, epsilon(), delta());
900 #endif
901  SCIPdebugMessage("simplifier ended with status %u (0: OKAY, 1: INFEASIBLE, 2: DUAL_INFEASIBLE, 3: UNBOUNDED, 4: VANISHED)\n", result);
902 
903  /* unsimplification is not designed for these cases, thus reload original/scaled lp */
904  if( result == SPxSimplifier::INFEASIBLE || result == SPxSimplifier::DUAL_INFEASIBLE )
905  {
906  SCIPdebugMessage("simplifier detected primal or dual infeasibility - reloading and solving unsimplified LP\n");
907 
908  simplifier->~SPxMainSM();
909  spx_free(simplifier);
910 
911  SPxSolver::loadLP(origlp);
912  m_sense = sense();
913 
914  goto SOLVEAGAIN;
915  }
916  /* reset verbosity */
917  Param::setVerbose(verbosity);
918  }
919 
920  /* solve */
921  m_itused = 0;
922  if( result != SPxSimplifier::VANISHED )
923  {
924  /* we have to deactivate the objective limit, since we do not know the transformed value */
925  Real objlolimit = getObjLoLimit();
926  Real objuplimit = getObjUpLimit();
927 
928  if( simplifier != NULL || scaler != NULL )
929  {
930  setObjLoLimit(-soplex::infinity);
931  setObjUpLimit(soplex::infinity);
932  }
933 
934 #ifndef NDEBUG
935  doSolve();
936 #else
937  doSolve(false);
938 #endif
939 
940  if( simplifier != NULL || scaler != NULL )
941  {
942  setObjLoLimit(objlolimit);
943  setObjUpLimit(objuplimit);
944  }
945  }
946 
947  /* unsimplification only stable for optimal basis */
948  if( m_stat != SPxSolver::OPTIMAL && simplifier != NULL )
949  {
950  SCIPdebugMessage("presolved LP not optimal - reloading and solving original LP\n");
951 
952  simplifier->~SPxMainSM();
953  spx_free(simplifier);
954 
955  SPxSolver::loadLP(origlp);
956  m_sense = sense();
957 
958  goto SOLVEAGAIN;
959  }
960 
961  /* if scaling or presolving was applied, restore original lp */
962  if( scaler != NULL || simplifier != NULL )
963  {
964  SPxSolver::VarStatus* cstat = NULL;
965  SPxSolver::VarStatus* rstat = NULL;
966 
967  /* get basis if at least regular */
968  if( (simplifier == NULL || result != SPxSimplifier::VANISHED) && SPxSolver::getBasisStatus() >= SPxBasis::REGULAR )
969  {
970  SCIPdebugMessage("get basis of presolved LP\n");
971  spx_alloc(rstat, nRows());
972  spx_alloc(cstat, nCols());
973  SPxSolver::getBasis(rstat, cstat);
974  }
975 
976  /* unsimplify */
977  if( simplifier != NULL && SPxSolver::getBasisStatus() >= SPxBasis::REGULAR )
978  {
979  assert((result == SPxSimplifier::VANISHED) == (cstat == NULL));
980  assert((result == SPxSimplifier::VANISHED) == (rstat == NULL));
981 
982  /* dimension of presolved lp */
983  int ncols = result == SPxSimplifier::VANISHED ? 0 : nCols();
984  int nrows = result == SPxSimplifier::VANISHED ? 0 : nRows();
985 
986  /* get solution of presolved lp */
987  DVector primals(ncols);
988  DVector duals(nrows);
989  DVector slacks(nrows);
990  DVector redcosts(ncols);
991  if( result != SPxSimplifier::VANISHED )
992  {
993  SPxSolver::getPrimal(primals);
994  SPxSolver::getDual(duals);
995  SPxSolver::getSlacks(slacks);
996  SPxSolver::getRedCost(redcosts);
997  }
998 
999  /* perform unsimplification */
1000  SCIPdebugMessage("unsimplify\n");
1001  try
1002  {
1003  simplifier->unsimplify(primals, duals, slacks, redcosts, rstat, cstat);
1004  }
1005  catch(SPxException x)
1006  {
1007  std::string s = x.what();
1008  SCIPmessagePrintWarning(m_messagehdlr, "SoPlex unsimplification unsuccessful; solving again without LP presolving (SoPlex says %s)\n",
1009  s.c_str());
1010  }
1011 
1012  if( cstat != NULL )
1013  spx_free(cstat);
1014  if( rstat != NULL )
1015  spx_free(rstat);
1016 
1017  if( simplifier->isUnsimplified() )
1018  {
1019  /* get basis for original lp */
1020  rstat = NULL;
1021  cstat = NULL;
1022  spx_alloc(rstat, origlp.nRows());
1023  spx_alloc(cstat, origlp.nCols());
1024  simplifier->getBasis(rstat, cstat);
1025  }
1026  }
1027 
1028  /* reload original lp */
1029  SCIPdebugMessage("reload original LP\n");
1030  SPxSolver::loadLP(origlp);
1031  m_sense = sense();
1032 
1033  /* set basis from preprocessed lp and reoptimize */
1034  if( rstat != NULL && cstat != NULL )
1035  {
1036  SCIPdebugMessage("load unsimplified basis into original LP\n");
1037  SPxSolver::setBasis(rstat, cstat);
1038  }
1039 
1040  SCIPdebugMessage("solve original LP\n");
1041 #ifndef NDEBUG
1042  doSolve();
1043 #else
1044  doSolve(false);
1045 #endif
1046 
1047  /* free allocated memory */
1048  if( cstat != NULL )
1049  spx_free(cstat);
1050  if( rstat != NULL )
1051  spx_free(rstat);
1052  if( scaler != NULL )
1053  {
1054  scaler->~SPxEquiliSC();
1055  spx_free(scaler);
1056  }
1057  if( simplifier != NULL )
1058  {
1059  simplifier->~SPxMainSM();
1060  spx_free(simplifier);
1061  }
1062  }
1063 
1064  if( m_stat == OPTIMAL )
1065  {
1066  Real objval = value();
1067 
1068  if( (objval > m_objUpLimit) || (objval < m_objLoLimit) )
1069  m_stat = ABORT_VALUE;
1070  }
1071 
1072  return m_stat;
1073  }
1074 
1075  /** save the current basis */
1076  void savePreStrongbranchingBasis()
1077  {
1078  assert(m_rowstat == NULL);
1079  assert(m_colstat == NULL);
1080 
1081  spx_alloc(m_rowstat, nRows());
1082  spx_alloc(m_colstat, nCols());
1083 
1084  try
1085  {
1086  m_stat = getBasis(m_rowstat, m_colstat);
1087  }
1088  catch(SPxException x)
1089  {
1090 #ifndef NDEBUG
1091  std::string s = x.what();
1092  SCIPmessagePrintWarning(m_messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
1093 
1094  /* since it is not clear if the status in SoPlex are set correctly
1095  * we want to make sure that if an error is thrown the status is
1096  * not OPTIMAL anymore.
1097  */
1098  assert(m_stat != SPxSolver::OPTIMAL);
1099 #endif
1100  }
1101  }
1102 
1103  /** restore basis */
1104  void restorePreStrongbranchingBasis()
1105  {
1106  assert(m_rowstat != NULL);
1107  assert(m_colstat != NULL);
1108 
1109  try
1110  {
1111  setBasis(m_rowstat, m_colstat);
1112  }
1113  catch(SPxException x)
1114  {
1115 #ifndef NDEBUG
1116  std::string s = x.what();
1117  SCIPmessagePrintWarning(m_messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
1118 #endif
1119  m_stat = SPxSolver::status();
1120 
1121  /* since it is not clear if the status in SoPlex are set correctly
1122  * we want to make sure that if an error is thrown the status is
1123  * not OPTIMAL anymore.
1124  */
1125  assert(m_stat != SPxSolver::OPTIMAL);
1126  }
1127  }
1128 
1129  /** if basis is in store, delete it without restoring it */
1130  void freePreStrongbranchingBasis()
1131  {
1132  if( m_rowstat != NULL )
1133  spx_free(m_rowstat);
1134  if( m_colstat != NULL )
1135  spx_free(m_colstat);
1136  }
1137 
1138  /** is pre-strong-branching basis freed? */
1139  bool preStrongbranchingBasisFreed()
1140  {
1141  return ((m_rowstat == NULL ) && (m_colstat == NULL));
1142  }
1143 
1144  Status getStatus() const
1145  {
1146  return m_stat;
1147  }
1148 
1149  Status updateStatus()
1150  {
1151  m_stat = SPxSolver::status();
1152  return m_stat;
1153  }
1154 
1155  bool isInitialized() const
1156  {
1157  return SPxSolver::isInitialized();
1158  }
1159 
1160  int iterations() const
1161  {
1162  return m_itused;
1163  }
1164 
1165  virtual void clear()
1166  {
1167  SPxSolver::clear();
1168  freePreStrongbranchingBasis();
1169  m_stat = NO_PROBLEM;
1170  m_sense = sense();
1171  }
1172 
1173  bool readLP(const char* fname)
1174  {
1175  clear();
1176 
1177  if ( m_rownames != 0 )
1178  m_rownames->~NameSet();
1179  else
1180  spx_alloc(m_colnames, 1);
1181 
1182  if ( m_colnames != 0 )
1183  m_colnames->~NameSet();
1184  else
1185  spx_alloc(m_rownames, 1);
1186 
1187  m_rownames = new (m_rownames) NameSet();
1188  m_colnames = new (m_colnames) NameSet();
1189 
1190  if( SPxSolver::readFile(fname, m_rownames, m_colnames) )
1191  {
1192  m_stat = NO_PROBLEM;
1193  m_sense = sense();
1194  return true;
1195  }
1196 
1197  return false;
1198  }
1199 
1200  /** copy column names into namestorage with access via colnames */
1201  void getColNames(
1202  int firstcol, /**< first column to get name from LP */
1203  int lastcol, /**< last column to get name from LP */
1204  char** colnames, /**< pointers to column names (of size at least lastcol-firstcol+1) */
1205  char* namestorage, /**< storage for col names */
1206  int namestoragesize, /**< size of namestorage (if 0, storageleft returns the storage needed) */
1207  int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) */
1208  )
1209  {
1210  assert( m_colnames != NULL );
1211 
1212  // compute size
1213  if ( namestoragesize == 0 )
1214  {
1215  // the following may overestimate the space requirements
1216  *storageleft = -m_colnames->memSize();
1217  }
1218  else
1219  {
1220  NameSet* names = m_colnames;
1221  assert( names != 0 );
1222  int sizeleft = namestoragesize;
1223  char* s = namestorage;
1224  for (int j = firstcol; j <= lastcol; ++j)
1225  {
1226  const char* t = (*names)[j];
1227  colnames[j-firstcol] = s;
1228  while( *t != '\0' && sizeleft >= 0 )
1229  {
1230  *(s++) = *(t++);
1231  --sizeleft;
1232  }
1233  *(s++) = '\0';
1234  }
1235  if ( sizeleft == 0 )
1236  {
1237  *storageleft = namestoragesize - m_colnames->memSize();
1238  assert( *storageleft <= 0 );
1239  }
1240  else
1241  *storageleft = sizeleft;
1242  }
1243  }
1244 
1245  /** copy row names into namestorage with access via row */
1246  void getRowNames(
1247  int firstrow, /**< first row to get name from LP */
1248  int lastrow, /**< last row to get name from LP */
1249  char** rownames, /**< pointers to row names (of size at least lastrow-firstrow+1) */
1250  char* namestorage, /**< storage for row names */
1251  int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */
1252  int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) */
1253  )
1254  {
1255  assert( m_rownames != NULL );
1256 
1257  // compute size
1258  if ( namestoragesize == 0 )
1259  {
1260  // the following may overestimate the space requirements
1261  *storageleft = -m_rownames->memSize();
1262  }
1263  else
1264  {
1265  NameSet* names = m_rownames;
1266  assert( names != 0 );
1267  int sizeleft = namestoragesize;
1268  char* s = namestorage;
1269  for (int i = firstrow; i <= lastrow; ++i)
1270  {
1271  const char* t = (*names)[i];
1272  rownames[i-firstrow] = s;
1273  while( *t != '\0' && sizeleft >= 0 )
1274  {
1275  *(s++) = *(t++);
1276  --sizeleft;
1277  }
1278  *(s++) = '\0';
1279  }
1280  if ( sizeleft == 0 )
1281  {
1282  *storageleft = m_rownames->memSize() - namestoragesize;
1283  assert( *storageleft <= 0 );
1284  }
1285  else
1286  *storageleft = sizeleft;
1287  }
1288  }
1289 }; /*lint !e1748*/
1290 
1291 
1292 
1293 
1294 /********************************************************************/
1295 /*----------------------------- C --------------------------------*/
1296 /********************************************************************/
1297 
1298 #include "lpi/lpi.h"
1299 #include "scip/bitencode.h"
1300 
1301 typedef SCIP_DUALPACKET COLPACKET; /* each column needs two bits of information (basic/on_lower/on_upper) */
1302 #define COLS_PER_PACKET SCIP_DUALPACKETSIZE
1303 typedef SCIP_DUALPACKET ROWPACKET; /* each row needs two bit of information (basic/on_lower/on_upper) */
1304 #define ROWS_PER_PACKET SCIP_DUALPACKETSIZE
1305 
1306 
1307 
1308 /** LP interface */
1309 struct SCIP_LPi
1310 {
1311  SPxSCIP* spx; /**< our SPxSolver implementation */
1312  int* cstat; /**< array for storing column basis status */
1313  int* rstat; /**< array for storing row basis status */
1314  int cstatsize; /**< size of cstat array */
1315  int rstatsize; /**< size of rstat array */
1316  SCIP_PRICING pricing; /**< current pricing strategy */
1317  SCIP_Bool solved; /**< was the current LP solved? */
1318  SLUFactor* factorization; /**< factorization possibly needed for basis inverse */
1319  SCIP_Real rowrepswitch; /**< use row representation if number of rows divided by number of columns exceeds this value */
1320  SCIP_Real conditionlimit; /**< maximum condition number of LP basis counted as stable (-1.0: no limit) */
1321  SCIP_Bool checkcondition; /**< should condition number of LP basis be checked for stability? */
1322  SCIP_MESSAGEHDLR* messagehdlr; /**< messagehdlr handler to printing messages, or NULL */
1323 };
1324 
1325 /** LPi state stores basis information */
1326 struct SCIP_LPiState
1327 {
1328  int ncols; /**< number of LP columns */
1329  int nrows; /**< number of LP rows */
1330  COLPACKET* packcstat; /**< column basis status in compressed form */
1331  ROWPACKET* packrstat; /**< row basis status in compressed form */
1332 };
1333 
1334 
1335 
1336 
1337 /*
1338  * dynamic memory arrays
1339  */
1340 
1341 /** resizes cstat array to have at least num entries */
1342 static
1343 SCIP_RETCODE ensureCstatMem(
1344  SCIP_LPI* lpi, /**< LP interface structure */
1345  int num /**< minimal number of entries in array */
1346  )
1347 {
1348  assert(lpi != NULL);
1349 
1350  if( num > lpi->cstatsize )
1351  {
1352  int newsize;
1353 
1354  newsize = MAX(2*lpi->cstatsize, num);
1355  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->cstat, newsize) );
1356  lpi->cstatsize = newsize;
1357  }
1358  assert(num <= lpi->cstatsize);
1359 
1360  return SCIP_OKAY;
1361 }
1362 
1363 /** resizes rstat array to have at least num entries */
1364 static
1365 SCIP_RETCODE ensureRstatMem(
1366  SCIP_LPI* lpi, /**< LP interface structure */
1367  int num /**< minimal number of entries in array */
1368  )
1369 {
1370  assert(lpi != NULL);
1371 
1372  if( num > lpi->rstatsize )
1373  {
1374  int newsize;
1375 
1376  newsize = MAX(2*lpi->rstatsize, num);
1377  SCIP_ALLOC( BMSreallocMemoryArray(&lpi->rstat, newsize) );
1378  lpi->rstatsize = newsize;
1379  }
1380  assert(num <= lpi->rstatsize);
1381 
1382  return SCIP_OKAY;
1383 }
1384 
1385 
1386 
1387 
1388 /*
1389  * LPi state methods
1390  */
1391 
1392 /** returns the number of packets needed to store column packet information */
1393 static
1394 int colpacketNum(
1395  int ncols /**< number of columns to store */
1396  )
1397 {
1398  return (ncols+(int)COLS_PER_PACKET-1)/(int)COLS_PER_PACKET;
1399 }
1400 
1401 /** returns the number of packets needed to store row packet information */
1402 static
1403 int rowpacketNum(
1404  int nrows /**< number of rows to store */
1405  )
1406 {
1407  return (nrows+(int)ROWS_PER_PACKET-1)/(int)ROWS_PER_PACKET;
1408 }
1409 
1410 /** store row and column basis status in a packed LPi state object */
1411 static
1412 void lpistatePack(
1413  SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */
1414  const int* cstat, /**< basis status of columns in unpacked format */
1415  const int* rstat /**< basis status of rows in unpacked format */
1416  )
1417 {
1418  assert(lpistate != NULL);
1419  assert(lpistate->packcstat != NULL);
1420  assert(lpistate->packrstat != NULL);
1421 
1422  SCIPencodeDualBit(cstat, lpistate->packcstat, lpistate->ncols);
1423  SCIPencodeDualBit(rstat, lpistate->packrstat, lpistate->nrows);
1424 }
1425 
1426 /** unpacks row and column basis status from a packed LPi state object */
1427 static
1428 void lpistateUnpack(
1429  const SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */
1430  int* cstat, /**< buffer for storing basis status of columns in unpacked format */
1431  int* rstat /**< buffer for storing basis status of rows in unpacked format */
1432  )
1433 {
1434  assert(lpistate != NULL);
1435  assert(lpistate->packcstat != NULL);
1436  assert(lpistate->packrstat != NULL);
1437 
1438  SCIPdecodeDualBit(lpistate->packcstat, cstat, lpistate->ncols);
1439  SCIPdecodeDualBit(lpistate->packrstat, rstat, lpistate->nrows);
1440 }
1441 
1442 /** creates LPi state information object */
1443 static
1444 SCIP_RETCODE lpistateCreate(
1445  SCIP_LPISTATE** lpistate, /**< pointer to LPi state */
1446  BMS_BLKMEM* blkmem, /**< block memory */
1447  int ncols, /**< number of columns to store */
1448  int nrows /**< number of rows to store */
1449  )
1450 {
1451  assert(lpistate != NULL);
1452  assert(blkmem != NULL);
1453  assert(ncols >= 0);
1454  assert(nrows >= 0);
1455 
1456  SCIP_ALLOC( BMSallocBlockMemory(blkmem, lpistate) );
1457  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum(ncols)) );
1458  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum(nrows)) );
1459 
1460  return SCIP_OKAY;
1461 }
1462 
1463 /** frees LPi state information */
1464 static
1465 void lpistateFree(
1466  SCIP_LPISTATE** lpistate, /**< pointer to LPi state information (like basis information) */
1467  BMS_BLKMEM* blkmem /**< block memory */
1468  )
1469 {
1470  assert(blkmem != NULL);
1471  assert(lpistate != NULL);
1472  assert(*lpistate != NULL);
1473 
1474  BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum((*lpistate)->ncols));
1475  BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum((*lpistate)->nrows));
1476  BMSfreeBlockMemory(blkmem, lpistate);
1477 }
1478 
1479 
1480 
1481 
1482 /*
1483  * local methods
1484  */
1485 
1486 /** converts SCIP's objective sense into SoPlex's objective sense */
1487 static
1488 SPxLP::SPxSense spxObjsen(
1489  SCIP_OBJSEN objsen /**< SCIP's objective sense value */
1490  )
1491 {
1492  switch( objsen )
1493  {
1494  case SCIP_OBJSEN_MAXIMIZE:
1495  return SPxLP::MAXIMIZE;
1496  case SCIP_OBJSEN_MINIMIZE:
1497  return SPxLP::MINIMIZE;
1498  default:
1499  SCIPerrorMessage("invalid objective sense\n");
1500  SCIPABORT();
1501  return SPxLP::MINIMIZE;
1502  }
1503 }
1504 
1505 /** marks the current LP to be unsolved */
1506 static
1507 void invalidateSolution(SCIP_LPI* lpi)
1508 {
1509  assert(lpi != NULL);
1510  lpi->solved = FALSE;
1511  if ( lpi->factorization != 0 )
1512  {
1513  delete lpi->factorization;
1514  lpi->factorization = 0;
1515  }
1516 }
1517 
1518 
1519 
1520 /*
1521  * LP Interface Methods
1522  */
1523 
1524 
1525 /*
1526  * Miscellaneous Methods
1527  */
1528 
1529 static char spxname[100];
1530 static char spxdesc[200];
1531 
1532 /**@name Miscellaneous Methods */
1533 /**@{ */
1534 
1535 /** gets name and version of LP solver */
1537  void
1538  )
1539 {
1540  SCIPdebugMessage("calling SCIPlpiGetSolverName()\n");
1541 
1542 #if (SOPLEX_SUBVERSION > 0)
1543  sprintf(spxname, "SoPlex %d.%d.%d.%d", SOPLEX_VERSION/100, (SOPLEX_VERSION % 100)/10, SOPLEX_VERSION % 10, SOPLEX_SUBVERSION);
1544 #else
1545  sprintf(spxname, "SoPlex %d.%d.%d", SOPLEX_VERSION/100, (SOPLEX_VERSION % 100)/10, SOPLEX_VERSION % 10);
1546 #endif
1547  return spxname;
1548 }
1549 
1550 /** gets description of LP solver (developer, webpage, ...) */
1552  void
1553  )
1554 {
1555  sprintf(spxdesc, "%s", "Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de)");
1556 #if (SOPLEX_VERSION >= 160)
1557  sprintf(spxdesc, "%s [GitHash: %s]", spxdesc, getGitHash());
1558 #endif
1559 #ifdef WITH_LPSCHECK
1560  sprintf(spxdesc, "%s %s", spxdesc, "- including CPLEX double check");
1561 #endif
1562  return spxdesc;
1563 }
1564 
1565 /** gets pointer for LP solver - use only with great care */
1567  SCIP_LPI* lpi /**< pointer to an LP interface structure */
1568  )
1569 {
1570  return (void*) lpi->spx;
1571 }
1572 /**@} */
1573 
1574 
1575 
1576 
1577 /*
1578  * LPI Creation and Destruction Methods
1579  */
1580 
1581 /**@name LPI Creation and Destruction Methods */
1582 /**@{ */
1583 
1584 /** creates an LP problem object */
1586  SCIP_LPI** lpi, /**< pointer to an LP interface structure */
1587  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler to use for printing messages, or NULL */
1588  const char* name, /**< problem name */
1589  SCIP_OBJSEN objsen /**< objective sense */
1590  )
1591 {
1592  assert(lpi != NULL);
1593 
1594  /* create SoPlex object */
1595  SCIP_ALLOC( BMSallocMemory(lpi) );
1596 
1597  /* we use this construction to allocate the memory for the SoPlex class also via the blockmemshell */
1598  (*lpi)->spx = static_cast<SPxSCIP*>(BMSallocMemoryCPP(sizeof(SPxSCIP)));
1599  SOPLEX_TRY( messagehdlr, (*lpi)->spx = new ((*lpi)->spx) SPxSCIP(messagehdlr, name) );
1600  (*lpi)->cstat = NULL;
1601  (*lpi)->rstat = NULL;
1602  (*lpi)->cstatsize = 0;
1603  (*lpi)->rstatsize = 0;
1604  (*lpi)->pricing = SCIP_PRICING_LPIDEFAULT;
1605  (*lpi)->factorization = 0;
1606  (*lpi)->rowrepswitch = SCIPlpiInfinity(*lpi);
1607  (*lpi)->conditionlimit = -1.0;
1608  (*lpi)->checkcondition = FALSE;
1609  (*lpi)->messagehdlr = messagehdlr;
1610 
1611  invalidateSolution(*lpi);
1612 
1613  /* set objective sense */
1614  SCIP_CALL( SCIPlpiChgObjsen(*lpi, objsen) );
1615 
1616  /* set default pricing */
1617  SCIP_CALL( SCIPlpiSetIntpar(*lpi, SCIP_LPPAR_PRICING, (int)(*lpi)->pricing) );
1618 
1619  return SCIP_OKAY;
1620 }
1621 
1622 /** deletes an LP problem object */
1624  SCIP_LPI** lpi /**< pointer to an LP interface structure */
1625  )
1626 {
1627  assert(lpi != NULL);
1628  assert(*lpi != NULL);
1629  assert((*lpi)->spx != NULL);
1630 
1631  /* free LP using destructor and free memory via blockmemshell */
1632  (*lpi)->spx->~SPxSCIP();
1633  BMSfreeMemory(&((*lpi)->spx));
1634 
1635  /* free memory */
1636  BMSfreeMemoryArrayNull(&(*lpi)->cstat);
1637  BMSfreeMemoryArrayNull(&(*lpi)->rstat);
1638  BMSfreeMemory(lpi);
1639 
1640  return SCIP_OKAY;
1641 }
1642 
1643 /**@} */
1644 
1645 
1646 
1647 
1648 /*
1649  * Modification Methods
1650  */
1651 
1652 /**@name Modification Methods */
1653 /**@{ */
1654 
1655 /** copies LP data with column matrix into LP solver */
1657  SCIP_LPI* lpi, /**< LP interface structure */
1658  SCIP_OBJSEN objsen, /**< objective sense */
1659  int ncols, /**< number of columns */
1660  const SCIP_Real* obj, /**< objective function values of columns */
1661  const SCIP_Real* lb, /**< lower bounds of columns */
1662  const SCIP_Real* ub, /**< upper bounds of columns */
1663  char** colnames, /**< column names, or NULL */
1664  int nrows, /**< number of rows */
1665  const SCIP_Real* lhs, /**< left hand sides of rows */
1666  const SCIP_Real* rhs, /**< right hand sides of rows */
1667  char** /*rownames*/, /**< row names, or NULL */
1668  int nnonz, /**< number of nonzero elements in the constraint matrix */
1669  const int* beg, /**< start index of each column in ind- and val-array */
1670  const int* ind, /**< row indices of constraint matrix entries */
1671  const SCIP_Real* val /**< values of constraint matrix entries */
1672  )
1673 {
1674  SCIPdebugMessage("calling SCIPlpiLoadColLP()\n");
1675 
1676  assert(lpi != NULL);
1677  assert(lpi->spx != NULL);
1678  assert(lhs != NULL);
1679  assert(rhs != NULL);
1680 
1681  invalidateSolution(lpi);
1682  assert( lpi->spx->preStrongbranchingBasisFreed() );
1683 
1684  try
1685  {
1686  SPxSCIP* spx = lpi->spx;
1687  LPRowSet rows(nrows);
1688  DSVector emptyVector(0);
1689  int i;
1690 
1691  spx->clear();
1692 
1693  /* set objective sense */
1694  spx->setSense(spxObjsen(objsen));
1695 
1696  /* create empty rows with given sides */
1697  for( i = 0; i < nrows; ++i )
1698  rows.add(lhs[i], emptyVector, rhs[i]);
1699  spx->addRows(rows);
1700 
1701  /* create column vectors with coefficients and bounds */
1702  SCIP_CALL( SCIPlpiAddCols(lpi, ncols, obj, lb, ub, colnames, nnonz, beg, ind, val) );
1703  }
1704  catch(SPxException x)
1705  {
1706 #ifndef NDEBUG
1707  std::string s = x.what();
1708  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
1709 #endif
1710  return SCIP_LPERROR;
1711  }
1712 
1713  return SCIP_OKAY;
1714 }
1715 
1716 /** adds columns to the LP */
1718  SCIP_LPI* lpi, /**< LP interface structure */
1719  int ncols, /**< number of columns to be added */
1720  const SCIP_Real* obj, /**< objective function values of new columns */
1721  const SCIP_Real* lb, /**< lower bounds of new columns */
1722  const SCIP_Real* ub, /**< upper bounds of new columns */
1723  char** /*colnames*/, /**< column names, or NULL */
1724  int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
1725  const int* beg, /**< start index of each column in ind- and val-array, or NULL if nnonz == 0 */
1726  const int* ind, /**< row indices of constraint matrix entries, or NULL if nnonz == 0 */
1727  const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
1728  )
1729 {
1730  SCIPdebugMessage("calling SCIPlpiAddCols()\n");
1731 
1732  assert(lpi != NULL);
1733  assert(lpi->spx != NULL);
1734  assert(obj != NULL);
1735  assert(lb != NULL);
1736  assert(ub != NULL);
1737  assert(nnonz == 0 || beg != NULL);
1738  assert(nnonz == 0 || ind != NULL);
1739  assert(nnonz == 0 || val != NULL);
1740 
1741  invalidateSolution(lpi);
1742 
1743  assert( lpi->spx->preStrongbranchingBasisFreed() );
1744 
1745  SPxSCIP* spx = lpi->spx;
1746  try
1747  {
1748  LPColSet cols(ncols);
1749  DSVector colVector(ncols);
1750  int start;
1751  int last;
1752  int i;
1753 
1754  /* create column vectors with coefficients and bounds */
1755  for( i = 0; i < ncols; ++i )
1756  {
1757  colVector.clear();
1758  if( nnonz > 0 )
1759  {
1760  start = beg[i];
1761  last = (i == ncols-1 ? nnonz : beg[i+1]);
1762  colVector.add( last-start, &ind[start], &val[start] );
1763  }
1764  cols.add(obj[i], lb[i], colVector, ub[i]);
1765  }
1766  spx->addCols(cols);
1767  }
1768  catch(SPxException x)
1769  {
1770 #ifndef NDEBUG
1771  std::string s = x.what();
1772  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
1773 #endif
1774  return SCIP_LPERROR;
1775  }
1776 
1777  return SCIP_OKAY;
1778 }
1779 
1780 /** deletes all columns in the given range from LP */
1782  SCIP_LPI* lpi, /**< LP interface structure */
1783  int firstcol, /**< first column to be deleted */
1784  int lastcol /**< last column to be deleted */
1785  )
1786 {
1787  SCIPdebugMessage("calling SCIPlpiDelCols()\n");
1788 
1789  assert(lpi != NULL);
1790  assert(lpi->spx != NULL);
1791  assert(0 <= firstcol && firstcol <= lastcol && lastcol < lpi->spx->nCols());
1792 
1793  invalidateSolution(lpi);
1794 
1795  assert( lpi->spx->preStrongbranchingBasisFreed() );
1796 
1797  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->removeColRange(firstcol, lastcol) );
1798 
1799  return SCIP_OKAY;
1800 }
1801 
1802 /** deletes columns from SCIP_LP; the new position of a column must not be greater that its old position */
1804  SCIP_LPI* lpi, /**< LP interface structure */
1805  int* dstat /**< deletion status of columns
1806  * input: 1 if column should be deleted, 0 if not
1807  * output: new position of column, -1 if column was deleted */
1808  )
1809 {
1810  int ncols;
1811  int i;
1812 
1813  SCIPdebugMessage("calling SCIPlpiDelColset()\n");
1814 
1815  assert(lpi != NULL);
1816  assert(lpi->spx != NULL);
1817 
1818  invalidateSolution(lpi);
1819 
1820  assert( lpi->spx->preStrongbranchingBasisFreed() );
1821 
1822  ncols = lpi->spx->nCols();
1823 
1824  /* SoPlex removeCols() method deletes the columns with dstat[i] < 0, so we have to negate the values */
1825  for( i = 0; i < ncols; ++i )
1826  dstat[i] *= -1;
1827 
1828  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->removeCols(dstat) );
1829 
1830  return SCIP_OKAY;
1831 }
1832 
1833 /** adds rows to the LP */
1835  SCIP_LPI* lpi, /**< LP interface structure */
1836  int nrows, /**< number of rows to be added */
1837  const SCIP_Real* lhs, /**< left hand sides of new rows */
1838  const SCIP_Real* rhs, /**< right hand sides of new rows */
1839  char** /*rownames*/, /**< row names, or NULL */
1840  int nnonz, /**< number of nonzero elements to be added to the constraint matrix */
1841  const int* beg, /**< start index of each row in ind- and val-array, or NULL if nnonz == 0 */
1842  const int* ind, /**< column indices of constraint matrix entries, or NULL if nnonz == 0 */
1843  const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */
1844  )
1845 {
1846  SCIPdebugMessage("calling SCIPlpiAddRows()\n");
1847 
1848  assert(lpi != NULL);
1849  assert(lpi->spx != NULL);
1850  assert(lhs != NULL);
1851  assert(rhs != NULL);
1852  assert(nnonz == 0 || beg != NULL);
1853  assert(nnonz == 0 || ind != NULL);
1854  assert(nnonz == 0 || val != NULL);
1855 
1856  invalidateSolution(lpi);
1857 
1858  assert( lpi->spx->preStrongbranchingBasisFreed() );
1859 
1860  try
1861  {
1862  SPxSCIP* spx = lpi->spx;
1863  LPRowSet rows(nrows);
1864  DSVector rowVector;
1865  int start;
1866  int last;
1867  int i;
1868 
1869  /* create row vectors with given sides */
1870  for( i = 0; i < nrows; ++i )
1871  {
1872  rowVector.clear();
1873  if( nnonz > 0 )
1874  {
1875  start = beg[i];
1876  last = (i == nrows-1 ? nnonz : beg[i+1]);
1877  rowVector.add( last-start, &ind[start], &val[start] );
1878  }
1879  rows.add(lhs[i], rowVector, rhs[i]);
1880  }
1881  spx->addRows(rows);
1882  }
1883  catch(SPxException x)
1884  {
1885 #ifndef NDEBUG
1886  std::string s = x.what();
1887  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
1888 #endif
1889  return SCIP_LPERROR;
1890  }
1891 
1892  return SCIP_OKAY;
1893 }
1894 
1895 /** deletes all rows in the given range from LP */
1897  SCIP_LPI* lpi, /**< LP interface structure */
1898  int firstrow, /**< first row to be deleted */
1899  int lastrow /**< last row to be deleted */
1900  )
1901 {
1902  SCIPdebugMessage("calling SCIPlpiDelRows()\n");
1903 
1904  assert(lpi != NULL);
1905  assert(lpi->spx != NULL);
1906  assert(0 <= firstrow && firstrow <= lastrow && lastrow < lpi->spx->nRows());
1907 
1908  invalidateSolution(lpi);
1909 
1910  assert( lpi->spx->preStrongbranchingBasisFreed() );
1911 
1912  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->removeRowRange(firstrow, lastrow) );
1913 
1914  return SCIP_OKAY;
1915 }
1916 
1917 /** deletes rows from SCIP_LP; the new position of a row must not be greater that its old position */
1919  SCIP_LPI* lpi, /**< LP interface structure */
1920  int* dstat /**< deletion status of rows
1921  * input: 1 if row should be deleted, 0 if not
1922  * output: new position of row, -1 if row was deleted */
1923  )
1924 {
1925  int nrows;
1926  int i;
1927 
1928  SCIPdebugMessage("calling SCIPlpiDelRowset()\n");
1929 
1930  assert(lpi != NULL);
1931  assert(lpi->spx != NULL);
1932 
1933  invalidateSolution(lpi);
1934 
1935  assert( lpi->spx->preStrongbranchingBasisFreed() );
1936 
1937  nrows = lpi->spx->nRows();
1938 
1939  /* SoPlex removeRows() method deletes the rows with dstat[i] < 0, so we have to negate the values */
1940  for( i = 0; i < nrows; ++i )
1941  dstat[i] *= -1;
1942 
1943  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->removeRows(dstat) );
1944 
1945  return SCIP_OKAY;
1946 }
1947 
1948 /** clears the whole LP */
1950  SCIP_LPI* lpi /**< LP interface structure */
1951  )
1952 {
1953  SCIPdebugMessage("calling SCIPlpiClear()\n");
1954 
1955  assert(lpi != NULL);
1956  assert(lpi->spx != NULL);
1957 
1958  invalidateSolution(lpi);
1959 
1960  assert( lpi->spx->preStrongbranchingBasisFreed() );
1961  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->clear() );
1962 
1963  return SCIP_OKAY;
1964 }
1965 
1966 /** changes lower and upper bounds of columns */
1968  SCIP_LPI* lpi, /**< LP interface structure */
1969  int ncols, /**< number of columns to change bounds for */
1970  const int* ind, /**< column indices */
1971  const SCIP_Real* lb, /**< values for the new lower bounds */
1972  const SCIP_Real* ub /**< values for the new upper bounds */
1973  )
1974 {
1975  int i;
1976 
1977  SCIPdebugMessage("calling SCIPlpiChgBounds()\n");
1978 
1979  assert(lpi != NULL);
1980  assert(lpi->spx != NULL);
1981  assert(ind != NULL);
1982  assert(lb != NULL);
1983  assert(ub != NULL);
1984 
1985  invalidateSolution(lpi);
1986 
1987  assert( lpi->spx->preStrongbranchingBasisFreed() );
1988 
1989  try
1990  {
1991  for( i = 0; i < ncols; ++i )
1992  {
1993  assert(0 <= ind[i] && ind[i] < lpi->spx->nCols());
1994  lpi->spx->changeBounds(ind[i], lb[i], ub[i]);
1995  assert(lpi->spx->lower(ind[i]) <= lpi->spx->upper(ind[i]));
1996  }
1997  }
1998  catch(SPxException x)
1999  {
2000 #ifndef NDEBUG
2001  std::string s = x.what();
2002  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
2003 #endif
2004  return SCIP_LPERROR;
2005  }
2006 
2007  return SCIP_OKAY;
2008 }
2009 
2010 /** changes left and right hand sides of rows */
2012  SCIP_LPI* lpi, /**< LP interface structure */
2013  int nrows, /**< number of rows to change sides for */
2014  const int* ind, /**< row indices */
2015  const SCIP_Real* lhs, /**< new values for left hand sides */
2016  const SCIP_Real* rhs /**< new values for right hand sides */
2017  )
2018 {
2019  int i;
2020 
2021  SCIPdebugMessage("calling SCIPlpiChgSides()\n");
2022 
2023  assert(lpi != NULL);
2024  assert(lpi->spx != NULL);
2025  assert(ind != NULL);
2026  assert(lhs != NULL);
2027  assert(rhs != NULL);
2028 
2029  invalidateSolution(lpi);
2030 
2031  assert( lpi->spx->preStrongbranchingBasisFreed() );
2032 
2033  try
2034  {
2035  for( i = 0; i < nrows; ++i )
2036  {
2037  assert(0 <= ind[i] && ind[i] < lpi->spx->nRows());
2038  lpi->spx->changeRange(ind[i], lhs[i], rhs[i]);
2039  assert(lpi->spx->lhs(ind[i]) <= lpi->spx->rhs(ind[i]));
2040  }
2041  }
2042  catch(SPxException x)
2043  {
2044 #ifndef NDEBUG
2045  std::string s = x.what();
2046  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
2047 #endif
2048  return SCIP_LPERROR;
2049  }
2050 
2051  return SCIP_OKAY;
2052 }
2053 
2054 /** changes a single coefficient */
2056  SCIP_LPI* lpi, /**< LP interface structure */
2057  int row, /**< row number of coefficient to change */
2058  int col, /**< column number of coefficient to change */
2059  SCIP_Real newval /**< new value of coefficient */
2060  )
2061 {
2062  SCIPdebugMessage("calling SCIPlpiChgCoef()\n");
2063 
2064  assert(lpi != NULL);
2065  assert(lpi->spx != NULL);
2066  assert(0 <= row && row < lpi->spx->nRows());
2067  assert(0 <= col && col < lpi->spx->nCols());
2068 
2069  invalidateSolution(lpi);
2070 
2071  assert( lpi->spx->preStrongbranchingBasisFreed() );
2072 
2073  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->changeElement(row, col, newval) );
2074 
2075  return SCIP_OKAY;
2076 }
2077 
2078 /** changes the objective sense */
2080  SCIP_LPI* lpi, /**< LP interface structure */
2081  SCIP_OBJSEN objsen /**< new objective sense */
2082  )
2083 {
2084  SCIPdebugMessage("calling SCIPlpiChgObjsen()\n");
2085 
2086  assert(lpi != NULL);
2087  assert(lpi->spx != NULL);
2088 
2089  invalidateSolution(lpi);
2090 
2091  assert( lpi->spx->preStrongbranchingBasisFreed() );
2092 
2093  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->setSense(spxObjsen(objsen)) );
2094 
2095  return SCIP_OKAY;
2096 }
2097 
2098 /** changes objective values of columns in the LP */
2100  SCIP_LPI* lpi, /**< LP interface structure */
2101  int ncols, /**< number of columns to change objective value for */
2102  int* ind, /**< column indices to change objective value for */
2103  SCIP_Real* obj /**< new objective values for columns */
2104  )
2105 {
2106  int i;
2107 
2108  SCIPdebugMessage("calling SCIPlpiChgObj()\n");
2109 
2110  assert(lpi != NULL);
2111  assert(lpi->spx != NULL);
2112  assert(ind != NULL);
2113  assert(obj != NULL);
2114 
2115  invalidateSolution(lpi);
2116 
2117  assert( lpi->spx->preStrongbranchingBasisFreed() );
2118 
2119  try
2120  {
2121  for( i = 0; i < ncols; ++i )
2122  {
2123  assert(0 <= ind[i] && ind[i] < lpi->spx->nCols());
2124  lpi->spx->changeObj(ind[i], obj[i]);
2125  }
2126  }
2127  catch(SPxException x)
2128  {
2129 #ifndef NDEBUG
2130  std::string s = x.what();
2131  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
2132 #endif
2133  return SCIP_LPERROR;
2134  }
2135 
2136  return SCIP_OKAY;
2137 }
2138 
2139 /** multiplies a row with a non-zero scalar; for negative scalars, the row's sense is switched accordingly */
2141  SCIP_LPI* lpi, /**< LP interface structure */
2142  int row, /**< row number to scale */
2143  SCIP_Real scaleval /**< scaling multiplier */
2144  )
2145 {
2146  SCIP_Real lhs;
2147  SCIP_Real rhs;
2148 
2149  SCIPdebugMessage("calling SCIPlpiScaleRow()\n");
2150 
2151  assert(lpi != NULL);
2152  assert(lpi->spx != NULL);
2153  assert(scaleval != 0.0);
2154 
2155  try
2156  {
2157  invalidateSolution(lpi);
2158 
2159  assert( lpi->spx->preStrongbranchingBasisFreed() );
2160 
2161  /* get the row vector and the row's sides */
2162  SVector rowvec = lpi->spx->rowVector(row);
2163  lhs = lpi->spx->lhs(row);
2164  rhs = lpi->spx->rhs(row);
2165 
2166  /* scale the row vector */
2167  rowvec *= scaleval;
2168 
2169  /* adjust the sides */
2170  if( lhs > -soplex::infinity )
2171  lhs *= scaleval;
2172  else if( scaleval < 0.0 )
2173  lhs = soplex::infinity;
2174  if( rhs < soplex::infinity )
2175  rhs *= scaleval;
2176  else if( scaleval < 0.0 )
2177  rhs = -soplex::infinity;
2178  if( scaleval < 0.0 )
2179  {
2180  SCIP_Real oldlhs = lhs;
2181  lhs = rhs;
2182  rhs = oldlhs;
2183  }
2184 
2185  /* create the new row */
2186  LPRow lprow(lhs, rowvec, rhs);
2187 
2188  /* change the row in the LP */
2189  lpi->spx->changeRow(row, lprow);
2190  assert(lpi->spx->lhs(row) <= lpi->spx->rhs(row));
2191  }
2192  catch(SPxException x)
2193  {
2194 #ifndef NDEBUG
2195  std::string s = x.what();
2196  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
2197 #endif
2198  return SCIP_LPERROR;
2199  }
2200 
2201  return SCIP_OKAY;
2202 }
2203 
2204 /** multiplies a column with a non-zero scalar; the objective value is multiplied with the scalar, and the bounds
2205  * are divided by the scalar; for negative scalars, the column's bounds are switched
2206  */
2208  SCIP_LPI* lpi, /**< LP interface structure */
2209  int col, /**< column number to scale */
2210  SCIP_Real scaleval /**< scaling multiplier */
2211  )
2212 {
2213  SCIP_Real obj;
2214  SCIP_Real lb;
2215  SCIP_Real ub;
2216 
2217  SCIPdebugMessage("calling SCIPlpiScaleCol()\n");
2218 
2219  assert(lpi != NULL);
2220  assert(lpi->spx != NULL);
2221  assert(scaleval != 0.0);
2222 
2223  try
2224  {
2225  invalidateSolution(lpi);
2226 
2227  assert( lpi->spx->preStrongbranchingBasisFreed() );
2228 
2229  /* get the col vector and the col's bounds and objective value */
2230  SVector colvec = lpi->spx->colVector(col);
2231  obj = lpi->spx->obj(col);
2232  lb = lpi->spx->lower(col);
2233  ub = lpi->spx->upper(col);
2234 
2235  /* scale the col vector */
2236  colvec *= scaleval;
2237 
2238  /* scale the objective value */
2239  obj *= scaleval;
2240 
2241  /* adjust the bounds */
2242  if( lb > -soplex::infinity )
2243  lb /= scaleval;
2244  else if( scaleval < 0.0 )
2245  lb = soplex::infinity;
2246  if( ub < soplex::infinity )
2247  ub /= scaleval;
2248  else if( scaleval < 0.0 )
2249  ub = -soplex::infinity;
2250  if( scaleval < 0.0 )
2251  {
2252  SCIP_Real oldlb = lb;
2253  lb = ub;
2254  ub = oldlb;
2255  }
2256 
2257  /* create the new col (in LPCol's constructor, the upper bound is given first!) */
2258  LPCol lpcol(obj, colvec, ub, lb);
2259 
2260  /* change the col in the LP */
2261  lpi->spx->changeCol(col, lpcol);
2262  assert(lpi->spx->lower(col) <= lpi->spx->upper(col));
2263  }
2264  catch(SPxException x)
2265  {
2266 #ifndef NDEBUG
2267  std::string s = x.what();
2268  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
2269 #endif
2270  return SCIP_LPERROR;
2271  }
2272 
2273  return SCIP_OKAY;
2274 }
2275 
2276 /**@} */
2277 
2278 
2279 
2280 
2281 /*
2282  * Data Accessing Methods
2283  */
2284 
2285 /**@name Data Accessing Methods */
2286 /**@{ */
2287 
2288 /** gets the number of rows in the LP */
2290  SCIP_LPI* lpi, /**< LP interface structure */
2291  int* nrows /**< pointer to store the number of rows */
2292  )
2293 {
2294  SCIPdebugMessage("calling SCIPlpiGetNRows()\n");
2295 
2296  assert(lpi != NULL);
2297  assert(lpi->spx != NULL);
2298  assert(nrows != NULL);
2299 
2300  *nrows = lpi->spx->nRows();
2301 
2302  return SCIP_OKAY;
2303 }
2304 
2305 /** gets the number of columns in the LP */
2307  SCIP_LPI* lpi, /**< LP interface structure */
2308  int* ncols /**< pointer to store the number of cols */
2309  )
2310 {
2311  SCIPdebugMessage("calling SCIPlpiGetNCols()\n");
2312 
2313  assert(lpi != NULL);
2314  assert(lpi->spx != NULL);
2315  assert(ncols != NULL);
2316 
2317  *ncols = lpi->spx->nCols();
2318 
2319  return SCIP_OKAY;
2320 }
2321 
2322 /** gets the number of nonzero elements in the LP constraint matrix */
2324  SCIP_LPI* lpi, /**< LP interface structure */
2325  int* nnonz /**< pointer to store the number of nonzeros */
2326  )
2327 {
2328  int i;
2329 
2330  SCIPdebugMessage("calling SCIPlpiGetNNonz()\n");
2331 
2332  assert(lpi != NULL);
2333  assert(lpi->spx != NULL);
2334  assert(nnonz != NULL);
2335 
2336  /* SoPlex has no direct method to return the number of nonzeros, so we have to count them manually */
2337  *nnonz = 0;
2338  if( lpi->spx->nRows() < lpi->spx->nCols() )
2339  {
2340  for( i = 0; i < lpi->spx->nRows(); ++i )
2341  (*nnonz) += lpi->spx->rowVector(i).size();
2342  }
2343  else
2344  {
2345  for( i = 0; i < lpi->spx->nCols(); ++i )
2346  (*nnonz) += lpi->spx->colVector(i).size();
2347  }
2348 
2349  return SCIP_OKAY;
2350 }
2351 
2352 /** gets columns from LP problem object; the arrays have to be large enough to store all values
2353  * Either both, lb and ub, have to be NULL, or both have to be non-NULL,
2354  * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
2355  */
2357  SCIP_LPI* lpi, /**< LP interface structure */
2358  int firstcol, /**< first column to get from LP */
2359  int lastcol, /**< last column to get from LP */
2360  SCIP_Real* lb, /**< buffer to store the lower bound vector, or NULL */
2361  SCIP_Real* ub, /**< buffer to store the upper bound vector, or NULL */
2362  int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
2363  int* beg, /**< buffer to store start index of each column in ind- and val-array, or NULL */
2364  int* ind, /**< buffer to store column indices of constraint matrix entries, or NULL */
2365  SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
2366  )
2367 {
2368  int i;
2369  int j;
2370 
2371  SCIPdebugMessage("calling SCIPlpiGetCols()\n");
2372 
2373  assert(lpi != NULL);
2374  assert(lpi->spx != NULL);
2375  assert(0 <= firstcol && firstcol <= lastcol && lastcol < lpi->spx->nCols());
2376 
2377  if( lb != NULL )
2378  {
2379  assert(ub != NULL);
2380 
2381  const Vector& lbvec = lpi->spx->lower();
2382  const Vector& ubvec = lpi->spx->upper();
2383  for( i = firstcol; i <= lastcol; ++i )
2384  {
2385  lb[i-firstcol] = lbvec[i];
2386  ub[i-firstcol] = ubvec[i];
2387  }
2388  }
2389  else
2390  assert(ub == NULL);
2391 
2392  if( nnonz != NULL )
2393  {
2394  *nnonz = 0;
2395  for( i = firstcol; i <= lastcol; ++i )
2396  {
2397  beg[i-firstcol] = *nnonz;
2398  const SVector& cvec = lpi->spx->colVector(i);
2399  for( j = 0; j < cvec.size(); ++j )
2400  {
2401  ind[*nnonz] = cvec.index(j);
2402  val[*nnonz] = cvec.value(j);
2403  (*nnonz)++;
2404  }
2405  }
2406  }
2407  else
2408  {
2409  assert(beg == NULL);
2410  assert(ind == NULL);
2411  assert(val == NULL);
2412  }
2413 
2414  return SCIP_OKAY;
2415 }
2416 
2417 /** gets rows from LP problem object; the arrays have to be large enough to store all values.
2418  * Either both, lhs and rhs, have to be NULL, or both have to be non-NULL,
2419  * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL.
2420  */
2422  SCIP_LPI* lpi, /**< LP interface structure */
2423  int firstrow, /**< first row to get from LP */
2424  int lastrow, /**< last row to get from LP */
2425  SCIP_Real* lhs, /**< buffer to store left hand side vector, or NULL */
2426  SCIP_Real* rhs, /**< buffer to store right hand side vector, or NULL */
2427  int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */
2428  int* beg, /**< buffer to store start index of each row in ind- and val-array, or NULL */
2429  int* ind, /**< buffer to store row indices of constraint matrix entries, or NULL */
2430  SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */
2431  )
2432 {
2433  int i;
2434  int j;
2435 
2436  SCIPdebugMessage("calling SCIPlpiGetRows()\n");
2437 
2438  assert(lpi != NULL);
2439  assert(lpi->spx != NULL);
2440  assert(0 <= firstrow && firstrow <= lastrow && lastrow < lpi->spx->nRows());
2441 
2442  if( lhs != NULL )
2443  {
2444  assert(rhs != NULL);
2445 
2446  const Vector& lhsvec = lpi->spx->lhs();
2447  const Vector& rhsvec = lpi->spx->rhs();
2448  for( i = firstrow; i <= lastrow; ++i )
2449  {
2450  lhs[i-firstrow] = lhsvec[i];
2451  rhs[i-firstrow] = rhsvec[i];
2452  }
2453  }
2454  else
2455  assert(rhs == NULL);
2456 
2457  if( nnonz != NULL )
2458  {
2459  *nnonz = 0;
2460  for( i = firstrow; i <= lastrow; ++i )
2461  {
2462  beg[i-firstrow] = *nnonz;
2463  const SVector& rvec = lpi->spx->rowVector(i);
2464  for( j = 0; j < rvec.size(); ++j )
2465  {
2466  ind[*nnonz] = rvec.index(j);
2467  val[*nnonz] = rvec.value(j);
2468  (*nnonz)++;
2469  }
2470  }
2471  }
2472  else
2473  {
2474  assert(beg == NULL);
2475  assert(ind == NULL);
2476  assert(val == NULL);
2477  }
2478 
2479  return SCIP_OKAY;
2480 }
2481 
2482 /** gets column names */
2484  SCIP_LPI* lpi, /**< LP interface structure */
2485  int firstcol, /**< first column to get name from LP */
2486  int lastcol, /**< last column to get name from LP */
2487  char** colnames, /**< pointers to column names (of size at least lastcol-firstcol+1) */
2488  char* namestorage, /**< storage for col names */
2489  int namestoragesize, /**< size of namestorage (if 0, storageleft returns the storage needed) */
2490  int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) */
2491  )
2492 {
2493  assert( lpi != NULL );
2494  assert( lpi->spx != NULL );
2495  assert( colnames != NULL || namestoragesize == 0 );
2496  assert( namestorage != NULL || namestoragesize == 0 );
2497  assert( namestoragesize >= 0 );
2498  assert( storageleft != NULL );
2499  assert( 0 <= firstcol && firstcol <= lastcol && lastcol < lpi->spx->nCols() );
2500 
2501  SCIPdebugMessage("getting column names %d to %d\n", firstcol, lastcol);
2502 
2503  lpi->spx->getColNames(firstcol, lastcol, colnames, namestorage, namestoragesize, storageleft);
2504 
2505  return SCIP_OKAY;
2506 }
2507 
2508 /** gets row names */
2510  SCIP_LPI* lpi, /**< LP interface structure */
2511  int firstrow, /**< first row to get name from LP */
2512  int lastrow, /**< last row to get name from LP */
2513  char** rownames, /**< pointers to row names (of size at least lastrow-firstrow+1) */
2514  char* namestorage, /**< storage for row names */
2515  int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */
2516  int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) */
2517  )
2518 {
2519  assert( lpi != NULL );
2520  assert( lpi->spx != NULL );
2521  assert( rownames != NULL || namestoragesize == 0 );
2522  assert( namestorage != NULL || namestoragesize == 0 );
2523  assert( namestoragesize >= 0 );
2524  assert( storageleft != NULL );
2525  assert( 0 <= firstrow && firstrow <= lastrow && lastrow < lpi->spx->nRows() );
2526 
2527  SCIPdebugMessage("getting row names %d to %d\n", firstrow, lastrow);
2528 
2529  lpi->spx->getRowNames(firstrow, lastrow, rownames, namestorage, namestoragesize, storageleft);
2530 
2531  return SCIP_OKAY;
2532 }
2533 
2534 /** gets objective sense of the LP */
2536  SCIP_LPI* lpi, /**< LP interface structure */
2537  SCIP_OBJSEN* objsen /**< pointer to store objective sense */
2538  )
2539 {
2540  SCIPdebugMessage("calling SCIPlpiGetObjsen()\n");
2541 
2542  assert(lpi != NULL);
2543  assert(lpi->spx != NULL);
2544  assert(objsen != NULL);
2545 
2546  *objsen = (lpi->spx->getSense() == SPxLP::MINIMIZE) ? SCIP_OBJSEN_MINIMIZE : SCIP_OBJSEN_MAXIMIZE;
2547 
2548  return SCIP_OKAY;
2549 }
2550 
2551 /** gets objective coefficients from LP problem object */
2553  SCIP_LPI* lpi, /**< LP interface structure */
2554  int firstcol, /**< first column to get objective coefficient for */
2555  int lastcol, /**< last column to get objective coefficient for */
2556  SCIP_Real* vals /**< array to store objective coefficients */
2557  )
2558 {
2559  int i;
2560 
2561  SCIPdebugMessage("calling SCIPlpiGetObj()\n");
2562 
2563  assert(lpi != NULL);
2564  assert(lpi->spx != NULL);
2565  assert(0 <= firstcol && firstcol <= lastcol && lastcol < lpi->spx->nCols());
2566  assert(vals != NULL);
2567 
2568  for( i = firstcol; i <= lastcol; ++i )
2569  vals[i-firstcol] = lpi->spx->obj(i);
2570 
2571  return SCIP_OKAY;
2572 }
2573 
2574 /** gets current bounds from LP problem object */
2576  SCIP_LPI* lpi, /**< LP interface structure */
2577  int firstcol, /**< first column to get objective value for */
2578  int lastcol, /**< last column to get objective value for */
2579  SCIP_Real* lbs, /**< array to store lower bound values, or NULL */
2580  SCIP_Real* ubs /**< array to store upper bound values, or NULL */
2581  )
2582 {
2583  int i;
2584 
2585  SCIPdebugMessage("calling SCIPlpiGetBounds()\n");
2586 
2587  assert(lpi != NULL);
2588  assert(lpi->spx != NULL);
2589  assert(0 <= firstcol && firstcol <= lastcol && lastcol < lpi->spx->nCols());
2590 
2591  for( i = firstcol; i <= lastcol; ++i )
2592  {
2593  if( lbs != NULL )
2594  lbs[i-firstcol] = lpi->spx->lower(i);
2595  if( ubs != NULL )
2596  ubs[i-firstcol] = lpi->spx->upper(i);
2597  }
2598 
2599  return SCIP_OKAY;
2600 }
2601 
2602 /** gets current row sides from LP problem object */
2604  SCIP_LPI* lpi, /**< LP interface structure */
2605  int firstrow, /**< first row to get sides for */
2606  int lastrow, /**< last row to get sides for */
2607  SCIP_Real* lhss, /**< array to store left hand side values, or NULL */
2608  SCIP_Real* rhss /**< array to store right hand side values, or NULL */
2609  )
2610 {
2611  int i;
2612 
2613  SCIPdebugMessage("calling SCIPlpiGetSides()\n");
2614 
2615  assert(lpi != NULL);
2616  assert(lpi->spx != NULL);
2617  assert(0 <= firstrow && firstrow <= lastrow && lastrow < lpi->spx->nRows());
2618 
2619  for( i = firstrow; i <= lastrow; ++i )
2620  {
2621  if( lhss != NULL )
2622  lhss[i-firstrow] = lpi->spx->lhs(i);
2623  if( rhss != NULL )
2624  rhss[i-firstrow] = lpi->spx->rhs(i);
2625  }
2626 
2627  return SCIP_OKAY;
2628 }
2629 
2630 /** gets a single coefficient */
2632  SCIP_LPI* lpi, /**< LP interface structure */
2633  int row, /**< row number of coefficient */
2634  int col, /**< column number of coefficient */
2635  SCIP_Real* val /**< pointer to store the value of the coefficient */
2636  )
2637 {
2638  SCIPdebugMessage("calling SCIPlpiGetCoef()\n");
2639 
2640  assert(lpi != NULL);
2641  assert(lpi->spx != NULL);
2642  assert(0 <= col && col < lpi->spx->nCols());
2643  assert(0 <= row && row < lpi->spx->nRows());
2644  assert(val != NULL);
2645 
2646  *val = lpi->spx->colVector(col)[row];
2647 
2648  return SCIP_OKAY;
2649 }
2650 
2651 /**@} */
2652 
2653 
2654 
2655 
2656 /*
2657  * Solving Methods
2658  */
2659 
2660 /**@name Solving Methods */
2661 /**@{ */
2662 
2663 /** solves LP -- used for both, primal and dual simplex, because SoPlex doesn't distinct the two cases */
2664 static
2665 SCIP_RETCODE spxSolve(
2666  SCIP_LPI* lpi, /**< LP interface structure */
2667  SPxSolver::Representation rep, /**< basis representation */
2668  SPxSolver::Type type /**< algorithm type */
2669  )
2670 {
2671  assert( lpi != NULL );
2672  assert( lpi->spx != NULL );
2673  assert( rep == SPxSolver::ROW || rep == SPxSolver::COLUMN );
2674  assert( type == SPxSolver::ENTER || type == SPxSolver::LEAVE );
2675 
2676  SCIPdebugMessage("calling SoPlex solve(): %d cols, %d rows\n", lpi->spx->nCols(), lpi->spx->nRows());
2677 
2678  invalidateSolution(lpi);
2679 
2680  assert( lpi->spx->preStrongbranchingBasisFreed() );
2681 
2682  /* set basis representation and algorithm type */
2683  lpi->spx->setRep(rep);
2684  lpi->spx->setType(type);
2685 
2686 #ifdef WITH_LPSCHECK
2687  lpi->spx->setDoubleCheck(CHECK_SPXSOLVE);
2688 #endif
2689 
2690  SPxSolver::Status status = lpi->spx->solve();
2691  SCIPdebugMessage(" -> SoPlex status: %d, basis status: %d\n", lpi->spx->getStatus(), lpi->spx->basis().status());
2692  lpi->solved = TRUE;
2693 
2694  switch( status )
2695  {
2696  case SPxSolver::ABORT_TIME:
2697  case SPxSolver::ABORT_ITER:
2698  case SPxSolver::ABORT_VALUE:
2699  case SPxSolver::SINGULAR:
2700  case SPxSolver::REGULAR:
2701  case SPxSolver::UNKNOWN:
2702  case SPxSolver::OPTIMAL:
2703  case SPxSolver::UNBOUNDED:
2704  case SPxSolver::INFEASIBLE:
2705  return SCIP_OKAY;
2706  default:
2707  return SCIP_LPERROR;
2708  } /*lint !e788*/
2709 }
2710 
2711 /** calls primal simplex to solve the LP */
2713  SCIP_LPI* lpi /**< LP interface structure */
2714  )
2715 {
2716  SCIPdebugMessage("calling SCIPlpiSolvePrimal()\n");
2717 
2718  SCIP_RETCODE retcode;
2719  SCIP_Bool rowrep;
2720 
2721  assert(lpi != NULL);
2722  assert(lpi->spx != NULL);
2723 
2724  /* first decide if we want to switch the basis representation; in order to avoid oscillatory behaviour, we add the
2725  factor 1.1 for switching back to column representation */
2726  if( lpi->rowrepswitch >= 0 )
2727  {
2728  rowrep = lpi->spx->rep() == SPxSolver::ROW;
2729 
2730  if( !rowrep )
2731  rowrep = lpi->spx->nRows() > lpi->spx->nCols() * (lpi->rowrepswitch);
2732  else
2733  rowrep = lpi->spx->nRows() * 1.1 > lpi->spx->nCols() * (lpi->rowrepswitch);
2734  }
2735  else
2736  rowrep = FALSE;
2737 
2738  /* SoPlex doesn't distinct between the primal and dual simplex; however
2739  * we can force SoPlex to start with the desired method:
2740  * If the representation is COLUMN:
2741  * - ENTER = PRIMAL
2742  * - LEAVE = DUAL
2743  *
2744  * If the representation is ROW:
2745  * - ENTER = DUAL
2746  * - LEAVE = PRIMAL
2747  */
2748  retcode = rowrep ? spxSolve(lpi, SPxSolver::ROW, SPxSolver::LEAVE) : spxSolve(lpi, SPxSolver::COLUMN, SPxSolver::ENTER);
2749  assert(!rowrep || lpi->spx->rep() == SPxSolver::ROW);
2750  assert(rowrep || lpi->spx->rep() == SPxSolver::COLUMN);
2751 
2752  return retcode;
2753 }
2754 
2755 /** calls dual simplex to solve the LP */
2757  SCIP_LPI* lpi /**< LP interface structure */
2758  )
2759 {
2760  SCIPdebugMessage("calling SCIPlpiSolveDual()\n");
2761 
2762  SCIP_RETCODE retcode;
2763  SCIP_Bool rowrep;
2764 
2765  assert(lpi != NULL);
2766  assert(lpi->spx != NULL);
2767 
2768  /* first decide if we want to switch the basis representation; in order to avoid oscillatory behaviour, we add the
2769  factor 1.1 for switching back to column representation */
2770  if( lpi->rowrepswitch >= 0 )
2771  {
2772  rowrep = lpi->spx->rep() == SPxSolver::ROW;
2773 
2774  if( !rowrep )
2775  rowrep = lpi->spx->nRows() > lpi->spx->nCols() * (lpi->rowrepswitch);
2776  else
2777  rowrep = lpi->spx->nRows() * 1.1 > lpi->spx->nCols() * (lpi->rowrepswitch);
2778  }
2779  else
2780  rowrep = FALSE;
2781 
2782  /* SoPlex doesn't distinct between the primal and dual simplex; however
2783  * we can force SoPlex to start with the desired method:
2784  * If the representation is COLUMN:
2785  * - ENTER = PRIMAL
2786  * - LEAVE = DUAL
2787  *
2788  * If the representation is ROW:
2789  * - ENTER = DUAL
2790  * - LEAVE = PRIMAL
2791  */
2792  retcode = rowrep ? spxSolve(lpi, SPxSolver::ROW, SPxSolver::ENTER) : spxSolve(lpi, SPxSolver::COLUMN, SPxSolver::LEAVE);
2793  assert(!rowrep || lpi->spx->rep() == SPxSolver::ROW);
2794  assert(rowrep || lpi->spx->rep() == SPxSolver::COLUMN);
2795 
2796  return retcode;
2797 }
2798 
2799 /** calls barrier or interior point algorithm to solve the LP with crossover to simplex basis */
2801  SCIP_LPI* lpi, /**< LP interface structure */
2802  SCIP_Bool crossover /**< perform crossover */
2803  )
2804 { /*lint --e{715}*/
2805  SCIPdebugMessage("calling SCIPlpiSolveBarrier()\n");
2806 
2807  /* SoPlex does not support barrier (yet) */
2808  SCIPerrorMessage("SCIPlpiSolveBarrier() not supported by SoPlex\n");
2809  return SCIP_INVALIDCALL;
2810 }
2811 
2812 /** start strong branching - call before any strongbranching */
2814  SCIP_LPI* lpi /**< LP interface structure */
2815  )
2816 {
2817  assert( lpi->spx->preStrongbranchingBasisFreed() );
2818  lpi->spx->savePreStrongbranchingBasis();
2819 
2820  return SCIP_OKAY;
2821 }
2822 
2823 /** end strong branching - call after any strongbranching */
2825  SCIP_LPI* lpi /**< LP interface structure */
2826  )
2827 {
2828  assert( ! lpi->spx->preStrongbranchingBasisFreed() );
2829  lpi->spx->restorePreStrongbranchingBasis();
2830  lpi->spx->freePreStrongbranchingBasis();
2831 
2832  return SCIP_OKAY;
2833 }
2834 
2835 /** performs strong branching iterations on one arbitrary candidate */
2836 static
2837 SCIP_RETCODE lpiStrongbranch(
2838  SCIP_LPI* lpi, /**< LP interface structure */
2839  int col, /**< column to apply strong branching on */
2840  SCIP_Real psol, /**< current primal solution value of column */
2841  int itlim, /**< iteration limit for strong branchings */
2842  SCIP_Real* down, /**< stores dual bound after branching column down */
2843  SCIP_Real* up, /**< stores dual bound after branching column up */
2844  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
2845  * otherwise, it can only be used as an estimate value */
2846  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
2847  * otherwise, it can only be used as an estimate value */
2848  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
2849  )
2850 {
2851  SPxSCIP* spx;
2852  SPxSolver::Status status;
2853  SCIP_Real oldlb;
2854  SCIP_Real oldub;
2855  SCIP_Real newlb;
2856  SCIP_Real newub;
2857  bool fromparentbasis;
2858  bool error;
2859  int oldItlim;
2860 
2861  SCIPdebugMessage("calling SCIPlpiStrongbranch() on variable %d (%d iterations)\n", col, itlim);
2862 
2863  assert(lpi != NULL);
2864  assert(lpi->spx != NULL);
2865  /* assert(down != NULL);
2866  * assert(up != NULL); temporary hack for cloud branching */
2867  assert(downvalid != NULL);
2868  assert(upvalid != NULL);
2869 
2870  spx = lpi->spx;
2871  status = SPxSolver::UNKNOWN;
2872  fromparentbasis = false;
2873  error = false;
2874  oldItlim = spx->getIterationLimit();
2875 
2876  /* get current bounds of column */
2877  oldlb = spx->lower(col);
2878  oldub = spx->upper(col);
2879 
2880  *downvalid = FALSE;
2881  *upvalid = FALSE;
2882 
2883  if( iter != NULL )
2884  *iter = 0;
2885 
2886  /* set the algorithm type to use dual simplex */
2887  lpi->spx->setType( lpi->spx->rep() == SPxSolver::ROW ? SPxSolver::ENTER : SPxSolver::LEAVE);
2888 
2889  /* down branch */
2890  newub = EPSCEIL(psol-1.0, lpi->spx->feastol());
2891  if( newub >= oldlb - 0.5 && down != NULL )
2892  {
2893  SCIPdebugMessage("strong branching down on x%d (%g) with %d iterations\n", col, psol, itlim);
2894 
2895  spx->changeUpper(col, newub);
2896  assert(spx->lower(col) <= spx->upper(col));
2897 
2898  spx->setIterationLimit(itlim);
2899  do
2900  {
2901 #ifdef WITH_LPSCHECK
2902  spx->setDoubleCheck(CHECK_SPXSTRONGBRANCH);
2903 #endif
2904  status = spx->solve();
2905  SCIPdebugMessage(" --> Terminate with status %d\n", status);
2906  switch( status )
2907  {
2908  case SPxSolver::OPTIMAL:
2909  *down = spx->value();
2910  *downvalid = TRUE;
2911  SCIPdebugMessage(" --> Terminate with value %f\n", spx->value());
2912  break;
2913  case SPxSolver::ABORT_TIME: /* SoPlex does not return a proven dual bound, if it is aborted */
2914  case SPxSolver::ABORT_ITER:
2915  case SPxSolver::ABORT_CYCLING:
2916  *down = spx->value();
2917  break;
2918  case SPxSolver::ABORT_VALUE:
2919  case SPxSolver::INFEASIBLE:
2920  *down = spx->terminationValue();
2921  *downvalid = TRUE;
2922  break;
2923  default:
2924  error = true;
2925  break;
2926  } /*lint !e788*/
2927  if( iter != NULL )
2928  (*iter) += spx->iterations();
2929 
2930 #ifdef STRONGBRANCH_RESTOREBASIS
2931  /* we restore the pre-strong-branching basis by default (and don't solve again) */
2932  assert( ! spx->preStrongbranchingBasisFreed() );
2933  spx->restorePreStrongbranchingBasis();
2934  fromparentbasis = false;
2935 #else
2936  /* if cycling or singular basis occured and we started not from the pre-strong-branching basis, then we restore the
2937  * pre-strong-branching basis and try again with reduced iteration limit */
2938  if( (status == SPxSolver::ABORT_CYCLING || status == SPxSolver::SINGULAR) && !fromparentbasis && spx->iterations() < itlim )
2939  {
2940  SCIPdebugMessage(" --> Repeat strong branching down with %d iterations after restoring basis\n", itlim - spx->iterations());
2941  spx->setIterationLimit(itlim - spx->iterations());
2942  assert( ! spx->hasPreStrongbranchingBasis() );
2943  spx->restorePreStrongbranchingBasis();
2944  fromparentbasis = true;
2945  error = false;
2946  }
2947  /* otherwise don't solve again */
2948  else
2949  fromparentbasis = false;
2950 #endif
2951  }
2952  while( fromparentbasis );
2953 
2954  spx->changeUpper(col, oldub);
2955  assert(spx->lower(col) <= spx->upper(col));
2956  }
2957  else if( down != NULL )
2958  {
2959  *down = spx->terminationValue();
2960  *downvalid = TRUE;
2961  }
2962  else
2963  *downvalid = TRUE;
2964 
2965  /* up branch */
2966  if( !error )
2967  {
2968  newlb = EPSFLOOR(psol+1.0, lpi->spx->feastol());
2969  if( newlb <= oldub + 0.5 && up != NULL )
2970  {
2971  SCIPdebugMessage("strong branching up on x%d (%g) with %d iterations\n", col, psol, itlim);
2972 
2973  spx->changeLower(col, newlb);
2974  assert(spx->lower(col) <= spx->upper(col));
2975 
2976  spx->setIterationLimit(itlim);
2977  do
2978  {
2979 #ifdef WITH_LPSCHECK
2980  spx->setDoubleCheck(CHECK_SPXSTRONGBRANCH);
2981 #endif
2982  status = spx->solve();
2983  SCIPdebugMessage(" --> Terminate with status %d\n", status);
2984  switch( status )
2985  {
2986  case SPxSolver::OPTIMAL:
2987  *up = spx->value();
2988  *upvalid = TRUE;
2989  SCIPdebugMessage(" --> Terminate with value %f\n", spx->value());
2990  break;
2991  case SPxSolver::ABORT_TIME: /* SoPlex does not return a proven dual bound, if it is aborted */
2992  case SPxSolver::ABORT_ITER:
2993  case SPxSolver::ABORT_CYCLING:
2994  *up = spx->value();
2995  break;
2996  case SPxSolver::ABORT_VALUE:
2997  case SPxSolver::INFEASIBLE:
2998  *up = spx->terminationValue();
2999  *upvalid = TRUE;
3000  break;
3001  default:
3002  error = true;
3003  break;
3004  } /*lint !e788*/
3005  if( iter != NULL )
3006  (*iter) += spx->iterations();
3007 
3008 #ifdef STRONGBRANCH_RESTOREBASIS
3009  /* we restore the pre-strong-branching basis by default (and don't solve again) */
3010  assert( ! spx->preStrongbranchingBasisFreed() );
3011  spx->restorePreStrongbranchingBasis();
3012  fromparentbasis = false;
3013 #else
3014  /* if cycling or singular basis occured and we started not from the pre-strong-branching basis, then we restore the
3015  * pre-strong-branching basis and try again with reduced iteration limit */
3016  else if( (status == SPxSolver::ABORT_CYCLING || status == SPxSolver::SINGULAR) && !fromparentbasis && spx->iterations() < itlim )
3017  {
3018  SCIPdebugMessage(" --> Repeat strong branching up with %d iterations after restoring basis\n", itlim - spx->iterations());
3019  assert( ! spx->hasPreStrongbranchingBasis() );
3020  spx->restorePreStrongbranchingBasis();
3021  spx->setIterationLimit(itlim - spx->iterations());
3022  error = false;
3023  fromparentbasis = true;
3024  }
3025  /* otherwise don't solve again */
3026  else
3027  fromparentbasis = false;
3028 #endif
3029  }
3030  while( fromparentbasis );
3031 
3032  spx->changeLower(col, oldlb);
3033  assert(spx->lower(col) <= spx->upper(col));
3034  }
3035  else if( up != NULL )
3036  {
3037  *up = spx->terminationValue();
3038  *upvalid = TRUE;
3039  }
3040  else
3041  *upvalid = TRUE;
3042  }
3043 
3044  /* reset old iteration limit */
3045  spx->setIterationLimit(oldItlim);
3046 
3047  if( error )
3048  {
3049  SCIPdebugMessage("SCIPlpiStrongbranch() returned SoPlex status %d\n", int(status));
3050  return SCIP_LPERROR;
3051  }
3052 
3053  return SCIP_OKAY;
3054 }
3055 
3056 /** performs strong branching iterations on one @b fractional candidate */
3058  SCIP_LPI* lpi, /**< LP interface structure */
3059  int col, /**< column to apply strong branching on */
3060  SCIP_Real psol, /**< fractional current primal solution value of column */
3061  int itlim, /**< iteration limit for strong branchings */
3062  SCIP_Real* down, /**< stores dual bound after branching column down */
3063  SCIP_Real* up, /**< stores dual bound after branching column up */
3064  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
3065  * otherwise, it can only be used as an estimate value */
3066  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
3067  * otherwise, it can only be used as an estimate value */
3068  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
3069  )
3070 {
3071  SCIP_RETCODE retcode;
3072 
3073  /* pass call on to lpiStrongbranch() */
3074  retcode = lpiStrongbranch(lpi, col, psol, itlim, down, up, downvalid, upvalid, iter);
3075 
3076  /* pass SCIP_LPERROR to SCIP without a back trace */
3077  if( retcode == SCIP_LPERROR )
3078  return SCIP_LPERROR;
3079 
3080  /* evaluate retcode */
3081  SCIP_CALL( retcode );
3082 
3083  return SCIP_OKAY;
3084 }
3085 
3086 /** performs strong branching iterations on given @b fractional candidates */
3088  SCIP_LPI* lpi, /**< LP interface structure */
3089  int* cols, /**< columns to apply strong branching on */
3090  int ncols, /**< number of columns */
3091  SCIP_Real* psols, /**< fractional current primal solution values of columns */
3092  int itlim, /**< iteration limit for strong branchings */
3093  SCIP_Real* down, /**< stores dual bounds after branching columns down */
3094  SCIP_Real* up, /**< stores dual bounds after branching columns up */
3095  SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
3096  * otherwise, they can only be used as an estimate values */
3097  SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
3098  * otherwise, they can only be used as an estimate values */
3099  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
3100  )
3101 {
3102  SCIP_RETCODE retcode;
3103 
3104  assert( iter != NULL );
3105  assert( cols != NULL );
3106  assert( psols != NULL );
3107  assert( down != NULL );
3108  assert( up != NULL );
3109  assert( downvalid != NULL );
3110  assert( upvalid != NULL );
3111  assert( down != NULL );
3112 
3113  if ( iter != NULL )
3114  *iter = 0;
3115 
3116  for (int j = 0; j < ncols; ++j)
3117  {
3118  /* pass call on to lpiStrongbranch() */
3119  retcode = lpiStrongbranch(lpi, cols[j], psols[j], itlim, &(down[j]), &(up[j]), &(downvalid[j]), &(upvalid[j]), iter);
3120 
3121  /* pass SCIP_LPERROR to SCIP without a back trace */
3122  if( retcode == SCIP_LPERROR )
3123  return SCIP_LPERROR;
3124 
3125  /* evaluate retcode */
3126  SCIP_CALL( retcode );
3127  }
3128  return SCIP_OKAY;
3129 }
3130 
3131 /** performs strong branching iterations on one candidate with @b integral value */
3133  SCIP_LPI* lpi, /**< LP interface structure */
3134  int col, /**< column to apply strong branching on */
3135  SCIP_Real psol, /**< current integral primal solution value of column */
3136  int itlim, /**< iteration limit for strong branchings */
3137  SCIP_Real* down, /**< stores dual bound after branching column down */
3138  SCIP_Real* up, /**< stores dual bound after branching column up */
3139  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound;
3140  * otherwise, it can only be used as an estimate value */
3141  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound;
3142  * otherwise, it can only be used as an estimate value */
3143  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
3144  )
3145 {
3146  SCIP_RETCODE retcode;
3147 
3148  /* pass call on to lpiStrongbranch() */
3149  retcode = lpiStrongbranch(lpi, col, psol, itlim, down, up, downvalid, upvalid, iter);
3150 
3151  /* pass SCIP_LPERROR to SCIP without a back trace */
3152  if( retcode == SCIP_LPERROR )
3153  return SCIP_LPERROR;
3154 
3155  /* evaluate retcode */
3156  SCIP_CALL( retcode );
3157 
3158  return SCIP_OKAY;
3159 }
3160 
3161 /** performs strong branching iterations on given candidates with @b integral values */
3163  SCIP_LPI* lpi, /**< LP interface structure */
3164  int* cols, /**< columns to apply strong branching on */
3165  int ncols, /**< number of columns */
3166  SCIP_Real* psols, /**< current integral primal solution values of columns */
3167  int itlim, /**< iteration limit for strong branchings */
3168  SCIP_Real* down, /**< stores dual bounds after branching columns down */
3169  SCIP_Real* up, /**< stores dual bounds after branching columns up */
3170  SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds;
3171  * otherwise, they can only be used as an estimate values */
3172  SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds;
3173  * otherwise, they can only be used as an estimate values */
3174  int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */
3175  )
3176 {
3177  SCIP_RETCODE retcode;
3178 
3179  assert( iter != NULL );
3180  assert( cols != NULL );
3181  assert( psols != NULL );
3182  assert( down != NULL );
3183  assert( up != NULL );
3184  assert( downvalid != NULL );
3185  assert( upvalid != NULL );
3186  assert( down != NULL );
3187 
3188  if ( iter != NULL )
3189  *iter = 0;
3190 
3191  for (int j = 0; j < ncols; ++j)
3192  {
3193  /* pass call on to lpiStrongbranch() */
3194  retcode = lpiStrongbranch(lpi, cols[j], psols[j], itlim, &(down[j]), &(up[j]), &(downvalid[j]), &(upvalid[j]), iter);
3195 
3196  /* pass SCIP_LPERROR to SCIP without a back trace */
3197  if( retcode == SCIP_LPERROR )
3198  return SCIP_LPERROR;
3199 
3200  /* evaluate retcode */
3201  SCIP_CALL( retcode );
3202  }
3203 
3204  return SCIP_OKAY;
3205 }
3206 /**@} */
3207 
3208 
3209 
3210 
3211 /*
3212  * Solution Information Methods
3213  */
3214 
3215 /**@name Solution Information Methods */
3216 /**@{ */
3217 
3218 /** returns whether a solve method was called after the last modification of the LP */
3220  SCIP_LPI* lpi /**< LP interface structure */
3221  )
3222 {
3223  assert(lpi != NULL);
3224 
3225  return lpi->solved;
3226 }
3227 
3228 /** gets information about primal and dual feasibility of the current LP solution */
3230  SCIP_LPI* lpi, /**< LP interface structure */
3231  SCIP_Bool* primalfeasible, /**< stores primal feasibility status */
3232  SCIP_Bool* dualfeasible /**< stores dual feasibility status */
3233  )
3234 {
3235  SCIPdebugMessage("calling SCIPlpiGetSolFeasibility()\n");
3236 
3237  assert(lpi != NULL);
3238  assert(primalfeasible != NULL);
3239  assert(dualfeasible != NULL);
3240 
3241  *primalfeasible = SCIPlpiIsPrimalFeasible(lpi);
3242  *dualfeasible = SCIPlpiIsDualFeasible(lpi);
3243 
3244  return SCIP_OKAY;
3245 }
3246 
3247 /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point);
3248  * this does not necessarily mean, that the solver knows and can return the primal ray
3249  */
3251  SCIP_LPI* lpi /**< LP interface structure */
3252  )
3253 {
3254  SCIPdebugMessage("calling SCIPlpiExistsPrimalRay()\n");
3255 
3256  assert(lpi != NULL);
3257  assert(lpi->spx != NULL);
3258 
3259  return (lpi->spx->getStatus() == SPxSolver::UNBOUNDED);
3260 }
3261 
3262 /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point),
3263  * and the solver knows and can return the primal ray
3264  */
3266  SCIP_LPI* lpi /**< LP interface structure */
3267  )
3268 {
3269  SCIPdebugMessage("calling SCIPlpiHasPrimalRay()\n");
3270 
3271  assert(lpi != NULL);
3272  assert(lpi->spx != NULL);
3273 
3274 #if ((SOPLEX_VERSION == 150 && SOPLEX_SUBVERSION >= 2) || SOPLEX_VERSION > 150)
3275  return (lpi->spx->getStatus() == SPxSolver::UNBOUNDED);
3276 #else
3277  return FALSE;
3278 #endif
3279 }
3280 
3281 /** returns TRUE iff LP is proven to be primal unbounded */
3283  SCIP_LPI* lpi /**< LP interface structure */
3284  )
3285 {
3286  SCIPdebugMessage("calling SCIPlpiIsPrimalUnbounded()\n");
3287 
3288  assert(lpi != NULL);
3289  assert(lpi->spx != NULL);
3290 
3291  assert(lpi->spx->getStatus() != SPxSolver::UNBOUNDED || lpi->spx->basis().status() == SPxBasis::UNBOUNDED);
3292 
3293  /* if SoPlex returns unbounded, this may only mean that an unbounded ray is available, not necessarily a primal
3294  * feasible point; hence we have to check the perturbation
3295  */
3296  return (lpi->spx->getStatus() == SPxSolver::UNBOUNDED && !lpi->spx->isPerturbed());
3297 }
3298 
3299 /** returns TRUE iff LP is proven to be primal infeasible */
3301  SCIP_LPI* lpi /**< LP interface structure */
3302  )
3303 {
3304  SCIPdebugMessage("calling SCIPlpiIsPrimalInfeasible()\n");
3305 
3306  assert(lpi != NULL);
3307  assert(lpi->spx != NULL);
3308 
3309  return (lpi->spx->getStatus() == SPxSolver::INFEASIBLE);
3310 }
3311 
3312 /** returns TRUE iff LP is proven to be primal feasible */
3314  SCIP_LPI* lpi /**< LP interface structure */
3315  )
3316 {
3317  SPxBasis::SPxStatus basestatus;
3318 
3319  SCIPdebugMessage("calling SCIPlpiIsPrimalFeasible()\n");
3320 
3321  assert(lpi != NULL);
3322  assert(lpi->spx != NULL);
3323 
3324  basestatus = lpi->spx->basis().status();
3325 
3326  /* note that the solver status may be ABORT_VALUE and the basis status optimal; if we are optimal, isPerturbed() may
3327  * still return true as long as perturbation plus violation is within tolerances
3328  */
3329  assert(basestatus == SPxBasis::OPTIMAL || lpi->spx->getStatus() != SPxSolver::OPTIMAL);
3330 
3331  return basestatus == SPxBasis::OPTIMAL ||
3332  ((basestatus == SPxBasis::PRIMAL || basestatus == SPxBasis::UNBOUNDED) && !lpi->spx->isPerturbed());
3333 }
3334 
3335 /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point);
3336  * this does not necessarily mean, that the solver knows and can return the dual ray
3337  */
3339  SCIP_LPI* lpi /**< LP interface structure */
3340  )
3341 {
3342  SCIPdebugMessage("calling SCIPlpiExistsDualRay()\n");
3343 
3344  assert(lpi != NULL);
3345  assert(lpi->spx != NULL);
3346 
3347  return (lpi->spx->getStatus() == SPxSolver::INFEASIBLE);
3348 }
3349 
3350 /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point),
3351  * and the solver knows and can return the dual ray
3352  */
3354  SCIP_LPI* lpi /**< LP interface structure */
3355  )
3356 {
3357  SCIPdebugMessage("calling SCIPlpiHasDualRay()\n");
3358 
3359  assert(lpi != NULL);
3360  assert(lpi->spx != NULL);
3361 
3362  return (lpi->spx->getStatus() == SPxSolver::INFEASIBLE);
3363 }
3364 
3365 /** returns TRUE iff LP is dual unbounded */
3367  SCIP_LPI* lpi /**< LP interface structure */
3368  )
3369 {
3370  SCIPdebugMessage("calling SCIPlpiIsDualUnbounded()\n");
3371 
3372  assert(lpi != NULL);
3373  assert(lpi->spx != NULL);
3374 
3375  return (lpi->spx->getStatus() == SPxSolver::INFEASIBLE && lpi->spx->basis().status() == SPxBasis::DUAL
3376  && !lpi->spx->isPerturbed());
3377 }
3378 
3379 /** returns TRUE iff LP is dual infeasible */
3381  SCIP_LPI* lpi /**< LP interface structure */
3382  )
3383 {
3384  SCIPdebugMessage("calling SCIPlpiIsDualInfeasible()\n");
3385 
3386  assert(lpi != NULL);
3387  assert(lpi->spx != NULL);
3388 
3389  return (lpi->spx->getStatus() == SPxSolver::UNBOUNDED);
3390 }
3391 
3392 /** returns TRUE iff LP is proven to be dual feasible */
3394  SCIP_LPI* lpi /**< LP interface structure */
3395  )
3396 {
3397  SCIPdebugMessage("calling SCIPlpiIsDualFeasible()\n");
3398 
3399  assert(lpi != NULL);
3400  assert(lpi->spx != NULL);
3401 
3402  /* note that the solver status may be ABORT_VALUE and the basis status optimal; if we are optimal, isPerturbed() may
3403  * still return true as long as perturbation plus violation is within tolerances
3404  */
3405  assert(lpi->spx->basis().status() == SPxBasis::OPTIMAL || lpi->spx->getStatus() != SPxSolver::OPTIMAL);
3406 
3407  return (lpi->spx->basis().status() == SPxBasis::OPTIMAL) ||
3408  (lpi->spx->basis().status() == SPxBasis::DUAL && !lpi->spx->isPerturbed());
3409 }
3410 
3411 /** returns TRUE iff LP was solved to optimality */
3413  SCIP_LPI* lpi /**< LP interface structure */
3414  )
3415 {
3416  SCIPdebugMessage("calling SCIPlpiIsOptimal()\n");
3417 
3418  assert(lpi != NULL);
3419  assert((lpi->spx->basis().status() == SPxBasis::OPTIMAL)
3421 
3422  /* note that the solver status may be ABORT_VALUE and the basis status optimal; if we are optimal, isPerturbed() may
3423  * still return true as long as perturbation plus violation is within tolerances
3424  */
3425  return (lpi->spx->basis().status() == SPxBasis::OPTIMAL);
3426 }
3427 
3428 /** returns TRUE iff current LP basis is stable */
3430  SCIP_LPI* lpi /**< LP interface structure */
3431  )
3432 {
3433  SCIPdebugMessage("calling SCIPlpiIsStable()\n");
3434 
3435  assert(lpi != NULL);
3436  assert(lpi->spx != NULL);
3437 
3438 #if ((SOPLEX_VERSION == 172 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 172)
3439  /* If the condition number of the basis should be checked, everything above the specified threshold is counted
3440  * as instable.
3441  */
3442  if( lpi->checkcondition && (SCIPlpiIsOptimal(lpi) || SCIPlpiIsObjlimExc(lpi)) )
3443  {
3444 #ifndef NDEBUG
3445  SCIP_RETCODE retcode;
3446 #endif
3447  SCIP_Real kappa;
3448 
3449 #ifndef NDEBUG
3450  retcode =
3451 #endif
3453  assert(kappa != SCIP_INVALID);
3454  assert(retcode == SCIP_OKAY);
3455 
3456  if( kappa > lpi->conditionlimit )
3457  return FALSE;
3458  }
3459 #endif
3460 
3461  return (lpi->spx->getStatus() != SPxSolver::ERROR && lpi->spx->getStatus() != SPxSolver::SINGULAR);
3462 }
3463 
3464 /** returns TRUE iff the objective limit was reached */
3466  SCIP_LPI* lpi /**< LP interface structure */
3467  )
3468 {
3469  SCIPdebugMessage("calling SCIPlpiIsObjlimExc()\n");
3470 
3471  assert(lpi != NULL);
3472  assert(lpi->spx != NULL);
3473 
3474  return (lpi->spx->getStatus() == SPxSolver::ABORT_VALUE);
3475 }
3476 
3477 /** returns TRUE iff the iteration limit was reached */
3479  SCIP_LPI* lpi /**< LP interface structure */
3480  )
3481 {
3482  SCIPdebugMessage("calling SCIPlpiIsIterlimExc()\n");
3483 
3484  assert(lpi != NULL);
3485  assert(lpi->spx != NULL);
3486 
3487  return (lpi->spx->getStatus() == SPxSolver::ABORT_ITER);
3488 }
3489 
3490 /** returns TRUE iff the time limit was reached */
3492  SCIP_LPI* lpi /**< LP interface structure */
3493  )
3494 {
3495  SCIPdebugMessage("calling SCIPlpiIsTimelimExc()\n");
3496 
3497  assert(lpi != NULL);
3498  assert(lpi->spx != NULL);
3499 
3500  return (lpi->spx->getStatus() == SPxSolver::ABORT_TIME);
3501 }
3502 
3503 /** returns the internal solution status of the solver */
3505  SCIP_LPI* lpi /**< LP interface structure */
3506  )
3507 {
3508  SCIPdebugMessage("calling SCIPlpiIsTimelimExc()\n");
3509 
3510  assert(lpi != NULL);
3511  assert(lpi->spx != NULL);
3512 
3513  return static_cast<int>(lpi->spx->getStatus());
3514 }
3515 
3516 /** tries to reset the internal status of the LP solver in order to ignore an instability of the last solving call */
3518  SCIP_LPI* lpi, /**< LP interface structure */
3519  SCIP_Bool* success /**< pointer to store, whether the instability could be ignored */
3520  )
3521 { /*lint --e{715}*/
3522  SCIPdebugMessage("calling SCIPlpiIgnoreInstability()\n");
3523 
3524  assert(lpi != NULL);
3525  assert(lpi->spx != NULL);
3526 
3527  /* instable situations cannot be ignored */
3528  *success = FALSE;
3529 
3530  return SCIP_OKAY;
3531 }
3532 
3533 /** gets objective value of solution */
3535  SCIP_LPI* lpi, /**< LP interface structure */
3536  SCIP_Real* objval /**< stores the objective value */
3537  )
3538 {
3539  SCIPdebugMessage("calling SCIPlpiGetObjval()\n");
3540 
3541  assert(lpi != NULL);
3542  assert(lpi->spx != NULL);
3543  assert(objval != NULL);
3544 
3545  *objval = lpi->spx->value();
3546 
3547  return SCIP_OKAY;
3548 }
3549 
3550 /** gets primal and dual solution vectors */
3552  SCIP_LPI* lpi, /**< LP interface structure */
3553  SCIP_Real* objval, /**< stores the objective value, may be NULL if not needed */
3554  SCIP_Real* primsol, /**< primal solution vector, may be NULL if not needed */
3555  SCIP_Real* dualsol, /**< dual solution vector, may be NULL if not needed */
3556  SCIP_Real* activity, /**< row activity vector, may be NULL if not needed */
3557  SCIP_Real* redcost /**< reduced cost vector, may be NULL if not needed */
3558  )
3559 {
3560  SCIPdebugMessage("calling SCIPlpiGetSol()\n");
3561 
3562  assert(lpi != NULL);
3563  assert(lpi->spx != NULL);
3564 
3565  if( objval != NULL )
3566  *objval = lpi->spx->value();
3567 
3568  try
3569  {
3570  if( primsol != NULL )
3571  {
3572  Vector tmp(lpi->spx->nCols(), primsol);
3573  (void)lpi->spx->getPrimal(tmp);
3574  }
3575  if( dualsol != NULL )
3576  {
3577  Vector tmp(lpi->spx->nRows(), dualsol);
3578  (void)lpi->spx->getDual(tmp);
3579  }
3580  if( activity != NULL )
3581  {
3582  Vector tmp(lpi->spx->nRows(), activity);
3583  (void)lpi->spx->getSlacks(tmp); /* in SoPlex, the activities are called "slacks" */
3584  }
3585  if( redcost != NULL )
3586  {
3587  Vector tmp(lpi->spx->nCols(), redcost);
3588  (void)lpi->spx->getRedCost(tmp);
3589  }
3590  }
3591  catch(SPxException x)
3592  {
3593 #ifndef NDEBUG
3594  std::string s = x.what();
3595  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
3596 #endif
3597  return SCIP_LPERROR;
3598  }
3599 
3600  return SCIP_OKAY;
3601 }
3602 
3603 /** gets primal ray for unbounded LPs */
3605  SCIP_LPI* lpi, /**< LP interface structure */
3606  SCIP_Real* ray /**< primal ray */
3607  )
3608 { /*lint --e{715}*/
3609  SCIPdebugMessage("calling SCIPlpiGetPrimalRay()\n");
3610 
3611  assert(lpi != NULL);
3612  assert(lpi->spx != NULL);
3613 
3614 #if ((SOPLEX_VERSION == 150 && SOPLEX_SUBVERSION >= 2) || SOPLEX_VERSION > 150)
3615  try
3616  {
3617  Vector tmp(lpi->spx->nCols(), ray);
3618  (void)lpi->spx->getPrimalray(tmp);
3619  }
3620  catch(SPxException x)
3621  {
3622 #ifndef NDEBUG
3623  std::string s = x.what();
3624  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
3625 #endif
3626  return SCIP_LPERROR;
3627  }
3628 
3629  return SCIP_OKAY;
3630 #else
3631  SCIPerrorMessage("SCIPlpiGetPrimalRay() not supported by SoPlex versions <= 1.5.0\n");
3632  return SCIP_LPERROR;
3633 #endif
3634 }
3635 
3636 /** gets dual farkas proof for infeasibility */
3638  SCIP_LPI* lpi, /**< LP interface structure */
3639  SCIP_Real* dualfarkas /**< dual farkas row multipliers */
3640  )
3641 {
3642  SCIPdebugMessage("calling SCIPlpiGetDualfarkas()\n");
3643 
3644  assert(lpi != NULL);
3645  assert(lpi->spx != NULL);
3646 
3647  try
3648  {
3649  Vector tmp(lpi->spx->nRows(), dualfarkas);
3650  (void)lpi->spx->getDualfarkas(tmp);
3651  }
3652  catch(SPxException x)
3653  {
3654 #ifndef NDEBUG
3655  std::string s = x.what();
3656  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
3657 #endif
3658  return SCIP_LPERROR;
3659  }
3660 
3661  return SCIP_OKAY;
3662 }
3663 
3664 /** gets the number of LP iterations of the last solve call */
3666  SCIP_LPI* lpi, /**< LP interface structure */
3667  int* iterations /**< pointer to store the number of iterations of the last solve call */
3668  )
3669 {
3670  SCIPdebugMessage("calling SCIPlpiGetIterations()\n");
3671 
3672  assert(lpi != NULL);
3673  assert(lpi->spx != NULL);
3674 
3675  *iterations = lpi->spx->iterations();
3676 
3677  return SCIP_OKAY;
3678 }
3679 
3680 /** gets information about the quality of an LP solution
3681  *
3682  * Such information is usually only available, if also a (maybe not optimal) solution is available.
3683  * The LPI should return SCIP_INVALID for @p quality, if the requested quality is not available.
3684  */
3686  SCIP_LPI* lpi, /**< LP interface structure */
3687  SCIP_LPSOLQUALITY qualityindicator, /**< indicates which quality should be returned */
3688  SCIP_Real* quality /**< pointer to store quality number */
3689  )
3690 {
3691  SCIPdebugMessage("calling SCIPlpiGetRealSolQuality()\n");
3692 
3693  assert(lpi != NULL);
3694  assert(quality != NULL);
3695 
3696 #if ((SOPLEX_VERSION == 172 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 172)
3697  int maxiter;
3698  Real tolerance;
3699 
3700  assert(lpi != NULL);
3701  assert(quality != NULL);
3702 
3703  SCIPdebugMessage("requesting solution quality from SoPlex: quality %d\n", qualityindicator);
3704 
3705  switch( qualityindicator )
3706  {
3708  maxiter = 20;
3709  tolerance = 1e-6;
3710  break;
3711 
3713  maxiter = 10000;
3714  tolerance = 1e-9;
3715  break;
3716 
3717  default:
3718  SCIPerrorMessage("Solution quality %d unknown.\n", qualityindicator);
3719  return SCIP_INVALIDDATA;
3720  }
3721 
3722  *quality = lpi->spx->basis().condition(maxiter, tolerance);
3723 #else
3724  *quality = SCIP_INVALID;
3725 #endif
3726  return SCIP_OKAY;
3727 }
3728 
3729 /**@} */
3730 
3731 
3732 
3733 
3734 /*
3735  * LP Basis Methods
3736  */
3737 
3738 /**@name LP Basis Methods */
3739 /**@{ */
3740 
3741 /** Return reduced cost of column @c col if this is readily available, otherwise return 0.0 */
3742 static
3743 SCIP_RETCODE getRedCostEst(SPxSCIP* spx, int col, SCIP_Real* val)
3744 {
3745  assert( spx != NULL );
3746  assert( val != NULL );
3747 
3748  *val = 0.0;
3749 
3750  /* Return if the vectors are not set up. The vectors are not set up if for instance we preformed
3751  * strong branching before. */
3752  if (! spx->isInitialized() )
3753  return SCIP_OKAY;
3754 
3755  assert( 0 <= col && col < spx->nCols() );
3756 
3757  if( spx->rep() == SPxSolver::COLUMN )
3758  {
3759  /* in column case the reduced costs are available: */
3760  if (spx->getSense() == SPxLP::MINIMIZE)
3761  *val = spx->pVec()[col] - spx->maxObj()[col];
3762  else
3763  *val = spx->maxObj()[col] - spx->pVec()[col];
3764  }
3765  else
3766  {
3767  assert( spx->rep() == SPxSolver::ROW );
3768 
3769  /* In row case for computing the reduced costs one needs to pass through the basis. We skip this expensive part. */
3770 #if 0
3771  /* Here is the code necessary to compute the reduced costs for row representation: */
3772  SCIP_Real sign = 1.0;
3773  if ( spx->getSense() == SPxLP::MINIMIZE )
3774  sign = -1.0;
3775 
3776  if ( spx->isColBasic(col) )
3777  {
3778  /* It seems necessary to search through the basis in order to find the correct position */
3779  for (int i = spx->dim() - 1; i >= 0; --i)
3780  {
3781  SPxId id = spx->basis().baseId(i);
3782  if ( id.isSPxColId() && col == spx->number(SPxColId(id)) )
3783  {
3784  *val = sign * spx->fVec()[i];
3785  break;
3786  }
3787  }
3788  }
3789 #endif
3790  }
3791 
3792  return SCIP_OKAY;
3793 }
3794 
3795 
3796 
3797 /** gets current basis status for columns and rows; arrays must be large enough to store the basis status */
3799  SCIP_LPI* lpi, /**< LP interface structure */
3800  int* cstat, /**< array to store column basis status, or NULL */
3801  int* rstat /**< array to store row basis status, or NULL */
3802  )
3803 {
3804  int i;
3805 
3806  SCIPdebugMessage("calling SCIPlpiGetBase()\n");
3807 
3808  assert(lpi != NULL);
3809  assert(lpi->spx != NULL);
3810 
3811  assert( lpi->spx->preStrongbranchingBasisFreed() );
3812 
3813  if( rstat != NULL )
3814  {
3815  for( i = 0; i < lpi->spx->nRows(); ++i )
3816  {
3817  switch( lpi->spx->getBasisRowStatus(i) )
3818  {
3819  case SPxSolver::BASIC:
3820  rstat[i] = SCIP_BASESTAT_BASIC; /*lint !e641*/
3821  break;
3822  case SPxSolver::FIXED:
3823  case SPxSolver::ON_LOWER:
3824  rstat[i] = SCIP_BASESTAT_LOWER; /*lint !e641*/
3825  break;
3826  case SPxSolver::ON_UPPER:
3827  rstat[i] = SCIP_BASESTAT_UPPER; /*lint !e641*/
3828  break;
3829  case SPxSolver::ZERO:
3830  SCIPerrorMessage("slack variable has basis status ZERO (should not occur)\n");
3831  return SCIP_LPERROR;
3832  default:
3833  SCIPerrorMessage("invalid basis status\n");
3834  SCIPABORT();
3835  return SCIP_INVALIDDATA; /*lint !e527*/
3836  }
3837  }
3838  }
3839 
3840  if( cstat != NULL )
3841  {
3842  for( i = 0; i < lpi->spx->nCols(); ++i )
3843  {
3844  SCIP_Real val = 0.0;
3845  switch( lpi->spx->getBasisColStatus(i) )
3846  {
3847  case SPxSolver::BASIC:
3848  cstat[i] = SCIP_BASESTAT_BASIC; /*lint !e641*/
3849  break;
3850  case SPxSolver::FIXED:
3851  /* Get reduced cost estimation. If the estimation is not correct this should not hurt:
3852  * If the basis is loaded into SoPlex again, the status is converted to FIXED again; in
3853  * this case there is no problem at all. If the basis is saved and/or used in some other
3854  * solver, it usually is very cheap to perform the pivots necessary to get an optimal
3855  * basis. */
3856  SCIP_CALL( getRedCostEst(lpi->spx, i, &val) );
3857  if( val < 0.0 ) /* reduced costs < 0 => UPPER else => LOWER */
3858  cstat[i] = SCIP_BASESTAT_UPPER; /*lint !e641*/
3859  else
3860  cstat[i] = SCIP_BASESTAT_LOWER; /*lint !e641*/
3861  break;
3862  case SPxSolver::ON_LOWER:
3863  cstat[i] = SCIP_BASESTAT_LOWER; /*lint !e641*/
3864  break;
3865  case SPxSolver::ON_UPPER:
3866  cstat[i] = SCIP_BASESTAT_UPPER; /*lint !e641*/
3867  break;
3868  case SPxSolver::ZERO:
3869  cstat[i] = SCIP_BASESTAT_ZERO; /*lint !e641*/
3870  break;
3871  default:
3872  SCIPerrorMessage("invalid basis status\n");
3873  SCIPABORT();
3874  return SCIP_INVALIDDATA; /*lint !e527*/
3875  }
3876  }
3877  }
3878 
3879  return SCIP_OKAY;
3880 }
3881 
3882 /** sets current basis status for columns and rows */
3884  SCIP_LPI* lpi, /**< LP interface structure */
3885  int* cstat, /**< array with column basis status */
3886  int* rstat /**< array with row basis status */
3887  )
3888 {
3889  int i;
3890 
3891  SCIPdebugMessage("calling SCIPlpiSetBase()\n");
3892 
3893  assert(lpi != NULL);
3894  assert(lpi->spx != NULL);
3895  assert(cstat != NULL || lpi->spx->nCols() == 0);
3896  assert(rstat != NULL || lpi->spx->nRows() == 0);
3897 
3898  assert( lpi->spx->preStrongbranchingBasisFreed() );
3899  invalidateSolution(lpi);
3900 
3901  SPxSolver::VarStatus* spxcstat = NULL;
3902  SPxSolver::VarStatus* spxrstat = NULL;
3903  SCIP_ALLOC( BMSallocMemoryArray(&spxcstat, lpi->spx->nCols()) );
3904  SCIP_ALLOC( BMSallocMemoryArray(&spxrstat, lpi->spx->nRows()) );
3905 
3906  for( i = 0; i < lpi->spx->nRows(); ++i )
3907  {
3908  switch( rstat[i] )
3909  {
3910  case SCIP_BASESTAT_LOWER:
3911  spxrstat[i] = SPxSolver::ON_LOWER;
3912  break;
3913  case SCIP_BASESTAT_BASIC:
3914  spxrstat[i] = SPxSolver::BASIC;
3915  break;
3916  case SCIP_BASESTAT_UPPER:
3917  spxrstat[i] = SPxSolver::ON_UPPER;
3918  break;
3919  case SCIP_BASESTAT_ZERO:
3920  SCIPerrorMessage("slack variable has basis status ZERO (should not occur)\n");
3921  BMSfreeMemoryArrayNull(&spxcstat);
3922  BMSfreeMemoryArrayNull(&spxrstat);
3923  return SCIP_LPERROR; /*lint !e429*/
3924  default:
3925  SCIPerrorMessage("invalid basis status\n");
3926  SCIPABORT();
3927  return SCIP_INVALIDDATA; /*lint !e527*/
3928  }
3929  }
3930 
3931  for( i = 0; i < lpi->spx->nCols(); ++i )
3932  {
3933  switch( cstat[i] )
3934  {
3935  case SCIP_BASESTAT_LOWER:
3936  spxcstat[i] = SPxSolver::ON_LOWER;
3937  break;
3938  case SCIP_BASESTAT_BASIC:
3939  spxcstat[i] = SPxSolver::BASIC;
3940  break;
3941  case SCIP_BASESTAT_UPPER:
3942  spxcstat[i] = SPxSolver::ON_UPPER;
3943  break;
3944  case SCIP_BASESTAT_ZERO:
3945  spxcstat[i] = SPxSolver::ZERO;
3946  break;
3947  default:
3948  SCIPerrorMessage("invalid basis status\n");
3949  SCIPABORT();
3950  return SCIP_INVALIDDATA; /*lint !e527*/
3951  }
3952  }
3953 
3954  SOPLEX_TRY( lpi->messagehdlr, lpi->spx->setBasis(spxrstat, spxcstat) );
3955  lpi->spx->updateStatus();
3956 
3957  BMSfreeMemoryArrayNull(&spxcstat);
3958  BMSfreeMemoryArrayNull(&spxrstat);
3959 
3960  return SCIP_OKAY;
3961 }
3962 
3963 /** returns the indices of the basic columns and rows; basic column n gives value n, basic row m gives value -1-m */
3965  SCIP_LPI* lpi, /**< LP interface structure */
3966  int* bind /**< pointer to store basis indices ready to keep number of rows entries */
3967  )
3968 {
3969  SCIPdebugMessage("calling SCIPlpiGetBasisInd()\n");
3970 
3971  SPxSolver* spx;
3972 
3973  assert(lpi != NULL);
3974  assert(lpi->spx != NULL);
3975 
3976  assert( lpi->spx->preStrongbranchingBasisFreed() );
3977 
3978  /* the LPi defines the basis as column basis, i.e., as the set of (indices of) non-fixed columns and rows; if SoPlex
3979  * uses row representation, this is just the complement of the basis
3980  */
3981  spx = lpi->spx;
3982 
3983  /* for column representation, return the basis */
3984  if( spx->rep() == SPxSolver::COLUMN )
3985  {
3986  for( int i = 0; i < spx->nRows(); ++i )
3987  {
3988  SPxId id = spx->basis().baseId(i);
3989 
3990  bind[i] = (id.isSPxColId() ? spx->number(id) : - 1 - spx->number(id));
3991  }
3992  }
3993  /* for row representation, return the complement of the basis; for this, we need to loop through all rows and columns */
3994  else
3995  {
3996  int k = 0;
3997 
3998  assert( spx->rep() == SPxSolver::ROW );
3999 
4000  for( int i = 0; i < spx->nRows(); ++i )
4001  {
4002  if( !spx->isRowBasic(i) )
4003  bind[k++] = -1 - i;
4004  }
4005 
4006  for( int j = 0; j < spx->nCols(); ++j )
4007  {
4008  if( !spx->isColBasic(j) )
4009  bind[k++] = j;
4010  }
4011 
4012  assert(k == spx->nRows());
4013  }
4014 
4015  return SCIP_OKAY;
4016 }
4017 
4018 #ifdef OLD_BINV
4019 /* prepare a factorization of the basis matrix in column representation */
4020 static
4021 SCIP_RETCODE prepareFactorization(
4022  SCIP_LPI* lpi
4023  )
4024 {
4025  SCIPdebugMessage("Preparing factorization for computation of basis inverse.\n");
4026 
4027  try
4028  {
4029  /* if the factorization has not been set up, we compute a new factorization */
4030  if ( lpi->factorization == 0 )
4031  {
4032  SPxSolver* spx = lpi->spx;
4033 
4034  /* matrix to store columns */
4035  DataArray <const SVector*> matrix(spx->nRows());
4036 
4037  int k = 0;
4038  for (int i = 0; i < spx->nRows(); ++i)
4039  {
4040  if ( ! spx->isRowBasic(i) )
4041  matrix[k++] = new UnitVector(i);
4042  }
4043  for (int j = 0; j < spx->nCols(); ++j)
4044  {
4045  if ( ! spx->isColBasic(j) )
4046  matrix[k++] = &spx->colVector(j);
4047  }
4048  assert( k == spx->nRows() );
4049  assert( k == matrix.size() );
4050 
4051  /* compute factorization */
4052  lpi->factorization = new SLUFactor;
4053 #ifndef NDEBUG
4054  SLinSolver::Status status = lpi->factorization->load(matrix.get_ptr(), k);
4055 #else
4056  (void) lpi->factorization->load(matrix.get_ptr(), k);
4057 #endif
4058  assert( status == SLinSolver::OK );
4059  assert( k == lpi->factorization->dim() );
4060 
4061  /* delete matrix columns corresponding to unit vectors */
4062  k = 0;
4063  for (int i = 0; i < spx->nRows(); ++i)
4064  {
4065  if ( ! spx->isRowBasic(i) )
4066  delete matrix[k++];
4067  }
4068  }
4069  }
4070  catch(SPxException x)
4071  {
4072 #ifndef NDEBUG
4073  std::string s = x.what();
4074  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
4075 #endif
4076  return SCIP_LPERROR;
4077  }
4078 
4079  return SCIP_OKAY;
4080 }
4081 #endif
4082 
4083 /** get dense row of inverse basis matrix B^-1 */
4085  SCIP_LPI* lpi, /**< LP interface structure */
4086  int r, /**< row number */
4087  SCIP_Real* coef /**< pointer to store the coefficients of the row */
4088  )
4089 {
4090  SCIPdebugMessage("calling SCIPlpiGetBInvRow()\n");
4091 
4092  assert( lpi != NULL );
4093  assert( lpi->spx != NULL );
4094  assert( lpi->spx->preStrongbranchingBasisFreed() );
4095 
4096  assert(r >= 0);
4097  assert(r < lpi->spx->nRows());
4098 
4099  try
4100  {
4101  SPxSolver* spx = lpi->spx;
4102 
4103  Vector x(spx->nRows(), coef); /* row of B^-1 has nrows entries - note that x is based on coef */
4104 
4105  /* in the column case use the existing factorization */
4106  if ( spx->rep() == SPxSolver::COLUMN )
4107  {
4108  DVector e(spx->nRows());
4109 
4110  /* prepare unit vector */
4111  e.clear();
4112  e[r] = 1.0;
4113 
4114  /* solve system "x = e_r^T * B^-1" to get r'th row of B^-1 */
4115  spx->basis().coSolve(x, e);
4116  }
4117  else
4118  {
4119  assert(spx->rep() == SPxSolver::ROW);
4120 
4121 #ifdef OLD_BINV
4122  DVector e(spx->nRows());
4123 
4124  /* prepare unit vector */
4125  e.clear();
4126  e[r] = 1.0;
4127 
4128  /* factorization is deleted in invalidateSolution() */
4129  SCIP_CALL( prepareFactorization(lpi) );
4130  assert( lpi->factorization != 0 );
4131  assert( lpi->factorization->dim() == spx->nRows() );
4132 
4133  /* solve system "x = e_r^T * B^-1" to get r'th row of B^-1 */
4134  lpi->factorization->solveLeft(x, e);
4135 #else
4136  /**@todo should rhs be a reference? */
4137  DSVector rhs(spx->nCols());
4138  SSVector y(spx->nCols());
4139  int* bind;
4140  int index;
4141 
4142  /**@todo should bind be stored globally in lpi? */
4143  /* get ordering of column basis matrix */
4144  SCIP_ALLOC( BMSallocMemoryArray(&bind, spx->nRows()) );
4145  SCIP_CALL( SCIPlpiGetBasisInd(lpi, bind) );
4146 
4147  /* get vector corresponding to requested index r */
4148  index = bind[r];
4149 
4150  /* r corresponds to a row vector */
4151  if( index < 0 )
4152  {
4153  index = -index-1;
4154 
4155  /* should be a valid row index and in the column basis matrix, i.e., not basic w.r.t. row representation */
4156  assert(index >= 0);
4157  assert(index < spx->nRows());
4158  assert(!spx->isRowBasic(index));
4159 
4160  /* get row vector */
4161  rhs = spx->rowVector(index);
4162  rhs *= -1.0;
4163  }
4164  /* r corresponds to a column vector */
4165  else
4166  {
4167  /* should be a valid column index and in the column basis matrix, i.e., not basic w.r.t. row representation */
4168  assert(index < spx->nCols());
4169  assert(!spx->isColBasic(index));
4170 
4171  /* get unit vector */
4172  rhs = spx->unitVector(index);
4173  }
4174 
4175  /* solve system "y B = rhs", where B is the row basis matrix */
4176  spx->basis().solve(y, rhs);
4177 
4178  /* initialize result vector x as zero */
4179  BMSclearMemoryArray(coef, spx->nRows());
4180 
4181  /* add nonzero entries */
4182  for( int i = 0; i < spx->nCols(); ++i )
4183  {
4184  SPxId id = spx->basis().baseId(i);
4185 
4186  if( id.isSPxRowId() )
4187  {
4188  assert(spx->number(id) >= 0);
4189  assert(spx->number(id) < spx->nRows());
4190  assert(bind[r] >= 0 || spx->number(id) != index);
4191 
4192  x[spx->number(id)] = y[i];
4193  }
4194  }
4195 
4196  /* if r corresponds to a row vector, we have to add a 1 at position r */
4197  if( bind[r] < 0 )
4198  {
4199  assert(x[index] == 0.0);
4200  x[index] = 1.0;
4201  }
4202 
4203  /* free memory */
4204  BMSfreeMemoryArray(&bind);
4205 #endif
4206  }
4207  }
4208  catch(SPxException x)
4209  {
4210 #ifndef NDEBUG
4211  std::string s = x.what();
4212  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
4213 #endif
4214  return SCIP_LPERROR;
4215  }
4216 
4217  return SCIP_OKAY;
4218 }
4219 
4220 /** get dense solution of basis matrix B * coef = rhs */
4221 static
4222 SCIP_RETCODE lpiGetBInvVec(
4223  SCIP_LPI* lpi, /**< LP interface structure */
4224  SCIP_Real* rhs, /**< right-hand side vector */
4225  SCIP_Real* coef /**< vector to return coefficients */
4226  )
4227 {
4228  SCIPdebugMessage("calling SCIPlpiGetBInvVec()\n");
4229 
4230  assert(lpi != NULL);
4231  assert(lpi->spx != NULL);
4232  assert(lpi->spx->preStrongbranchingBasisFreed());
4233  assert(rhs != NULL);
4234  assert(coef != NULL);
4235 
4236  try
4237  {
4238  SPxSolver* spx = lpi->spx;
4239  Vector v(spx->nRows(), rhs);
4240  Vector x(spx->nRows(), coef);
4241 
4242  /* in the column case use the existing factorization */
4243  if( spx->rep() == SPxSolver::COLUMN )
4244  {
4245  /* solve system "x = B^-1 * A_c" to get c'th column of B^-1 * A */
4246  spx->basis().solve(x, v);
4247  }
4248  else
4249  {
4250  assert(spx->rep() == SPxSolver::ROW);
4251 
4252 #ifdef OLD_BINV
4253  /* factorization is deleted in invalidateSolution() */
4254  SCIP_CALL( prepareFactorization(lpi) );
4255  assert(lpi->factorization != 0);
4256  assert(lpi->factorization->dim() == spx->nRows());
4257 
4258  /* solve system B * x = v */
4259  lpi->factorization->solveRight(x, v);
4260 #else
4261  DSVector rowrhs(spx->nCols());
4262  SSVector y(spx->nCols());
4263  int* bind;
4264 
4265  /**@todo should bind be stored globally in lpi? */
4266  /* get ordering of column basis matrix */
4267  SCIP_ALLOC( BMSallocMemoryArray(&bind, spx->nRows()) );
4268  SCIP_CALL( SCIPlpiGetBasisInd(lpi, bind) );
4269 
4270  /* fill right-hand side for row-based system */
4271  for( int i = 0; i < spx->nCols(); ++i )
4272  {
4273  SPxId id = spx->basis().baseId(i);
4274 
4275  if( id.isSPxRowId() )
4276  {
4277  assert(spx->number(id) >= 0);
4278  assert(spx->number(id) < spx->nRows());
4279 
4280  rowrhs.add(i, v[spx->number(id)]);
4281  }
4282  else
4283  {
4284  assert(rowrhs[i] == 0.0);
4285  }
4286  }
4287 
4288  /* solve system "B y = rowrhs", where B is the row basis matrix */
4289  spx->basis().coSolve(y, rowrhs);
4290 
4291  /* fill result w.r.t. order given by bind */
4292  for( int i = 0; i < spx->nRows(); ++i )
4293  {
4294  int index;
4295 
4296  index = bind[i];
4297 
4298  if( index < 0 )
4299  {
4300  index = -index-1;
4301 
4302  /* should be a valid row index and in the column basis matrix, i.e., not basic w.r.t. row representation */
4303  assert(index >= 0);
4304  assert(index < spx->nRows());
4305  assert(!spx->isRowBasic(index));
4306 
4307  x[i] = v[index] - (spx->rowVector(index) * Vector(spx->nCols(), y.get_ptr()));
4308  }
4309  else
4310  {
4311  /* should be a valid column index and in the column basis matrix, i.e., not basic w.r.t. row representation */
4312  assert(index >= 0);
4313  assert(index < spx->nCols());
4314  assert(!spx->isColBasic(index));
4315 
4316  x[i] = y[index];
4317  }
4318  }
4319 
4320  /* free memory */
4321  BMSfreeMemoryArray(&bind);
4322 #endif
4323  }
4324  }
4325  catch(SPxException x)
4326  {
4327 #ifndef NDEBUG
4328  std::string s = x.what();
4329  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
4330 #endif
4331  return SCIP_LPERROR;
4332  }
4333 
4334  return SCIP_OKAY;
4335 }
4336 
4337 /** get dense column of inverse basis matrix B^-1 */
4339  SCIP_LPI* lpi, /**< LP interface structure */
4340  int c, /**< column number of B^-1; this is NOT the number of the column in the LP;
4341  * you have to call SCIPlpiGetBasisInd() to get the array which links the
4342  * B^-1 column numbers to the row and column numbers of the LP!
4343  * c must be between 0 and nrows-1, since the basis has the size
4344  * nrows * nrows */
4345  SCIP_Real* coef /**< pointer to store the coefficients of the column */
4346  )
4347 {
4348  SCIPdebugMessage("calling SCIPlpiGetBInvCol()\n");
4349 
4350  assert( lpi != NULL );
4351  assert( lpi->spx != NULL );
4352  assert( lpi->spx->preStrongbranchingBasisFreed() );
4353 
4354  /* prepare unit vector */
4355  DVector e(lpi->spx->nRows());
4356 
4357  e.clear();
4358 
4359  assert(c >= 0);
4360  assert(c < lpi->spx->nRows());
4361  e[c] = 1.0;
4362 
4363  /* solve */
4364  SCIP_CALL( lpiGetBInvVec(lpi, e.get_ptr(), coef) );
4365 
4366  return SCIP_OKAY;
4367 }
4368 
4369 /** get dense row of inverse basis matrix times constraint matrix B^-1 * A */
4371  SCIP_LPI* lpi, /**< LP interface structure */
4372  int r, /**< row number */
4373  const SCIP_Real* binvrow, /**< row in (A_B)^-1 from prior call to SCIPlpiGetBInvRow(), or NULL */
4374  SCIP_Real* coef /**< vector to return coefficients */
4375  )
4376 {
4377  SCIP_Real* buf;
4378  SCIP_Real* binv;
4379  int nrows;
4380  int ncols;
4381  int c;
4382 
4383  SCIPdebugMessage("calling SCIPlpiGetBInvARow()\n");
4384 
4385  assert(lpi != NULL);
4386  assert(lpi->spx != NULL);
4387  assert( lpi->spx->preStrongbranchingBasisFreed() );
4388 
4389  nrows = lpi->spx->nRows();
4390  ncols = lpi->spx->nCols();
4391  buf = NULL;
4392 
4393  /* get (or calculate) the row in B^-1 */
4394  if( binvrow == NULL )
4395  {
4396  SCIP_ALLOC( BMSallocMemoryArray(&buf, nrows) );
4397  SCIP_CALL( SCIPlpiGetBInvRow(lpi, r, buf) );
4398  binv = buf;
4399  }
4400  else
4401  binv = const_cast<SCIP_Real*>(binvrow);
4402 
4403  assert(binv != NULL);
4404 
4405  /* calculate the scalar product of the row in B^-1 and A */
4406  soplex::Vector binvvec(nrows, binv);
4407  for( c = 0; c < ncols; ++c )
4408  coef[c] = binvvec * lpi->spx->colVector(c); /* scalar product */ /*lint !e1702*/
4409 
4410  /* free memory if it was temporarily allocated */
4411  BMSfreeMemoryArrayNull(&buf);
4412 
4413  return SCIP_OKAY;
4414 }
4415 
4416 /** get dense column of inverse basis matrix times constraint matrix B^-1 * A */
4418  SCIP_LPI* lpi, /**< LP interface structure */
4419  int c, /**< column number */
4420  SCIP_Real* coef /**< vector to return coefficients */
4421  )
4422 {
4423  DVector col(lpi->spx->nRows());
4424 
4425  SCIPdebugMessage("calling SCIPlpiGetBInvACol()\n");
4426 
4427  assert( lpi != NULL );
4428  assert( lpi->spx != NULL );
4429  assert( lpi->spx->preStrongbranchingBasisFreed() );
4430 
4431  /* extract column c of A */
4432  assert(c >= 0);
4433  assert(c < lpi->spx->nCols());
4434 
4435  col.clear();
4436  col = lpi->spx->colVector(c);
4437  col.reDim(lpi->spx->nRows());
4438 
4439  /* solve */
4440  SCIP_CALL( lpiGetBInvVec(lpi, col.get_ptr(), coef) );
4441 
4442  return SCIP_OKAY;
4443 }
4444 
4445 /**@} */
4446 
4447 
4448 
4449 
4450 /*
4451  * LP State Methods
4452  */
4453 
4454 /**@name LP State Methods */
4455 /**@{ */
4456 
4457 /** stores LPi state (like basis information) into lpistate object */
4459  SCIP_LPI* lpi, /**< LP interface structure */
4460  BMS_BLKMEM* blkmem, /**< block memory */
4461  SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
4462  )
4463 {
4464  int ncols;
4465  int nrows;
4466 
4467  SCIPdebugMessage("calling SCIPlpiGetState()\n");
4468 
4469  assert(blkmem != NULL);
4470  assert(lpi != NULL);
4471  assert(lpi->spx != NULL);
4472  assert(lpistate != NULL);
4473 
4474  assert( lpi->spx->preStrongbranchingBasisFreed() );
4475 
4476  ncols = lpi->spx->nCols();
4477  nrows = lpi->spx->nRows();
4478  assert(ncols >= 0);
4479  assert(nrows >= 0);
4480 
4481  /* allocate lpistate data */
4482  SCIP_CALL( lpistateCreate(lpistate, blkmem, ncols, nrows) );
4483 
4484  /* allocate enough memory for storing uncompressed basis information */
4485  SCIP_CALL( ensureCstatMem(lpi, ncols) );
4486  SCIP_CALL( ensureRstatMem(lpi, nrows) );
4487 
4488  /* get unpacked basis information */
4489  SCIP_CALL( SCIPlpiGetBase(lpi, lpi->cstat, lpi->rstat) );
4490 
4491  /* pack LPi state data */
4492  (*lpistate)->ncols = ncols;
4493  (*lpistate)->nrows = nrows;
4494  lpistatePack(*lpistate, lpi->cstat, lpi->rstat);
4495 
4496  return SCIP_OKAY;
4497 }
4498 
4499 /** loads LPi state (like basis information) into solver; note that the LP might have been extended with additional
4500  * columns and rows since the state was stored with SCIPlpiGetState()
4501  */
4503  SCIP_LPI* lpi, /**< LP interface structure */
4504  BMS_BLKMEM* /*blkmem*/, /**< block memory */
4505  SCIP_LPISTATE* lpistate /**< LPi state information (like basis information) */
4506  )
4507 {
4508  int lpncols;
4509  int lpnrows;
4510  int i;
4511 
4512  SCIPdebugMessage("calling SCIPlpiSetState()\n");
4513 
4514  assert(lpi != NULL);
4515  assert(lpi->spx != NULL);
4516  assert(lpistate != NULL);
4517 
4518  assert( lpi->spx->preStrongbranchingBasisFreed() );
4519 
4520  lpncols = lpi->spx->nCols();
4521  lpnrows = lpi->spx->nRows();
4522  assert(lpistate->ncols <= lpncols);
4523  assert(lpistate->nrows <= lpnrows);
4524 
4525  /* allocate enough memory for storing uncompressed basis information */
4526  SCIP_CALL( ensureCstatMem(lpi, lpncols) );
4527  SCIP_CALL( ensureRstatMem(lpi, lpnrows) );
4528 
4529  /* unpack LPi state data */
4530  lpistateUnpack(lpistate, lpi->cstat, lpi->rstat);
4531 
4532  /* extend the basis to the current LP beyond the previously existing columns */
4533  for( i = lpistate->ncols; i < lpncols; ++i )
4534  {
4535  SCIP_Real bnd = lpi->spx->lower(i);
4536  if ( SCIPlpiIsInfinity(lpi, REALABS(bnd)) )
4537  {
4538  /* if lower bound is +/- infinity -> try upper bound */
4539  bnd = lpi->spx->lower(i);
4540  if ( SCIPlpiIsInfinity(lpi, REALABS(bnd)) )
4541  lpi->cstat[i] = SCIP_BASESTAT_ZERO; /* variable is free */
4542  else
4543  lpi->cstat[i] = SCIP_BASESTAT_UPPER; /* use finite upper bound */
4544  }
4545  else
4546  lpi->cstat[i] = SCIP_BASESTAT_LOWER; /* use finite lower bound */
4547  }
4548  for( i = lpistate->nrows; i < lpnrows; ++i )
4549  lpi->rstat[i] = SCIP_BASESTAT_BASIC; /*lint !e641*/
4550 
4551  /* load basis information */
4552  SCIP_CALL( SCIPlpiSetBase(lpi, lpi->cstat, lpi->rstat) );
4553 
4554  return SCIP_OKAY;
4555 }
4556 
4557 /** clears current LPi state (like basis information) of the solver */
4559  SCIP_LPI* lpi /**< LP interface structure */
4560  )
4561 { /*lint --e{715}*/
4562  SCIPdebugMessage("calling SCIPlpiClearState()\n");
4563 
4564  assert(lpi != NULL);
4565  assert(lpi->spx != NULL);
4566 
4567  try
4568  {
4569  lpi->spx->reLoad();
4570  }
4571  catch(SPxException x)
4572  {
4573 #ifndef NDEBUG
4574  std::string s = x.what();
4575  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
4576 #endif
4577  assert( lpi->spx->getStatus() != SPxSolver::OPTIMAL );
4578  return SCIP_LPERROR;
4579  }
4580 
4581  return SCIP_OKAY;
4582 }
4583 
4584 /** frees LPi state information */
4586  SCIP_LPI* lpi, /**< LP interface structure */
4587  BMS_BLKMEM* blkmem, /**< block memory */
4588  SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */
4589  )
4590 { /*lint --e{715}*/
4591  SCIPdebugMessage("calling SCIPlpiFreeState()\n");
4592 
4593  assert(lpi != NULL);
4594  assert(lpistate != NULL);
4595 
4596  if ( *lpistate != NULL )
4597  lpistateFree(lpistate, blkmem);
4598 
4599  return SCIP_OKAY;
4600 }
4601 
4602 /** checks, whether the given LP state contains simplex basis information */
4604  SCIP_LPI* lpi, /**< LP interface structure */
4605  SCIP_LPISTATE* lpistate /**< LP state information (like basis information) */
4606  )
4607 { /*lint --e{715}*/
4608  return TRUE;
4609 }
4610 
4611 /** reads LP state (like basis information from a file */
4613  SCIP_LPI* lpi, /**< LP interface structure */
4614  const char* fname /**< file name */
4615  )
4616 {
4617  SCIPdebugMessage("calling SCIPlpiReadState()\n");
4618 
4619  assert( lpi->spx->preStrongbranchingBasisFreed() );
4620 
4621  bool success;
4622  SOPLEX_TRY( lpi->messagehdlr, success = lpi->spx->readBasisFile(fname, 0, 0) );
4623 
4624  return success ? SCIP_OKAY : SCIP_LPERROR;
4625 }
4626 
4627 /** writes LP state (like basis information) to a file */
4629  SCIP_LPI* lpi, /**< LP interface structure */
4630  const char* fname /**< file name */
4631  )
4632 {
4633  SCIPdebugMessage("calling SCIPlpiWriteState()\n");
4634 
4635  assert( lpi->spx->preStrongbranchingBasisFreed() );
4636 
4637  bool res;
4638  SOPLEX_TRY( lpi->messagehdlr, res = lpi->spx->writeBasisFile(fname, 0, 0) );
4639 
4640  if ( ! res )
4641  return SCIP_LPERROR;
4642 
4643  return SCIP_OKAY;
4644 }
4645 
4646 /**@} */
4647 
4648 
4649 
4650 
4651 /*
4652  * LP Pricing Norms Methods
4653  */
4654 
4655 /**@name LP Pricing Norms Methods */
4656 /**@{ */
4657 
4658 /** stores LPi pricing norms information
4659  * @todo should we store norm information?
4660  */
4662  SCIP_LPI* lpi, /**< LP interface structure */
4663  BMS_BLKMEM* blkmem, /**< block memory */
4664  SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
4665  )
4666 {
4667  assert(lpinorms != NULL);
4668 
4669  (*lpinorms) = NULL;
4670 
4671  return SCIP_OKAY;
4672 }
4673 
4674 /** loads LPi pricing norms into solver; note that the LP might have been extended with additional
4675  * columns and rows since the state was stored with SCIPlpiGetNorms()
4676  */
4678  SCIP_LPI* lpi, /**< LP interface structure */
4679  BMS_BLKMEM* blkmem, /**< block memory */
4680  SCIP_LPINORMS* lpinorms /**< LPi pricing norms information */
4681  )
4682 {
4683  assert(lpinorms == NULL);
4684 
4685  /* no work necessary */
4686  return SCIP_OKAY;
4687 }
4688 
4689 /** frees pricing norms information */
4691  SCIP_LPI* lpi, /**< LP interface structure */
4692  BMS_BLKMEM* blkmem, /**< block memory */
4693  SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */
4694  )
4695 {
4696  assert(lpinorms == NULL);
4697 
4698  /* no work necessary */
4699  return SCIP_OKAY;
4700 }
4701 
4702 /**@} */
4703 
4704 
4705 
4706 
4707 /*
4708  * Parameter Methods
4709  */
4710 
4711 /**@name Parameter Methods */
4712 /**@{ */
4713 
4714 /** gets integer parameter of LP */
4716  SCIP_LPI* lpi, /**< LP interface structure */
4717  SCIP_LPPARAM type, /**< parameter number */
4718  int* ival /**< buffer to store the parameter value */
4719  )
4720 {
4721  SCIPdebugMessage("calling SCIPlpiGetIntpar()\n");
4722 
4723  assert(lpi != NULL);
4724  assert(lpi->spx != NULL);
4725  assert(ival != NULL);
4726 
4727  switch( type )
4728  {
4730  *ival = lpi->spx->getFromScratch();
4731  break;
4732  case SCIP_LPPAR_LPINFO:
4733  *ival = lpi->spx->getLpInfo();
4734  break;
4735  case SCIP_LPPAR_LPITLIM:
4736  *ival = lpi->spx->getIterationLimit();
4737  break;
4738  case SCIP_LPPAR_PRESOLVING:
4739  *ival = lpi->spx->getPresolving();
4740  break;
4741  case SCIP_LPPAR_PRICING:
4742  *ival = (int)lpi->pricing;
4743  break;
4744  case SCIP_LPPAR_SCALING:
4745  *ival = lpi->spx->getScaling();
4746  break;
4747  default:
4748  return SCIP_PARAMETERUNKNOWN;
4749  } /*lint !e788*/
4750 
4751  return SCIP_OKAY;
4752 }
4753 
4754 /** sets integer parameter of LP */
4756  SCIP_LPI* lpi, /**< LP interface structure */
4757  SCIP_LPPARAM type, /**< parameter number */
4758  int ival /**< parameter value */
4759  )
4760 {
4761  SCIPdebugMessage("calling SCIPlpiSetIntpar()\n");
4762 
4763  assert(lpi != NULL);
4764  assert(lpi->spx != NULL);
4765 
4766  switch( type )
4767  {
4769  assert(ival == TRUE || ival == FALSE);
4770  lpi->spx->setFromScratch(bool(ival));
4771  break;
4772  case SCIP_LPPAR_LPINFO:
4773  assert(ival == TRUE || ival == FALSE);
4774  lpi->spx->setLpInfo(bool(ival));
4775  break;
4776  case SCIP_LPPAR_LPITLIM:
4777  assert(ival >= -1);
4778  lpi->spx->setIterationLimit(ival);
4779  break;
4780  case SCIP_LPPAR_PRESOLVING:
4781  assert(ival == TRUE || ival == FALSE);
4782  lpi->spx->setPresolving(bool(ival));
4783  break;
4784  case SCIP_LPPAR_PRICING:
4785  lpi->pricing = (SCIP_PRICING)ival;
4786  switch( lpi->pricing )
4787  {
4789  case SCIP_PRICING_AUTO:
4790  lpi->spx->setAutoPricer();
4791  break;
4792  case SCIP_PRICING_FULL:
4793  lpi->spx->setFullPricer();
4794  break;
4795  case SCIP_PRICING_PARTIAL:
4796  lpi->spx->setParmultPricer();
4797  break;
4798  case SCIP_PRICING_STEEP:
4799  lpi->spx->setSteepPricer();
4800  break;
4802  lpi->spx->setSteepQStartPricer();
4803  break;
4804  case SCIP_PRICING_DEVEX:
4805  lpi->spx->setDevexPricer();
4806  break;
4807  default:
4808  return SCIP_LPERROR;
4809  }
4810  break;
4811  case SCIP_LPPAR_SCALING:
4812  assert(ival == TRUE || ival == FALSE);
4813  lpi->spx->setScaling(bool(ival));
4814  break;
4815  default:
4816  return SCIP_PARAMETERUNKNOWN;
4817  } /*lint !e788*/
4818 
4819  return SCIP_OKAY;
4820 }
4821 
4822 /** gets floating point parameter of LP */
4824  SCIP_LPI* lpi, /**< LP interface structure */
4825  SCIP_LPPARAM type, /**< parameter number */
4826  SCIP_Real* dval /**< buffer to store the parameter value */
4827  )
4828 {
4829  SCIPdebugMessage("calling SCIPlpiGetRealpar()\n");
4830 
4831  assert(lpi != NULL);
4832  assert(lpi->spx != NULL);
4833  assert(dval != NULL);
4834 
4835  switch( type )
4836  {
4837  case SCIP_LPPAR_FEASTOL:
4838  *dval = lpi->spx->feastol();
4839  break;
4840 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 160)
4842  *dval = lpi->spx->opttol();
4843  break;
4844 #endif
4845  case SCIP_LPPAR_LOBJLIM:
4846  *dval = lpi->spx->getObjLoLimit();
4847  break;
4848  case SCIP_LPPAR_UOBJLIM:
4849  *dval = lpi->spx->getObjUpLimit();
4850  break;
4851  case SCIP_LPPAR_LPTILIM:
4852  *dval = lpi->spx->terminationTime();
4853  break;
4855  *dval = lpi->rowrepswitch;
4856  break;
4858  *dval = lpi->conditionlimit;
4859  break;
4860  default:
4861  return SCIP_PARAMETERUNKNOWN;
4862  } /*lint !e788*/
4863 
4864  return SCIP_OKAY;
4865 }
4866 
4867 /** sets floating point parameter of LP */
4869  SCIP_LPI* lpi, /**< LP interface structure */
4870  SCIP_LPPARAM type, /**< parameter number */
4871  SCIP_Real dval /**< parameter value */
4872  )
4873 {
4874  SCIPdebugMessage("calling SCIPlpiSetRealpar()\n");
4875 
4876  assert(lpi != NULL);
4877  assert(lpi->spx != NULL);
4878 
4879  switch( type )
4880  {
4881  case SCIP_LPPAR_FEASTOL:
4882  lpi->spx->setFeastol(dval);
4883  break;
4884 #if ((SOPLEX_VERSION == 160 && SOPLEX_SUBVERSION >= 5) || SOPLEX_VERSION > 160)
4886  lpi->spx->setOpttol(dval);
4887  break;
4888 #endif
4889  case SCIP_LPPAR_LOBJLIM:
4890  lpi->spx->setObjLoLimit(dval);
4891  break;
4892  case SCIP_LPPAR_UOBJLIM:
4893  lpi->spx->setObjUpLimit(dval);
4894  break;
4895  case SCIP_LPPAR_LPTILIM:
4896  lpi->spx->setTerminationTime(dval);
4897  break;
4899  assert(dval >= -1.5);
4900  lpi->rowrepswitch = dval;
4901  break;
4903  lpi->conditionlimit = dval;
4904  lpi->checkcondition = (dval >= 0);
4905  break;
4906  default:
4907  return SCIP_PARAMETERUNKNOWN;
4908  } /*lint !e788*/
4909 
4910  return SCIP_OKAY;
4911 }
4912 
4913 /**@} */
4914 
4915 
4916 
4917 
4918 /*
4919  * Numerical Methods
4920  */
4921 
4922 /**@name Numerical Methods */
4923 /**@{ */
4924 
4925 /** returns value treated as infinity in the LP solver */
4927  SCIP_LPI* /*lpi*/ /**< LP interface structure */
4928  )
4929 {
4930  SCIPdebugMessage("calling SCIPlpiInfinity()\n");
4931 
4932  return soplex::infinity;
4933 }
4934 
4935 /** checks if given value is treated as infinity in the LP solver */
4937  SCIP_LPI* /*lpi*/, /**< LP interface structure */
4938  SCIP_Real val
4939  )
4940 {
4941  SCIPdebugMessage("calling SCIPlpiIsInfinity()\n");
4942 
4943  return (val >= soplex::infinity);
4944 }
4945 
4946 /**@} */
4947 
4948 
4949 
4950 
4951 /*
4952  * File Interface Methods
4953  */
4954 
4955 /**@name File Interface Methods */
4956 /**@{ */
4957 
4958 /** returns, whether the given file exists */
4959 static
4960 SCIP_Bool fileExists(
4961  const char* filename /**< file name */
4962  )
4963 {
4964  FILE* f;
4965 
4966  f = fopen(filename, "r");
4967  if( f == NULL )
4968  return FALSE;
4969 
4970  fclose(f);
4971 
4972  return TRUE;
4973 }
4974 
4975 /** reads LP from a file */
4977  SCIP_LPI* lpi, /**< LP interface structure */
4978  const char* fname /**< file name */
4979  )
4980 {
4981  SCIPdebugMessage("calling SCIPlpiReadLP()\n");
4982 
4983  assert(lpi != NULL);
4984  assert(lpi->spx != NULL);
4985 
4986  assert( lpi->spx->preStrongbranchingBasisFreed() );
4987 
4988  if( !fileExists(fname) )
4989  return SCIP_NOFILE;
4990 
4991  try
4992  {
4993  if( !lpi->spx->readLP(fname) )
4994  return SCIP_READERROR;
4995  }
4996  catch(SPxException x)
4997  {
4998 #ifndef NDEBUG
4999  std::string s = x.what();
5000  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
5001 #endif
5002  return SCIP_READERROR;
5003  }
5004 
5005  return SCIP_OKAY;
5006 }
5007 
5008 /** writes LP to a file */
5010  SCIP_LPI* lpi, /**< LP interface structure */
5011  const char* fname /**< file name */
5012  )
5013 {
5014  SCIPdebugMessage("calling SCIPlpiWriteLP()\n");
5015 
5016  assert(lpi != NULL);
5017  assert(lpi->spx != NULL);
5018 
5019  try
5020  {
5021  lpi->spx->writeFile(fname);
5022  }
5023  catch(SPxException x)
5024  {
5025 #ifndef NDEBUG
5026  std::string s = x.what();
5027  SCIPmessagePrintWarning(lpi->messagehdlr, "SoPlex threw an exception: %s\n", s.c_str());
5028 #endif
5029  return SCIP_WRITEERROR;
5030  }
5031 
5032  return SCIP_OKAY;
5033 }
5034 
5035 /**@} */
5036