Google OR-Tools: ortools/linear_solver/linear

Google OR-Tools: ortools/linear_solver/linear_solver.h Source File

133

134#ifndef ORTOOLS_LINEAR_SOLVER_LINEAR_SOLVER_H_

135#define ORTOOLS_LINEAR_SOLVER_LINEAR_SOLVER_H_

136

137#include <atomic>

138#include <cstdint>

139#include <functional>

140#include <limits>

141#include <map>

142#include <memory>

143#include <optional>

144#include <ostream>

145#include <string>

146#include <utility>

147#include <vector>

148

149#include "absl/base/attributes.h"

150#include "absl/base/port.h"

151#include "absl/base/thread_annotations.h"

152#include "absl/container/flat_hash_map.h"

153#include "absl/flags/declare.h"

154#include "absl/log/check.h"

155#include "absl/log/log.h"

156#include "absl/status/status.h"

157#include "absl/strings/str_format.h"

158#include "absl/strings/string_view.h"

159#include "absl/time/clock.h"

160#include "absl/time/time.h"

168

169#ifndef SWIG

173#endif

174

176

178

184

185

187

193 public:

201

202

206

207

208

212

213

214

220

221

223

224

225

226

227

228

230

231

233

234

247

248#ifndef SWIG

249

255

285

291

299

305 const std::string& solver_id);

306

307 bool IsMIP() const;

308

310 const std::string& Name() const {

311 return name_;

316 return problem_type_;

320

325

327 int NumVariables() const { return variables_.size(); }

328

333 const std::vector<MPVariable*>& variables() const { return variables_; }

334

339

346

355 const std::string& name);

356

359

362

365

380 void MakeVarArray(int nb, double lb, double ub, bool integer,

381 const std::string& name_prefix,

382 std::vector<MPVariable*>* vars);

383

385 void MakeNumVarArray(int nb, double lb, double ub, const std::string& name,

386 std::vector<MPVariable*>* vars);

387

389 void MakeIntVarArray(int nb, double lb, double ub, const std::string& name,

390 std::vector<MPVariable*>* vars);

391

394 std::vector<MPVariable*>* vars);

395

397 int NumConstraints() const { return constraints_.size(); }

398

404 const std::vector<MPConstraint*>& constraints() const { return constraints_; }

405

408

417 const std::string& constraint_name) const;

418

428

431

434 const std::string& name);

435

438

444

447 const std::string& name);

448

456

459

485

488

493 void Write(const std::string& file_name);

494

502

521 bool VerifySolution(double tolerance, bool log_errors) const;

522

532

543

554 std::string* error_message,

555 bool clear_names = true);

564 const MPModelProto& input_model, std::string* error_message);

565

568

587 ABSL_DEPRECATED("Prefer SolveMPModel() from solve_mp_model.h.")

590 std::atomic<bool>* interrupt = nullptr);

591

601 ABSL_DEPRECATED("Prefer SolveMPModel() from solve_mp_model.h.")

604 std::atomic<bool>* interrupt = nullptr);

605

607 "Prefer SolverTypeSupportsInterruption() from solve_mp_model.h.")

622

658 double tolerance = std::numeric_limits<double>::infinity());

659

665

674 std::string* model_str) const;

675

687

689 int GetNumThreads() const { return num_threads_; }

690

699 return solver_specific_parameter_string_;

703

717 void SetHint(std::vector<std::pair<const MPVariable*, double> > hint);

718

719

720

721 ABSL_DEPRECATED("Prefer MPModelRequestLoggingInfo() from solve_mp_model.h.")

724

738

749 const std::vector<MPSolver::BasisStatus>& variable_statuses,

750 const std::vector<MPSolver::BasisStatus>& constraint_statuses);

751

757 static double infinity() { return std::numeric_limits<double>::infinity(); }

769

772

775

776 absl::Duration TimeLimit() const { return time_limit_; }

783 return absl::Now() - construction_time_;

788

794 int64_t nodes() const;

795

798

813

838

854

855

856

857

858

861

862

863

864

867

873 return time_limit_ == absl::InfiniteDuration()

875 : absl::ToInt64Milliseconds(time_limit_);

876 }

877 void set_time_limit(int64_t time_limit_milliseconds) {

879 ? absl::InfiniteDuration()

880 : absl::Milliseconds(time_limit_milliseconds));

881 }

883 return static_cast<double>(time_limit()) / 1000.0;

907

909

910 private:

911

912

913

914 int ComputeMaxConstraintSize(int min_constraint_index,

915 int max_constraint_index) const;

916

917

918 bool HasInfeasibleConstraints() const;

919

920

921 bool HasIntegerVariables() const;

922

923

924 void GenerateVariableNameIndex() const;

925

926

927 void GenerateConstraintNameIndex() const;

928

929

930 const std::string name_;

931

932

934

935

936 std::unique_ptr<MPSolverInterface> interface_;

937

938

939 std::vector<MPVariable*> variables_;

940

941 mutable std::optional<absl::flat_hash_map<std::string, int> >

942 variable_name_to_index_;

943

944 std::vector<bool> variable_is_extracted_;

945

946

947 std::vector<MPConstraint*> constraints_;

948

949 mutable std::optional<absl::flat_hash_map<std::string, int> >

950 constraint_name_to_index_;

951

952 std::vector<bool> constraint_is_extracted_;

953

954

955 std::unique_ptr<MPObjective> objective_;

956

957

958

959

960

961

962

963

964 std::vector<std::pair<const MPVariable*, double> > solution_hint_;

965

966 absl::Duration time_limit_ = absl::InfiniteDuration();

967

968 const absl::Time construction_time_;

969

970

971 int num_threads_ = 1;

972

973

974 std::string solver_specific_parameter_string_;

975

976 static absl::Mutex global_count_mutex_;

977#ifndef SWIG

978 static int64_t global_num_variables_ ABSL_GUARDED_BY(global_count_mutex_);

979 static int64_t global_num_constraints_ ABSL_GUARDED_BY(global_count_mutex_);

980#endif

981

982 enum ModelProtoNamesPolicy {

983 DEFAULT_CLEAR_NAMES = 0,

984 INVALID_MODEL_ON_DUPLICATE_NONEMPTY_NAMES = 1,

985 DIE_ON_DUPLICATE_NONEMPTY_NAMES = 2,

986 };

988 const MPModelProto& input_model, ModelProtoNamesPolicy name_policy,

989 bool check_model_validity, std::string* error_message);

990};

991

998

1000 std::ostream& os,

1002 return os << ToString(optimization_problem_type);

1003}

1004

1005inline std::ostream& operator<<(std::ostream& os,

1007 return os << ProtoEnumToString<MPSolverResponseStatus>(

1009}

1010

1013 std::string* error);

1014

1021class MPObjective {

1022 public:

1024

1034

1042

1049

1055 const absl::flat_hash_map<const MPVariable*, double>& terms() const {

1056 return coefficients_;

1061

1063 double offset() const { return offset_; }

1064

1070

1082

1085

1088

1091

1094

1097

1109 double Value() const;

1110

1118

1119 private:

1137

1138

1139

1140

1141

1143 : interface_(interface_in), coefficients_(1), offset_(0.0) {}

1144

1146

1147

1148 absl::flat_hash_map<const MPVariable*, double> coefficients_;

1149

1150 double offset_;

1151};

1152

1154class MPVariable {

1155 public:

1157

1163 const std::string& name() const { return name_; }

1164

1167

1169 bool integer() const { return integer_; }

1170

1179

1181 int index() const { return index_; }

1182

1184 double lb() const { return lb_; }

1185

1187 double ub() const { return ub_; }

1188

1191

1194

1197

1205

1211

1219

1233 protected:

1252

1253

1254

1258 lb_(lb),

1259 ub_(ub),

1261 name_(name.empty() ? absl::StrFormat("auto_v_%09d", index) : name),

1262 solution_value_(0.0),

1263 reduced_cost_(0.0),

1264 interface_(interface_in) {}

1265

1270 const int index_;

1271 double lb_;

1272 double ub_;

1273 bool integer_;

1274 const std::string name_;

1275 double solution_value_;

1276 double reduced_cost_;

1277 int branching_priority_ = 0;

1279};

1280

1282

1287 public:

1289

1295 const std::string& name() const { return name_; }

1296

1299

1307

1313

1319 const absl::flat_hash_map<const MPVariable*, double>& terms() const {

1320 return coefficients_;

1324 double lb() const { return lb_; }

1325

1327 double ub() const { return ub_; }

1328

1331

1334

1337

1339 bool is_lazy() const { return is_lazy_; }

1340

1354 void set_is_lazy(bool laziness) { is_lazy_ = laziness; }

1355

1357 bool indicator_value() const { return indicator_value_; }

1360 int index() const { return index_; }

1361

1367

1381

1382 protected:

1400

1401

1402

1405 : coefficients_(1),

1407 lb_(lb),

1408 ub_(ub),

1409 name_(name.empty() ? absl::StrFormat("auto_c_%09d", index) : name),

1410 is_lazy_(false),

1411 indicator_variable_(nullptr),

1412 dual_value_(0.0),

1413 interface_(interface_in) {}

1414

1416

1418

1419

1420 bool ContainsNewVariables();

1421

1422

1423 absl::flat_hash_map<const MPVariable*, double> coefficients_;

1424

1425 const int index_;

1426

1427

1428 double lb_;

1429

1430

1431 double ub_;

1432

1433

1434 const std::string name_;

1435

1436

1437

1438

1439 bool is_lazy_;

1440

1441

1442

1443 const MPVariable* indicator_variable_;

1444 bool indicator_value_;

1445

1446 double dual_value_;

1448};

1449

1451

1476class

1477#ifndef SWIG

1479#endif

1481 public:

1549

1553

1557

1558

1559

1560

1561

1570

1571#ifndef SWIG

1572

1579

1582

1589

1596

1599

1602

1605

1606 private:

1607

1608

1609

1610 double relative_mip_gap_value_;

1611 double primal_tolerance_value_;

1612 double dual_tolerance_value_;

1613 int presolve_value_;

1614 int scaling_value_;

1615 int lp_algorithm_value_;

1616 int incrementality_value_;

1617

1618

1619

1620

1621 bool lp_algorithm_is_default_;

1622};

1623

1624

1625

1626

1627

1628

1630

1631

1632

1633

1634

1635

1636

1637

1638

1639

1641 public:

1643

1656

1658

1659

1661

1662

1663

1666

1667

1668

1669

1671

1672

1673

1674

1675

1676

1677

1679 std::atomic<bool>* ) const {

1680 return false;

1681 }

1684

1685

1686 std::atomic<bool>* ) {

1687 LOG(DFATAL) << "Default implementation should never be called.";

1689 }

1690

1691

1692

1693 virtual void Write(const std::string& filename);

1694

1695

1696

1697 virtual void Reset() = 0;

1698

1699

1701

1702

1703 virtual void SetVariableBounds(int index, double lb, double ub) = 0;

1704

1707

1710

1713

1715

1717 LOG(ERROR) << "Solver doesn't support indicator constraints.";

1718 return false;

1719 }

1720

1721

1723

1724

1726 const MPVariable* variable, double new_value,

1727 double old_value) = 0;

1728

1729

1731

1732

1734 double coefficient) = 0;

1736

1738

1739

1741

1743

1744

1745

1746 virtual int64_t iterations() const = 0;

1747

1748

1749 virtual int64_t nodes() const = 0;

1750

1751

1753

1755

1756

1758

1760

1761

1762

1763

1765

1766

1768

1774

1775

1776

1777

1778

1779

1781

1782 virtual bool IsLP() const = 0;

1783

1785

1786

1788

1790 return solver_->variable_is_extracted_[var_index];

1793 solver_->variable_is_extracted_[var_index] = extracted;

1796 return solver_->constraint_is_extracted_[ct_index];

1799 solver_->constraint_is_extracted_[ct_index] = extracted;

1804

1806

1807

1815

1816

1818

1819

1820

1822

1823

1825 const std::vector<MPSolver::BasisStatus>& ,

1826 const std::vector<MPSolver::BasisStatus>& ) {

1827 LOG(FATAL) << "Not supported by this solver.";

1828 }

1829

1830 virtual double infinity() { return std::numeric_limits<double>::infinity(); }

1831

1833

1834

1835 virtual bool NextSolution() { return false; }

1836

1837

1839 LOG(FATAL) << "Callbacks not supported for this solver.";

1843

1845

1846

1852

1854

1855

1857

1859

1860

1862

1864

1867

1870

1873

1875

1877

1878

1880

1882

1884

1886

1888

1889

1891

1892

1894

1896

1898

1900

1903

1905 double value);

1906

1909

1915

1916 virtual absl::Status SetNumThreads(int num_threads);

1917

1918

1919

1920

1921

1922

1923

1925 const std::string& parameters);

1926

1927

1932

1933

1935

1936

1937

1938

1939

1940

1941

1942

1943

1944

1945

1946

1947

1948

1949

1950

1951

1952

1953

1954

1955

1956

1957

1958

1960 public:

1961 static MPSolverInterfaceFactoryRepository* GetInstance();

1962

1963

1964

1965

1968 std::function<bool()> is_runtime_ready = {});

1969

1970

1971

1972

1974

1975

1976

1978

1979

1981 const;

1982

1983

1985

1986

1988

1989 private:

1990

1991

1992

1993

1996

1997 mutable absl::Mutex mutex_;

1998 struct Entry {

2000 std::function<bool()> is_runtime_ready;

2001 };

2002 std::map<MPSolver::OptimizationProblemType, Entry> map_;

2003};

2004

2005}

2006

2007#endif

Definition linear_solver.h:1288

bool is_lazy() const

Advanced usage: returns true if the constraint is "lazy" (see below).

Definition linear_solver.h:1341

friend class SCIPInterface

Definition linear_solver.h:1390

void set_dual_value(double dual_value)

Definition linear_solver.h:1417

void Clear()

Clears all variables and coefficients. Does not clear the bounds.

void SetCoefficient(const MPVariable *var, double coeff)

double lb() const

Returns the lower bound.

Definition linear_solver.h:1326

friend class SLMInterface

Definition linear_solver.h:1391

friend class CLPInterface

Definition linear_solver.h:1388

const absl::flat_hash_map< const MPVariable *, double > & terms() const

Definition linear_solver.h:1321

friend class GLOPInterface

Definition linear_solver.h:1395

friend class BopInterface

Definition linear_solver.h:1396

double ub() const

Returns the upper bound.

Definition linear_solver.h:1329

void SetUB(double ub)

Sets the upper bound.

Definition linear_solver.h:1335

void SetLB(double lb)

Sets the lower bound.

Definition linear_solver.h:1332

MPSolver::BasisStatus basis_status() const

MPConstraint(const MPConstraint &)=delete

friend class PdlpInterface

Definition linear_solver.h:1398

const MPVariable * indicator_variable() const

Definition linear_solver.h:1358

void set_is_lazy(bool laziness)

Definition linear_solver.h:1356

MPConstraint & operator=(const MPConstraint &)=delete

double GetCoefficient(const MPVariable *var) const

const std::string & name() const

Returns the name of the constraint.

Definition linear_solver.h:1297

friend class XpressInterface

Definition linear_solver.h:1394

int index() const

Returns the index of the constraint in the MPSolver::constraints_.

Definition linear_solver.h:1362

void SetBounds(double lb, double ub)

Sets both the lower and upper bounds.

friend class MPSolverInterface

Definition linear_solver.h:1386

friend class GurobiInterface

Definition linear_solver.h:1392

friend class MPSolver

Definition linear_solver.h:1385

friend class SatInterface

Definition linear_solver.h:1397

bool indicator_value() const

Definition linear_solver.h:1359

double dual_value() const

friend class GLPKInterface

Definition linear_solver.h:1389

friend class CplexInterface

Definition linear_solver.h:1393

friend class HighsInterface

Definition linear_solver.h:1399

friend class KnapsackInterface

Definition linear_solver.h:1400

friend class CBCInterface

Definition linear_solver.h:1387

MPModelRequest_SolverType SolverType

static constexpr SolverType SAT_INTEGER_PROGRAMMING

static constexpr SolverType GUROBI_MIXED_INTEGER_PROGRAMMING

static constexpr SolverType PDLP_LINEAR_PROGRAMMING

static constexpr SolverType GUROBI_LINEAR_PROGRAMMING

static constexpr SolverType GLOP_LINEAR_PROGRAMMING

A class to express a linear objective.

Definition linear_solver.h:1023

void MinimizeLinearExpr(const LinearExpr &linear_expr)

Resets the current objective to minimize linear_expr.

Definition linear_solver.h:1078

void SetCoefficient(const MPVariable *var, double coeff)

double GetCoefficient(const MPVariable *var) const

friend class SCIPInterface

Definition linear_solver.h:1127

void SetOffset(double value)

Sets the constant term in the objective.

MPObjective(const MPObjective &)=delete

const absl::flat_hash_map< const MPVariable *, double > & terms() const

Definition linear_solver.h:1057

friend class SLMInterface

Definition linear_solver.h:1128

friend class CLPInterface

Definition linear_solver.h:1125

void MaximizeLinearExpr(const LinearExpr &linear_expr)

Resets the current objective to maximize linear_expr.

Definition linear_solver.h:1074

friend class GLOPInterface

Definition linear_solver.h:1132

bool minimization() const

Is the optimization direction set to minimize?

friend class BopInterface

Definition linear_solver.h:1133

void SetMaximization()

Sets the optimization direction to maximize.

Definition linear_solver.h:1092

bool maximization() const

Is the optimization direction set to maximize?

double offset() const

Gets the constant term in the objective.

Definition linear_solver.h:1065

friend class PdlpInterface

Definition linear_solver.h:1135

void AddLinearExpr(const LinearExpr &linear_expr)

Adds linear_expr to the current objective, does not change the direction.

void OptimizeLinearExpr(const LinearExpr &linear_expr, bool is_maximization)

friend class XpressInterface

Definition linear_solver.h:1131

friend class MPSolverInterface

Definition linear_solver.h:1123

friend class GurobiInterface

Definition linear_solver.h:1129

friend class MPSolver

Definition linear_solver.h:1122

friend class SatInterface

Definition linear_solver.h:1134

void SetOptimizationDirection(bool maximize)

Sets the optimization direction (maximize: true or minimize: false).

friend class GLPKInterface

Definition linear_solver.h:1126

friend class CplexInterface

Definition linear_solver.h:1130

friend class HighsInterface

Definition linear_solver.h:1136

MPObjective & operator=(const MPObjective &)=delete

friend class KnapsackInterface

Definition linear_solver.h:1137

friend class CBCInterface

Definition linear_solver.h:1124

void SetMinimization()

Sets the optimization direction to minimize.

Definition linear_solver.h:1089

Definition linear_solver.h:1961

std::string PrettyPrintAllRegisteredProblemTypes() const

MPSolverInterface * Create(MPSolver *solver) const

std::vector< MPSolver::OptimizationProblemType > ListAllRegisteredProblemTypes() const

static MPSolverInterfaceFactoryRepository * GetInstance()

bool Unregister(MPSolver::OptimizationProblemType problem_type)

bool Supports(MPSolver::OptimizationProblemType problem_type) const

void Register(MPSolverInterfaceFactory factory, MPSolver::OptimizationProblemType problem_type, std::function< bool()> is_runtime_ready={})

Definition linear_solver.h:1642

void set_variable_as_extracted(int var_index, bool extracted)

Definition linear_solver.h:1794

virtual void AddVariable(MPVariable *var)=0

MPSolver::ResultStatus result_status() const

Definition linear_solver.h:1810

double best_objective_bound() const

virtual void SetCallback(MPCallback *)

Definition linear_solver.h:1840

bool CheckSolutionIsSynchronized() const

virtual void SetPrimalTolerance(double value)=0

virtual void ExtractNewConstraints()=0

virtual bool SupportsCallbacks() const

Definition linear_solver.h:1844

virtual void ClearObjective()=0

static constexpr int64_t kUnknownNumberOfIterations

Definition linear_solver.h:1659

virtual void ExtractObjective()=0

friend class MPConstraint

Definition linear_solver.h:1849

void InvalidateSolutionSynchronization()

virtual void SetRelativeMipGap(double value)=0

virtual void SetObjectiveCoefficient(const MPVariable *variable, double coefficient)=0

virtual void SetStartingLpBasis(const std::vector< MPSolver::BasisStatus > &, const std::vector< MPSolver::BasisStatus > &)

Definition linear_solver.h:1826

void set_constraint_as_extracted(int ct_index, bool extracted)

Definition linear_solver.h:1800

virtual bool IsMIP() const =0

virtual int64_t nodes() const =0

void ResetExtractionInformation()

int last_variable_index_

Definition linear_solver.h:1865

virtual void SetIntegerParamToUnsupportedValue(MPSolverParameters::IntegerParam param, int value)

int last_variable_index() const

Definition linear_solver.h:1789

virtual void SetPresolveMode(int value)=0

int last_constraint_index_

Definition linear_solver.h:1863

virtual MPSolver::BasisStatus column_status(int variable_index) const =0

virtual void SetCoefficient(MPConstraint *constraint, const MPVariable *variable, double new_value, double old_value)=0

virtual std::string SolverVersion() const =0

virtual void SetVariableInteger(int index, bool integer)=0

virtual absl::Status SetNumThreads(int num_threads)

virtual int64_t iterations() const =0

virtual bool InterruptSolve()

Definition linear_solver.h:1834

virtual void BranchingPriorityChangedForVariable(int)

Definition linear_solver.h:1744

virtual bool SetSolverSpecificParametersAsString(const std::string &parameters)

static const int kDummyVariableIndex

Definition linear_solver.h:1878

virtual void SetObjectiveOffset(double value)=0

virtual void SetParameters(const MPSolverParameters &param)=0

virtual bool CheckSolutionExists() const

virtual bool IsContinuous() const =0

friend class MPObjective

Definition linear_solver.h:1850

virtual void SetLpAlgorithm(int value)=0

virtual void SetUnsupportedIntegerParam(MPSolverParameters::IntegerParam param)

virtual bool NextSolution()

Definition linear_solver.h:1837

bool variable_is_extracted(int var_index) const

Definition linear_solver.h:1791

virtual bool IsLP() const =0

void SetUnsupportedDoubleParam(MPSolverParameters::DoubleParam param)

bool quiet() const

Definition linear_solver.h:1805

virtual void * underlying_solver()=0

virtual bool SupportsDirectlySolveProto(std::atomic< bool > *) const

Definition linear_solver.h:1680

bool constraint_is_extracted(int ct_index) const

Definition linear_solver.h:1797

SynchronizationStatus

Definition linear_solver.h:1644

@ SOLUTION_SYNCHRONIZED

Definition linear_solver.h:1654

@ MUST_RELOAD

Definition linear_solver.h:1647

@ MODEL_SYNCHRONIZED

Definition linear_solver.h:1651

static constexpr int64_t kUnknownNumberOfNodes

Definition linear_solver.h:1662

virtual void ExtractNewVariables()=0

virtual MPSolver::ResultStatus Solve(const MPSolverParameters &param)=0

double objective_value() const

double objective_value_

Definition linear_solver.h:1868

double best_objective_bound_

Definition linear_solver.h:1871

void SetDoubleParamToUnsupportedValue(MPSolverParameters::DoubleParam param, double value)

virtual void SetScalingMode(int value)=0

bool maximize_

Definition linear_solver.h:1860

virtual double ComputeExactConditionNumber() const

virtual MPSolver::BasisStatus row_status(int constraint_index) const =0

virtual void AddRowConstraint(MPConstraint *ct)=0

virtual MPSolutionResponse DirectlySolveProto(LazyMutableCopy< MPModelRequest >, std::atomic< bool > *)

Definition linear_solver.h:1684

virtual void Write(const std::string &filename)

void SetMIPParameters(const MPSolverParameters &param)

virtual ~MPSolverInterface()

virtual void SetDualTolerance(double value)=0

MPSolverInterface(MPSolver *solver)

virtual bool AddIndicatorConstraint(MPConstraint *const)

Definition linear_solver.h:1718

friend class MPSolver

Definition linear_solver.h:1846

virtual void SetOptimizationDirection(bool maximize)=0

virtual double infinity()

Definition linear_solver.h:1832

bool quiet_

Definition linear_solver.h:1874

void SetCommonParameters(const MPSolverParameters &param)

virtual void ClearConstraint(MPConstraint *constraint)=0

bool CheckSolutionIsSynchronizedAndExists() const

Definition linear_solver.h:1771

void set_quiet(bool quiet_value)

Definition linear_solver.h:1807

MPSolver::ResultStatus result_status_

Definition linear_solver.h:1858

MPSolver *const solver_

Definition linear_solver.h:1853

virtual void SetConstraintBounds(int index, double lb, double ub)=0

SynchronizationStatus sync_status_

Definition linear_solver.h:1855

virtual void SetVariableBounds(int index, double lb, double ub)=0

Definition linear_solver.h:1482

static const PresolveValues kDefaultPresolve

Definition linear_solver.h:1567

void ResetIntegerParam(MPSolverParameters::IntegerParam param)

static const double kDefaultDualTolerance

Definition linear_solver.h:1566

MPSolverParameters & operator=(const MPSolverParameters &)=delete

static const double kDefaultPrimalTolerance

Definition linear_solver.h:1565

DoubleParam

Enumeration of parameters that take continuous values.

Definition linear_solver.h:1485

@ DUAL_TOLERANCE

Advanced usage: tolerance for dual feasibility of basic solutions.

Definition linear_solver.h:1497

@ PRIMAL_TOLERANCE

Definition linear_solver.h:1495

@ RELATIVE_MIP_GAP

Limit for relative MIP gap.

Definition linear_solver.h:1487

double GetDoubleParam(MPSolverParameters::DoubleParam param) const

Returns the value of a double parameter.

PresolveValues

For each categorical parameter, enumeration of possible values.

Definition linear_solver.h:1513

@ PRESOLVE_OFF

Presolve is off.

Definition linear_solver.h:1515

@ PRESOLVE_ON

Presolve is on.

Definition linear_solver.h:1517

static const double kUnknownDoubleParamValue

Definition linear_solver.h:1556

static const int kUnknownIntegerParamValue

Definition linear_solver.h:1557

void ResetDoubleParam(MPSolverParameters::DoubleParam param)

static const int kDefaultIntegerParamValue

Definition linear_solver.h:1553

LpAlgorithmValues

LP algorithm to use.

Definition linear_solver.h:1521

@ DUAL

Dual simplex.

Definition linear_solver.h:1523

@ PRIMAL

Primal simplex.

Definition linear_solver.h:1525

@ BARRIER

Barrier algorithm.

Definition linear_solver.h:1527

void SetDoubleParam(MPSolverParameters::DoubleParam param, double value)

Sets a double parameter to a specific value.

IntegerParam

Enumeration of parameters that take integer or categorical values.

Definition linear_solver.h:1501

@ INCREMENTALITY

Advanced usage: incrementality from one solve to the next.

Definition linear_solver.h:1507

@ PRESOLVE

Advanced usage: presolve mode.

Definition linear_solver.h:1503

@ LP_ALGORITHM

Algorithm to solve linear programs.

Definition linear_solver.h:1505

@ SCALING

Advanced usage: enable or disable matrix scaling.

Definition linear_solver.h:1509

MPSolverParameters()

The constructor sets all parameters to their default value.

static const IncrementalityValues kDefaultIncrementality

Definition linear_solver.h:1568

IncrementalityValues

Advanced usage: Incrementality options.

Definition linear_solver.h:1531

@ INCREMENTALITY_OFF

Start solve from scratch.

Definition linear_solver.h:1533

@ INCREMENTALITY_ON

Definition linear_solver.h:1539

static const double kDefaultRelativeMipGap

Definition linear_solver.h:1564

void Reset()

Sets all parameters to their default value.

ScalingValues

Advanced usage: Scaling options.

Definition linear_solver.h:1543

@ SCALING_ON

Scaling is on.

Definition linear_solver.h:1547

@ SCALING_OFF

Scaling is off.

Definition linear_solver.h:1545

int GetIntegerParam(MPSolverParameters::IntegerParam param) const

Returns the value of an integer parameter.

static const double kDefaultDoubleParamValue

Definition linear_solver.h:1552

void SetIntegerParam(MPSolverParameters::IntegerParam param, int value)

Sets a integer parameter to a specific value.

Definition linear_solver.h:192

int64_t time_limit() const

Definition linear_solver.h:874

static void SolveLazyMutableRequest(LazyMutableCopy< MPModelRequest > request, MPSolutionResponse *response, std::atomic< bool > *interrupt=nullptr)

double time_limit_in_secs() const

Definition linear_solver.h:884

int64_t iterations() const

Returns the number of simplex iterations.

int NumVariables() const

Returns the number of variables.

Definition linear_solver.h:329

static MPSolver * CreateSolver(const std::string &solver_id)

void SetStartingLpBasis(const std::vector< MPSolver::BasisStatus > &variable_statuses, const std::vector< MPSolver::BasisStatus > &constraint_statuses)

MPVariable * MakeVar(double lb, double ub, bool integer, const std::string &name)

const std::vector< MPVariable * > & variables() const

Definition linear_solver.h:335

MPVariable * MakeIntVar(double lb, double ub, const std::string &name)

Creates an integer variable.

int NumConstraints() const

Returns the number of constraints.

Definition linear_solver.h:399

ResultStatus

Definition linear_solver.h:468

@ MODEL_INVALID

the model is trivially invalid (NaN coefficients, etc).

Definition linear_solver.h:480

@ FEASIBLE

feasible, or stopped by limit.

Definition linear_solver.h:472

@ NOT_SOLVED

not been solved yet.

Definition linear_solver.h:482

@ OPTIMAL

optimal.

Definition linear_solver.h:470

@ INFEASIBLE

proven infeasible.

Definition linear_solver.h:474

@ UNBOUNDED

proven unbounded.

Definition linear_solver.h:476

@ ABNORMAL

abnormal, i.e., error of some kind.

Definition linear_solver.h:478

ABSL_DEPRECATED("Prefer SolverTypeSupportsInterruption() from solve_mp_model.h.") static bool SolverTypeSupportsInterruption(const MPModelRequest

Definition linear_solver.h:608

ResultStatus Solve()

Solves the problem using the default parameter values.

MPSolverResponseStatus LoadModelFromProto(const MPModelProto &input_model, std::string *error_message, bool clear_names=true)

friend class SCIPInterface

Definition linear_solver.h:896

bool VerifySolution(double tolerance, bool log_errors) const

void MakeVarArray(int nb, double lb, double ub, bool integer, const std::string &name_prefix, std::vector< MPVariable * > *vars)

bool ExportModelAsLpFormat(bool obfuscate, std::string *model_str) const

const MPObjective & Objective() const

Definition linear_solver.h:457

void SetCallback(MPCallback *mp_callback)

OptimizationProblemType

Definition linear_solver.h:200

@ GLPK_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:218

@ GLOP_LINEAR_PROGRAMMING

Definition linear_solver.h:206

@ SCIP_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:217

@ CPLEX_LINEAR_PROGRAMMING

Definition linear_solver.h:239

@ SAT_INTEGER_PROGRAMMING

Definition linear_solver.h:231

@ XPRESS_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:242

@ CBC_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:219

@ HIGHS_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:220

@ GUROBI_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:238

@ COPT_LINEAR_PROGRAMMING

Definition linear_solver.h:243

@ CLP_LINEAR_PROGRAMMING

Definition linear_solver.h:204

@ XPRESS_LINEAR_PROGRAMMING

Definition linear_solver.h:241

@ PDLP_LINEAR_PROGRAMMING

Definition linear_solver.h:210

@ COPT_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:244

@ HIGHS_LINEAR_PROGRAMMING

Definition linear_solver.h:211

@ BOP_INTEGER_PROGRAMMING

Definition linear_solver.h:224

@ GLPK_LINEAR_PROGRAMMING

Definition linear_solver.h:205

@ CPLEX_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:240

@ KNAPSACK_MIXED_INTEGER_PROGRAMMING

Definition linear_solver.h:234

@ GUROBI_LINEAR_PROGRAMMING

Definition linear_solver.h:237

void SetTimeLimit(absl::Duration time_limit)

Definition linear_solver.h:779

MPSolverResponseStatus LoadModelFromProtoWithUniqueNamesOrDie(const MPModelProto &input_model, std::string *error_message)

bool SetSolverSpecificParametersAsString(const std::string &parameters)

MPVariable * MakeBoolVar(const std::string &name)

Creates a boolean variable.

virtual OptimizationProblemType ProblemType() const

Returns the optimization problem type set at construction.

Definition linear_solver.h:317

ABSL_MUST_USE_RESULT bool NextSolution()

static bool SupportsProblemType(OptimizationProblemType problem_type)

static double infinity()

Definition linear_solver.h:759

friend class SLMInterface

Definition linear_solver.h:900

void MakeIntVarArray(int nb, double lb, double ub, const std::string &name, std::vector< MPVariable * > *vars)

Creates an array of integer variables.

double ComputeExactConditionNumber() const

std::string GetSolverSpecificParametersAsString() const

Definition linear_solver.h:700

absl::Duration DurationSinceConstruction() const

Definition linear_solver.h:784

friend class GLOPInterface

Definition linear_solver.h:902

absl::Status SetNumThreads(int num_threads)

MPVariable * variable(int index) const

Definition linear_solver.h:340

friend class BopInterface

Definition linear_solver.h:903

absl::Status ClampSolutionWithinBounds()

bool OwnsVariable(const MPVariable *var) const

void MakeNumVarArray(int nb, double lb, double ub, const std::string &name, std::vector< MPVariable * > *vars)

Creates an array of continuous variables.

BasisStatus

Definition linear_solver.h:731

@ BASIC

Definition linear_solver.h:736

@ AT_LOWER_BOUND

Definition linear_solver.h:733

@ AT_UPPER_BOUND

Definition linear_solver.h:734

@ FREE

Definition linear_solver.h:732

@ FIXED_VALUE

Definition linear_solver.h:735

std::vector< double > ComputeConstraintActivities() const

int GetNumThreads() const

Returns the number of threads to be used during solve.

Definition linear_solver.h:691

bool SupportsCallbacks() const

void FillSolutionResponseProto(MPSolutionResponse *response) const

Encodes the current solution in a solution response protocol buffer.

int64_t wall_time() const

Definition linear_solver.h:889

friend class PdlpInterface

Definition linear_solver.h:905

void ExportModelToProto(MPModelProto *output_model) const

Exports model to protocol buffer.

static std::string GetMPModelRequestLoggingInfo(const MPModelRequest &request)

MPConstraint * MakeRowConstraint()

Creates a constraint with -infinity and +infinity bounds.

const std::vector< MPConstraint * > & constraints() const

Definition linear_solver.h:406

MPObjective * MutableObjective()

Returns the mutable objective object.

Definition linear_solver.h:460

bool OutputIsEnabled() const

static OptimizationProblemType ParseSolverTypeOrDie(const std::string &solver_id)

absl::Status LoadSolutionFromProto(const MPSolutionResponse &response, double tolerance=std::numeric_limits< double >::infinity())

absl::Duration TimeLimit() const

Definition linear_solver.h:778

MPVariable * MakeNumVar(double lb, double ub, const std::string &name)

Creates a continuous variable.

MPSolver(const std::string &name, OptimizationProblemType problem_type)

Create a solver with the given name and underlying solver backend.

MPConstraint * LookupConstraintOrNull(const std::string &constraint_name) const

MPConstraint * constraint(int index) const

Definition linear_solver.h:409

void EnableOutput()

Enables solver logging.

friend class XpressInterface

Definition linear_solver.h:899

static int64_t global_num_variables()

MPSolver & operator=(const MPSolver &)=delete

void SetHint(std::vector< std::pair< const MPVariable *, double > > hint)

void SuppressOutput()

Suppresses solver logging.

friend class MPSolverInterface

Definition linear_solver.h:901

friend class GurobiInterface

Definition linear_solver.h:897

void * underlying_solver()

MPVariable * LookupVariableOrNull(const std::string &var_name) const

friend class SatInterface

Definition linear_solver.h:904

void Write(const std::string &file_name)

static int64_t global_num_constraints()

const std::string & Name() const

Returns the name of the model set at construction.

Definition linear_solver.h:312

bool ExportModelAsMpsFormat(bool fixed_format, bool obfuscate, std::string *model_str) const

static bool ParseSolverType(absl::string_view solver_id, OptimizationProblemType *type)

friend class CplexInterface

Definition linear_solver.h:898

friend class HighsInterface

Definition linear_solver.h:906

static void SolveWithProto(const MPModelRequest &model_request, MPSolutionResponse *response, std::atomic< bool > *interrupt=nullptr)

friend class KnapsackInterface

Definition linear_solver.h:907

std::string SolverVersion() const

Returns a string describing the underlying solver and its version.

friend class CBCInterface

Definition linear_solver.h:895

void MakeBoolVarArray(int nb, const std::string &name, std::vector< MPVariable * > *vars)

Creates an array of boolean variables.

void set_time_limit(int64_t time_limit_milliseconds)

Definition linear_solver.h:879

The class for variables of a Mathematical Programming (MP) model.

Definition linear_solver.h:1156

double reduced_cost() const

void SetInteger(bool integer)

Sets the integrality requirement of the variable.

bool integer() const

Returns the integrality requirement of the variable.

Definition linear_solver.h:1171

void SetBranchingPriority(int priority)

void SetLB(double lb)

Sets the lower bound.

Definition linear_solver.h:1192

double lb() const

Returns the lower bound.

Definition linear_solver.h:1186

double ub() const

Returns the upper bound.

Definition linear_solver.h:1189

friend class SCIPInterface

Definition linear_solver.h:1250

MPVariable(const MPVariable &)=delete

void SetUB(double ub)

Sets the upper bound.

Definition linear_solver.h:1195

void SetBounds(double lb, double ub)

Sets both the lower and upper bounds.

const std::string & name() const

Returns the name of the variable.

Definition linear_solver.h:1165

friend class SLMInterface

Definition linear_solver.h:1251

friend class CLPInterface

Definition linear_solver.h:1238

MPVariable & operator=(const MPVariable &)=delete

friend class GLOPInterface

Definition linear_solver.h:1240

int branching_priority() const

Definition linear_solver.h:1232

friend class BopInterface

Definition linear_solver.h:1236

void set_reduced_cost(double reduced_cost)

Definition linear_solver.h:1269

friend class MPVariableSolutionValueTest

Definition linear_solver.h:1247

void set_solution_value(double value)

Definition linear_solver.h:1268

friend class PdlpInterface

Definition linear_solver.h:1248

double solution_value() const

MPSolver::BasisStatus basis_status() const

friend class XpressInterface

Definition linear_solver.h:1252

friend class MPSolverInterface

Definition linear_solver.h:1246

friend class GurobiInterface

Definition linear_solver.h:1242

friend class MPSolver

Definition linear_solver.h:1245

int index() const

Returns the index of the variable in the MPSolver::variables_.

Definition linear_solver.h:1183

friend class SatInterface

Definition linear_solver.h:1249

friend class GLPKInterface

Definition linear_solver.h:1241

friend class CplexInterface

Definition linear_solver.h:1239

friend class HighsInterface

Definition linear_solver.h:1243

friend class KnapsackInterface

Definition linear_solver.h:1244

double unrounded_solution_value() const

friend class CBCInterface

Definition linear_solver.h:1237

OR_DLL ABSL_DECLARE_FLAG(bool, linear_solver_enable_verbose_output)

constexpr double kDefaultPrimalTolerance

Definition linear_solver.h:177

std::function< MPSolverInterface *(MPSolver *)> MPSolverInterfaceFactory

Definition linear_solver.h:1936

bool SolverTypeSupportsInterruption(const MPModelRequest::SolverType solver)

bool MPSolverResponseStatusIsRpcError(MPSolverResponseStatus status)

bool SolverTypeIsMip(MPModelRequest::SolverType solver_type)

std::ostream & operator<<(std::ostream &out, const Assignment &assignment)

bool AbslParseFlag(const absl::string_view text, MPSolver::OptimizationProblemType *solver_type, std::string *error)

absl::string_view ToString(MPSolver::OptimizationProblemType optimization_problem_type)

std::string AbslUnparseFlag(MPSolver::OptimizationProblemType solver_type)

Definition linear_solver.h:1017