OR-Tools  8.2
cplex_interface.cc
Go to the documentation of this file.
1 // Copyright 2014 IBM Corporation
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // Initial version of this code was written by Daniel Junglas (IBM)
15 
16 #include <limits>
17 #include <memory>
18 
19 #include "absl/strings/str_format.h"
21 #include "ortools/base/logging.h"
22 #include "ortools/base/timer.h"
24 
25 #if defined(USE_CPLEX)
26 
27 extern "C" {
28 #include "ilcplex/cplexx.h"
29 // This is an undocumented function, setting the objective offset
30 // is not supported everywhere (for example it may not be exported if a
31 // model is written to a file), but it works in the cases we need here.
32 CPXLIBAPI int CPXPUBLIC CPXEsetobjoffset(CPXCENVptr, CPXLPptr, double);
33 }
34 
35 // In case we need to return a double but don't have a value for that
36 // we just return a NaN.
37 #if !defined(CPX_NAN)
38 #define CPX_NAN std::numeric_limits<double>::quiet_NaN()
39 #endif
40 
41 // The argument to this macro is the invocation of a CPXX function that
42 // returns a status. If the function returns non-zero the macro aborts
43 // the program with an appropriate error message.
44 #define CHECK_STATUS(s) \
45  do { \
46  int const status_ = s; \
47  CHECK_EQ(0, status_); \
48  } while (0)
49 
50 namespace operations_research {
51 
52 using std::unique_ptr;
53 
54 // For a model that is extracted to an instance of this class there is a
55 // 1:1 corresponence between MPVariable instances and CPLEX columns: the
56 // index of an extracted variable is the column index in the CPLEX model.
57 // Similiar for instances of MPConstraint: the index of the constraint in
58 // the model is the row index in the CPLEX model.
59 class CplexInterface : public MPSolverInterface {
60  public:
61  // NOTE: 'mip' specifies the type of the problem (either continuous or
62  // mixed integer. This type is fixed for the lifetime of the
63  // instance. There are no dynamic changes to the model type.
64  explicit CplexInterface(MPSolver* const solver, bool mip);
65  ~CplexInterface();
66 
67  // Sets the optimization direction (min/max).
68  virtual void SetOptimizationDirection(bool maximize);
69 
70  // ----- Solve -----
71  // Solve the problem using the parameter values specified.
72  virtual MPSolver::ResultStatus Solve(MPSolverParameters const& param);
73 
74  // ----- Model modifications and extraction -----
75  // Resets extracted model
76  virtual void Reset();
77 
78  virtual void SetVariableBounds(int var_index, double lb, double ub);
79  virtual void SetVariableInteger(int var_index, bool integer);
80  virtual void SetConstraintBounds(int row_index, double lb, double ub);
81 
82  virtual void AddRowConstraint(MPConstraint* const ct);
83  virtual void AddVariable(MPVariable* const var);
84  virtual void SetCoefficient(MPConstraint* const constraint,
85  MPVariable const* const variable,
86  double new_value, double old_value);
87 
88  // Clear a constraint from all its terms.
89  virtual void ClearConstraint(MPConstraint* const constraint);
90  // Change a coefficient in the linear objective
91  virtual void SetObjectiveCoefficient(MPVariable const* const variable,
92  double coefficient);
93  // Change the constant term in the linear objective.
94  virtual void SetObjectiveOffset(double value);
95  // Clear the objective from all its terms.
96  virtual void ClearObjective();
97 
98  // ------ Query statistics on the solution and the solve ------
99  // Number of simplex iterations
100  virtual int64 iterations() const;
101  // Number of branch-and-bound nodes. Only available for discrete problems.
102  virtual int64 nodes() const;
103 
104  // Returns the basis status of a row.
105  virtual MPSolver::BasisStatus row_status(int constraint_index) const;
106  // Returns the basis status of a column.
107  virtual MPSolver::BasisStatus column_status(int variable_index) const;
108 
109  // ----- Misc -----
110 
111  // Query problem type.
112  // Remember that problem type is a static property that is set
113  // in the constructor and never changed.
114  virtual bool IsContinuous() const { return IsLP(); }
115  virtual bool IsLP() const { return !mMip; }
116  virtual bool IsMIP() const { return mMip; }
117 
118  virtual void ExtractNewVariables();
119  virtual void ExtractNewConstraints();
120  virtual void ExtractObjective();
121 
122  virtual std::string SolverVersion() const;
123 
124  virtual void* underlying_solver() { return reinterpret_cast<void*>(mLp); }
125 
126  virtual double ComputeExactConditionNumber() const {
127  if (!IsContinuous()) {
128  LOG(DFATAL) << "ComputeExactConditionNumber not implemented for"
129  << " CPLEX_MIXED_INTEGER_PROGRAMMING";
130  return CPX_NAN;
131  }
132 
133  if (CheckSolutionIsSynchronized()) {
134  double kappa = CPX_NAN;
135  CHECK_STATUS(CPXXgetdblquality(mEnv, mLp, &kappa, CPX_EXACT_KAPPA));
136  return kappa;
137  }
138  LOG(DFATAL) << "Cannot get exact condition number without solution";
139  return CPX_NAN;
140  }
141 
142  protected:
143  // Set all parameters in the underlying solver.
144  virtual void SetParameters(MPSolverParameters const& param);
145  // Set each parameter in the underlying solver.
146  virtual void SetRelativeMipGap(double value);
147  virtual void SetPrimalTolerance(double value);
148  virtual void SetDualTolerance(double value);
149  virtual void SetPresolveMode(int value);
150  virtual void SetScalingMode(int value);
151  virtual void SetLpAlgorithm(int value);
152 
153  virtual bool ReadParameterFile(std::string const& filename);
154  virtual std::string ValidFileExtensionForParameterFile() const;
155 
156  private:
157  // Mark modeling object "out of sync". This implicitly invalidates
158  // solution information as well. It is the counterpart of
159  // MPSolverInterface::InvalidateSolutionSynchronization
160  void InvalidateModelSynchronization() {
161  mCstat = 0;
162  mRstat = 0;
163  sync_status_ = MUST_RELOAD;
164  }
165 
166  // Transform CPLEX basis status to MPSolver basis status.
167  static MPSolver::BasisStatus xformBasisStatus(int cplex_basis_status);
168 
169  private:
170  CPXLPptr mLp;
171  CPXENVptr mEnv;
172  bool const mMip;
173  // Incremental extraction.
174  // Without incremental extraction we have to re-extract the model every
175  // time we perform a solve. Due to the way the Reset() function is
176  // implemented, this will lose MIP start or basis information from a
177  // previous solve. On the other hand, if there is a significant changes
178  // to the model then just re-extracting everything is usually faster than
179  // keeping the low-level modeling object in sync with the high-level
180  // variables/constraints.
181  // Note that incremental extraction is particularly expensive in function
182  // ExtractNewVariables() since there we must scan _all_ old constraints
183  // and update them with respect to the new variables.
184  bool const supportIncrementalExtraction;
185 
186  // Use slow and immediate updates or try to do bulk updates.
187  // For many updates to the model we have the option to either perform
188  // the update immediately with a potentially slow operation or to
189  // just mark the low-level modeling object out of sync and re-extract
190  // the model later.
191  enum SlowUpdates {
192  SlowSetCoefficient = 0x0001,
193  SlowClearConstraint = 0x0002,
194  SlowSetObjectiveCoefficient = 0x0004,
195  SlowClearObjective = 0x0008,
196  SlowSetConstraintBounds = 0x0010,
197  SlowSetVariableInteger = 0x0020,
198  SlowSetVariableBounds = 0x0040,
199  SlowUpdatesAll = 0xffff
200  } const slowUpdates;
201  // CPLEX has no method to query the basis status of a single variable.
202  // Hence we query the status only once and cache the array. This is
203  // much faster in case the basis status of more than one row/column
204  // is required.
205  unique_ptr<int[]> mutable mCstat;
206  unique_ptr<int[]> mutable mRstat;
207 
208  // Setup the right-hand side of a constraint from its lower and upper bound.
209  static void MakeRhs(double lb, double ub, double& rhs, char& sense,
210  double& range);
211 };
212 
213 // Creates a LP/MIP instance.
214 CplexInterface::CplexInterface(MPSolver* const solver, bool mip)
215  : MPSolverInterface(solver),
216  mEnv(0),
217  mLp(0),
218  mMip(mip),
219  slowUpdates(static_cast<SlowUpdates>(SlowSetObjectiveCoefficient |
220  SlowClearObjective)),
221  supportIncrementalExtraction(false),
222  mCstat(),
223  mRstat() {
224  int status;
225 
226  mEnv = CPXXopenCPLEX(&status);
227  CHECK_STATUS(status);
228  DCHECK(mEnv != nullptr); // should not be NULL if status=0
229 
230  char const* name = solver_->name_.c_str();
231  mLp = CPXXcreateprob(mEnv, &status, name);
232  CHECK_STATUS(status);
233  DCHECK(mLp != nullptr); // should not be NULL if status=0
234 
235  CHECK_STATUS(CPXXchgobjsen(mEnv, mLp, maximize_ ? CPX_MAX : CPX_MIN));
236  if (mMip) CHECK_STATUS(CPXXchgprobtype(mEnv, mLp, CPXPROB_MILP));
237 }
238 
239 CplexInterface::~CplexInterface() {
240  CHECK_STATUS(CPXXfreeprob(mEnv, &mLp));
241  CHECK_STATUS(CPXXcloseCPLEX(&mEnv));
242 }
243 
244 std::string CplexInterface::SolverVersion() const {
245  // We prefer CPXXversionnumber() over CPXXversion() since the
246  // former will never pose any encoding issues.
247  int version = 0;
248  CHECK_STATUS(CPXXversionnumber(mEnv, &version));
249 
250  int const major = version / 1000000;
251  version -= major * 1000000;
252  int const release = version / 10000;
253  version -= release * 10000;
254  int const mod = version / 100;
255  version -= mod * 100;
256  int const fix = version;
257 
258  return absl::StrFormat("CPLEX library version %d.%02d.%02d.%02d", major,
259  release, mod, fix);
260 }
261 
262 // ------ Model modifications and extraction -----
263 
264 void CplexInterface::Reset() {
265  // Instead of explicitly clearing all modeling objects we
266  // just delete the problem object and allocate a new one.
267  CHECK_STATUS(CPXXfreeprob(mEnv, &mLp));
268 
269  int status;
270  const char* const name = solver_->name_.c_str();
271  mLp = CPXXcreateprob(mEnv, &status, name);
272  CHECK_STATUS(status);
273  DCHECK(mLp != nullptr); // should not be NULL if status=0
274 
275  CHECK_STATUS(CPXXchgobjsen(mEnv, mLp, maximize_ ? CPX_MAX : CPX_MIN));
276  if (mMip) CHECK_STATUS(CPXXchgprobtype(mEnv, mLp, CPXPROB_MILP));
277 
278  ResetExtractionInformation();
279  mCstat = 0;
280  mRstat = 0;
281 }
282 
283 void CplexInterface::SetOptimizationDirection(bool maximize) {
284  InvalidateSolutionSynchronization();
285  CPXXchgobjsen(mEnv, mLp, maximize ? CPX_MAX : CPX_MIN);
286 }
287 
288 void CplexInterface::SetVariableBounds(int var_index, double lb, double ub) {
289  InvalidateSolutionSynchronization();
290 
291  // Changing the bounds of a variable is fast. However, doing this for
292  // many variables may still be slow. So we don't perform the update by
293  // default. However, if we support incremental extraction
294  // (supportIncrementalExtraction is true) then we MUST perform the
295  // update here or we will lose it.
296 
297  if (!supportIncrementalExtraction && !(slowUpdates & SlowSetVariableBounds)) {
298  InvalidateModelSynchronization();
299  } else {
300  if (variable_is_extracted(var_index)) {
301  // Variable has already been extracted, so we must modify the
302  // modeling object.
303  DCHECK_LT(var_index, last_variable_index_);
304  char const lu[2] = {'L', 'U'};
305  double const bd[2] = {lb, ub};
306  CPXDIM const idx[2] = {var_index, var_index};
307  CHECK_STATUS(CPXXchgbds(mEnv, mLp, 2, idx, lu, bd));
308  } else {
309  // Variable is not yet extracted. It is sufficient to just mark
310  // the modeling object "out of sync"
311  InvalidateModelSynchronization();
312  }
313  }
314 }
315 
316 // Modifies integrality of an extracted variable.
317 void CplexInterface::SetVariableInteger(int var_index, bool integer) {
318  InvalidateSolutionSynchronization();
319 
320  // NOTE: The type of the model (continuous or mixed integer) is
321  // defined once and for all in the constructor. There are no
322  // dynamic changes to the model type.
323 
324  // Changing the type of a variable should be fast. Still, doing all
325  // updates in one big chunk right before solve() is usually faster.
326  // However, if we support incremental extraction
327  // (supportIncrementalExtraction is true) then we MUST change the
328  // type of extracted variables here.
329 
330  if (!supportIncrementalExtraction &&
331  !(slowUpdates && SlowSetVariableInteger)) {
332  InvalidateModelSynchronization();
333  } else {
334  if (mMip) {
335  if (variable_is_extracted(var_index)) {
336  // Variable is extracted. Change the type immediately.
337  // TODO: Should we check the current type and don't do anything
338  // in case the type does not change?
339  DCHECK_LE(var_index, CPXXgetnumcols(mEnv, mLp));
340  char const type = integer ? CPX_INTEGER : CPX_CONTINUOUS;
341  CHECK_STATUS(CPXXchgctype(mEnv, mLp, 1, &var_index, &type));
342  } else
343  InvalidateModelSynchronization();
344  } else {
345  LOG(DFATAL)
346  << "Attempt to change variable to integer in non-MIP problem!";
347  }
348  }
349 }
350 
351 // Setup the right-hand side of a constraint.
352 void CplexInterface::MakeRhs(double lb, double ub, double& rhs, char& sense,
353  double& range) {
354  if (lb == ub) {
355  // Both bounds are equal -> this is an equality constraint
356  rhs = lb;
357  range = 0.0;
358  sense = 'E';
359  } else if (lb > -CPX_INFBOUND && ub < CPX_INFBOUND) {
360  // Both bounds are finite -> this is a ranged constraint
361  // The value of a ranged constraint is allowed to be in
362  // [ rhs[i], rhs[i]+rngval[i] ]
363  // see also the reference documentation for CPXXnewrows()
364  if (ub < lb) {
365  // The bounds for the constraint are contradictory. CPLEX models
366  // a range constraint l <= ax <= u as
367  // ax = l + v
368  // where v is an auxiliary variable the range of which is controlled
369  // by l and u: if l < u then v in [0, u-l]
370  // else v in [u-l, 0]
371  // (the range is specified as the rngval[] argument to CPXXnewrows).
372  // Thus CPLEX cannot represent range constraints with contradictory
373  // bounds and we must error out here.
374  CHECK_STATUS(CPXERR_BAD_ARGUMENT);
375  }
376  rhs = lb;
377  range = ub - lb;
378  sense = 'R';
379  } else if (ub < CPX_INFBOUND ||
380  (std::abs(ub) == CPX_INFBOUND && std::abs(lb) > CPX_INFBOUND)) {
381  // Finite upper, infinite lower bound -> this is a <= constraint
382  rhs = ub;
383  range = 0.0;
384  sense = 'L';
385  } else if (lb > -CPX_INFBOUND ||
386  (std::abs(lb) == CPX_INFBOUND && std::abs(ub) > CPX_INFBOUND)) {
387  // Finite lower, infinite upper bound -> this is a >= constraint
388  rhs = lb;
389  range = 0.0;
390  sense = 'G';
391  } else {
392  // Lower and upper bound are both infinite.
393  // This is used for example in .mps files to specify alternate
394  // objective functions.
395  // Note that the case lb==ub was already handled above, so we just
396  // pick the bound with larger magnitude and create a constraint for it.
397  // Note that we replace the infinite bound by CPX_INFBOUND since
398  // bounds with larger magnitude may cause other CPLEX functions to
399  // fail (for example the export to LP files).
400  DCHECK_GT(std::abs(lb), CPX_INFBOUND);
401  DCHECK_GT(std::abs(ub), CPX_INFBOUND);
402  if (std::abs(lb) > std::abs(ub)) {
403  rhs = (lb < 0) ? -CPX_INFBOUND : CPX_INFBOUND;
404  sense = 'G';
405  } else {
406  rhs = (ub < 0) ? -CPX_INFBOUND : CPX_INFBOUND;
407  sense = 'L';
408  }
409  range = 0.0;
410  }
411 }
412 
413 void CplexInterface::SetConstraintBounds(int index, double lb, double ub) {
414  InvalidateSolutionSynchronization();
415 
416  // Changing rhs, sense, or range of a constraint is not too slow.
417  // Still, doing all the updates in one large operation is faster.
418  // Note however that if we do not want to re-extract the full model
419  // for each solve (supportIncrementalExtraction is true) then we MUST
420  // update the constraint here, otherwise we lose this update information.
421 
422  if (!supportIncrementalExtraction &&
423  !(slowUpdates & SlowSetConstraintBounds)) {
424  InvalidateModelSynchronization();
425  } else {
426  if (constraint_is_extracted(index)) {
427  // Constraint is already extracted, so we must update its bounds
428  // and its type.
429  DCHECK(mLp != NULL);
430  char sense;
431  double range, rhs;
432  MakeRhs(lb, ub, rhs, sense, range);
433  CHECK_STATUS(CPXXchgrhs(mEnv, mLp, 1, &index, &lb));
434  CHECK_STATUS(CPXXchgsense(mEnv, mLp, 1, &index, &sense));
435  CHECK_STATUS(CPXXchgrngval(mEnv, mLp, 1, &index, &range));
436  } else {
437  // Constraint is not yet extracted. It is sufficient to mark the
438  // modeling object as "out of sync"
439  InvalidateModelSynchronization();
440  }
441  }
442 }
443 
444 void CplexInterface::AddRowConstraint(MPConstraint* const ct) {
445  // This is currently only invoked when a new constraint is created,
446  // see MPSolver::MakeRowConstraint().
447  // At this point we only have the lower and upper bounds of the
448  // constraint. We could immediately call CPXXaddrows() here but it is
449  // usually much faster to handle the fully populated constraint in
450  // ExtractNewConstraints() right before the solve.
451  InvalidateModelSynchronization();
452 }
453 
454 void CplexInterface::AddVariable(MPVariable* const ct) {
455  // This is currently only invoked when a new variable is created,
456  // see MPSolver::MakeVar().
457  // At this point the variable does not appear in any constraints or
458  // the objective function. We could invoke CPXXaddcols() to immediately
459  // create the variable here but it is usually much faster to handle the
460  // fully setup variable in ExtractNewVariables() right before the solve.
461  InvalidateModelSynchronization();
462 }
463 
464 void CplexInterface::SetCoefficient(MPConstraint* const constraint,
465  MPVariable const* const variable,
466  double new_value, double) {
467  InvalidateSolutionSynchronization();
468 
469  // Changing a single coefficient in the matrix is potentially pretty
470  // slow since that coefficient has to be found in the sparse matrix
471  // representation. So by default we don't perform this update immediately
472  // but instead mark the low-level modeling object "out of sync".
473  // If we want to support incremental extraction then we MUST perform
474  // the modification immediately or we will lose it.
475 
476  if (!supportIncrementalExtraction && !(slowUpdates & SlowSetCoefficient)) {
477  InvalidateModelSynchronization();
478  } else {
479  int const row = constraint->index();
480  int const col = variable->index();
481  if (constraint_is_extracted(row) && variable_is_extracted(col)) {
482  // If row and column are both extracted then we can directly
483  // update the modeling object
484  DCHECK_LE(row, last_constraint_index_);
485  DCHECK_LE(col, last_variable_index_);
486  CHECK_STATUS(CPXXchgcoef(mEnv, mLp, row, col, new_value));
487  } else {
488  // If either row or column is not yet extracted then we can
489  // defer the update to ExtractModel()
490  InvalidateModelSynchronization();
491  }
492  }
493 }
494 
495 void CplexInterface::ClearConstraint(MPConstraint* const constraint) {
496  CPXDIM const row = constraint->index();
497  if (!constraint_is_extracted(row))
498  // There is nothing to do if the constraint was not even extracted.
499  return;
500 
501  // Clearing a constraint means setting all coefficients in the corresponding
502  // row to 0 (we cannot just delete the row since that would renumber all
503  // the constraints/rows after it).
504  // Modifying coefficients in the matrix is potentially pretty expensive
505  // since they must be found in the sparse matrix representation. That is
506  // why by default we do not modify the coefficients here but only mark
507  // the low-level modeling object "out of sync".
508 
509  if (!(slowUpdates & SlowClearConstraint)) {
510  InvalidateModelSynchronization();
511  } else {
512  InvalidateSolutionSynchronization();
513 
514  CPXDIM const len = constraint->coefficients_.size();
515  unique_ptr<CPXDIM[]> rowind(new CPXDIM[len]);
516  unique_ptr<CPXDIM[]> colind(new CPXDIM[len]);
517  unique_ptr<double[]> val(new double[len]);
518  CPXDIM j = 0;
519  const auto& coeffs = constraint->coefficients_;
520  for (auto it(coeffs.begin()); it != coeffs.end(); ++it) {
521  CPXDIM const col = it->first->index();
522  if (variable_is_extracted(col)) {
523  rowind[j] = row;
524  colind[j] = col;
525  val[j] = 0.0;
526  ++j;
527  }
528  }
529  if (j)
530  CHECK_STATUS(
531  CPXXchgcoeflist(mEnv, mLp, j, rowind.get(), colind.get(), val.get()));
532  }
533 }
534 
535 void CplexInterface::SetObjectiveCoefficient(MPVariable const* const variable,
536  double coefficient) {
537  CPXDIM const col = variable->index();
538  if (!variable_is_extracted(col))
539  // Nothing to do if variable was not even extracted
540  return;
541 
542  InvalidateSolutionSynchronization();
543 
544  // The objective function is stored as a dense vector, so updating a
545  // single coefficient is O(1). So by default we update the low-level
546  // modeling object here.
547  // If we support incremental extraction then we have no choice but to
548  // perform the update immediately.
549 
550  if (supportIncrementalExtraction ||
551  (slowUpdates & SlowSetObjectiveCoefficient)) {
552  CHECK_STATUS(CPXXchgobj(mEnv, mLp, 1, &col, &coefficient));
553  } else
554  InvalidateModelSynchronization();
555 }
556 
557 void CplexInterface::SetObjectiveOffset(double value) {
558  // Changing the objective offset is O(1), so we always do it immediately.
559  InvalidateSolutionSynchronization();
560  CHECK_STATUS(CPXEsetobjoffset(mEnv, mLp, value));
561 }
562 
563 void CplexInterface::ClearObjective() {
564  InvalidateSolutionSynchronization();
565 
566  // Since the objective function is stored as a dense vector updating
567  // it is O(n), so we usually perform the update immediately.
568  // If we want to support incremental extraction then we have no choice
569  // but to perform the update immediately.
570 
571  if (supportIncrementalExtraction || (slowUpdates & SlowClearObjective)) {
572  CPXDIM const cols = CPXXgetnumcols(mEnv, mLp);
573  unique_ptr<CPXDIM[]> ind(new CPXDIM[cols]);
574  unique_ptr<double[]> zero(new double[cols]);
575  CPXDIM j = 0;
576  const auto& coeffs = solver_->objective_->coefficients_;
577  for (auto it(coeffs.begin()); it != coeffs.end(); ++it) {
578  CPXDIM const idx = it->first->index();
579  // We only need to reset variables that have been extracted.
580  if (variable_is_extracted(idx)) {
581  DCHECK_LT(idx, cols);
582  ind[j] = idx;
583  zero[j] = 0.0;
584  ++j;
585  }
586  }
587  if (j > 0) CHECK_STATUS(CPXXchgobj(mEnv, mLp, j, ind.get(), zero.get()));
588  CHECK_STATUS(CPXEsetobjoffset(mEnv, mLp, 0.0));
589  } else
590  InvalidateModelSynchronization();
591 }
592 
593 // ------ Query statistics on the solution and the solve ------
594 
595 int64 CplexInterface::iterations() const {
596  int iter;
597  if (!CheckSolutionIsSynchronized()) return kUnknownNumberOfIterations;
598  if (mMip)
599  return static_cast<int64>(CPXXgetmipitcnt(mEnv, mLp));
600  else
601  return static_cast<int64>(CPXXgetitcnt(mEnv, mLp));
602 }
603 
604 int64 CplexInterface::nodes() const {
605  if (mMip) {
606  if (!CheckSolutionIsSynchronized()) return kUnknownNumberOfNodes;
607  return static_cast<int64>(CPXXgetnodecnt(mEnv, mLp));
608  } else {
609  LOG(DFATAL) << "Number of nodes only available for discrete problems";
610  return kUnknownNumberOfNodes;
611  }
612 }
613 
614 // Transform a CPLEX basis status to an MPSolver basis status.
615 MPSolver::BasisStatus CplexInterface::xformBasisStatus(int cplex_basis_status) {
616  switch (cplex_basis_status) {
617  case CPX_AT_LOWER:
618  return MPSolver::AT_LOWER_BOUND;
619  case CPX_BASIC:
620  return MPSolver::BASIC;
621  case CPX_AT_UPPER:
622  return MPSolver::AT_UPPER_BOUND;
623  case CPX_FREE_SUPER:
624  return MPSolver::FREE;
625  default:
626  LOG(DFATAL) << "Unknown CPLEX basis status";
627  return MPSolver::FREE;
628  }
629 }
630 
631 // Returns the basis status of a row.
632 MPSolver::BasisStatus CplexInterface::row_status(int constraint_index) const {
633  if (mMip) {
634  LOG(FATAL) << "Basis status only available for continuous problems";
635  return MPSolver::FREE;
636  }
637 
638  if (CheckSolutionIsSynchronized()) {
639  if (!mRstat) {
640  CPXDIM const rows = CPXXgetnumrows(mEnv, mLp);
641  unique_ptr<int[]> data(new int[rows]);
642  mRstat.swap(data);
643  CHECK_STATUS(CPXXgetbase(mEnv, mLp, 0, mRstat.get()));
644  }
645  } else
646  mRstat = 0;
647 
648  if (mRstat)
649  return xformBasisStatus(mRstat[constraint_index]);
650  else {
651  LOG(FATAL) << "Row basis status not available";
652  return MPSolver::FREE;
653  }
654 }
655 
656 // Returns the basis status of a column.
657 MPSolver::BasisStatus CplexInterface::column_status(int variable_index) const {
658  if (mMip) {
659  LOG(FATAL) << "Basis status only available for continuous problems";
660  return MPSolver::FREE;
661  }
662 
663  if (CheckSolutionIsSynchronized()) {
664  if (!mCstat) {
665  CPXDIM const cols = CPXXgetnumcols(mEnv, mLp);
666  unique_ptr<int[]> data(new int[cols]);
667  mCstat.swap(data);
668  CHECK_STATUS(CPXXgetbase(mEnv, mLp, mCstat.get(), 0));
669  }
670  } else
671  mCstat = 0;
672 
673  if (mCstat)
674  return xformBasisStatus(mCstat[variable_index]);
675  else {
676  LOG(FATAL) << "Column basis status not available";
677  return MPSolver::FREE;
678  }
679 }
680 
681 // Extract all variables that have not yet been extracted.
682 void CplexInterface::ExtractNewVariables() {
683  // NOTE: The code assumes that a linear expression can never contain
684  // non-zero duplicates.
685 
686  InvalidateSolutionSynchronization();
687 
688  if (!supportIncrementalExtraction) {
689  // Without incremental extraction ExtractModel() is always called
690  // to extract the full model.
691  CHECK(last_variable_index_ == 0 ||
692  last_variable_index_ == solver_->variables_.size());
693  CHECK(last_constraint_index_ == 0 ||
694  last_constraint_index_ == solver_->constraints_.size());
695  }
696 
697  int const last_extracted = last_variable_index_;
698  int const var_count = solver_->variables_.size();
699  CPXDIM newcols = var_count - last_extracted;
700  if (newcols > 0) {
701  // There are non-extracted variables. Extract them now.
702 
703  unique_ptr<double[]> obj(new double[newcols]);
704  unique_ptr<double[]> lb(new double[newcols]);
705  unique_ptr<double[]> ub(new double[newcols]);
706  unique_ptr<char[]> ctype(new char[newcols]);
707  unique_ptr<const char*[]> colname(new const char*[newcols]);
708 
709  bool have_names = false;
710  for (int j = 0, varidx = last_extracted; j < newcols; ++j, ++varidx) {
711  MPVariable const* const var = solver_->variables_[varidx];
712  lb[j] = var->lb();
713  ub[j] = var->ub();
714  ctype[j] = var->integer() ? CPX_INTEGER : CPX_CONTINUOUS;
715  colname[j] = var->name().empty() ? 0 : var->name().c_str();
716  have_names = have_names || var->name().empty();
717  obj[j] = solver_->objective_->GetCoefficient(var);
718  }
719 
720  // Arrays for modifying the problem are setup. Update the index
721  // of variables that will get extracted now. Updating indices
722  // _before_ the actual extraction makes things much simpler in
723  // case we support incremental extraction.
724  // In case of error we just reset the indeces.
725  std::vector<MPVariable*> const& variables = solver_->variables();
726  for (int j = last_extracted; j < var_count; ++j) {
727  CHECK(!variable_is_extracted(variables[j]->index()));
728  set_variable_as_extracted(variables[j]->index(), true);
729  }
730 
731  try {
732  bool use_newcols = true;
733 
734  if (supportIncrementalExtraction) {
735  // If we support incremental extraction then we must
736  // update existing constraints with the new variables.
737  // To do that we use CPXXaddcols() to actually create the
738  // variables. This is supposed to be faster than combining
739  // CPXXnewcols() and CPXXchgcoeflist().
740 
741  // For each column count the size of the intersection with
742  // existing constraints.
743  unique_ptr<CPXDIM[]> collen(new CPXDIM[newcols]);
744  for (CPXDIM j = 0; j < newcols; ++j) collen[j] = 0;
745  CPXNNZ nonzeros = 0;
746  // TODO: Use a bitarray to flag the constraints that actually
747  // intersect new variables?
748  for (int i = 0; i < last_constraint_index_; ++i) {
749  MPConstraint const* const ct = solver_->constraints_[i];
750  CHECK(constraint_is_extracted(ct->index()));
751  const auto& coeffs = ct->coefficients_;
752  for (auto it(coeffs.begin()); it != coeffs.end(); ++it) {
753  int const idx = it->first->index();
754  if (variable_is_extracted(idx) && idx > last_variable_index_) {
755  collen[idx - last_variable_index_]++;
756  ++nonzeros;
757  }
758  }
759  }
760 
761  if (nonzeros > 0) {
762  // At least one of the new variables did intersect with an
763  // old constraint. We have to create the new columns via
764  // CPXXaddcols().
765  use_newcols = false;
766  unique_ptr<CPXNNZ[]> begin(new CPXNNZ[newcols + 2]);
767  unique_ptr<CPXDIM[]> cmatind(new CPXDIM[nonzeros]);
768  unique_ptr<double[]> cmatval(new double[nonzeros]);
769 
770  // Here is how cmatbeg[] is setup:
771  // - it is initialized as
772  // [ 0, 0, collen[0], collen[0]+collen[1], ... ]
773  // so that cmatbeg[j+1] tells us where in cmatind[] and
774  // cmatval[] we need to put the next nonzero for column
775  // j
776  // - after nonzeros have been setup the array looks like
777  // [ 0, collen[0], collen[0]+collen[1], ... ]
778  // so that it is the correct input argument for CPXXaddcols
779  CPXNNZ* cmatbeg = begin.get();
780  cmatbeg[0] = 0;
781  cmatbeg[1] = 0;
782  ++cmatbeg;
783  for (CPXDIM j = 0; j < newcols; ++j)
784  cmatbeg[j + 1] = cmatbeg[j] + collen[j];
785 
786  for (int i = 0; i < last_constraint_index_; ++i) {
787  MPConstraint const* const ct = solver_->constraints_[i];
788  CPXDIM const row = ct->index();
789  const auto& coeffs = ct->coefficients_;
790  for (auto it(coeffs.begin()); it != coeffs.end(); ++it) {
791  int const idx = it->first->index();
792  if (variable_is_extracted(idx) && idx > last_variable_index_) {
793  CPXNNZ const nz = cmatbeg[idx]++;
794  cmatind[nz] = idx;
795  cmatval[nz] = it->second;
796  }
797  }
798  }
799  --cmatbeg;
800  CHECK_STATUS(CPXXaddcols(mEnv, mLp, newcols, nonzeros, obj.get(),
801  cmatbeg, cmatind.get(), cmatval.get(),
802  lb.get(), ub.get(),
803  have_names ? colname.get() : 0));
804  }
805  }
806  if (use_newcols) {
807  // Either incremental extraction is not supported or none of
808  // the new variables did intersect an existing constraint.
809  // We can just use CPXXnewcols() to create the new variables.
810  CHECK_STATUS(CPXXnewcols(mEnv, mLp, newcols, obj.get(), lb.get(),
811  ub.get(), mMip ? ctype.get() : 0,
812  have_names ? colname.get() : 0));
813  } else {
814  // Incremental extraction: we must update the ctype of the
815  // newly created variables (CPXXaddcols() does not allow
816  // specifying the ctype)
817  if (mMip) {
818  // Query the actual number of columns in case we did not
819  // manage to extract all columns.
820  int const cols = CPXXgetnumcols(mEnv, mLp);
821  unique_ptr<CPXDIM[]> ind(new CPXDIM[newcols]);
822  for (int j = last_extracted; j < cols; ++j)
823  ind[j - last_extracted] = j;
824  CHECK_STATUS(CPXXchgctype(mEnv, mLp, cols - last_extracted, ind.get(),
825  ctype.get()));
826  }
827  }
828  } catch (...) {
829  // Undo all changes in case of error.
830  CPXDIM const cols = CPXXgetnumcols(mEnv, mLp);
831  if (cols > last_extracted)
832  (void)CPXXdelcols(mEnv, mLp, last_extracted, cols - 1);
833  std::vector<MPVariable*> const& variables = solver_->variables();
834  int const size = variables.size();
835  for (int j = last_extracted; j < size; ++j)
836  set_variable_as_extracted(j, false);
837  throw;
838  }
839  }
840 }
841 
842 // Extract constraints that have not yet been extracted.
843 void CplexInterface::ExtractNewConstraints() {
844  // NOTE: The code assumes that a linear expression can never contain
845  // non-zero duplicates.
846 
847  if (!supportIncrementalExtraction) {
848  // Without incremental extraction ExtractModel() is always called
849  // to extract the full model.
850  CHECK(last_variable_index_ == 0 ||
851  last_variable_index_ == solver_->variables_.size());
852  CHECK(last_constraint_index_ == 0 ||
853  last_constraint_index_ == solver_->constraints_.size());
854  }
855 
856  CPXDIM const offset = last_constraint_index_;
857  CPXDIM const total = solver_->constraints_.size();
858 
859  if (total > offset) {
860  // There are constraints that are not yet extracted.
861 
862  InvalidateSolutionSynchronization();
863 
864  CPXDIM newCons = total - offset;
865  CPXDIM const cols = CPXXgetnumcols(mEnv, mLp);
866  DCHECK_EQ(last_variable_index_, cols);
867  CPXDIM const chunk = 10; // max number of rows to add in one shot
868 
869  // Update indices of new constraints _before_ actually extracting
870  // them. In case of error we will just reset the indices.
871  for (CPXDIM c = offset; c < total; ++c)
872  set_constraint_as_extracted(c, true);
873 
874  try {
875  unique_ptr<CPXDIM[]> rmatind(new CPXDIM[cols]);
876  unique_ptr<double[]> rmatval(new double[cols]);
877  unique_ptr<CPXNNZ[]> rmatbeg(new CPXNNZ[chunk]);
878  unique_ptr<char[]> sense(new char[chunk]);
879  unique_ptr<double[]> rhs(new double[chunk]);
880  unique_ptr<char const*[]> name(new char const*[chunk]);
881  unique_ptr<double[]> rngval(new double[chunk]);
882  unique_ptr<CPXDIM[]> rngind(new CPXDIM[chunk]);
883  bool haveRanges = false;
884 
885  // Loop over the new constraints, collecting rows for up to
886  // CHUNK constraints into the arrays so that adding constraints
887  // is faster.
888  for (CPXDIM c = 0; c < newCons; /* nothing */) {
889  // Collect up to CHUNK constraints into the arrays.
890  CPXDIM nextRow = 0;
891  CPXNNZ nextNz = 0;
892  for (/* nothing */; c < newCons && nextRow < chunk; ++c, ++nextRow) {
893  MPConstraint const* const ct = solver_->constraints_[offset + c];
894 
895  // Stop if there is not enough room in the arrays
896  // to add the current constraint.
897  if (nextNz + ct->coefficients_.size() > cols) {
898  DCHECK_GT(nextRow, 0);
899  break;
900  }
901 
902  // Setup right-hand side of constraint.
903  MakeRhs(ct->lb(), ct->ub(), rhs[nextRow], sense[nextRow],
904  rngval[nextRow]);
905  haveRanges = haveRanges || (rngval[nextRow] != 0.0);
906  rngind[nextRow] = offset + c;
907 
908  // Setup left-hand side of constraint.
909  rmatbeg[nextRow] = nextNz;
910  const auto& coeffs = ct->coefficients_;
911  for (auto it(coeffs.begin()); it != coeffs.end(); ++it) {
912  CPXDIM const idx = it->first->index();
913  if (variable_is_extracted(idx)) {
914  DCHECK_LT(nextNz, cols);
915  DCHECK_LT(idx, cols);
916  rmatind[nextNz] = idx;
917  rmatval[nextNz] = it->second;
918  ++nextNz;
919  }
920  }
921 
922  // Finally the name of the constraint.
923  name[nextRow] = ct->name().empty() ? 0 : ct->name().c_str();
924  }
925  if (nextRow > 0) {
926  CHECK_STATUS(CPXXaddrows(mEnv, mLp, 0, nextRow, nextNz, rhs.get(),
927  sense.get(), rmatbeg.get(), rmatind.get(),
928  rmatval.get(), 0, name.get()));
929  if (haveRanges) {
930  CHECK_STATUS(
931  CPXXchgrngval(mEnv, mLp, nextRow, rngind.get(), rngval.get()));
932  }
933  }
934  }
935  } catch (...) {
936  // Undo all changes in case of error.
937  CPXDIM const rows = CPXXgetnumrows(mEnv, mLp);
938  if (rows > offset) (void)CPXXdelrows(mEnv, mLp, offset, rows - 1);
939  std::vector<MPConstraint*> const& constraints = solver_->constraints();
940  int const size = constraints.size();
941  for (int i = offset; i < size; ++i) set_constraint_as_extracted(i, false);
942  throw;
943  }
944  }
945 }
946 
947 // Extract the objective function.
948 void CplexInterface::ExtractObjective() {
949  // NOTE: The code assumes that the objective expression does not contain
950  // any non-zero duplicates.
951 
952  CPXDIM const cols = CPXXgetnumcols(mEnv, mLp);
953  DCHECK_EQ(last_variable_index_, cols);
954 
955  unique_ptr<CPXDIM[]> ind(new CPXDIM[cols]);
956  unique_ptr<double[]> val(new double[cols]);
957  for (CPXDIM j = 0; j < cols; ++j) {
958  ind[j] = j;
959  val[j] = 0.0;
960  }
961 
962  const auto& coeffs = solver_->objective_->coefficients_;
963  for (auto it = coeffs.begin(); it != coeffs.end(); ++it) {
964  CPXDIM const idx = it->first->index();
965  if (variable_is_extracted(idx)) {
966  DCHECK_LT(idx, cols);
967  val[idx] = it->second;
968  }
969  }
970 
971  CHECK_STATUS(CPXXchgobj(mEnv, mLp, cols, ind.get(), val.get()));
972  CHECK_STATUS(CPXEsetobjoffset(mEnv, mLp, solver_->Objective().offset()));
973 }
974 
975 // ------ Parameters -----
976 
977 void CplexInterface::SetParameters(const MPSolverParameters& param) {
978  SetCommonParameters(param);
979  if (mMip) SetMIPParameters(param);
980 }
981 
982 void CplexInterface::SetRelativeMipGap(double value) {
983  if (mMip) {
984  CHECK_STATUS(CPXXsetdblparam(mEnv, CPX_PARAM_EPGAP, value));
985  } else {
986  LOG(WARNING) << "The relative MIP gap is only available "
987  << "for discrete problems.";
988  }
989 }
990 
991 void CplexInterface::SetPrimalTolerance(double value) {
992  CHECK_STATUS(CPXXsetdblparam(mEnv, CPX_PARAM_EPRHS, value));
993 }
994 
995 void CplexInterface::SetDualTolerance(double value) {
996  CHECK_STATUS(CPXXsetdblparam(mEnv, CPX_PARAM_EPOPT, value));
997 }
998 
999 void CplexInterface::SetPresolveMode(int value) {
1000  MPSolverParameters::PresolveValues const presolve =
1001  static_cast<MPSolverParameters::PresolveValues>(value);
1002 
1003  switch (presolve) {
1004  case MPSolverParameters::PRESOLVE_OFF:
1005  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_PREIND, CPX_OFF));
1006  return;
1007  case MPSolverParameters::PRESOLVE_ON:
1008  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_PREIND, CPX_ON));
1009  return;
1010  }
1011  SetIntegerParamToUnsupportedValue(MPSolverParameters::PRESOLVE, value);
1012 }
1013 
1014 // Sets the scaling mode.
1015 void CplexInterface::SetScalingMode(int value) {
1016  MPSolverParameters::ScalingValues const scaling =
1017  static_cast<MPSolverParameters::ScalingValues>(value);
1018 
1019  switch (scaling) {
1020  case MPSolverParameters::SCALING_OFF:
1021  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_SCAIND, -1));
1022  break;
1023  case MPSolverParameters::SCALING_ON:
1024  // TODO: 0 is equilibrium scaling (the default), CPLEX also supports
1025  // 1 aggressive scaling
1026  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_SCAIND, 0));
1027  break;
1028  }
1029 }
1030 
1031 // Sets the LP algorithm : primal, dual or barrier. Note that CPLEX offers other
1032 // LP algorithm (e.g. network) and automatic selection
1033 void CplexInterface::SetLpAlgorithm(int value) {
1034  MPSolverParameters::LpAlgorithmValues const algorithm =
1035  static_cast<MPSolverParameters::LpAlgorithmValues>(value);
1036 
1037  int alg = CPX_ALG_NONE;
1038 
1039  switch (algorithm) {
1040  case MPSolverParameters::DUAL:
1041  alg = CPX_ALG_DUAL;
1042  break;
1043  case MPSolverParameters::PRIMAL:
1044  alg = CPX_ALG_PRIMAL;
1045  break;
1046  case MPSolverParameters::BARRIER:
1047  alg = CPX_ALG_BARRIER;
1048  break;
1049  }
1050 
1051  if (alg == CPX_ALG_NONE)
1052  SetIntegerParamToUnsupportedValue(MPSolverParameters::LP_ALGORITHM, value);
1053  else {
1054  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_LPMETHOD, alg));
1055  if (mMip) {
1056  // For MIP we have to change two more parameters to specify the
1057  // algorithm that is used to solve LP relaxations.
1058  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_STARTALG, alg));
1059  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_SUBALG, alg));
1060  }
1061  }
1062 }
1063 
1064 bool CplexInterface::ReadParameterFile(std::string const& filename) {
1065  // Return true on success and false on error.
1066  return CPXXreadcopyparam(mEnv, filename.c_str()) == 0;
1067 }
1068 
1069 std::string CplexInterface::ValidFileExtensionForParameterFile() const {
1070  return ".prm";
1071 }
1072 
1073 MPSolver::ResultStatus CplexInterface::Solve(MPSolverParameters const& param) {
1074  int status;
1075 
1076  // Delete chached information
1077  mCstat = 0;
1078  mRstat = 0;
1079 
1080  WallTimer timer;
1081  timer.Start();
1082 
1083  // Set incrementality
1084  MPSolverParameters::IncrementalityValues const inc =
1085  static_cast<MPSolverParameters::IncrementalityValues>(
1086  param.GetIntegerParam(MPSolverParameters::INCREMENTALITY));
1087  switch (inc) {
1088  case MPSolverParameters::INCREMENTALITY_OFF:
1089  Reset(); /* This should not be required but re-extracting everything
1090  * may be faster, so we do it. */
1091  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_ADVIND, 0));
1092  break;
1093  case MPSolverParameters::INCREMENTALITY_ON:
1094  CHECK_STATUS(CPXXsetintparam(mEnv, CPX_PARAM_ADVIND, 2));
1095  break;
1096  }
1097 
1098  // Extract the model to be solved.
1099  // If we don't support incremental extraction and the low-level modeling
1100  // is out of sync then we have to re-extract everything. Note that this
1101  // will lose MIP starts or advanced basis information from a previous
1102  // solve.
1103  if (!supportIncrementalExtraction && sync_status_ == MUST_RELOAD) Reset();
1104  ExtractModel();
1105  VLOG(1) << absl::StrFormat("Model build in %.3f seconds.", timer.Get());
1106 
1107  // Set log level.
1108  CHECK_STATUS(
1109  CPXXsetintparam(mEnv, CPX_PARAM_SCRIND, quiet() ? CPX_OFF : CPX_ON));
1110 
1111  // Set parameters.
1112  // NOTE: We must invoke SetSolverSpecificParametersAsString() _first_.
1113  // Its current implementation invokes ReadParameterFile() which in
1114  // turn invokes CPXXreadcopyparam(). The latter will _overwrite_
1115  // all current parameter settings in the environment.
1116  solver_->SetSolverSpecificParametersAsString(
1117  solver_->solver_specific_parameter_string_);
1118  SetParameters(param);
1119  if (solver_->time_limit()) {
1120  VLOG(1) << "Setting time limit = " << solver_->time_limit() << " ms.";
1121  CHECK_STATUS(
1122  CPXXsetdblparam(mEnv, CPX_PARAM_TILIM, solver_->time_limit() * 1e-3));
1123  }
1124 
1125  // Solve.
1126  // Do not CHECK_STATUS here since some errors (for example CPXERR_NO_MEMORY)
1127  // still allow us to query useful information.
1128  timer.Restart();
1129  if (mMip) {
1130  status = CPXXmipopt(mEnv, mLp);
1131  } else {
1132  status = CPXXlpopt(mEnv, mLp);
1133  }
1134 
1135  // Disable screen output right after solve
1136  (void)CPXXsetintparam(mEnv, CPX_PARAM_SCRIND, CPX_OFF);
1137 
1138  if (status) {
1139  VLOG(1) << absl::StrFormat("Failed to optimize MIP. Error %d", status);
1140  // NOTE: We do not return immediately since there may be information
1141  // to grab (for example an incumbent)
1142  } else {
1143  VLOG(1) << absl::StrFormat("Solved in %.3f seconds.", timer.Get());
1144  }
1145 
1146  int const cpxstat = CPXXgetstat(mEnv, mLp);
1147  VLOG(1) << absl::StrFormat("CPLEX solution status %d.", cpxstat);
1148 
1149  // Figure out what solution we have.
1150  int solnmethod, solntype, pfeas, dfeas;
1151  CHECK_STATUS(CPXXsolninfo(mEnv, mLp, &solnmethod, &solntype, &pfeas, &dfeas));
1152  bool const feasible = pfeas != 0;
1153 
1154  // Get problem dimensions for solution queries below.
1155  CPXDIM const rows = CPXXgetnumrows(mEnv, mLp);
1156  CPXDIM const cols = CPXXgetnumcols(mEnv, mLp);
1157  DCHECK_EQ(rows, solver_->constraints_.size());
1158  DCHECK_EQ(cols, solver_->variables_.size());
1159 
1160  // Capture objective function value.
1161  objective_value_ = CPX_NAN;
1162  best_objective_bound_ = CPX_NAN;
1163  if (feasible) {
1164  CHECK_STATUS(CPXXgetobjval(mEnv, mLp, &objective_value_));
1165  if (mMip) {
1166  CHECK_STATUS(CPXXgetbestobjval(mEnv, mLp, &best_objective_bound_));
1167  }
1168  }
1169  VLOG(1) << "objective=" << objective_value_
1170  << ", bound=" << best_objective_bound_;
1171 
1172  // Capture primal and dual solutions
1173  if (mMip) {
1174  // If there is a primal feasible solution then capture it.
1175  if (feasible) {
1176  if (cols > 0) {
1177  unique_ptr<double[]> x(new double[cols]);
1178  CHECK_STATUS(CPXXgetx(mEnv, mLp, x.get(), 0, cols - 1));
1179  for (int i = 0; i < solver_->variables_.size(); ++i) {
1180  MPVariable* const var = solver_->variables_[i];
1181  var->set_solution_value(x[i]);
1182  VLOG(3) << var->name() << ": value =" << x[i];
1183  }
1184  }
1185  } else {
1186  for (int i = 0; i < solver_->variables_.size(); ++i)
1187  solver_->variables_[i]->set_solution_value(CPX_NAN);
1188  }
1189 
1190  // MIP does not have duals
1191  for (int i = 0; i < solver_->variables_.size(); ++i)
1192  solver_->variables_[i]->set_reduced_cost(CPX_NAN);
1193  for (int i = 0; i < solver_->constraints_.size(); ++i)
1194  solver_->constraints_[i]->set_dual_value(CPX_NAN);
1195  } else {
1196  // Continuous problem.
1197  if (cols > 0) {
1198  unique_ptr<double[]> x(new double[cols]);
1199  unique_ptr<double[]> dj(new double[cols]);
1200  if (feasible) CHECK_STATUS(CPXXgetx(mEnv, mLp, x.get(), 0, cols - 1));
1201  if (dfeas) CHECK_STATUS(CPXXgetdj(mEnv, mLp, dj.get(), 0, cols - 1));
1202  for (int i = 0; i < solver_->variables_.size(); ++i) {
1203  MPVariable* const var = solver_->variables_[i];
1204  var->set_solution_value(x[i]);
1205  bool value = false, dual = false;
1206 
1207  if (feasible) {
1208  var->set_solution_value(x[i]);
1209  value = true;
1210  } else
1211  var->set_solution_value(CPX_NAN);
1212  if (dfeas) {
1213  var->set_reduced_cost(dj[i]);
1214  dual = true;
1215  } else
1216  var->set_reduced_cost(CPX_NAN);
1217  VLOG(3) << var->name() << ":"
1218  << (value ? absl::StrFormat(" value = %f", x[i]) : "")
1219  << (dual ? absl::StrFormat(" reduced cost = %f", dj[i]) : "");
1220  }
1221  }
1222 
1223  if (rows > 0) {
1224  unique_ptr<double[]> pi(new double[rows]);
1225  if (dfeas) CHECK_STATUS(CPXXgetpi(mEnv, mLp, pi.get(), 0, rows - 1));
1226  for (int i = 0; i < solver_->constraints_.size(); ++i) {
1227  MPConstraint* const ct = solver_->constraints_[i];
1228  bool dual = false;
1229  if (dfeas) {
1230  ct->set_dual_value(pi[i]);
1231  dual = true;
1232  } else
1233  ct->set_dual_value(CPX_NAN);
1234  VLOG(4) << "row " << ct->index() << ":"
1235  << (dual ? absl::StrFormat(" dual = %f", pi[i]) : "");
1236  }
1237  }
1238  }
1239 
1240  // Map CPLEX status to more generic solution status in MPSolver
1241  switch (cpxstat) {
1242  case CPX_STAT_OPTIMAL:
1243  case CPXMIP_OPTIMAL:
1244  result_status_ = MPSolver::OPTIMAL;
1245  break;
1246  case CPXMIP_OPTIMAL_TOL:
1247  // To be consistent with the other solvers.
1248  result_status_ = MPSolver::OPTIMAL;
1249  break;
1250  case CPX_STAT_INFEASIBLE:
1251  case CPXMIP_INFEASIBLE:
1252  result_status_ = MPSolver::INFEASIBLE;
1253  break;
1254  case CPX_STAT_UNBOUNDED:
1255  case CPXMIP_UNBOUNDED:
1256  result_status_ = MPSolver::UNBOUNDED;
1257  break;
1258  case CPX_STAT_INForUNBD:
1259  case CPXMIP_INForUNBD:
1260  result_status_ = MPSolver::INFEASIBLE;
1261  break;
1262  default:
1263  result_status_ = feasible ? MPSolver::FEASIBLE : MPSolver::ABNORMAL;
1264  break;
1265  }
1266 
1267  sync_status_ = SOLUTION_SYNCHRONIZED;
1268  return result_status_;
1269 }
1270 
1271 MPSolverInterface* BuildCplexInterface(bool mip, MPSolver* const solver) {
1272  return new CplexInterface(solver, mip);
1273 }
1274 
1275 } // namespace operations_research
1276 #endif // #if defined(USE_CPLEX)
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
void Start()
Definition: timer.h:31
void Restart()
Definition: timer.h:35
double Get() const
Definition: timer.h:45
ResultStatus
The status of solving the problem.
BasisStatus
Advanced usage: possible basis status values for a variable and the slack variable of a linear constr...
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
const int WARNING
Definition: log_severity.h:31
const int FATAL
Definition: log_severity.h:32
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
Definition: cleanup.h:22
CpSolverResponse Solve(const CpModelProto &model_proto)
Solves the given CpModelProto and returns an instance of CpSolverResponse.
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508
int64 coefficient
const bool maximize_
Definition: search.cc:2499