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"
22#include "ortools/base/timer.h"
24
25#if defined(USE_CPLEX)
26
27extern "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.
32CPXLIBAPI 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
50namespace operations_research {
51
52using 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.
59class 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.
214CplexInterface::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
239CplexInterface::~CplexInterface() {
240 CHECK_STATUS(CPXXfreeprob(mEnv, &mLp));
241 CHECK_STATUS(CPXXcloseCPLEX(&mEnv));
242}
243
244std::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
264void 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
283void CplexInterface::SetOptimizationDirection(bool maximize) {
284 InvalidateSolutionSynchronization();
285 CPXXchgobjsen(mEnv, mLp, maximize ? CPX_MAX : CPX_MIN);
286}
287
288void 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.
317void 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.
352void 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
413void 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
444void 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
454void 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
464void 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
495void 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
535void 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
557void 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
563void 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
595int64 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
604int64 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.
615MPSolver::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.
632MPSolver::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.
657MPSolver::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.
682void 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.
843void 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.
948void 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
977void CplexInterface::SetParameters(const MPSolverParameters& param) {
978 SetCommonParameters(param);
979 if (mMip) SetMIPParameters(param);
980}
981
982void 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
991void CplexInterface::SetPrimalTolerance(double value) {
992 CHECK_STATUS(CPXXsetdblparam(mEnv, CPX_PARAM_EPRHS, value));
993}
994
995void CplexInterface::SetDualTolerance(double value) {
996 CHECK_STATUS(CPXXsetdblparam(mEnv, CPX_PARAM_EPOPT, value));
997}
998
999void 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.
1015void 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
1033void 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
1064bool 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
1069std::string CplexInterface::ValidFileExtensionForParameterFile() const {
1070 return ".prm";
1071}
1072
1073MPSolver::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
1271MPSolverInterface* 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