2025-01-10 11:35:44 +01:00
|
|
|
// Copyright 2010-2025 Google LLC
|
2012-09-13 16:25:28 +00:00
|
|
|
// 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.
|
2016-10-05 14:08:27 +02:00
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
// Frequency Assignment Problem
|
|
|
|
|
// The Radio Link Frequency Assignment Problem consists in assigning frequencies
|
|
|
|
|
// to a set of radio links defined between pairs of sites in order to avoid
|
|
|
|
|
// interferences. Each radio link is represented by a variable whose domain is
|
2016-10-05 14:08:27 +02:00
|
|
|
// the set of all frequencies that are available for this link.
|
|
|
|
|
// The essential constraint involving two variables of the problem F1 and F2,
|
|
|
|
|
// which represent two frequencies in the spectrum, is
|
2012-09-13 16:25:28 +00:00
|
|
|
// |F1 - F2| > k12, where k12 is a predefined constant value.
|
|
|
|
|
// The Frequency Assignment Problem is an NP-complete problem as proved by means
|
|
|
|
|
// of reduction from k-Colorability problem for undirected graphs.
|
|
|
|
|
// The solution of the problem can be based on various criteria:
|
|
|
|
|
// - Simple satisfaction
|
2016-10-05 14:08:27 +02:00
|
|
|
// - Minimizing the number of distinct frequencies used
|
2023-06-21 17:31:06 +02:00
|
|
|
// - Minimizing the maximum frequency used, i.e. minimizing the total width of
|
2016-10-05 14:08:27 +02:00
|
|
|
// the spectrum
|
2012-09-13 16:25:28 +00:00
|
|
|
// - Minimizing a weighted sum of violated constraints if the problem is
|
|
|
|
|
// inconsistent
|
|
|
|
|
// More on the Frequency Assignment Problem and the data format of its instances
|
|
|
|
|
// can be found at: http://www.inra.fr/mia/T/schiex/Doc/CELAR.shtml#synt
|
|
|
|
|
//
|
|
|
|
|
// Implementation
|
2016-10-05 14:08:27 +02:00
|
|
|
// Two solvers are implemented: The HardFapSolver finds the solution to
|
|
|
|
|
// feasible instances of the problem with objective either the minimization of
|
|
|
|
|
// the largest frequency assigned or the minimization of the number of
|
|
|
|
|
// frequencies used to the solution.
|
|
|
|
|
// The SoftFapSolver is optimizes the unfeasible instances. Some of the
|
|
|
|
|
// constraints of these instances may actually be soft constraints which may be
|
|
|
|
|
// violated at some predefined constant cost. The SoftFapSolver aims to minimize
|
|
|
|
|
// the total cost of violated constraints, i.e. to minimize the sum of all the
|
|
|
|
|
// violation costs.
|
2012-09-13 16:25:28 +00:00
|
|
|
// If the latter solver is forced to solve a feasible instance, the main
|
2016-10-05 14:08:27 +02:00
|
|
|
// function redirects to the former, afterwards.
|
2012-09-13 16:25:28 +00:00
|
|
|
//
|
|
|
|
|
|
|
|
|
|
#include <algorithm>
|
2021-04-23 14:55:51 +02:00
|
|
|
#include <cstdint>
|
2023-01-31 20:46:43 +01:00
|
|
|
#include <string>
|
2016-12-13 15:49:57 +01:00
|
|
|
#include <utility>
|
2012-09-13 16:25:28 +00:00
|
|
|
#include <vector>
|
|
|
|
|
|
2023-01-31 20:46:43 +01:00
|
|
|
#include "absl/container/btree_map.h"
|
|
|
|
|
#include "absl/strings/string_view.h"
|
2024-03-25 11:59:02 +01:00
|
|
|
#include "absl/types/span.h"
|
2018-06-08 16:40:43 +02:00
|
|
|
#include "examples/cpp/fap_model_printer.h"
|
|
|
|
|
#include "examples/cpp/fap_parser.h"
|
|
|
|
|
#include "examples/cpp/fap_utilities.h"
|
2023-01-31 20:46:43 +01:00
|
|
|
#include "ortools/base/init_google.h"
|
2017-04-26 17:30:25 +02:00
|
|
|
#include "ortools/base/logging.h"
|
|
|
|
|
#include "ortools/base/map_util.h"
|
|
|
|
|
#include "ortools/constraint_solver/constraint_solver.h"
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2020-10-23 11:50:14 +02:00
|
|
|
ABSL_FLAG(std::string, directory, "", "Specifies the directory of the data.");
|
|
|
|
|
ABSL_FLAG(std::string, value_evaluator, "",
|
|
|
|
|
"Specifies if a value evaluator will be used by the "
|
|
|
|
|
"decision builder.");
|
|
|
|
|
ABSL_FLAG(std::string, variable_evaluator, "",
|
|
|
|
|
"Specifies if a variable evaluator will be used by the "
|
|
|
|
|
"decision builder.");
|
|
|
|
|
ABSL_FLAG(int, time_limit_in_ms, 0, "Time limit in ms, <= 0 means no limit.");
|
|
|
|
|
ABSL_FLAG(int, choose_next_variable_strategy, 1,
|
|
|
|
|
"Selection strategy for variable: "
|
|
|
|
|
"1 = CHOOSE_FIRST_UNBOUND, "
|
|
|
|
|
"2 = CHOOSE_MIN_SIZE_LOWEST_MIN, "
|
|
|
|
|
"3 = CHOOSE_MIN_SIZE_HIGHEST_MAX, "
|
|
|
|
|
"4 = CHOOSE_RANDOM, ");
|
|
|
|
|
ABSL_FLAG(int, restart, -1, "Parameter for constant restart monitor.");
|
|
|
|
|
ABSL_FLAG(bool, find_components, false,
|
|
|
|
|
"If possible, split the problem into independent sub-problems.");
|
|
|
|
|
ABSL_FLAG(bool, luby, false,
|
|
|
|
|
"Use luby restart monitor instead of constant restart monitor.");
|
|
|
|
|
ABSL_FLAG(bool, log_search, true, "Create a search log.");
|
|
|
|
|
ABSL_FLAG(bool, soft, false, "Use soft solver instead of hard solver.");
|
|
|
|
|
ABSL_FLAG(bool, display_time, true,
|
|
|
|
|
"Print how much time the solving process took.");
|
|
|
|
|
ABSL_FLAG(bool, display_results, true,
|
|
|
|
|
"Print the results of the solving process.");
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
namespace operations_research {
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Decision on the relative order that the two variables of a constraint
|
|
|
|
|
// will have. It takes as parameters the components of the constraint.
|
|
|
|
|
class OrderingDecision : public Decision {
|
2020-10-22 23:36:58 +02:00
|
|
|
public:
|
2020-10-29 14:25:39 +01:00
|
|
|
OrderingDecision(IntVar* const variable1, IntVar* const variable2, int value,
|
2016-10-05 14:08:27 +02:00
|
|
|
std::string operation)
|
2020-10-22 23:36:58 +02:00
|
|
|
: variable1_(variable1),
|
|
|
|
|
variable2_(variable2),
|
|
|
|
|
value_(value),
|
2016-12-13 15:49:57 +01:00
|
|
|
operator_(std::move(operation)) {}
|
2024-03-25 11:59:02 +01:00
|
|
|
|
|
|
|
|
// This type is neither copyable nor movable.
|
|
|
|
|
OrderingDecision(const OrderingDecision&) = delete;
|
|
|
|
|
OrderingDecision& operator=(const OrderingDecision&) = delete;
|
2023-06-21 17:31:06 +02:00
|
|
|
~OrderingDecision() override = default;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// Apply will be called first when the decision is executed.
|
2020-10-29 14:25:39 +01:00
|
|
|
void Apply(Solver* const s) override {
|
2016-10-05 14:08:27 +02:00
|
|
|
// variable1 < variable2
|
|
|
|
|
MakeDecision(s, variable1_, variable2_);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Refute will be called after a backtrack.
|
2020-10-29 14:25:39 +01:00
|
|
|
void Refute(Solver* const s) override {
|
2016-10-05 14:08:27 +02:00
|
|
|
// variable1 > variable2
|
|
|
|
|
MakeDecision(s, variable2_, variable1_);
|
|
|
|
|
}
|
|
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
private:
|
2020-10-29 14:25:39 +01:00
|
|
|
void MakeDecision(Solver* s, IntVar* variable1, IntVar* variable2) {
|
2016-10-05 14:08:27 +02:00
|
|
|
if (operator_ == ">") {
|
2020-10-29 14:25:39 +01:00
|
|
|
IntExpr* difference = (s->MakeDifference(variable2, variable1));
|
2016-10-05 14:08:27 +02:00
|
|
|
s->AddConstraint(s->MakeGreater(difference, value_));
|
|
|
|
|
} else if (operator_ == "=") {
|
2020-10-29 14:25:39 +01:00
|
|
|
IntExpr* difference = (s->MakeDifference(variable2, variable1));
|
2016-10-05 14:08:27 +02:00
|
|
|
s->AddConstraint(s->MakeEquality(difference, value_));
|
|
|
|
|
} else {
|
|
|
|
|
LOG(FATAL) << "No right operator specified.";
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* const variable1_;
|
|
|
|
|
IntVar* const variable2_;
|
2016-10-05 14:08:27 +02:00
|
|
|
const int value_;
|
|
|
|
|
const std::string operator_;
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// Decision on whether a soft constraint will be added to a model
|
|
|
|
|
// or if it will be violated.
|
|
|
|
|
class ConstraintDecision : public Decision {
|
2020-10-22 23:36:58 +02:00
|
|
|
public:
|
2020-10-29 14:25:39 +01:00
|
|
|
explicit ConstraintDecision(IntVar* const constraint_violation)
|
2016-10-05 14:08:27 +02:00
|
|
|
: constraint_violation_(constraint_violation) {}
|
|
|
|
|
|
2024-03-25 11:59:02 +01:00
|
|
|
// This type is neither copyable nor movable.
|
|
|
|
|
ConstraintDecision(const ConstraintDecision&) = delete;
|
|
|
|
|
ConstraintDecision& operator=(const ConstraintDecision&) = delete;
|
|
|
|
|
|
2023-06-21 17:31:06 +02:00
|
|
|
~ConstraintDecision() override = default;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// Apply will be called first when the decision is executed.
|
2023-06-21 17:31:06 +02:00
|
|
|
void Apply(Solver* const) override {
|
2016-10-05 14:08:27 +02:00
|
|
|
// The constraint with which the builder is dealing, will be satisfied.
|
|
|
|
|
constraint_violation_->SetValue(0);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Refute will be called after a backtrack.
|
2023-06-21 17:31:06 +02:00
|
|
|
void Refute(Solver* const) override {
|
2016-10-05 14:08:27 +02:00
|
|
|
// The constraint with which the builder is dealing, will not be satisfied.
|
|
|
|
|
constraint_violation_->SetValue(1);
|
|
|
|
|
}
|
|
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
private:
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* const constraint_violation_;
|
2016-10-05 14:08:27 +02:00
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// The ordering builder resolves the relative order of the two variables
|
|
|
|
|
// included in each of the constraints of the problem. In that way the
|
|
|
|
|
// solving becomes much more efficient since we are branching on the
|
|
|
|
|
// disjunction implied by the absolute value expression.
|
|
|
|
|
class OrderingBuilder : public DecisionBuilder {
|
2020-10-22 23:36:58 +02:00
|
|
|
public:
|
|
|
|
|
enum Order { LESS = -1, EQUAL = 0, GREATER = 1 };
|
2020-10-21 00:21:54 +02:00
|
|
|
|
2023-02-01 14:14:30 +01:00
|
|
|
OrderingBuilder(const absl::btree_map<int, FapVariable>& data_variables,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<FapConstraint>& data_constraints,
|
|
|
|
|
const std::vector<IntVar*>& variables,
|
|
|
|
|
const std::vector<IntVar*>& violated_constraints,
|
2023-01-31 20:46:43 +01:00
|
|
|
const absl::btree_map<int, int>& index_from_key)
|
2020-10-22 23:36:58 +02:00
|
|
|
: data_variables_(data_variables),
|
|
|
|
|
data_constraints_(data_constraints),
|
|
|
|
|
variables_(variables),
|
|
|
|
|
violated_constraints_(violated_constraints),
|
|
|
|
|
index_from_key_(index_from_key),
|
|
|
|
|
size_(data_constraints.size()),
|
|
|
|
|
iter_(0),
|
|
|
|
|
checked_iter_(0) {
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const auto& it : data_variables_) {
|
2016-10-05 14:08:27 +02:00
|
|
|
int first_element = (it.second.domain)[0];
|
|
|
|
|
minimum_value_available_.push_back(first_element);
|
|
|
|
|
variable_state_.push_back(EQUAL);
|
|
|
|
|
}
|
|
|
|
|
CHECK_EQ(minimum_value_available_.size(), variables_.size());
|
|
|
|
|
CHECK_EQ(variable_state_.size(), variables_.size());
|
|
|
|
|
}
|
|
|
|
|
|
2024-03-25 11:59:02 +01:00
|
|
|
// This type is neither copyable nor movable.
|
|
|
|
|
OrderingBuilder(const OrderingBuilder&) = delete;
|
|
|
|
|
OrderingBuilder& operator=(const OrderingBuilder&) = delete;
|
|
|
|
|
|
2023-06-21 17:31:06 +02:00
|
|
|
~OrderingBuilder() override = default;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
Decision* Next(Solver* const s) override {
|
2016-10-05 14:08:27 +02:00
|
|
|
if (iter_ < size_) {
|
|
|
|
|
FapConstraint constraint = data_constraints_[iter_];
|
2018-04-11 13:00:30 +02:00
|
|
|
const int index1 = gtl::FindOrDie(index_from_key_, constraint.variable1);
|
|
|
|
|
const int index2 = gtl::FindOrDie(index_from_key_, constraint.variable2);
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* variable1 = variables_[index1];
|
|
|
|
|
IntVar* variable2 = variables_[index2];
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// checked_iter is equal to 0 means that whether the constraint is to be
|
|
|
|
|
// added or dropped hasn't been checked.
|
|
|
|
|
// If it is equal to 1, this has already been checked and the ordering
|
|
|
|
|
// of the constraint is to be done.
|
|
|
|
|
if (!checked_iter_ && !constraint.hard) {
|
|
|
|
|
// New Soft Constraint: Check if it will be added or dropped.
|
2020-10-29 14:25:39 +01:00
|
|
|
ConstraintDecision* constraint_decision =
|
2016-10-05 14:08:27 +02:00
|
|
|
new ConstraintDecision(violated_constraints_[iter_]);
|
|
|
|
|
|
|
|
|
|
s->SaveAndAdd(&checked_iter_, 1);
|
|
|
|
|
return s->RevAlloc(constraint_decision);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// The constraint is either hard or soft and checked already.
|
|
|
|
|
if (violated_constraints_[iter_]->Bound() &&
|
|
|
|
|
violated_constraints_[iter_]->Value() == 0) {
|
|
|
|
|
// If the constraint is added, do the ordering of its variables.
|
2020-10-29 14:25:39 +01:00
|
|
|
OrderingDecision* ordering_decision;
|
2016-10-05 14:08:27 +02:00
|
|
|
Order hint = Hint(constraint);
|
|
|
|
|
if (hint == LESS || hint == EQUAL) {
|
|
|
|
|
ordering_decision = new OrderingDecision(
|
|
|
|
|
variable1, variable2, constraint.value, constraint.operation);
|
|
|
|
|
} else {
|
|
|
|
|
ordering_decision = new OrderingDecision(
|
|
|
|
|
variable2, variable1, constraint.value, constraint.operation);
|
|
|
|
|
}
|
|
|
|
|
// Proceed to the next constraint.
|
|
|
|
|
s->SaveAndAdd(&iter_, 1);
|
|
|
|
|
// Assign checked_iter_ back to 0 to flag a new unchecked constraint.
|
|
|
|
|
s->SaveAndSetValue(&checked_iter_, 0);
|
|
|
|
|
return s->RevAlloc(ordering_decision);
|
|
|
|
|
} else {
|
|
|
|
|
// The constraint was dropped.
|
2017-04-26 17:30:25 +02:00
|
|
|
return nullptr;
|
2016-10-05 14:08:27 +02:00
|
|
|
}
|
|
|
|
|
} else {
|
|
|
|
|
// All the constraints were processed. No decision to take.
|
2017-04-26 17:30:25 +02:00
|
|
|
return nullptr;
|
2016-10-05 14:08:27 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
private:
|
2016-10-05 14:08:27 +02:00
|
|
|
Order Variable1LessVariable2(const int variable1, const int variable2,
|
|
|
|
|
const int value) {
|
|
|
|
|
minimum_value_available_[variable2] =
|
|
|
|
|
std::max(minimum_value_available_[variable2],
|
|
|
|
|
minimum_value_available_[variable1] + value);
|
|
|
|
|
return LESS;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
Order Variable1GreaterVariable2(const int variable1, const int variable2,
|
|
|
|
|
const int value) {
|
|
|
|
|
minimum_value_available_[variable1] =
|
|
|
|
|
std::max(minimum_value_available_[variable1],
|
|
|
|
|
minimum_value_available_[variable2] + value);
|
|
|
|
|
return GREATER;
|
|
|
|
|
}
|
|
|
|
|
// The Hint() function takes as parameter a constraint of the model and
|
|
|
|
|
// returns the most probable relative order that the two variables
|
|
|
|
|
// involved in the constraint should have.
|
|
|
|
|
// The function reaches such a decision, by taking into consideration if
|
|
|
|
|
// variable1 or variable2 or both have been denoted as less (state = -1)
|
|
|
|
|
// or greater (state = 1) than another variable in a previous constraint
|
|
|
|
|
// and tries to maintain the same state in the current constraint too.
|
|
|
|
|
// If both variables have the same state, the variable whose minimum value is
|
|
|
|
|
// the smallest is set to be lower than the other one.
|
|
|
|
|
// If none of the above are applicable variable1 is set to be lower than
|
|
|
|
|
// variable2. This ordering is more efficient if used with the
|
|
|
|
|
// Solver::ASSIGN_MIN_VALUE value selection strategy.
|
|
|
|
|
// It returns 1 if variable1 > variable2 or -1 if variable1 < variable2.
|
2020-10-29 14:25:39 +01:00
|
|
|
Order Hint(const FapConstraint& constraint) {
|
2016-10-05 14:08:27 +02:00
|
|
|
const int id1 = constraint.variable1;
|
|
|
|
|
const int id2 = constraint.variable2;
|
2018-04-11 13:00:30 +02:00
|
|
|
const int variable1 = gtl::FindOrDie(index_from_key_, id1);
|
|
|
|
|
const int variable2 = gtl::FindOrDie(index_from_key_, id2);
|
2016-10-05 14:08:27 +02:00
|
|
|
const int value = constraint.value;
|
|
|
|
|
CHECK_LT(variable1, variable_state_.size());
|
|
|
|
|
CHECK_LT(variable2, variable_state_.size());
|
|
|
|
|
CHECK_LT(variable1, minimum_value_available_.size());
|
|
|
|
|
CHECK_LT(variable2, minimum_value_available_.size());
|
|
|
|
|
|
|
|
|
|
if (variable_state_[variable1] > variable_state_[variable2]) {
|
|
|
|
|
variable_state_[variable1] = GREATER;
|
|
|
|
|
variable_state_[variable2] = LESS;
|
|
|
|
|
return Variable1GreaterVariable2(variable1, variable2, value);
|
|
|
|
|
} else if (variable_state_[variable1] < variable_state_[variable2]) {
|
|
|
|
|
variable_state_[variable1] = LESS;
|
|
|
|
|
variable_state_[variable2] = GREATER;
|
|
|
|
|
return Variable1LessVariable2(variable1, variable2, value);
|
|
|
|
|
} else {
|
|
|
|
|
if (variable_state_[variable1] == 0 && variable_state_[variable2] == 0) {
|
|
|
|
|
variable_state_[variable1] = LESS;
|
|
|
|
|
variable_state_[variable2] = GREATER;
|
|
|
|
|
return Variable1LessVariable2(variable1, variable2, value);
|
|
|
|
|
} else {
|
|
|
|
|
if (minimum_value_available_[variable1] >
|
|
|
|
|
minimum_value_available_[variable2]) {
|
|
|
|
|
return Variable1GreaterVariable2(variable1, variable2, value);
|
|
|
|
|
} else {
|
|
|
|
|
return Variable1LessVariable2(variable1, variable2, value);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Passed as arguments from the function that creates the Decision Builder.
|
2023-02-01 14:14:30 +01:00
|
|
|
const absl::btree_map<int, FapVariable> data_variables_;
|
2016-10-05 14:08:27 +02:00
|
|
|
const std::vector<FapConstraint> data_constraints_;
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<IntVar*> variables_;
|
|
|
|
|
const std::vector<IntVar*> violated_constraints_;
|
2023-01-31 20:46:43 +01:00
|
|
|
const absl::btree_map<int, int> index_from_key_;
|
2016-10-05 14:08:27 +02:00
|
|
|
// Used by Next() for monitoring decisions.
|
|
|
|
|
const int size_;
|
|
|
|
|
int iter_;
|
|
|
|
|
int checked_iter_;
|
|
|
|
|
// Used by Hint() for indicating the most probable ordering.
|
|
|
|
|
std::vector<Order> variable_state_;
|
|
|
|
|
std::vector<int> minimum_value_available_;
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// A comparator for sorting the constraints depending on their impact.
|
|
|
|
|
bool ConstraintImpactComparator(FapConstraint constraint1,
|
|
|
|
|
FapConstraint constraint2) {
|
|
|
|
|
if (constraint1.impact == constraint2.impact) {
|
|
|
|
|
return (constraint1.value > constraint2.value);
|
|
|
|
|
}
|
|
|
|
|
return (constraint1.impact > constraint2.impact);
|
|
|
|
|
}
|
|
|
|
|
|
2021-04-02 14:58:16 +02:00
|
|
|
int64_t ValueEvaluator(
|
2021-04-23 14:55:51 +02:00
|
|
|
absl::flat_hash_map<int64_t, std::pair<int64_t, int64_t>>*
|
|
|
|
|
value_evaluator_map,
|
2021-04-02 14:58:16 +02:00
|
|
|
int64_t variable_index, int64_t value) {
|
2018-04-11 13:47:07 +02:00
|
|
|
CHECK(value_evaluator_map != nullptr);
|
2012-09-13 16:25:28 +00:00
|
|
|
// Evaluate the choice. Smaller ranking denotes a better choice.
|
2021-04-02 14:58:16 +02:00
|
|
|
int64_t ranking = -1;
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const auto& it : *value_evaluator_map) {
|
2016-10-05 14:08:27 +02:00
|
|
|
if ((it.first != variable_index) && (it.second.first == value)) {
|
2012-09-13 16:25:28 +00:00
|
|
|
ranking = -2;
|
|
|
|
|
break;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Update the history of assigned values and their rankings of each variable.
|
2021-04-02 14:58:16 +02:00
|
|
|
absl::flat_hash_map<int64_t, std::pair<int64_t, int64_t>>::iterator it;
|
|
|
|
|
int64_t new_value = value;
|
|
|
|
|
int64_t new_ranking = ranking;
|
2016-10-05 14:08:27 +02:00
|
|
|
if ((it = value_evaluator_map->find(variable_index)) !=
|
|
|
|
|
value_evaluator_map->end()) {
|
2021-04-02 14:58:16 +02:00
|
|
|
std::pair<int64_t, int64_t> existing_value_ranking = it->second;
|
2012-09-13 16:25:28 +00:00
|
|
|
// Replace only if the current choice for this variable has smaller
|
|
|
|
|
// ranking or same ranking but smaller value of the existing choice.
|
|
|
|
|
if (!(existing_value_ranking.second > ranking ||
|
|
|
|
|
(existing_value_ranking.second == ranking &&
|
|
|
|
|
existing_value_ranking.first > value))) {
|
2016-10-05 14:08:27 +02:00
|
|
|
new_value = existing_value_ranking.first;
|
|
|
|
|
new_ranking = existing_value_ranking.second;
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
}
|
2021-04-02 14:58:16 +02:00
|
|
|
std::pair<int64_t, int64_t> new_value_ranking =
|
2016-11-16 18:20:16 +01:00
|
|
|
std::make_pair(new_value, new_ranking);
|
2023-01-31 20:46:43 +01:00
|
|
|
value_evaluator_map->insert_or_assign(variable_index, new_value_ranking);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
return new_ranking;
|
|
|
|
|
}
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// The variables which participate in more constraints and have the
|
|
|
|
|
// smaller domain should be in higher priority for assignment.
|
2023-06-21 17:31:06 +02:00
|
|
|
int64_t VariableEvaluator(
|
2024-03-25 11:59:02 +01:00
|
|
|
absl::Span<const int> key_from_index,
|
2023-06-21 17:31:06 +02:00
|
|
|
const absl::btree_map<int, FapVariable>& data_variables,
|
|
|
|
|
int64_t variable_index) {
|
2016-10-05 14:08:27 +02:00
|
|
|
FapVariable variable =
|
2018-04-11 13:00:30 +02:00
|
|
|
gtl::FindOrDie(data_variables, key_from_index[variable_index]);
|
2021-04-02 14:58:16 +02:00
|
|
|
int64_t result = -(variable.degree * 100 / variable.domain_size);
|
2016-10-05 14:08:27 +02:00
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
// Creates the variables of the solver from the parsed data.
|
2023-06-21 17:31:06 +02:00
|
|
|
void CreateModelVariables(
|
|
|
|
|
const absl::btree_map<int, FapVariable>& data_variables, Solver* solver,
|
|
|
|
|
std::vector<IntVar*>* model_variables,
|
|
|
|
|
absl::btree_map<int, int>* index_from_key,
|
|
|
|
|
std::vector<int>* key_from_index) {
|
2018-04-11 13:47:07 +02:00
|
|
|
CHECK(solver != nullptr);
|
|
|
|
|
CHECK(model_variables != nullptr);
|
|
|
|
|
CHECK(index_from_key != nullptr);
|
|
|
|
|
CHECK(key_from_index != nullptr);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
const int number_of_variables = static_cast<int>(data_variables.size());
|
|
|
|
|
model_variables->resize(number_of_variables);
|
|
|
|
|
key_from_index->resize(number_of_variables);
|
|
|
|
|
|
|
|
|
|
int index = 0;
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const auto& it : data_variables) {
|
2012-09-13 16:25:28 +00:00
|
|
|
CHECK_LT(index, model_variables->size());
|
2016-10-05 14:08:27 +02:00
|
|
|
(*model_variables)[index] = solver->MakeIntVar(it.second.domain);
|
2023-01-31 20:46:43 +01:00
|
|
|
index_from_key->insert_or_assign(it.first, index);
|
2016-10-05 14:08:27 +02:00
|
|
|
(*key_from_index)[index] = it.first;
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
if ((it.second.initial_position != -1) && (it.second.hard)) {
|
|
|
|
|
CHECK_LT(it.second.mobility_cost, 0);
|
2012-09-13 16:25:28 +00:00
|
|
|
solver->AddConstraint(solver->MakeEquality((*model_variables)[index],
|
2016-10-05 14:08:27 +02:00
|
|
|
it.second.initial_position));
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
index++;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Creates the constraints of the instance from the parsed data.
|
2024-03-25 11:59:02 +01:00
|
|
|
void CreateModelConstraints(absl::Span<const FapConstraint> data_constraints,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<IntVar*>& variables,
|
2023-01-31 20:46:43 +01:00
|
|
|
const absl::btree_map<int, int>& index_from_key,
|
2020-10-29 14:25:39 +01:00
|
|
|
Solver* solver) {
|
2018-04-11 13:47:07 +02:00
|
|
|
CHECK(solver != nullptr);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const FapConstraint& ct : data_constraints) {
|
2018-04-11 13:00:30 +02:00
|
|
|
const int index1 = gtl::FindOrDie(index_from_key, ct.variable1);
|
|
|
|
|
const int index2 = gtl::FindOrDie(index_from_key, ct.variable2);
|
2012-09-13 16:25:28 +00:00
|
|
|
CHECK_LT(index1, variables.size());
|
|
|
|
|
CHECK_LT(index2, variables.size());
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* var1 = variables[index1];
|
|
|
|
|
IntVar* var2 = variables[index2];
|
|
|
|
|
IntVar* absolute_difference =
|
2016-10-05 14:08:27 +02:00
|
|
|
solver->MakeAbs(solver->MakeDifference(var1, var2))->Var();
|
|
|
|
|
if (ct.operation == ">") {
|
|
|
|
|
solver->AddConstraint(solver->MakeGreater(absolute_difference, ct.value));
|
|
|
|
|
} else if (ct.operation == "=") {
|
|
|
|
|
solver->AddConstraint(
|
|
|
|
|
solver->MakeEquality(absolute_difference, ct.value));
|
2012-09-13 16:25:28 +00:00
|
|
|
} else {
|
|
|
|
|
LOG(FATAL) << "Invalid operator detected.";
|
|
|
|
|
return;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// According to the value of a command line flag, chooses the strategy which
|
|
|
|
|
// determines the selection of the variable to be assigned next.
|
2020-10-29 14:25:39 +01:00
|
|
|
void ChooseVariableStrategy(Solver::IntVarStrategy* variable_strategy) {
|
2018-04-11 13:47:07 +02:00
|
|
|
CHECK(variable_strategy != nullptr);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2020-10-21 00:21:54 +02:00
|
|
|
switch (absl::GetFlag(FLAGS_choose_next_variable_strategy)) {
|
2020-10-22 23:36:58 +02:00
|
|
|
case 1: {
|
|
|
|
|
*variable_strategy = Solver::CHOOSE_FIRST_UNBOUND;
|
|
|
|
|
LOG(INFO) << "Using Solver::CHOOSE_FIRST_UNBOUND "
|
|
|
|
|
"for variable selection strategy.";
|
|
|
|
|
break;
|
|
|
|
|
}
|
|
|
|
|
case 2: {
|
|
|
|
|
*variable_strategy = Solver::CHOOSE_MIN_SIZE_LOWEST_MIN;
|
|
|
|
|
LOG(INFO) << "Using Solver::CHOOSE_MIN_SIZE_LOWEST_MIN "
|
|
|
|
|
"for variable selection strategy.";
|
|
|
|
|
break;
|
|
|
|
|
}
|
|
|
|
|
case 3: {
|
|
|
|
|
*variable_strategy = Solver::CHOOSE_MIN_SIZE_HIGHEST_MAX;
|
|
|
|
|
LOG(INFO) << "Using Solver::CHOOSE_MIN_SIZE_HIGHEST_MAX "
|
|
|
|
|
"for variable selection strategy.";
|
|
|
|
|
break;
|
|
|
|
|
}
|
|
|
|
|
case 4: {
|
|
|
|
|
*variable_strategy = Solver::CHOOSE_RANDOM;
|
|
|
|
|
LOG(INFO) << "Using Solver::CHOOSE_RANDOM "
|
|
|
|
|
"for variable selection strategy.";
|
|
|
|
|
break;
|
|
|
|
|
}
|
|
|
|
|
default: {
|
|
|
|
|
LOG(FATAL) << "Should not be here";
|
|
|
|
|
return;
|
|
|
|
|
}
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// According to the values of some command line flags, adds some monitors
|
|
|
|
|
// for the search of the Solver.
|
2020-10-29 14:25:39 +01:00
|
|
|
void CreateAdditionalMonitors(OptimizeVar* const objective, Solver* solver,
|
|
|
|
|
std::vector<SearchMonitor*>* monitors) {
|
2018-04-11 13:47:07 +02:00
|
|
|
CHECK(solver != nullptr);
|
|
|
|
|
CHECK(monitors != nullptr);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
// Search Log
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_log_search)) {
|
2020-10-29 14:25:39 +01:00
|
|
|
SearchMonitor* const log = solver->MakeSearchLog(100000, objective);
|
2012-09-13 16:25:28 +00:00
|
|
|
monitors->push_back(log);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Time Limit
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_time_limit_in_ms) != 0) {
|
|
|
|
|
LOG(INFO) << "Adding time limit of "
|
|
|
|
|
<< absl::GetFlag(FLAGS_time_limit_in_ms) << " ms.";
|
2021-01-14 10:48:19 +01:00
|
|
|
SearchLimit* const limit = solver->MakeTimeLimit(
|
|
|
|
|
absl::Milliseconds(absl::GetFlag(FLAGS_time_limit_in_ms)));
|
2012-09-13 16:25:28 +00:00
|
|
|
monitors->push_back(limit);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Search Restart
|
2020-10-29 14:25:39 +01:00
|
|
|
SearchMonitor* const restart =
|
2020-10-21 00:21:54 +02:00
|
|
|
absl::GetFlag(FLAGS_restart) != -1
|
|
|
|
|
? (absl::GetFlag(FLAGS_luby)
|
|
|
|
|
? solver->MakeLubyRestart(absl::GetFlag(FLAGS_restart))
|
|
|
|
|
: solver->MakeConstantRestart(absl::GetFlag(FLAGS_restart)))
|
2017-04-26 17:30:25 +02:00
|
|
|
: nullptr;
|
2012-09-13 16:25:28 +00:00
|
|
|
if (restart) {
|
|
|
|
|
monitors->push_back(restart);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// The Hard Solver is dealing with finding the solution to feasible
|
|
|
|
|
// instances of the problem with objective either the minimization of
|
|
|
|
|
// the largest frequency assigned or the minimization of the number
|
|
|
|
|
// of frequencies used to the solution.
|
2023-02-01 14:14:30 +01:00
|
|
|
void HardFapSolver(const absl::btree_map<int, FapVariable>& data_variables,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<FapConstraint>& data_constraints,
|
2023-01-31 20:46:43 +01:00
|
|
|
absl::string_view data_objective,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<int>& values) {
|
2016-10-05 14:08:27 +02:00
|
|
|
Solver solver("HardFapSolver");
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<SearchMonitor*> monitors;
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Create Model Variables.
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<IntVar*> variables;
|
2023-01-31 20:46:43 +01:00
|
|
|
absl::btree_map<int, int> index_from_key;
|
2012-09-13 16:25:28 +00:00
|
|
|
std::vector<int> key_from_index;
|
2016-10-05 14:08:27 +02:00
|
|
|
CreateModelVariables(data_variables, &solver, &variables, &index_from_key,
|
|
|
|
|
&key_from_index);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Create Model Constraints.
|
2012-09-13 16:25:28 +00:00
|
|
|
CreateModelConstraints(data_constraints, variables, index_from_key, &solver);
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Order the constraints according to their impact in the instance.
|
|
|
|
|
std::vector<FapConstraint> ordered_constraints(data_constraints);
|
|
|
|
|
std::sort(ordered_constraints.begin(), ordered_constraints.end(),
|
|
|
|
|
ConstraintImpactComparator);
|
|
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<IntVar*> violated_constraints;
|
2016-10-05 14:08:27 +02:00
|
|
|
solver.MakeIntVarArray(ordered_constraints.size(), 0, 0,
|
|
|
|
|
&violated_constraints);
|
|
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
// Objective:
|
|
|
|
|
// Either minimize the largest assigned frequency or
|
2016-10-05 14:08:27 +02:00
|
|
|
// minimize the number of different frequencies assigned.
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* objective_var;
|
|
|
|
|
OptimizeVar* objective;
|
2012-09-13 16:25:28 +00:00
|
|
|
if (data_objective == "Minimize the largest assigned value.") {
|
|
|
|
|
LOG(INFO) << "Minimize the largest assigned value.";
|
|
|
|
|
// The objective_var is set to hold the maximum value assigned
|
|
|
|
|
// in the variables vector.
|
|
|
|
|
objective_var = solver.MakeMax(variables)->Var();
|
|
|
|
|
objective = solver.MakeMinimize(objective_var, 1);
|
|
|
|
|
} else if (data_objective == "Minimize the number of assigned values.") {
|
|
|
|
|
LOG(INFO) << "Minimize the number of assigned values.";
|
|
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<IntVar*> cardinality;
|
2016-10-05 14:08:27 +02:00
|
|
|
solver.MakeIntVarArray(static_cast<int>(values.size()), 0,
|
|
|
|
|
static_cast<int>(variables.size()), &cardinality);
|
2012-09-13 16:25:28 +00:00
|
|
|
solver.AddConstraint(solver.MakeDistribute(variables, values, cardinality));
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<IntVar*> value_not_assigned;
|
2026-01-05 10:51:26 +00:00
|
|
|
value_not_assigned.reserve(values.size());
|
2012-09-13 16:25:28 +00:00
|
|
|
for (int val = 0; val < values.size(); ++val) {
|
2016-10-05 14:08:27 +02:00
|
|
|
value_not_assigned.push_back(
|
|
|
|
|
solver.MakeIsEqualCstVar(cardinality[val], 0));
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
CHECK(!value_not_assigned.empty());
|
|
|
|
|
// The objective_var is set to maximize the number of values
|
|
|
|
|
// that have not been assigned to a variable.
|
|
|
|
|
objective_var = solver.MakeSum(value_not_assigned)->Var();
|
|
|
|
|
objective = solver.MakeMaximize(objective_var, 1);
|
|
|
|
|
} else {
|
|
|
|
|
LOG(FATAL) << "No right objective specified.";
|
|
|
|
|
return;
|
|
|
|
|
}
|
|
|
|
|
monitors.push_back(objective);
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Ordering Builder
|
2020-10-29 14:25:39 +01:00
|
|
|
OrderingBuilder* ob = solver.RevAlloc(
|
2016-10-05 14:08:27 +02:00
|
|
|
new OrderingBuilder(data_variables, ordered_constraints, variables,
|
|
|
|
|
violated_constraints, index_from_key));
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
// Decision Builder Configuration
|
2016-10-05 14:08:27 +02:00
|
|
|
// Choose the next variable selection strategy.
|
2012-09-13 16:25:28 +00:00
|
|
|
Solver::IntVarStrategy variable_strategy;
|
|
|
|
|
ChooseVariableStrategy(&variable_strategy);
|
2016-10-05 14:08:27 +02:00
|
|
|
// Choose the value selection strategy.
|
2020-10-29 14:25:39 +01:00
|
|
|
DecisionBuilder* db;
|
2021-04-02 14:58:16 +02:00
|
|
|
absl::flat_hash_map<int64_t, std::pair<int64_t, int64_t>> history;
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_value_evaluator) == "value_evaluator") {
|
2012-09-13 16:25:28 +00:00
|
|
|
LOG(INFO) << "Using ValueEvaluator for value selection strategy.";
|
2021-04-02 14:58:16 +02:00
|
|
|
Solver::IndexEvaluator2 index_evaluator2 = [&history](int64_t var,
|
|
|
|
|
int64_t value) {
|
2016-11-04 16:26:27 +01:00
|
|
|
return ValueEvaluator(&history, var, value);
|
2020-10-22 23:36:58 +02:00
|
|
|
};
|
2016-11-04 16:26:27 +01:00
|
|
|
LOG(INFO) << "Using ValueEvaluator for value selection strategy.";
|
|
|
|
|
db = solver.MakePhase(variables, variable_strategy, index_evaluator2);
|
2012-09-13 16:25:28 +00:00
|
|
|
} else {
|
|
|
|
|
LOG(INFO) << "Using Solver::ASSIGN_MIN_VALUE for value selection strategy.";
|
2016-10-05 14:08:27 +02:00
|
|
|
db = solver.MakePhase(variables, variable_strategy,
|
2012-09-13 16:25:28 +00:00
|
|
|
Solver::ASSIGN_MIN_VALUE);
|
|
|
|
|
}
|
|
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
DecisionBuilder* final_db = solver.Compose(ob, db);
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// Create Additional Monitors.
|
2012-09-13 16:25:28 +00:00
|
|
|
CreateAdditionalMonitors(objective, &solver, &monitors);
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Collector
|
2020-10-29 14:25:39 +01:00
|
|
|
SolutionCollector* const collector = solver.MakeLastSolutionCollector();
|
2016-10-05 14:08:27 +02:00
|
|
|
collector->Add(variables);
|
|
|
|
|
collector->Add(objective_var);
|
|
|
|
|
monitors.push_back(collector);
|
|
|
|
|
|
|
|
|
|
// Solve.
|
2012-09-13 16:25:28 +00:00
|
|
|
LOG(INFO) << "Solving...";
|
2021-04-02 14:58:16 +02:00
|
|
|
const int64_t time1 = solver.wall_time();
|
2016-10-05 14:08:27 +02:00
|
|
|
solver.Solve(final_db, monitors);
|
2021-04-02 14:58:16 +02:00
|
|
|
const int64_t time2 = solver.wall_time();
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Display Time.
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_display_time)) {
|
2012-09-13 16:25:28 +00:00
|
|
|
PrintElapsedTime(time1, time2);
|
|
|
|
|
}
|
2016-10-05 14:08:27 +02:00
|
|
|
// Display Results.
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_display_results)) {
|
2016-10-05 14:08:27 +02:00
|
|
|
PrintResultsHard(collector, variables, objective_var, data_variables,
|
|
|
|
|
data_constraints, index_from_key, key_from_index);
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Splits variables of the instance to hard and soft.
|
2023-06-21 17:31:06 +02:00
|
|
|
void SplitVariablesHardSoft(
|
|
|
|
|
const absl::btree_map<int, FapVariable>& data_variables,
|
|
|
|
|
absl::btree_map<int, FapVariable>* hard_variables,
|
|
|
|
|
absl::btree_map<int, FapVariable>* soft_variables) {
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const auto& it : data_variables) {
|
2016-10-05 14:08:27 +02:00
|
|
|
if (it.second.initial_position != -1) {
|
|
|
|
|
if (it.second.hard) {
|
|
|
|
|
CHECK_LT(it.second.mobility_cost, 0);
|
2023-01-31 20:46:43 +01:00
|
|
|
hard_variables->insert_or_assign(it.first, it.second);
|
2016-10-05 14:08:27 +02:00
|
|
|
} else {
|
|
|
|
|
CHECK_GE(it.second.mobility_cost, 0);
|
2023-01-31 20:46:43 +01:00
|
|
|
soft_variables->insert_or_assign(it.first, it.second);
|
2016-10-05 14:08:27 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Splits constraints of the instance to hard and soft.
|
2024-03-25 11:59:02 +01:00
|
|
|
void SplitConstraintHardSoft(absl::Span<const FapConstraint> data_constraints,
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<FapConstraint>* hard_constraints,
|
|
|
|
|
std::vector<FapConstraint>* soft_constraints) {
|
|
|
|
|
for (const FapConstraint& ct : data_constraints) {
|
2016-10-05 14:08:27 +02:00
|
|
|
if (ct.hard) {
|
|
|
|
|
CHECK_LT(ct.weight_cost, 0);
|
|
|
|
|
hard_constraints->push_back(ct);
|
|
|
|
|
} else {
|
|
|
|
|
CHECK_GE(ct.weight_cost, 0);
|
|
|
|
|
soft_constraints->push_back(ct);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Penalize the modification of the initial position of soft variable of
|
|
|
|
|
// the instance.
|
2020-10-22 23:36:58 +02:00
|
|
|
void PenalizeVariablesViolation(
|
2023-02-01 14:14:30 +01:00
|
|
|
const absl::btree_map<int, FapVariable>& soft_variables,
|
2023-01-31 20:46:43 +01:00
|
|
|
const absl::btree_map<int, int>& index_from_key,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<IntVar*>& variables, std::vector<IntVar*>* cost,
|
|
|
|
|
Solver* solver) {
|
|
|
|
|
for (const auto& it : soft_variables) {
|
2018-04-11 13:00:30 +02:00
|
|
|
const int index = gtl::FindOrDie(index_from_key, it.first);
|
2016-10-05 14:08:27 +02:00
|
|
|
CHECK_LT(index, variables.size());
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* const displaced = solver->MakeIsDifferentCstVar(
|
2016-10-05 14:08:27 +02:00
|
|
|
variables[index], it.second.initial_position);
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* const weight =
|
2016-10-05 14:08:27 +02:00
|
|
|
solver->MakeProd(displaced, it.second.mobility_cost)->Var();
|
|
|
|
|
cost->push_back(weight);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Penalize the violation of soft constraints of the instance.
|
2016-11-16 18:20:16 +01:00
|
|
|
void PenalizeConstraintsViolation(
|
2024-03-25 11:59:02 +01:00
|
|
|
absl::Span<const FapConstraint> constraints,
|
|
|
|
|
absl::Span<const FapConstraint> soft_constraints,
|
2023-01-31 20:46:43 +01:00
|
|
|
const absl::btree_map<int, int>& index_from_key,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<IntVar*>& variables, std::vector<IntVar*>* cost,
|
|
|
|
|
std::vector<IntVar*>* violated_constraints, Solver* solver) {
|
2016-10-05 14:08:27 +02:00
|
|
|
int violated_constraints_index = 0;
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const FapConstraint& ct : constraints) {
|
2016-10-05 14:08:27 +02:00
|
|
|
CHECK_LT(violated_constraints_index, violated_constraints->size());
|
|
|
|
|
if (!ct.hard) {
|
|
|
|
|
// The violated_constraints_index will stop at the first soft constraint.
|
|
|
|
|
break;
|
|
|
|
|
}
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* const hard_violation = solver->MakeIntVar(0, 0);
|
2016-10-05 14:08:27 +02:00
|
|
|
(*violated_constraints)[violated_constraints_index] = hard_violation;
|
|
|
|
|
violated_constraints_index++;
|
|
|
|
|
}
|
|
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const FapConstraint& ct : soft_constraints) {
|
2018-04-11 13:00:30 +02:00
|
|
|
const int index1 = gtl::FindOrDie(index_from_key, ct.variable1);
|
|
|
|
|
const int index2 = gtl::FindOrDie(index_from_key, ct.variable2);
|
2016-10-05 14:08:27 +02:00
|
|
|
CHECK_LT(index1, variables.size());
|
|
|
|
|
CHECK_LT(index2, variables.size());
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* const absolute_difference =
|
2020-10-22 23:36:58 +02:00
|
|
|
solver
|
|
|
|
|
->MakeAbs(
|
|
|
|
|
solver->MakeDifference(variables[index1], variables[index2]))
|
|
|
|
|
->Var();
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* violation = nullptr;
|
2016-10-05 14:08:27 +02:00
|
|
|
if (ct.operation == ">") {
|
|
|
|
|
violation = solver->MakeIsLessCstVar(absolute_difference, ct.value);
|
|
|
|
|
} else if (ct.operation == "=") {
|
|
|
|
|
violation = solver->MakeIsDifferentCstVar(absolute_difference, ct.value);
|
|
|
|
|
} else {
|
|
|
|
|
LOG(FATAL) << "Invalid operator detected.";
|
|
|
|
|
}
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* const weight = solver->MakeProd(violation, ct.weight_cost)->Var();
|
2016-10-05 14:08:27 +02:00
|
|
|
cost->push_back(weight);
|
|
|
|
|
CHECK_LT(violated_constraints_index, violated_constraints->size());
|
|
|
|
|
(*violated_constraints)[violated_constraints_index] = violation;
|
|
|
|
|
violated_constraints_index++;
|
|
|
|
|
}
|
|
|
|
|
CHECK_EQ(violated_constraints->size(), constraints.size());
|
|
|
|
|
}
|
|
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
// The Soft Solver is dealing with the optimization of unfeasible instances
|
|
|
|
|
// and aims to minimize the total cost of violated constraints. Returning value
|
2016-10-05 14:08:27 +02:00
|
|
|
// equal to 0 denotes that the instance is feasible.
|
2023-02-01 14:14:30 +01:00
|
|
|
int SoftFapSolver(const absl::btree_map<int, FapVariable>& data_variables,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<FapConstraint>& data_constraints,
|
2023-06-21 17:31:06 +02:00
|
|
|
absl::string_view /*data_objective*/,
|
2024-03-25 11:59:02 +01:00
|
|
|
absl::Span<const int> /*values*/) {
|
2016-10-05 14:08:27 +02:00
|
|
|
Solver solver("SoftFapSolver");
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<SearchMonitor*> monitors;
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Split variables to hard and soft.
|
2023-02-01 14:14:30 +01:00
|
|
|
absl::btree_map<int, FapVariable> hard_variables;
|
|
|
|
|
absl::btree_map<int, FapVariable> soft_variables;
|
2016-10-05 14:08:27 +02:00
|
|
|
SplitVariablesHardSoft(data_variables, &hard_variables, &soft_variables);
|
|
|
|
|
|
|
|
|
|
// Order instance's constraints by their impact and then split them to
|
|
|
|
|
// hard and soft.
|
|
|
|
|
std::vector<FapConstraint> ordered_constraints(data_constraints);
|
|
|
|
|
std::sort(ordered_constraints.begin(), ordered_constraints.end(),
|
|
|
|
|
ConstraintImpactComparator);
|
2012-09-13 16:25:28 +00:00
|
|
|
std::vector<FapConstraint> hard_constraints;
|
|
|
|
|
std::vector<FapConstraint> soft_constraints;
|
2016-10-05 14:08:27 +02:00
|
|
|
SplitConstraintHardSoft(ordered_constraints, &hard_constraints,
|
|
|
|
|
&soft_constraints);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Create Model Variables.
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<IntVar*> variables;
|
2023-01-31 20:46:43 +01:00
|
|
|
absl::btree_map<int, int> index_from_key;
|
2012-09-13 16:25:28 +00:00
|
|
|
std::vector<int> key_from_index;
|
2016-10-05 14:08:27 +02:00
|
|
|
CreateModelVariables(data_variables, &solver, &variables, &index_from_key,
|
|
|
|
|
&key_from_index);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Create Model Constraints.
|
2012-09-13 16:25:28 +00:00
|
|
|
CreateModelConstraints(hard_constraints, variables, index_from_key, &solver);
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Penalize variable and constraint violations.
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<IntVar*> cost;
|
|
|
|
|
std::vector<IntVar*> violated_constraints(ordered_constraints.size(),
|
|
|
|
|
nullptr);
|
2016-10-05 14:08:27 +02:00
|
|
|
PenalizeVariablesViolation(soft_variables, index_from_key, variables, &cost,
|
|
|
|
|
&solver);
|
|
|
|
|
PenalizeConstraintsViolation(ordered_constraints, soft_constraints,
|
|
|
|
|
index_from_key, variables, &cost,
|
|
|
|
|
&violated_constraints, &solver);
|
|
|
|
|
|
|
|
|
|
// Objective
|
|
|
|
|
// Minimize the sum of violation penalties.
|
2020-10-29 14:25:39 +01:00
|
|
|
IntVar* objective_var = solver.MakeSum(cost)->Var();
|
|
|
|
|
OptimizeVar* objective = solver.MakeMinimize(objective_var, 1);
|
2012-09-13 16:25:28 +00:00
|
|
|
monitors.push_back(objective);
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Ordering Builder
|
2020-10-29 14:25:39 +01:00
|
|
|
OrderingBuilder* ob = solver.RevAlloc(
|
2016-10-05 14:08:27 +02:00
|
|
|
new OrderingBuilder(data_variables, ordered_constraints, variables,
|
|
|
|
|
violated_constraints, index_from_key));
|
|
|
|
|
|
|
|
|
|
// Decision Builder Configuration
|
|
|
|
|
// Choose the next variable selection strategy.
|
2020-10-29 14:25:39 +01:00
|
|
|
DecisionBuilder* db;
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_variable_evaluator) == "variable_evaluator") {
|
2016-10-05 14:08:27 +02:00
|
|
|
LOG(INFO) << "Using VariableEvaluator for variable selection strategy and "
|
|
|
|
|
"Solver::ASSIGN_MIN_VALUE for value selection strategy.";
|
2020-10-22 23:36:58 +02:00
|
|
|
Solver::IndexEvaluator1 var_evaluator = [&key_from_index,
|
2021-04-02 14:58:16 +02:00
|
|
|
&data_variables](int64_t index) {
|
2016-10-05 14:08:27 +02:00
|
|
|
return VariableEvaluator(key_from_index, data_variables, index);
|
2020-10-22 23:36:58 +02:00
|
|
|
};
|
2016-10-05 14:08:27 +02:00
|
|
|
db = solver.MakePhase(variables, var_evaluator, Solver::ASSIGN_MIN_VALUE);
|
|
|
|
|
} else {
|
|
|
|
|
LOG(INFO) << "Using Solver::CHOOSE_FIRST_UNBOUND for variable selection "
|
|
|
|
|
"strategy and Solver::ASSIGN_MIN_VALUE for value selection "
|
|
|
|
|
"strategy.";
|
|
|
|
|
db = solver.MakePhase(variables, Solver::CHOOSE_FIRST_UNBOUND,
|
|
|
|
|
Solver::ASSIGN_MIN_VALUE);
|
|
|
|
|
}
|
2020-10-29 14:25:39 +01:00
|
|
|
DecisionBuilder* final_db = solver.Compose(ob, db);
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// Create Additional Monitors.
|
|
|
|
|
CreateAdditionalMonitors(objective, &solver, &monitors);
|
|
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
// Collector
|
2020-10-29 14:25:39 +01:00
|
|
|
SolutionCollector* const collector = solver.MakeLastSolutionCollector();
|
2012-09-13 16:25:28 +00:00
|
|
|
collector->Add(variables);
|
|
|
|
|
collector->Add(objective_var);
|
|
|
|
|
monitors.push_back(collector);
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Solve.
|
2012-09-13 16:25:28 +00:00
|
|
|
LOG(INFO) << "Solving...";
|
2021-04-02 14:58:16 +02:00
|
|
|
const int64_t time1 = solver.wall_time();
|
2016-10-05 14:08:27 +02:00
|
|
|
solver.Solve(final_db, monitors);
|
2021-04-02 14:58:16 +02:00
|
|
|
const int64_t time2 = solver.wall_time();
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
int violation_sum =
|
|
|
|
|
collector->Value(collector->solution_count() - 1, objective_var);
|
|
|
|
|
// Display Time.
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_display_time)) {
|
2012-09-13 16:25:28 +00:00
|
|
|
PrintElapsedTime(time1, time2);
|
|
|
|
|
}
|
2016-10-05 14:08:27 +02:00
|
|
|
// Display Results.
|
2020-10-21 00:21:54 +02:00
|
|
|
if (absl::GetFlag(FLAGS_display_results)) {
|
2016-10-05 14:08:27 +02:00
|
|
|
PrintResultsSoft(collector, variables, objective_var, hard_variables,
|
|
|
|
|
hard_constraints, soft_variables, soft_constraints,
|
|
|
|
|
index_from_key, key_from_index);
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
return violation_sum;
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
|
2023-02-01 14:14:30 +01:00
|
|
|
void SolveProblem(const absl::btree_map<int, FapVariable>& variables,
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<FapConstraint>& constraints,
|
2023-06-21 17:31:06 +02:00
|
|
|
absl::string_view objective, const std::vector<int>& values,
|
2016-10-05 14:08:27 +02:00
|
|
|
bool soft) {
|
|
|
|
|
// Print Instance!
|
|
|
|
|
FapModelPrinter model_printer(variables, constraints, objective, values);
|
|
|
|
|
model_printer.PrintFapObjective();
|
|
|
|
|
model_printer.PrintFapVariables();
|
|
|
|
|
model_printer.PrintFapConstraints();
|
|
|
|
|
model_printer.PrintFapValues();
|
|
|
|
|
// Create Model & Solve!
|
|
|
|
|
if (!soft) {
|
|
|
|
|
LOG(INFO) << "Running HardFapSolver";
|
|
|
|
|
HardFapSolver(variables, constraints, objective, values);
|
|
|
|
|
} else {
|
|
|
|
|
LOG(INFO) << "Running SoftFapSolver";
|
|
|
|
|
int violation = SoftFapSolver(variables, constraints, objective, values);
|
|
|
|
|
if (violation == 0) {
|
|
|
|
|
LOG(INFO) << "The instance is feasible. "
|
|
|
|
|
"Now the HardFapSolver will be executed.";
|
|
|
|
|
LOG(INFO) << "Running HardFapSolver";
|
|
|
|
|
HardFapSolver(variables, constraints, objective, values);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
} // namespace operations_research
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
int main(int argc, char** argv) {
|
2023-01-31 20:46:43 +01:00
|
|
|
InitGoogle(argv[0], &argc, &argv, true);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2020-10-21 00:21:54 +02:00
|
|
|
CHECK(!absl::GetFlag(FLAGS_directory).empty())
|
|
|
|
|
<< "Requires --directory=<directory name>";
|
2012-09-13 16:25:28 +00:00
|
|
|
|
2020-10-21 00:21:54 +02:00
|
|
|
LOG(INFO) << "Solving instance in directory "
|
|
|
|
|
<< absl::GetFlag(FLAGS_directory);
|
2012-09-13 16:25:28 +00:00
|
|
|
// Parse!
|
2023-02-01 14:14:30 +01:00
|
|
|
absl::btree_map<int, operations_research::FapVariable> variables;
|
2012-09-13 16:25:28 +00:00
|
|
|
std::vector<operations_research::FapConstraint> constraints;
|
2016-10-05 14:08:27 +02:00
|
|
|
std::string objective;
|
2012-09-13 16:25:28 +00:00
|
|
|
std::vector<int> values;
|
2018-10-31 16:18:18 +01:00
|
|
|
absl::flat_hash_map<int, operations_research::FapComponent> components;
|
2020-10-21 00:21:54 +02:00
|
|
|
operations_research::ParseInstance(
|
|
|
|
|
absl::GetFlag(FLAGS_directory), absl::GetFlag(FLAGS_find_components),
|
|
|
|
|
&variables, &constraints, &objective, &values, &components);
|
|
|
|
|
if (!absl::GetFlag(FLAGS_find_components)) {
|
2016-10-05 14:08:27 +02:00
|
|
|
operations_research::SolveProblem(variables, constraints, objective, values,
|
2020-10-21 00:21:54 +02:00
|
|
|
absl::GetFlag(FLAGS_soft));
|
2012-09-13 16:25:28 +00:00
|
|
|
} else {
|
2016-10-05 14:08:27 +02:00
|
|
|
int component_id = 1;
|
|
|
|
|
LOG(INFO) << "Number of components in the RLFAP graph "
|
|
|
|
|
<< components.size();
|
2020-10-29 14:25:39 +01:00
|
|
|
for (const auto& component : components) {
|
2016-10-05 14:08:27 +02:00
|
|
|
LOG(INFO) << "Solving Component " << component_id;
|
|
|
|
|
operations_research::SolveProblem(component.second.variables,
|
|
|
|
|
component.second.constraints, objective,
|
2020-10-21 00:21:54 +02:00
|
|
|
values, absl::GetFlag(FLAGS_soft));
|
2016-10-05 14:08:27 +02:00
|
|
|
component_id++;
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
|
|
|
|
}
|
2018-11-07 09:52:37 +01:00
|
|
|
return EXIT_SUCCESS;
|
2012-09-13 16:25:28 +00:00
|
|
|
}
|
