Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
Public Member Functions | |
XpressInterface (MPSolver *solver, bool mip) | |
Creates an LP/MIP instance. | |
~XpressInterface () override | |
void | SetOptimizationDirection (bool maximize) override |
Sets the optimization direction (min/max). | |
MPSolver::ResultStatus | Solve (MPSolverParameters const ¶m) override |
void | Write (const std::string &filename) override |
Writes the model. | |
void | Reset () override |
---— Model modifications and extraction --— | |
void | SetVariableBounds (int var_index, double lb, double ub) override |
Modifies bounds of an extracted variable. | |
void | SetVariableInteger (int var_index, bool integer) override |
Modifies integrality of an extracted variable. | |
void | SetConstraintBounds (int row_index, double lb, double ub) override |
Modify bounds of an extracted variable. | |
void | AddRowConstraint (MPConstraint *ct) override |
Adds a linear constraint. | |
void | AddVariable (MPVariable *var) override |
Add a variable. | |
void | SetCoefficient (MPConstraint *constraint, MPVariable const *variable, double new_value, double old_value) override |
Changes a coefficient in a constraint. | |
void | ClearConstraint (MPConstraint *constraint) override |
Clear a constraint from all its terms. | |
void | SetObjectiveCoefficient (MPVariable const *variable, double coefficient) override |
Change a coefficient in the linear objective. | |
void | SetObjectiveOffset (double value) override |
Change the constant term in the linear objective. | |
void | ClearObjective () override |
Clear the objective from all its terms. | |
virtual int64_t | iterations () const |
---— Query statistics on the solution and the solve ---— | |
virtual int64_t | nodes () const |
Number of branch-and-bound nodes. Only available for discrete problems. | |
MPSolver::BasisStatus | row_status (int constraint_index) const override |
Returns the basis status of a row. | |
MPSolver::BasisStatus | column_status (int variable_index) const override |
Returns the basis status of a column. | |
bool | IsContinuous () const override |
--— Misc --— | |
bool | IsLP () const override |
Returns true if the problem is continuous and linear. | |
bool | IsMIP () const override |
Returns true if the problem is discrete and linear. | |
void | SetStartingLpBasis (const std::vector< MPSolver::BasisStatus > &variable_statuses, const std::vector< MPSolver::BasisStatus > &constraint_statuses) override |
See MPSolver::SetStartingLpBasis(). | |
void | ExtractNewVariables () override |
Extract all variables that have not yet been extracted. | |
void | ExtractNewConstraints () override |
Extract constraints that have not yet been extracted. | |
void | ExtractObjective () override |
Extract the objective function. | |
std::string | SolverVersion () const override |
Returns a string describing the underlying solver and its version. | |
void * | underlying_solver () override |
Returns the underlying solver. | |
double | ComputeExactConditionNumber () const override |
void | SetCallback (MPCallback *mp_callback) override |
See MPSolver::SetCallback() for details. | |
bool | SupportsCallbacks () const override |
bool | InterruptSolve () override |
Public Member Functions inherited from operations_research::MPSolverInterface | |
MPSolverInterface (MPSolver *solver) | |
virtual | ~MPSolverInterface () |
virtual bool | SupportsDirectlySolveProto (std::atomic< bool > *) const |
virtual MPSolutionResponse | DirectlySolveProto (LazyMutableCopy< MPModelRequest >, std::atomic< bool > *) |
virtual bool | AddIndicatorConstraint (MPConstraint *const) |
virtual void | BranchingPriorityChangedForVariable (int) |
double | best_objective_bound () const |
double | objective_value () const |
Returns the objective value of the best solution found so far. | |
bool | CheckSolutionIsSynchronized () const |
virtual bool | CheckSolutionExists () const |
bool | CheckSolutionIsSynchronizedAndExists () const |
Handy shortcut to do both checks above (it is often used). | |
int | last_variable_index () const |
Returns the index of the last variable extracted. | |
bool | variable_is_extracted (int var_index) const |
void | set_variable_as_extracted (int var_index, bool extracted) |
bool | constraint_is_extracted (int ct_index) const |
void | set_constraint_as_extracted (int ct_index, bool extracted) |
bool | quiet () const |
Returns the boolean indicating the verbosity of the solver output. | |
void | set_quiet (bool quiet_value) |
Sets the boolean indicating the verbosity of the solver output. | |
MPSolver::ResultStatus | result_status () const |
Returns the result status of the last solve. | |
virtual double | infinity () |
virtual bool | NextSolution () |
See MPSolver::NextSolution() for contract. | |
Protected Member Functions | |
void | SetParameters (MPSolverParameters const ¶m) override |
Set all parameters in the underlying solver. | |
void | SetRelativeMipGap (double value) override |
Set each parameter in the underlying solver. | |
void | SetPrimalTolerance (double value) override |
void | SetDualTolerance (double value) override |
void | SetPresolveMode (int value) override |
void | SetScalingMode (int value) override |
Sets the scaling mode. | |
void | SetLpAlgorithm (int value) override |
virtual bool | ReadParameterFile (std::string const &filename) |
virtual std::string | ValidFileExtensionForParameterFile () const |
Protected Member Functions inherited from operations_research::MPSolverInterface | |
void | ExtractModel () |
Extracts model stored in MPSolver. | |
void | ResetExtractionInformation () |
Resets the extraction information. | |
void | InvalidateSolutionSynchronization () |
void | SetCommonParameters (const MPSolverParameters ¶m) |
Sets parameters common to LP and MIP in the underlying solver. | |
void | SetMIPParameters (const MPSolverParameters ¶m) |
Sets MIP specific parameters in the underlying solver. | |
void | SetUnsupportedDoubleParam (MPSolverParameters::DoubleParam param) |
Sets an unsupported double parameter. | |
virtual void | SetUnsupportedIntegerParam (MPSolverParameters::IntegerParam param) |
Sets an unsupported integer parameter. | |
void | SetDoubleParamToUnsupportedValue (MPSolverParameters::DoubleParam param, double value) |
Sets a supported double parameter to an unsupported value. | |
virtual void | SetIntegerParamToUnsupportedValue (MPSolverParameters::IntegerParam param, int value) |
Sets a supported integer parameter to an unsupported value. | |
virtual absl::Status | SetNumThreads (int num_threads) |
Sets the number of threads to be used by the solver. | |
Additional Inherited Members | |
Public Types inherited from operations_research::MPSolverInterface | |
enum | SynchronizationStatus { MUST_RELOAD , MODEL_SYNCHRONIZED , SOLUTION_SYNCHRONIZED } |
Static Public Attributes inherited from operations_research::MPSolverInterface | |
static constexpr int64_t | kUnknownNumberOfIterations = -1 |
static constexpr int64_t | kUnknownNumberOfNodes = -1 |
Protected Attributes inherited from operations_research::MPSolverInterface | |
MPSolver *const | solver_ |
SynchronizationStatus | sync_status_ |
Indicates whether the model and the solution are synchronized. | |
MPSolver::ResultStatus | result_status_ |
bool | maximize_ |
Optimization direction. | |
int | last_constraint_index_ |
Index in MPSolver::variables_ of last constraint extracted. | |
int | last_variable_index_ |
Index in MPSolver::constraints_ of last variable extracted. | |
double | objective_value_ |
The value of the objective function. | |
double | best_objective_bound_ |
The value of the best objective bound. Used only for MIP solvers. | |
bool | quiet_ |
Boolean indicator for the verbosity of the solver output. | |
Static Protected Attributes inherited from operations_research::MPSolverInterface | |
static const int | kDummyVariableIndex = 0 |
-------— MPSolverInterface -------— | |
For a model that is extracted to an instance of this class there is a 1:1 correspondence between MPVariable instances and XPRESS columns: the index of an extracted variable is the column index in the XPRESS model. Similar for instances of MPConstraint: the index of the constraint in the model is the row index in the XPRESS model.
Definition at line 304 of file xpress_interface.cc.
|
explicit |
Creates an LP/MIP instance.
Definition at line 838 of file xpress_interface.cc.
|
override |
Definition at line 859 of file xpress_interface.cc.
|
overridevirtual |
Adds a linear constraint.
This is currently only invoked when a new constraint is created, see MPSolver::MakeRowConstraint(). At this point we only have the lower and upper bounds of the constraint. We could immediately call XPRSaddrows() here but it is usually much faster to handle the fully populated constraint in ExtractNewConstraints() right before the solve.
Implements operations_research::MPSolverInterface.
Definition at line 1067 of file xpress_interface.cc.
|
overridevirtual |
Add a variable.
This is currently only invoked when a new variable is created, see MPSolver::MakeVar(). At this point the variable does not appear in any constraints or the objective function. We could invoke XPRSaddcols() to immediately create the variable here, but it is usually much faster to handle the fully set-up variable in ExtractNewVariables() right before the solve.
Implements operations_research::MPSolverInterface.
Definition at line 1081 of file xpress_interface.cc.
|
overridevirtual |
Clear a constraint from all its terms.
There is nothing to do if the constraint was not even extracted.
Clearing a constraint means setting all coefficients in the corresponding row to 0 (we cannot just delete the row since that would renumber all the constraints/rows after it). Modifying coefficients in the matrix is potentially pretty expensive since they must be found in the sparse matrix representation. That is why by default we do not modify the coefficients here but only mark the low-level modeling object "out of sync".
Implements operations_research::MPSolverInterface.
Definition at line 1128 of file xpress_interface.cc.
|
overridevirtual |
Clear the objective from all its terms.
Since the objective function is stored as a dense vector updating it is O(n), so we usually perform the update immediately. If we want to support incremental extraction then we have no choice but to perform the update immediately.
We only need to reset variables that have been extracted.
Implements operations_research::MPSolverInterface.
Definition at line 1196 of file xpress_interface.cc.
|
overridevirtual |
Returns the basis status of a column.
Implements operations_research::MPSolverInterface.
Definition at line 1309 of file xpress_interface.cc.
|
inlineoverridevirtual |
Computes exact condition number. Only available for continuous problems and only implemented in GLPK.
Override this method in interfaces that actually support it.
Reimplemented from operations_research::MPSolverInterface.
Definition at line 377 of file xpress_interface.cc.
|
overridevirtual |
Extract constraints that have not yet been extracted.
Without incremental extraction ExtractModel() is always called to extract the full model.
There are constraints that are not yet extracted.
Update indices of new constraints before actually extracting them. In case of error we will just reset the indices.
Loop over the new constraints, collecting rows for up to CHUNK constraints into the arrays so that adding constraints is faster.
Collect up to CHUNK constraints into the arrays.
Stop if there is not enough room in the arrays to add the current constraint.
Setup right-hand side of constraint.
Setup left-hand side of constraint.
Undo all changes in case of error.
Implements operations_research::MPSolverInterface.
Definition at line 1509 of file xpress_interface.cc.
|
overridevirtual |
Extract all variables that have not yet been extracted.
Without incremental extraction ExtractModel() is always called to extract the full model.
There are non-extracted variables. Extract them now.
Arrays for modifying the problem are setup. Update the index of variables that will get extracted now. Updating indices before the actual extraction makes things much simpler in case we support incremental extraction. In case of error we just reset the indices.
If we support incremental extraction then we must update existing constraints with the new variables. To do that we use XPRSaddcols() to actually create the variables. This is supposed to be faster than combining XPRSnewcols() and XPRSchgcoeflist().
For each column count the size of the intersection with existing constraints.
At least one of the new variables did intersect with an old constraint. We have to create the new columns via XPRSaddcols().
Here is how cmatbeg[] is setup:
Either incremental extraction is not supported or none of the new variables did intersect an existing constraint. We can just use XPRSnewcols() to create the new variables.
Incremental extraction: we must update the ctype of the newly created variables (XPRSaddcols() does not allow specifying the ctype)
Query the actual number of columns in case we did not manage to extract all columns.
Undo all changes in case of error.
Implements operations_research::MPSolverInterface.
Definition at line 1334 of file xpress_interface.cc.
|
overridevirtual |
Extract the objective function.
DCHECK_EQ(last_variable_index_, cols);
Implements operations_research::MPSolverInterface.
Definition at line 1602 of file xpress_interface.cc.
|
inlineoverridevirtual |
Reimplemented from operations_research::MPSolverInterface.
Definition at line 393 of file xpress_interface.cc.
|
inlineoverridevirtual |
--— Misc --—
Query problem type. Remember that problem type is a static property that is set in the constructor and never changed.
Implements operations_research::MPSolverInterface.
Definition at line 361 of file xpress_interface.cc.
|
inlineoverridevirtual |
Returns true if the problem is continuous and linear.
Implements operations_research::MPSolverInterface.
Definition at line 362 of file xpress_interface.cc.
|
inlineoverridevirtual |
Returns true if the problem is discrete and linear.
Implements operations_research::MPSolverInterface.
Definition at line 363 of file xpress_interface.cc.
|
virtual |
---— Query statistics on the solution and the solve ---—
---— Query statistics on the solution and the solve ---— Number of simplex iterations
Implements operations_research::MPSolverInterface.
Definition at line 1231 of file xpress_interface.cc.
|
virtual |
Number of branch-and-bound nodes. Only available for discrete problems.
Implements operations_research::MPSolverInterface.
Definition at line 1236 of file xpress_interface.cc.
|
protectedvirtual |
Return true on success and false on error.
Definition at line 1778 of file xpress_interface.cc.
|
overridevirtual |
---— Model modifications and extraction --—
--— Model modifications and extraction --— Resets extracted model
Instead of explicitly clearing all modeling objects we just delete the problem object and allocate a new one.
Implements operations_research::MPSolverInterface.
Definition at line 884 of file xpress_interface.cc.
|
overridevirtual |
Returns the basis status of a row.
Implements operations_research::MPSolverInterface.
Definition at line 1284 of file xpress_interface.cc.
|
overridevirtual |
See MPSolver::SetCallback() for details.
replace existing callback by removing it first
Reimplemented from operations_research::MPSolverInterface.
Definition at line 2217 of file xpress_interface.cc.
|
overridevirtual |
Changes a coefficient in a constraint.
Changing a single coefficient in the matrix is potentially pretty slow since that coefficient has to be found in the sparse matrix representation. So by default we don't perform this update immediately but instead mark the low-level modeling object "out of sync". If we want to support incremental extraction then we MUST perform the modification immediately, or we will lose it.
If row and column are both extracted then we can directly update the modeling object
If either row or column is not yet extracted then we can defer the update to ExtractModel()
Implements operations_research::MPSolverInterface.
Definition at line 1097 of file xpress_interface.cc.
|
overridevirtual |
Modify bounds of an extracted variable.
Changing rhs, sense, or range of a constraint is not too slow. Still, doing all the updates in one large operation is faster. Note however that if we do not want to re-extract the full model for each solve (supportIncrementalExtraction is true) then we MUST update the constraint here, otherwise we lose this update information.
Constraint is already extracted, so we must update its bounds and its type.
Rather than doing the complicated analysis required for XPRSchgrhsrange(), we first convert the row into an 'L' row with defined rhs and then change the range value.
Constraint is not yet extracted. It is sufficient to mark the modeling object as "out of sync"
Implements operations_research::MPSolverInterface.
Definition at line 1028 of file xpress_interface.cc.
|
overrideprotectedvirtual |
Implements operations_research::MPSolverInterface.
Definition at line 1650 of file xpress_interface.cc.
|
overrideprotectedvirtual |
Sets the LP algorithm : primal, dual or barrier. Note that XPRESS offers other LP algorithm (e.g. network) and automatic selection
Implements operations_research::MPSolverInterface.
Definition at line 1688 of file xpress_interface.cc.
|
overridevirtual |
Change a coefficient in the linear objective.
Nothing to do if variable was not even extracted
The objective function is stored as a dense vector, so updating a single coefficient is O(1). So by default we update the low-level modeling object here. If we support incremental extraction then we have no choice but to perform the update immediately.
Implements operations_research::MPSolverInterface.
Definition at line 1167 of file xpress_interface.cc.
|
overridevirtual |
Change the constant term in the linear objective.
Changing the objective offset is O(1), so we always do it immediately.
Implements operations_research::MPSolverInterface.
Definition at line 1190 of file xpress_interface.cc.
|
overridevirtual |
Sets the optimization direction (min/max).
Implements operations_research::MPSolverInterface.
Definition at line 904 of file xpress_interface.cc.
|
overrideprotectedvirtual |
Set all parameters in the underlying solver.
---— Parameters --—
Implements operations_research::MPSolverInterface.
Definition at line 1631 of file xpress_interface.cc.
|
overrideprotectedvirtual |
Implements operations_research::MPSolverInterface.
Definition at line 1654 of file xpress_interface.cc.
|
overrideprotectedvirtual |
Implements operations_research::MPSolverInterface.
Definition at line 1646 of file xpress_interface.cc.
|
overrideprotectedvirtual |
Set each parameter in the underlying solver.
Implements operations_research::MPSolverInterface.
Definition at line 1637 of file xpress_interface.cc.
|
overrideprotectedvirtual |
Sets the scaling mode.
In Xpress, scaling is not a binary on/off control, but a bit vector control setting it to 1 would only enable bit 1. Instead, we reset it to its default (163 for the current version 8.6) Alternatively, we could call CHECK_STATUS(XPRSsetintcontrol(mLp, XPRS_SCALING, 163));
Implements operations_research::MPSolverInterface.
Definition at line 1669 of file xpress_interface.cc.
|
overridevirtual |
See MPSolver::SetStartingLpBasis().
Reimplemented from operations_research::MPSolverInterface.
Definition at line 1721 of file xpress_interface.cc.
|
overridevirtual |
Modifies bounds of an extracted variable.
Changing the bounds of a variable is fast. However, doing this for many variables may still be slow. So we don't perform the update by default. However, if we support incremental extraction (supportIncrementalExtraction is true) then we MUST perform the update here, or we will lose it.
Variable has already been extracted, so we must modify the modeling object.
Variable is not yet extracted. It is sufficient to just mark the modeling object "out of sync"
Implements operations_research::MPSolverInterface.
Definition at line 909 of file xpress_interface.cc.
|
overridevirtual |
Modifies integrality of an extracted variable.
Changing the type of a variable should be fast. Still, doing all updates in one big chunk right before solve() is usually faster. However, if we support incremental extraction (supportIncrementalExtraction is true) then we MUST change the type of extracted variables here.
Variable is extracted. Change the type immediately.
Implements operations_research::MPSolverInterface.
Definition at line 938 of file xpress_interface.cc.
|
overridevirtual |
--— Solve --— Solve the problem using the parameter values specified.
Delete cached information
Set incrementality
may be faster, so we do it.
Extract the model to be solved. If we don't support incremental extraction and the low-level modeling is out of sync then we have to re-extract everything. Note that this will lose MIP starts or advanced basis information from a previous solve.
Set log level.
Set parameters. We first set our internal MPSolverParameters from 'param' and then set any user-specified internal solver parameters via solver_specific_parameter_string_. Default MPSolverParameters can override custom parameters while specific parameters allow a higher level of customization (for example for presolving) and therefore we apply MPSolverParameters first.
In Xpress, a time limit should usually have a negative sign. With a positive sign, the solver will only stop when a solution has been found.
Load basis if present
Set the hint (if any)
Add opt node callback to optimizer. We have to do this here (just before solve) to make sure the variables are fully initialized
Solve. Do not CHECK_STATUS here since some errors (for example CPXERR_NO_MEMORY) still allow us to query useful information.
Disable screen output right after solve
Figure out what solution we have.
Get problem dimensions for solution queries below.
Capture objective function value.
Capture primal and dual solutions
If there is a primal feasible solution then capture it.
MIP does not have duals
Continuous problem.
Map XPRESS status to more generic solution status in MPSolver
Implements operations_research::MPSolverInterface.
Definition at line 1789 of file xpress_interface.cc.
|
overridevirtual |
Returns a string describing the underlying solver and its version.
We prefer XPRSversionnumber() over XPRSversion() since the former will never pose any encoding issues.
Implements operations_research::MPSolverInterface.
Definition at line 864 of file xpress_interface.cc.
|
inlineoverridevirtual |
Reimplemented from operations_research::MPSolverInterface.
Definition at line 391 of file xpress_interface.cc.
|
inlineoverridevirtual |
Returns the underlying solver.
Implements operations_research::MPSolverInterface.
Definition at line 375 of file xpress_interface.cc.
|
protectedvirtual |
Definition at line 1785 of file xpress_interface.cc.
|
overridevirtual |
Writes the model.
Reimplemented from operations_research::MPSolverInterface.
Definition at line 2080 of file xpress_interface.cc.