Google OR-Tools: ortools/constraint_solver/constraints.cc Source File

14#include <string.h>

16#include <algorithm>

17#include <cstdint>

18#include <limits>

19#include <memory>

20#include <string>

21#include <utility>

22#include <vector>

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

25#include "absl/strings/str_cat.h"

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

27#include "absl/strings/str_join.h"

39 "InitialPropagate");

40}

45 "InitialPropagate");

46}

48namespace {

49class ActionDemon : public Demon {

50 public:

51 explicit ActionDemon(const Solver::Action& action) : action_(action) {

52 CHECK(action != nullptr);

53 }

55 ~ActionDemon() override {}

57 void Run(Solver* const solver) override { action_(solver); }

59 private:

61};

63class ClosureDemon : public Demon {

64 public:

65 explicit ClosureDemon(const Solver::Closure& closure) : closure_(closure) {

66 CHECK(closure != nullptr);

67 }

69 ~ClosureDemon() override {}

71 void Run(Solver* const solver) override { closure_(); }

73 private:

75};

79class TrueConstraint : public Constraint {

80 public:

81 explicit TrueConstraint(Solver* const s) : Constraint(s) {}

82 ~TrueConstraint() override {}

84 void Post() override {}

85 void InitialPropagate() override {}

86 std::string DebugString() const override { return "TrueConstraint()"; }

88 void Accept(ModelVisitor* const visitor) const override {

91 }

92 IntVar* Var() override { return solver()->MakeIntConst(1); }

93};

95class FalseConstraint : public Constraint {

96 public:

97 explicit FalseConstraint(Solver* const s) : Constraint(s) {}

98 FalseConstraint(Solver* const s, const std::string& explanation)

99 : Constraint(s), explanation_(explanation) {}

100 ~FalseConstraint() override {}

101

102 void Post() override {}

103 void InitialPropagate() override { solver()->Fail(); }

104 std::string DebugString() const override {

105 return absl::StrCat("FalseConstraint(", explanation_, ")");

106 }

107

108 void Accept(ModelVisitor* const visitor) const override {

111 }

112 IntVar* Var() override { return solver()->MakeIntConst(0); }

113

114 private:

115 const std::string explanation_;

116};

117

118

119

120

121

122

123

125 public:

126 MapDomain(Solver* const s, IntVar* const var,

127 const std::vector<IntVar*>& actives)

128 : Constraint(s), var_(var), actives_(actives) {

129 holes_ = var->MakeHoleIterator(true);

130 }

131

132 ~MapDomain() override {}

133

134 void Post() override {

136 "VarDomain");

137 var_->WhenDomain(vd);

138 Demon* vb =

140 var_->WhenBound(vb);

141 std::unique_ptr<IntVarIterator> domain_it(

142 var_->MakeDomainIterator(false));

143 for (const int64_t index : InitAndGetValues(domain_it.get())) {

144 if (index >= 0 && index < actives_.size() && !actives_[index]->Bound()) {

146 solver(), this, &MapDomain::UpdateActive, "UpdateActive", index);

147 actives_[index]->WhenDomain(d);

148 }

149 }

150 }

151

152 void InitialPropagate() override {

153 for (int i = 0; i < actives_.size(); ++i) {

154 actives_[i]->SetRange(int64_t{0}, int64_t{1});

155 if (!var_->Contains(i)) {

156 actives_[i]->SetValue(0);

157 } else if (actives_[i]->Max() == 0LL) {

158 var_->RemoveValue(i);

159 }

160 if (actives_[i]->Min() == 1LL) {

161 var_->SetValue(i);

162 }

163 }

164 if (var_->Bound()) {

165 VarBound();

166 }

167 }

168

169 void UpdateActive(int64_t index) {

170 IntVar* const act = actives_[index];

171 if (act->Max() == 0) {

172 var_->RemoveValue(index);

173 } else if (act->Min() == 1) {

174 var_->SetValue(index);

175 }

176 }

177

178 void VarDomain() {

179 const int64_t oldmin = var_->OldMin();

180 const int64_t oldmax = var_->OldMax();

181 const int64_t vmin = var_->Min();

182 const int64_t vmax = var_->Max();

183 const int64_t size = actives_.size();

184 for (int64_t j = std::max(oldmin, int64_t{0}); j < std::min(vmin, size);

185 ++j) {

186 actives_[j]->SetValue(0);

187 }

188 for (const int64_t j : InitAndGetValues(holes_)) {

189 if (j >= 0 && j < size) {

190 actives_[j]->SetValue(0);

191 }

192 }

193 for (int64_t j = std::max(vmax + int64_t{1}, int64_t{0});

194 j <= std::min(oldmax, size - int64_t{1}); ++j) {

195 actives_[j]->SetValue(int64_t{0});

196 }

197 }

198

199 void VarBound() {

200 const int64_t val = var_->Min();

201 if (val >= 0 && val < actives_.size()) {

202 actives_[val]->SetValue(1);

203 }

204 }

205 std::string DebugString() const override {

206 return absl::StrFormat("MapDomain(%s, [%s])", var_->DebugString(),

208 }

209

210 void Accept(ModelVisitor* const visitor) const override {

213 var_);

215 actives_);

217 }

218

219 private:

220 IntVar* const var_;

221 std::vector<IntVar*> actives_;

222 IntVarIterator* holes_;

223};

224

225

226

227class LexicalLessOrEqual : public Constraint {

228 public:

229 LexicalLessOrEqual(Solver* const s, std::vector<IntVar*> left,

230 std::vector<IntVar*> right, std::vector<int64_t> offsets)

231 : Constraint(s),

232 left_(std::move(left)),

233 right_(std::move(right)),

234 active_var_(0),

235 offsets_(std::move(offsets)),

236 demon_added_(offsets_.size(), false),

237 demon_(nullptr) {

238 CHECK_EQ(left_.size(), right_.size());

239 CHECK_EQ(offsets_.size(), right_.size());

240 CHECK(std::all_of(offsets_.begin(), offsets_.end(),

241 [](int step) { return step > 0; }));

242 }

243

244 ~LexicalLessOrEqual() override {}

245

246 void Post() override {

247 const int position = JumpEqualVariables(0);

248 active_var_.SetValue(solver(), position);

249 if (position < left_.size()) {

250 demon_ = solver()->MakeConstraintInitialPropagateCallback(this);

251 AddDemon(position);

252 }

253 }

254

255 void InitialPropagate() override {

256 const int position = JumpEqualVariables(active_var_.Value());

257 if (position >= left_.size()) return;

258 if (position != active_var_.Value()) {

259 AddDemon(position);

260 active_var_.SetValue(solver(), position);

261 }

262 const int next_non_equal = JumpEqualVariables(position + 1);

263 if (next_non_equal < left_.size() &&

264 left_[next_non_equal]->Min() > right_[next_non_equal]->Max()) {

265

266 left_[position]->SetMax(

267 CapSub(right_[position]->Max(), offsets_[position]));

268 right_[position]->SetMin(

269 CapAdd(left_[position]->Min(), offsets_[position]));

270 } else {

271 left_[position]->SetMax(right_[position]->Max());

272 right_[position]->SetMin(left_[position]->Min());

273 }

274

275

276 if (next_non_equal < left_.size()) {

277 AddDemon(next_non_equal);

278 }

279 }

280

281 std::string DebugString() const override {

282 return absl::StrFormat(

283 "LexicalLessOrEqual([%s], [%s], [%s])", JoinDebugStringPtr(left_, ", "),

285 }

286

287 void Accept(ModelVisitor* const visitor) const override {

290 left_);

292 right_);

295 }

296

297 private:

298 int JumpEqualVariables(int start_position) const {

299 int position = start_position;

300 while (position < left_.size() &&

301 left_[position]->Max() <= right_[position]->Min() &&

302 CapSub(right_[position]->Max(), CapSub(offsets_[position], 1)) <=

303 left_[position]->Min()) {

304 position++;

305 }

306 return position;

307 }

308 void AddDemon(int position) {

309 if (demon_added_.Value(position)) return;

310 left_[position]->WhenRange(demon_);

311 right_[position]->WhenRange(demon_);

312 demon_added_.SetValue(solver(), position, true);

313 }

314

315 std::vector<IntVar*> left_;

316 std::vector<IntVar*> right_;

317 NumericalRev<int> active_var_;

318 std::vector<int64_t> offsets_;

319 RevArray<bool> demon_added_;

320 Demon* demon_;

321};

322

323

324

325class InversePermutationConstraint : public Constraint {

326 public:

327 InversePermutationConstraint(Solver* const s,

328 const std::vector<IntVar*>& left,

329 const std::vector<IntVar*>& right)

330 : Constraint(s),

331 left_(left),

332 right_(right),

333 left_hole_iterators_(left.size()),

334 left_domain_iterators_(left_.size()),

335 right_hole_iterators_(right_.size()),

336 right_domain_iterators_(right_.size()) {

337 CHECK_EQ(left_.size(), right_.size());

338 for (int i = 0; i < left_.size(); ++i) {

339 left_hole_iterators_[i] = left_[i]->MakeHoleIterator(true);

340 left_domain_iterators_[i] = left_[i]->MakeDomainIterator(true);

341 right_hole_iterators_[i] = right_[i]->MakeHoleIterator(true);

342 right_domain_iterators_[i] = right_[i]->MakeDomainIterator(true);

343 }

344 }

345

346 ~InversePermutationConstraint() override {}

347

348 void Post() override {

349 for (int i = 0; i < left_.size(); ++i) {

351 solver(), this,

352 &InversePermutationConstraint::PropagateHolesOfLeftVarToRight,

353 "PropagateHolesOfLeftVarToRight", i);

354 left_[i]->WhenDomain(left_demon);

356 solver(), this,

357 &InversePermutationConstraint::PropagateHolesOfRightVarToLeft,

358 "PropagateHolesOfRightVarToLeft", i);

359 right_[i]->WhenDomain(right_demon);

360 }

361 solver()->AddConstraint(

362 solver()->MakeAllDifferent(left_, false));

363 solver()->AddConstraint(

364 solver()->MakeAllDifferent(right_, false));

365 }

366

367 void InitialPropagate() override {

368 const int size = left_.size();

369 for (int i = 0; i < size; ++i) {

370 left_[i]->SetRange(0, size - 1);

371 right_[i]->SetRange(0, size - 1);

372 }

373 for (int i = 0; i < size; ++i) {

374 PropagateDomain(i, left_[i], left_domain_iterators_[i], right_);

375 PropagateDomain(i, right_[i], right_domain_iterators_[i], left_);

376 }

377 }

378

379 void PropagateHolesOfLeftVarToRight(int index) {

380 PropagateHoles(index, left_[index], left_hole_iterators_[index], right_);

381 }

382

383 void PropagateHolesOfRightVarToLeft(int index) {

384 PropagateHoles(index, right_[index], right_hole_iterators_[index], left_);

385 }

386

387 std::string DebugString() const override {

388 return absl::StrFormat("InversePermutationConstraint([%s], [%s])",

391 }

392

393 void Accept(ModelVisitor* const visitor) const override {

396 left_);

398 right_);

400 }

401

402 private:

403

404 void PropagateHoles(int index, IntVar* const var, IntVarIterator* const holes,

405 const std::vector<IntVar*>& inverse) {

406 const int64_t oldmin = std::max(var->OldMin(), int64_t{0});

407 const int64_t oldmax =

408 std::min(var->OldMax(), static_cast<int64_t>(left_.size() - 1));

409 const int64_t vmin = var->Min();

410 const int64_t vmax = var->Max();

411 for (int64_t value = oldmin; value < vmin; ++value) {

412 inverse[value]->RemoveValue(index);

413 }

414 for (const int64_t hole : InitAndGetValues(holes)) {

415 if (hole >= 0 && hole < left_.size()) {

416 inverse[hole]->RemoveValue(index);

417 }

418 }

419 for (int64_t value = vmax + 1; value <= oldmax; ++value) {

420 inverse[value]->RemoveValue(index);

421 }

422 }

423

424 void PropagateDomain(int index, IntVar* const var,

425 IntVarIterator* const domain,

426 const std::vector<IntVar*>& inverse) {

427

428 tmp_removed_values_.clear();

429 for (const int64_t value : InitAndGetValues(domain)) {

430 if (!inverse[value]->Contains(index)) {

431 tmp_removed_values_.push_back(value);

432 }

433 }

434

435

436 if (!tmp_removed_values_.empty()) {

437 var->RemoveValues(tmp_removed_values_);

438 }

439 }

440

441 std::vector<IntVar*> left_;

442 std::vector<IntVar*> right_;

443 std::vector<IntVarIterator*> left_hole_iterators_;

444 std::vector<IntVarIterator*> left_domain_iterators_;

445 std::vector<IntVarIterator*> right_hole_iterators_;

446 std::vector<IntVarIterator*> right_domain_iterators_;

447

448

449 std::vector<int64_t> tmp_removed_values_;

450};

451

452

453

454class IndexOfFirstMaxValue : public Constraint {

455 public:

456 IndexOfFirstMaxValue(Solver* solver, IntVar* index,

457 const std::vector<IntVar*>& vars)

458 : Constraint(solver), index_(index), vars_(vars) {}

459

460 ~IndexOfFirstMaxValue() override {}

461

462 void Post() override {

463 Demon* const demon =

464 solver()->MakeDelayedConstraintInitialPropagateCallback(this);

465 index_->WhenRange(demon);

466 for (IntVar* const var : vars_) {

467 var->WhenRange(demon);

468 }

469 }

470

471 void InitialPropagate() override {

472 const int64_t vsize = vars_.size();

473 const int64_t imin = std::max(int64_t{0}, index_->Min());

474 const int64_t imax = std::min(vsize - 1, index_->Max());

475 int64_t max_max = std::numeric_limits<int64_t>::min();

476 int64_t max_min = std::numeric_limits<int64_t>::min();

477

478

479 for (int i = imin; i <= imax; ++i) {

480 max_max = std::max(max_max, vars_[i]->Max());

481 max_min = std::max(max_min, vars_[i]->Min());

482 }

483

484

485

486 for (int i = 0; i < imin; ++i) {

487 vars_[i]->SetMax(max_max - 1);

488 }

489 for (int i = imax + 1; i < vsize; ++i) {

490 vars_[i]->SetMax(max_max);

491 }

492

493

494 int64_t min_index = imin;

495 while (vars_[min_index]->Max() < max_min) {

496 min_index++;

497 }

498 int64_t max_index = imax;

499 while (vars_[max_index]->Max() < max_min) {

500 max_index--;

501 }

502 index_->SetRange(min_index, max_index);

503 }

504

505 std::string DebugString() const override {

506 return absl::StrFormat("IndexMax(%s, [%s])", index_->DebugString(),

508 }

509

510 void Accept(ModelVisitor* const visitor) const override {

511

512 }

513

514 private:

515 IntVar* const index_;

516 const std::vector<IntVar*> vars_;

517};

518}

519

520

521

523 return RevAlloc(new ActionDemon(action));

524}

525

527 return RevAlloc(new ClosureDemon(closure));

528}

529

531 DCHECK(true_constraint_ != nullptr);

532 return true_constraint_;

533}

534

536 DCHECK(false_constraint_ != nullptr);

537 return false_constraint_;

538}

540 return RevAlloc(new FalseConstraint(this, explanation));

541}

542

543void Solver::InitCachedConstraint() {

544 DCHECK(true_constraint_ == nullptr);

545 true_constraint_ = RevAlloc(new TrueConstraint(this));

546 DCHECK(false_constraint_ == nullptr);

547 false_constraint_ = RevAlloc(new FalseConstraint(this));

548}

549

551 const std::vector<IntVar*>& actives) {

552 return RevAlloc(new MapDomain(this, var, actives));

553}

554

556 const std::vector<IntVar*>& right) {

557 std::vector<IntVar*> adjusted_left = left;

559 std::vector<IntVar*> adjusted_right = right;

562 std::move(adjusted_left), std::move(adjusted_right),

563 std::vector<int64_t>(left.size() + 1, 1));

564}

565

567 const std::vector<IntVar*>& right) {

569 left, right, std::vector<int64_t>(left.size(), 1));

570}

571

573 std::vector<IntVar*> left, std::vector<IntVar*> right,

574 std::vector<int64_t> offsets) {

575 return RevAlloc(new LexicalLessOrEqual(this, std::move(left),

576 std::move(right), std::move(offsets)));

577}

578

580 std::vector<IntVar*> left, std::vector<IntVar*> right,

581 std::vector<int64_t> offsets, IntVar* boolvar) {

582 std::vector<IntVar*> adjusted_left = std::move(left);

583 adjusted_left.insert(adjusted_left.begin(), boolvar);

584 std::vector<IntVar*> adjusted_right = std::move(right);

585 adjusted_right.insert(adjusted_right.begin(), MakeIntConst(1));

586 std::vector<int64_t> adjusted_offsets = std::move(offsets);

587 adjusted_offsets.insert(adjusted_offsets.begin(), 1);

589 std::move(adjusted_right),

590 std::move(adjusted_offsets));

591}

592

594 const std::vector<IntVar*>& left, const std::vector<IntVar*>& right) {

595 return RevAlloc(new InversePermutationConstraint(this, left, right));

596}

597

599 IntVar* index, const std::vector<IntVar*>& vars) {

600 return RevAlloc(new IndexOfFirstMaxValue(this, index, vars));

601}

602

604 IntVar* index, const std::vector<IntVar*>& vars) {

605 std::vector<IntVar*> opp_vars(vars.size());

606 for (int i = 0; i < vars.size(); ++i) {

608 }

609 return RevAlloc(new IndexOfFirstMaxValue(this, index, opp_vars));

610}

611}

virtual void InitialPropagate()=0

virtual IntVar * Var()=0

Creates a variable from the expression.

static const char kLexLess[]

static const char kFalseConstraint[]

static const char kTargetArgument[]

static const char kMapDomain[]

static const char kRightArgument[]

static const char kValuesArgument[]

static const char kVarsArgument[]

static const char kLeftArgument[]

static const char kInversePermutation[]

static const char kTrueConstraint[]

Constraint * MakeIsLexicalLessOrEqualWithOffsetsCt(std::vector< IntVar * > left, std::vector< IntVar * > right, std::vector< int64_t > offsets, IntVar *boolvar)

Definition constraints.cc:579

Demon * MakeClosureDemon(Closure closure)

Creates a demon from a closure.

Definition constraints.cc:526

Constraint * MakeLexicalLess(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)

Definition constraints.cc:555

IntExpr * MakeOpposite(IntExpr *expr)

-expr

std::function< void(Solver *)> Action

Constraint * MakeLexicalLessOrEqual(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)

Definition constraints.cc:566

Constraint * MakeIndexOfFirstMinValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)

Definition constraints.cc:603

std::function< void()> Closure

Constraint * MakeIndexOfFirstMaxValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)

Definition constraints.cc:598

Constraint * MakeMapDomain(IntVar *var, const std::vector< IntVar * > &actives)

Definition constraints.cc:550

Constraint * MakeTrueConstraint()

This constraint always succeeds.

Definition constraints.cc:530

Demon * MakeDelayedConstraintInitialPropagateCallback(Constraint *ct)

Definition constraints.cc:42

Constraint * MakeLexicalLessOrEqualWithOffsets(std::vector< IntVar * > left, std::vector< IntVar * > right, std::vector< int64_t > offsets)

Definition constraints.cc:572

Demon * MakeConstraintInitialPropagateCallback(Constraint *ct)

Definition constraints.cc:37

Constraint * MakeFalseConstraint()

This constraint always fails.

Definition constraints.cc:535

IntVar * MakeIntConst(int64_t val, const std::string &name)

IntConst will create a constant expression.

Demon * MakeActionDemon(Action action)

Creates a demon from a callback.

Definition constraints.cc:522

Constraint * MakeInversePermutationConstraint(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)

Definition constraints.cc:593

For infeasible and unbounded see Not checked if options check_solutions_if_inf_or_unbounded and the If options first_solution_only is false

int64_t CapAdd(int64_t x, int64_t y)

std::string JoinDebugStringPtr(const std::vector< T > &v, absl::string_view separator)

int64_t CapSub(int64_t x, int64_t y)

Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)

Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)

Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)