Google OR-Tools: ortools/linear_solver/knapsack

Google OR-Tools: ortools/linear_solver/knapsack_interface.cc Source File

20#include <cstdint>

21#include <limits>

22#include <memory>

23#include <string>

24#include <vector>

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

34 public:

42 void Reset() override;

50 double new_value, double old_value) override;

53 double coefficient) override;

59 int64_t nodes() const override;

65 bool IsLP() const override;

66 bool IsMIP() const override;

83 private:

84 bool IsKnapsackModel() const;

85 bool IsVariableFixedToValue(const MPVariable* var, double value) const;

86 bool IsVariableFixed(const MPVariable* var) const;

87 double GetVariableValueFromSolution(const MPVariable* var) const;

90 std::unique_ptr<KnapsackSolver> knapsack_solver_;

91 std::vector<int64_t> profits_;

92 std::vector<std::vector<int64_t>> weights_;

93 std::vector<int64_t> capacities_;

94};

100

104 if (!IsKnapsackModel()) {

105 LOG(ERROR) << "Model is not a knapsack model";

108 }

112

115 if (profits_.size() <= 64 && capacities_.size() == 1) {

117 }

118 knapsack_solver_ =

119 std::make_unique<KnapsackSolver>(solver_type, "linear_solver");

120 const double time_limit_seconds =

122 ? (static_cast<double>(solver_->time_limit()) / 1000.0)

123 : std::numeric_limits<double>::infinity();

124 knapsack_solver_->set_time_limit(time_limit_seconds);

125 knapsack_solver_->Init(profits_, weights_, capacities_);

126 knapsack_solver_->Solve();

130 for (int var_id = 0; var_id < solver_->variables_.size(); ++var_id) {

132 const double value = GetVariableValueFromSolution(var);

135 }

137}

138

141 profits_.clear();

142 weights_.clear();

143 capacities_.clear();

144 knapsack_solver_.reset(nullptr);

145}

146

148 NonIncrementalChange();

149}

150

152 NonIncrementalChange();

153}

154

156 NonIncrementalChange();

157}

158

160 NonIncrementalChange();

161}

162

164 NonIncrementalChange();

165}

166

168 NonIncrementalChange();

169}

170

173 double new_value, double old_value) {

174 NonIncrementalChange();

175}

176

178 NonIncrementalChange();

179}

180

182 const MPVariable* const variable, double coefficient) {

183 NonIncrementalChange();

184}

185

187 NonIncrementalChange();

188}

189

191

193

195

197 int constraint_index) const {

198

200}

201

203 int variable_index) const {

204

206}

207

209

211

213

215 return "knapsack_solver-0.0";

216}

217

219

222 for (int column = 0; column < solver_->variables_.size(); ++column) {

224 }

225}

226

229 weights_.resize(solver_->constraints_.size());

230 capacities_.resize(solver_->constraints_.size(),

231 std::numeric_limits<int64_t>::max());

232 for (int row = 0; row < solver_->constraints_.size(); ++row) {

234 double fixed_usage = 0.0;

236 std::vector<double> coefficients(solver_->variables_.size() + 1, 0.0);

237 for (const auto& entry : ct->coefficients_) {

238 const int var_index = entry.first->index();

240 if (IsVariableFixedToValue(entry.first, 1.0)) {

241 fixed_usage += entry.second;

242 } else if (!IsVariableFixedToValue(entry.first, 0.0)) {

243 coefficients[var_index] = entry.second;

244 }

245 }

246

247

248 const double capacity = ct->ub() - fixed_usage;

249

250 coefficients[solver_->variables_.size()] = capacity;

251 double relative_error = 0.0;

252 double scaling_factor = 0.0;

254 std::numeric_limits<int64_t>::max(),

255 &scaling_factor, &relative_error);

256 const int64_t gcd =

258 std::vector<int64_t> scaled_coefficients(solver_->variables_.size(), 0);

259 for (const auto& entry : ct->coefficients_) {

260 if (!IsVariableFixed(entry.first)) {

261 scaled_coefficients[entry.first->index()] =

262 static_cast<int64_t>(round(scaling_factor * entry.second)) / gcd;

263 }

264 }

265 weights_[row].swap(scaled_coefficients);

266 capacities_[row] =

267 static_cast<int64_t>(round(scaling_factor * capacity)) / gcd;

268 }

269}

270

272 std::vector<double> coefficients(solver_->variables_.size(), 0.0);

273 for (const auto& entry : solver_->objective_->coefficients_) {

274

275

276

277 if (!IsVariableFixed(entry.first)) {

278 coefficients[entry.first->index()] = entry.second;

279 }

280 }

281 double relative_error = 0.0;

282 double scaling_factor = 0.0;

284 std::numeric_limits<int64_t>::max(),

285 &scaling_factor, &relative_error);

287 std::vector<int64_t> scaled_coefficients(solver_->variables_.size(), 0);

288 for (const auto& entry : solver_->objective_->coefficients_) {

289 scaled_coefficients[entry.first->index()] =

290 static_cast<int64_t>(round(scaling_factor * entry.second)) / gcd;

291 }

292 profits_.swap(scaled_coefficients);

293}

294

298

300

302

304

306

308

310

311bool KnapsackInterface::IsKnapsackModel() const {

312

313 for (int column = 0; column < solver_->variables_.size(); ++column) {

315 if (var->lb() <= -1.0 || var->ub() >= 2.0 || !var->integer()) {

316 return false;

317 }

318 }

319

320 for (const auto& entry : solver_->objective_->coefficients_) {

321 if (entry.second < 0) {

322 return false;

323 }

324 }

325

326 for (int row = 0; row < solver_->constraints_.size(); ++row) {

328 if (ct->lb() > 0.0) {

329 return false;

330 }

331 for (const auto& entry : ct->coefficients_) {

332 if (entry.second < 0) {

333 return false;

334 }

335 }

336 }

337

339}

340

341bool KnapsackInterface::IsVariableFixedToValue(const MPVariable* var,

342 double value) const {

343 const double lb_round_up = ceil(var->lb());

344 return value == lb_round_up && floor(var->ub()) == lb_round_up;

345}

346

347bool KnapsackInterface::IsVariableFixed(const MPVariable* var) const {

348 return IsVariableFixedToValue(var, 0.0) || IsVariableFixedToValue(var, 1.0);

349}

350

351double KnapsackInterface::GetVariableValueFromSolution(

353 return !IsVariableFixedToValue(var, 0.0) &&

354 (knapsack_solver_->BestSolutionContains(var->index()) ||

355 IsVariableFixedToValue(var, 1.0))

356 ? 1.0

357 : 0.0;

358}

359

360namespace {

361

362

363const void* const kRegisterKnapsack ABSL_ATTRIBUTE_UNUSED = [] {

367 return nullptr;

368}();

369

370}

371

372}

void SetDualTolerance(double value) override

Definition knapsack_interface.cc:303

~KnapsackInterface() override

Definition knapsack_interface.cc:99

void SetVariableInteger(int index, bool integer) override

Definition knapsack_interface.cc:155

int64_t nodes() const override

Definition knapsack_interface.cc:194

void ClearConstraint(MPConstraint *constraint) override

Definition knapsack_interface.cc:177

void ExtractNewVariables() override

Definition knapsack_interface.cc:220

int64_t iterations() const override

Definition knapsack_interface.cc:192

std::string SolverVersion() const override

Definition knapsack_interface.cc:214

void Reset() override

Definition knapsack_interface.cc:139

void ExtractNewConstraints() override

Definition knapsack_interface.cc:227

void SetVariableBounds(int index, double lb, double ub) override

Definition knapsack_interface.cc:151

void SetCoefficient(MPConstraint *constraint, const MPVariable *variable, double new_value, double old_value) override

Definition knapsack_interface.cc:171

void AddVariable(MPVariable *var) override

Definition knapsack_interface.cc:167

void SetLpAlgorithm(int value) override

Definition knapsack_interface.cc:309

void SetRelativeMipGap(double value) override

Definition knapsack_interface.cc:299

void AddRowConstraint(MPConstraint *ct) override

Definition knapsack_interface.cc:163

void * underlying_solver() override

Definition knapsack_interface.cc:218

void SetObjectiveCoefficient(const MPVariable *variable, double coefficient) override

Definition knapsack_interface.cc:181

MPSolver::BasisStatus row_status(int constraint_index) const override

Definition knapsack_interface.cc:196

void SetObjectiveOffset(double value) override

Definition knapsack_interface.cc:186

void SetConstraintBounds(int index, double lb, double ub) override

Definition knapsack_interface.cc:159

void ClearObjective() override

Definition knapsack_interface.cc:190

void SetPrimalTolerance(double value) override

Definition knapsack_interface.cc:301

void SetOptimizationDirection(bool maximize) override

Definition knapsack_interface.cc:147

MPSolver::BasisStatus column_status(int variable_index) const override

Definition knapsack_interface.cc:202

KnapsackInterface(MPSolver *solver)

Definition knapsack_interface.cc:96

void ExtractObjective() override

Definition knapsack_interface.cc:271

void SetParameters(const MPSolverParameters &param) override

Definition knapsack_interface.cc:295

void SetScalingMode(int value) override

Definition knapsack_interface.cc:307

MPSolver::ResultStatus Solve(const MPSolverParameters &param) override

Definition knapsack_interface.cc:101

bool IsContinuous() const override

Definition knapsack_interface.cc:208

bool IsMIP() const override

Definition knapsack_interface.cc:212

bool IsLP() const override

Definition knapsack_interface.cc:210

void SetPresolveMode(int value) override

Definition knapsack_interface.cc:305

SolverType

Enum controlling which underlying algorithm is used.

@ KNAPSACK_64ITEMS_SOLVER

@ KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER

double ub() const

Returns the upper bound.

static MPSolverInterfaceFactoryRepository * GetInstance()

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

void set_variable_as_extracted(int var_index, bool extracted)

friend class MPConstraint

void set_constraint_as_extracted(int ct_index, bool extracted)

void ResetExtractionInformation()

int last_constraint_index_

bool variable_is_extracted(int var_index) const

static constexpr int64_t kUnknownNumberOfNodes

MPSolverInterface(MPSolver *solver)

void SetCommonParameters(const MPSolverParameters &param)

MPSolver::ResultStatus result_status_

SynchronizationStatus sync_status_

@ MODEL_INVALID

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

@ FEASIBLE

feasible, or stopped by limit.

@ KNAPSACK_MIXED_INTEGER_PROGRAMMING

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

bool integer() const

Returns the integrality requirement of the variable.

double lb() const

Returns the lower bound.

double ub() const

Returns the upper bound.

void set_solution_value(double value)

double GetBestScalingOfDoublesToInt64(absl::Span< const double > input, absl::Span< const double > lb, absl::Span< const double > ub, int64_t max_absolute_sum)

int64_t ComputeGcdOfRoundedDoubles(absl::Span< const double > x, double scaling_factor)