Google OR-Tools: ortools/sat/cp_model

Google OR-Tools: ortools/sat/cp_model_utils.h Source File

14#ifndef ORTOOLS_SAT_CP_MODEL_UTILS_H_

15#define ORTOOLS_SAT_CP_MODEL_UTILS_H_

17#include <algorithm>

18#include <cstdint>

19#include <limits>

20#include <string>

21#include <vector>

23#if !defined(__PORTABLE_PLATFORM__)

25#endif

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

27#include "absl/functional/function_ref.h"

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

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

30#include "absl/strings/match.h"

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

32#include "absl/types/span.h"

33#include "google/protobuf/message.h"

34#include "google/protobuf/text_format.h"

42#ifndef SWIG

47#endif

50namespace sat {

53inline int NegatedRef(int ref) { return -ref - 1; }

67int64_t LinearExpressionGcd(const LinearExpressionProto& expr, int64_t gcd = 0);

75 LinearExpressionProto* output_negated_expr);

87 std::vector<int>* variables,

88 std::vector<int>* literals);

100

101

104

105

106

108

109

111

112

129

130

131

132template <typename ProtoWithDomain>

134 for (int i = 0; i < proto.domain_size(); i += 2) {

135 if (value >= proto.domain(i) && value <= proto.domain(i + 1)) return true;

136 }

137 return false;

138}

139

140

141template <typename ProtoWithDomain>

143 proto->clear_domain();

144 proto->mutable_domain()->Reserve(2 * domain.NumIntervals());

146 proto->add_domain(interval.start);

147 proto->add_domain(interval.end);

148 }

149}

150

151template <typename ProtoWithDomain>

153 proto->clear_domain();

154 proto->mutable_domain()->Reserve(2);

155 proto->add_domain(lb);

156 proto->add_domain(ub);

157}

158

159template <typename ProtoWithDomain>

161 proto->clear_domain();

162 proto->mutable_domain()->Reserve(2);

163 proto->add_domain(value);

164 proto->add_domain(value);

165}

166

167

168template <typename ProtoWithDomain>

170#if defined(__PORTABLE_PLATFORM__)

172 {proto.domain().begin(), proto.domain().end()});

173#else

175#endif

176}

177

178

179

180

181

182template <typename ProtoWithDomain>

184 std::vector<int64_t> result;

185 for (int i = 0; i < proto.domain_size(); i += 2) {

186 for (int64_t v = proto.domain(i); v <= proto.domain(i + 1); ++v) {

187 CHECK_LE(result.size(), 1e6);

188 result.push_back(v);

189 }

190 }

191 return result;

192}

193

194

196 int64_t value) {

197 double result = static_cast<double>(value);

198 if (value == std::numeric_limits<int64_t>::min())

199 result = -std::numeric_limits<double>::infinity();

200 if (value == std::numeric_limits<int64_t>::max())

201 result = std::numeric_limits<double>::infinity();

202 result += proto.offset();

205}

206

207

209 int64_t value) {

212 }

216}

217

218

220 double value) {

221 double result = value;

224 }

225 return result - proto.offset();

226}

227

228

229

230

232 absl::Span<const int64_t> solution);

233

234

236

237

239

240

241

243

244

246 int64_t value) {

248 return expr.offset() + value * expr.coeffs(0);

249}

250

251

252

254 int64_t value) {

256 const int64_t var_value = (value - expr.offset()) / expr.coeffs(0);

257 DCHECK_EQ(value, var_value * expr.coeffs(0) + expr.offset());

258 return var_value;

259}

260

261

263 int var) {

264 return expr.vars_size() == 1 && expr.vars(0) == var;

265}

266

267

268

269

270

271

273 int64_t coefficient,

274 LinearConstraintProto* linear);

275

276

277

278

280 LinearConstraintProto* linear,

281 int64_t* offset);

282

283

284void LiteralsToLinear(absl::Span<const int> literals, int64_t lb, int64_t ub,

285 LinearConstraintProto* linear);

286

287

289 const LinearExpressionProto& expr, int64_t coefficient,

290 LinearConstraintProto* linear);

291

292

294

295

297 const LinearExpressionProto& b,

298 int64_t b_scaling = 1);

299

300

301template <class ExpressionList>

303 int unique_var = -1;

305 for (const int var : expr.vars()) {

307 if (unique_var == -1) {

308 unique_var = var;

309 } else if (var != unique_var) {

310 return false;

311 }

312 }

313 }

314 return unique_var != -1;

315}

316

317

319

320template <class T>

322 const google::protobuf::RepeatedField<T>& sequence, uint64_t seed) {

323 if (sequence.empty()) return seed;

324 return fasthash64(reinterpret_cast<const char*>(sequence.data()),

325 sequence.size() * sizeof(T), seed);

326}

327

328template <class T>

330 return fasthash64(reinterpret_cast<const char*>(&field), sizeof(T), seed);

331}

332

333

335

336

339

340#if !defined(__PORTABLE_PLATFORM__)

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

360#endif

361

362template <class M>

364#if defined(__PORTABLE_PLATFORM__)

365 return false;

366#else

367 if (absl::EndsWith(filename, "txt") ||

368 absl::EndsWith(filename, "textproto")) {

369 std::string proto_string;

370 google::protobuf::TextFormat::Printer printer;

372 printer.PrintToString(proto, &proto_string);

374 } else {

376 }

377#endif

378}

379

380

381

382

385 if (absl::MakeConstSpan(lhs.literals()) !=

386 absl::MakeConstSpan(rhs.literals())) {

387 return false;

388 }

392 }

393 return true;

394}

395

396template <typename H>

398 for (const int lit : m.literals()) {

399 h = H::combine(std::move(h), lit);

400 }

401 return h;

402}

403

406 if (absl::MakeConstSpan(lhs.vars()) != absl::MakeConstSpan(rhs.vars())) {

407 return false;

408 }

409 if (absl::MakeConstSpan(lhs.coeffs()) != absl::MakeConstSpan(rhs.coeffs())) {

410 return false;

411 }

412 if (absl::MakeConstSpan(lhs.domain()) != absl::MakeConstSpan(rhs.domain())) {

413 return false;

414 }

415 return true;

416}

417

418template <typename H>

420 for (const int var : m.vars()) {

421 h = H::combine(std::move(h), var);

422 }

423 for (const int64_t coeff : m.coeffs()) {

424 h = H::combine(std::move(h), coeff);

425 }

426 for (const int64_t bound : m.domain()) {

427 h = H::combine(std::move(h), bound);

428 }

429 return h;

430}

431

433

434

435

437

438

439int CombineSeed(int base_seed, int64_t delta);

440

441}

442}

443

444#endif

static Domain FromFlatIntervals(const std::vector< int64_t > &flat_intervals)

static Domain FromFlatSpanOfIntervals(absl::Span< const int64_t > flat_intervals)

::int32_t literals(int index) const

int literals_size() const

::int32_t enforcement_literal(int index) const

const ::operations_research::sat::IntervalConstraintProto & interval() const

const ::operations_research::sat::ConstraintProto & constraints(int index) const

double scaling_factor() const

::int64_t integer_scaling_factor() const

::int64_t integer_after_offset() const

::int64_t integer_before_offset() const

const ::operations_research::sat::LinearExpressionProto & size() const

const ::operations_research::sat::LinearExpressionProto & end() const

const ::operations_research::sat::LinearExpressionProto & start() const

::int32_t vars(int index) const

::int64_t coeffs(int index) const

::int64_t domain(int index) const

::int64_t coeffs(int index) const

::int32_t vars(int index) const

OR_DLL ABSL_DECLARE_FLAG(bool, cp_model_dump_models)

absl::Status SetBinaryProto(absl::string_view file_name, const google::protobuf::Message &proto, Options options)

absl::Status SetContents(absl::string_view file_name, absl::string_view contents, Options options)

void SetToNegatedLinearExpression(const LinearExpressionProto &input_expr, LinearExpressionProto *output_negated_expr)

constexpr uint64_t kDefaultFingerprintSeed

Definition cp_model_utils.h:318

uint64_t FingerprintRepeatedField(const google::protobuf::RepeatedField< T > &sequence, uint64_t seed)

Definition cp_model_utils.h:321

void ApplyToAllVariableIndices(absl::FunctionRef< void(int *)> f, ConstraintProto *ct)

void RemoveVariablesFromInterval(const CpModelProto &model_proto, int index, Bitset64< int > &output)

Definition cp_model_utils.h:121

double UnscaleObjectiveValue(const CpObjectiveProto &proto, double value)

Definition cp_model_utils.h:219

bool RefIsPositive(int ref)

Definition cp_model_utils.h:55

bool LinearExpressionProtosAreEqual(const LinearExpressionProto &a, const LinearExpressionProto &b, int64_t b_scaling)

int64_t ComputeInnerObjective(const CpObjectiveProto &objective, absl::Span< const int64_t > solution)

bool operator==(const BoolArgumentProto &lhs, const BoolArgumentProto &rhs)

Definition cp_model_utils.h:383

bool ConvertCpModelProtoToWCnf(const CpModelProto &cp_model, std::string *out)

void ApplyToAllLiteralIndices(absl::FunctionRef< void(int *)> f, ConstraintProto *ct)

bool HasEnforcementLiteral(const ConstraintProto &ct)

Definition cp_model_utils.h:58

int CombineSeed(int base_seed, int64_t delta)

bool WriteModelProtoToFile(const M &proto, absl::string_view filename)

Definition cp_model_utils.h:363

bool DomainInProtoContains(const ProtoWithDomain &proto, int64_t value)

Definition cp_model_utils.h:133

bool SafeAddLinearExpressionToLinearConstraint(const LinearExpressionProto &expr, int64_t coefficient, LinearConstraintProto *linear)

int64_t GetInnerVarValue(const LinearExpressionProto &expr, int64_t value)

Definition cp_model_utils.h:253

uint64_t FingerprintModel(const CpModelProto &model, uint64_t seed)

uint64_t FingerprintSingleField(const T &field, uint64_t seed)

Definition cp_model_utils.h:329

double ScaleObjectiveValue(const CpObjectiveProto &proto, int64_t value)

Definition cp_model_utils.h:195

bool ConvertCpModelProtoToCnf(const CpModelProto &cp_model, std::string *out)

uint64_t FingerprintExpression(const LinearExpressionProto &lin, uint64_t seed)

bool ExpressionIsAffine(const LinearExpressionProto &expr)

std::vector< int > UsedVariables(const ConstraintProto &ct)

std::vector< int > UsedIntervals(const ConstraintProto &ct)

void LiteralsToLinear(absl::Span< const int > literals, int64_t lb, int64_t ub, LinearConstraintProto *linear)

void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)

Definition cp_model_utils.h:142

int64_t AffineExpressionValueAt(const LinearExpressionProto &expr, int64_t value)

Definition cp_model_utils.h:245

H AbslHashValue(H h, const IntVar &i)

Domain ReadDomainFromProto(const ProtoWithDomain &proto)

Definition cp_model_utils.h:169

bool ExpressionsContainsOnlyOneVar(const ExpressionList &exprs)

Definition cp_model_utils.h:302

void SetupTextFormatPrinter(google::protobuf::TextFormat::Printer *printer)

absl::string_view ConstraintCaseName(ConstraintProto::ConstraintCase constraint_case)

bool ExpressionContainsSingleRef(const LinearExpressionProto &expr)

int64_t LinearExpressionGcd(const LinearExpressionProto &expr, int64_t gcd)

int PositiveRef(int ref)

Definition cp_model_utils.h:54

void DivideLinearExpression(int64_t divisor, LinearExpressionProto *expr)

void AddLinearExpressionToLinearConstraint(const LinearExpressionProto &expr, int64_t coefficient, LinearConstraintProto *linear)

int GetSingleRefFromExpression(const LinearExpressionProto &expr)

int64_t ScaleInnerObjectiveValue(const CpObjectiveProto &proto, int64_t value)

Definition cp_model_utils.h:208

bool IsAffineIntAbs(const ConstraintProto &ct)

int EnforcementLiteral(const ConstraintProto &ct)

Definition cp_model_utils.h:61

int NegatedRef(int ref)

Definition cp_model_utils.h:53

void ApplyToAllIntervalIndices(absl::FunctionRef< void(int *)> f, ConstraintProto *ct)

void InsertVariablesFromInterval(const CpModelProto &model_proto, int index, Bitset64< int > &output)

Definition cp_model_utils.h:113

IndexReferences GetReferencesUsedByConstraint(const ConstraintProto &ct)

void AddWeightedLiteralToLinearConstraint(int lit, int64_t coeff, LinearConstraintProto *linear, int64_t *offset)

bool AffineExpressionContainsVar(const LinearExpressionProto &expr, int var)

Definition cp_model_utils.h:262

std::vector< int64_t > AllValuesInDomain(const ProtoWithDomain &proto)

Definition cp_model_utils.h:183

Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid

uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)

Definition cp_model_utils.h:81

std::vector< int > variables

Definition cp_model_utils.h:82

std::vector< int > literals

Definition cp_model_utils.h:83