converge-optimization 0.1.1

Optimization algorithms for converge.zone - Rust reimplementation of OR-Tools subset
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

// Copyright 2010-2025 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Golomb ruler problem
//
//  find minimal ruler so that the differences between ticks are unique.
//
// First solutions:
//   0, 1
//   0, 1, 3
//   0, 1, 4,  6
//   0, 1, 4,  9, 11
//   0, 1, 4, 10, 12, 17
//   0, 1, 4, 10, 18, 23, 25

#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>

#include "absl/base/log_severity.h"
#include "absl/flags/flag.h"
#include "absl/log/check.h"
#include "absl/log/globals.h"
#include "absl/log/log.h"
#include "absl/strings/str_format.h"
#include "google/protobuf/text_format.h"
#include "ortools/base/init_google.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/model.h"
#include "ortools/util/sorted_interval_list.h"

ABSL_FLAG(bool, print, false, "If true, print the minimal solution.");
ABSL_FLAG(
    int, size, 0,
    "Size of the problem. If equal to 0, will test several increasing sizes.");
ABSL_FLAG(std::string, params, "", "Sat parameters.");

static const int kBestSolutions[] = {0, 1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85,
                                     // just for the optimistics ones, the rest:
                                     106, 127, 151, 177, 199, 216, 246};

static const int kKnownSolutions = 19;

namespace operations_research {
namespace sat {

void GolombRuler(int size) {
  CHECK_GE(size, 1);
  CpModelBuilder cp_model;

  std::vector<IntVar> ticks(size);
  ticks[0] = cp_model.NewConstant(0);
  const int64_t max = size * size;
  Domain domain(1, max);
  for (int i = 1; i < size; ++i) {
    ticks[i] = cp_model.NewIntVar(domain);
  }
  std::vector<IntVar> diffs;
  for (int i = 0; i < size; ++i) {
    for (int j = i + 1; j < size; ++j) {
      const IntVar diff = cp_model.NewIntVar(domain);
      cp_model.AddEquality(diff, ticks[j] - ticks[i]);
      diffs.push_back(diff);
    }
  }

  cp_model.AddAllDifferent(diffs);

  // Symmetry breaking.
  if (size > 2) {
    cp_model.AddLessThan(diffs.front(), diffs.back());
  }

  // Objective.
  cp_model.Minimize(ticks.back());

  // Search strategy.
  cp_model.AddDecisionStrategy(ticks, DecisionStrategyProto::CHOOSE_FIRST,
                               DecisionStrategyProto::SELECT_MIN_VALUE);

  Model model;
  SatParameters parameters;
  parameters.set_search_branching(SatParameters::FIXED_SEARCH);
  // Parse the --params flag.
  if (!absl::GetFlag(FLAGS_params).empty()) {
    CHECK(google::protobuf::TextFormat::MergeFromString(
        absl::GetFlag(FLAGS_params), &parameters))
        << absl::GetFlag(FLAGS_params);
  }
  model.Add(NewSatParameters(parameters));
  const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);

  if (response.status() == CpSolverStatus::OPTIMAL) {
    const int64_t result = SolutionIntegerValue(response, ticks.back());
    const int64_t num_failures = response.num_conflicts();
    absl::PrintF("N = %d, optimal length = %d (conflicts:%d, time=%f s)\n",
                 size, result, num_failures, response.wall_time());
    if (size - 1 < kKnownSolutions) {
      CHECK_EQ(result, kBestSolutions[size - 1]);
    }
    if (absl::GetFlag(FLAGS_print)) {
      for (int i = 0; i < size; ++i) {
        const int64_t tick = SolutionIntegerValue(response, ticks[i]);
        printf("%d ", static_cast<int>(tick));
      }
      printf("\n");
    }
  }
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char** argv) {
  absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo);
  InitGoogle(argv[0], &argc, &argv, true);

  if (absl::GetFlag(FLAGS_size) != 0) {
    operations_research::sat::GolombRuler(absl::GetFlag(FLAGS_size));
  } else {
    for (int n = 1; n < 11; ++n) {
      operations_research::sat::GolombRuler(n);
    }
  }
  return EXIT_SUCCESS;
}