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
|
|
|
// Reading and parsing the data of Frequency Assignment Problem
|
|
|
|
|
// Format: http://www.inra.fr/mia/T/schiex/Doc/CELAR.shtml#synt
|
|
|
|
|
|
2025-11-05 11:34:49 +01:00
|
|
|
#ifndef ORTOOLS_EXAMPLES_FAP_PARSER_H_
|
|
|
|
|
#define ORTOOLS_EXAMPLES_FAP_PARSER_H_
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
#include <string>
|
|
|
|
|
#include <vector>
|
2020-09-23 11:45:03 +02:00
|
|
|
|
2023-06-21 17:31:06 +02:00
|
|
|
#include "absl/container/btree_map.h"
|
2018-10-31 16:18:18 +01:00
|
|
|
#include "absl/container/flat_hash_map.h"
|
2025-02-25 16:03:40 +01:00
|
|
|
#include "absl/strings/string_view.h"
|
2025-12-01 10:22:54 +01:00
|
|
|
#include "absl/types/span.h"
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
namespace operations_research {
|
|
|
|
|
|
|
|
|
|
// Takes a filename and a buffer and fills the lines buffer
|
|
|
|
|
// with the lines of the file corresponding to the filename.
|
2025-02-25 16:03:40 +01:00
|
|
|
void ParseFileByLines(absl::string_view filename,
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<std::string>* lines);
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
// The FapVariable struct represents a radio link of the
|
|
|
|
|
// frequency assignment problem.
|
|
|
|
|
struct FapVariable {
|
2016-10-05 14:08:27 +02:00
|
|
|
// Fields:
|
|
|
|
|
// the index of a subset of all available frequencies of the instance
|
2021-08-23 14:46:12 +02:00
|
|
|
int domain_index = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the number of the frequencies available for the link
|
2021-08-23 14:46:12 +02:00
|
|
|
int domain_size = 0;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the link's domain, i.e. a finite set of frequencies that can be
|
|
|
|
|
// assigned to this link
|
|
|
|
|
std::vector<int> domain;
|
|
|
|
|
|
|
|
|
|
// the number of constraints in which the link appears
|
2021-08-23 14:46:12 +02:00
|
|
|
int degree = 0;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// if positive, it means that the link has already been assigned a frequency
|
|
|
|
|
// of that value
|
2021-08-23 14:46:12 +02:00
|
|
|
int initial_position = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the index of mobility cost
|
2021-08-23 14:46:12 +02:00
|
|
|
int mobility_index = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the cost of modification of a link's pre-assigned value
|
2021-08-23 14:46:12 +02:00
|
|
|
int mobility_cost = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// if true, it means that the link's pre-assigned position cannot be modified
|
2021-08-23 14:46:12 +02:00
|
|
|
bool hard = false;
|
2012-09-13 16:25:28 +00:00
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// The FapConstraint struct represents a constraint between two
|
|
|
|
|
// radio links of the frequency assignment problem.
|
|
|
|
|
struct FapConstraint {
|
2016-10-05 14:08:27 +02:00
|
|
|
// Fields:
|
|
|
|
|
// the index of the first variable appearing in the constraint
|
2021-08-23 14:46:12 +02:00
|
|
|
int variable1 = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the index of the second variable appearing in the constraint
|
2021-08-23 14:46:12 +02:00
|
|
|
int variable2 = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the importance of a constraint based on the degree of its variables,
|
|
|
|
|
// the operator used in the constraint ("=" or ">") and whether it is a hard
|
|
|
|
|
// or soft constraint and with what weight cost.
|
|
|
|
|
// impact = (max_degree + min_degree + operator_impact + hardness_impact)
|
2021-08-23 14:46:12 +02:00
|
|
|
int impact = 0;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the constraint type (D (difference), C (viscosity), F (fixed),P (prefix)
|
|
|
|
|
// or L (far fields)) which is not used in practice
|
|
|
|
|
std::string type;
|
|
|
|
|
|
|
|
|
|
// the operator used in the constraint ("=" or ">")
|
|
|
|
|
std::string operation;
|
|
|
|
|
|
|
|
|
|
// the constraint deviation: it defines the constant k12 mentioned in RLFAP
|
|
|
|
|
// description
|
2021-08-23 14:46:12 +02:00
|
|
|
int value = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the index of weight cost
|
2021-08-23 14:46:12 +02:00
|
|
|
int weight_index = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the cost of not satisfaction of the constraint
|
2021-08-23 14:46:12 +02:00
|
|
|
int weight_cost = -1;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// if true, it means that the constraint must be satisfied
|
2021-08-23 14:46:12 +02:00
|
|
|
bool hard = false;
|
2016-10-05 14:08:27 +02:00
|
|
|
};
|
|
|
|
|
|
2023-06-21 17:31:06 +02:00
|
|
|
// The FapComponent struct represents a component of the RLFAP graph.
|
2016-10-05 14:08:27 +02:00
|
|
|
// It models an independent sub-problem of the initial instance.
|
|
|
|
|
struct FapComponent {
|
|
|
|
|
// Fields:
|
|
|
|
|
// the variable set of the sub-problem, i.e. the vertices of the component
|
2023-02-01 14:14:30 +01:00
|
|
|
absl::btree_map<int, FapVariable> variables;
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// the constraint set of the sub-problem, i.e. the edges of the component
|
|
|
|
|
std::vector<FapConstraint> constraints;
|
2012-09-13 16:25:28 +00:00
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// Parser of the var.txt file.
|
|
|
|
|
// This file describes all the variables in the instance.
|
|
|
|
|
// Each line corresponds to one variable.
|
|
|
|
|
class VariableParser {
|
2020-10-22 23:36:58 +02:00
|
|
|
public:
|
2020-10-29 14:25:39 +01:00
|
|
|
explicit VariableParser(const std::string& data_directory);
|
2025-01-06 13:20:57 +01:00
|
|
|
|
|
|
|
|
// This type is neither copyable nor movable.
|
|
|
|
|
VariableParser(const VariableParser&) = delete;
|
|
|
|
|
VariableParser& operator=(const VariableParser&) = delete;
|
|
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
~VariableParser();
|
|
|
|
|
|
2023-06-21 17:31:06 +02:00
|
|
|
const absl::btree_map<int, FapVariable>& variables() const {
|
|
|
|
|
return variables_;
|
|
|
|
|
}
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
void Parse();
|
|
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
private:
|
2016-10-05 14:08:27 +02:00
|
|
|
const std::string filename_;
|
|
|
|
|
// A map is used because in the model, the variables have ids which may not
|
|
|
|
|
// be consecutive, may be very sparse and don't have a specific upper-bound.
|
|
|
|
|
// The key of the map, is the link's id.
|
2023-02-01 14:14:30 +01:00
|
|
|
absl::btree_map<int, FapVariable> variables_;
|
2012-09-13 16:25:28 +00:00
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// Parser of the dom.txt file.
|
|
|
|
|
// This file describes the domains used by the variables of the problem.
|
|
|
|
|
// Each line describes one domain.
|
|
|
|
|
class DomainParser {
|
2020-10-22 23:36:58 +02:00
|
|
|
public:
|
2020-10-29 14:25:39 +01:00
|
|
|
explicit DomainParser(const std::string& data_directory);
|
2025-01-06 13:20:57 +01:00
|
|
|
|
|
|
|
|
// This type is neither copyable nor movable.
|
|
|
|
|
DomainParser(const DomainParser&) = delete;
|
|
|
|
|
DomainParser& operator=(const DomainParser&) = delete;
|
|
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
~DomainParser();
|
|
|
|
|
|
2023-06-21 17:31:06 +02:00
|
|
|
const absl::btree_map<int, std::vector<int> >& domains() const {
|
|
|
|
|
return domains_;
|
|
|
|
|
}
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
void Parse();
|
|
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
private:
|
2016-10-05 14:08:27 +02:00
|
|
|
const std::string filename_;
|
|
|
|
|
// A map is used because in the model, the ids of the different available
|
|
|
|
|
// domains may be random values, since they are used as names. The key of the
|
|
|
|
|
// map is the subset's id.
|
2023-02-01 14:14:30 +01:00
|
|
|
absl::btree_map<int, std::vector<int> > domains_;
|
2012-09-13 16:25:28 +00:00
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// Parse ctr.txt file.
|
|
|
|
|
// This file describes the constraints of the instance.
|
|
|
|
|
// Each line defines a binary constraint.
|
|
|
|
|
class ConstraintParser {
|
2020-10-22 23:36:58 +02:00
|
|
|
public:
|
2020-10-29 14:25:39 +01:00
|
|
|
explicit ConstraintParser(const std::string& data_directory);
|
2025-01-06 13:20:57 +01:00
|
|
|
|
|
|
|
|
// This type is neither copyable nor movable.
|
|
|
|
|
ConstraintParser(const ConstraintParser&) = delete;
|
|
|
|
|
ConstraintParser& operator=(const ConstraintParser&) = delete;
|
|
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
~ConstraintParser();
|
|
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<FapConstraint>& constraints() const { return constraints_; }
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
void Parse();
|
|
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
private:
|
2016-10-05 14:08:27 +02:00
|
|
|
const std::string filename_;
|
2012-09-13 16:25:28 +00:00
|
|
|
std::vector<FapConstraint> constraints_;
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// Parse cst.txt file.
|
|
|
|
|
// This file defines the criterion on which the solution will be based.
|
|
|
|
|
// It may also contain 8 coefficients: 4 for different constraint violation
|
|
|
|
|
// costs and 4 for different variable mobility costs.
|
|
|
|
|
class ParametersParser {
|
2020-10-22 23:36:58 +02:00
|
|
|
public:
|
2020-10-29 14:25:39 +01:00
|
|
|
explicit ParametersParser(const std::string& data_directory);
|
2012-09-13 16:25:28 +00:00
|
|
|
~ParametersParser();
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
std::string objective() const { return objective_; }
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<int>& constraint_weights() const {
|
2016-11-16 18:20:16 +01:00
|
|
|
return constraint_weights_;
|
|
|
|
|
}
|
2020-10-29 14:25:39 +01:00
|
|
|
const std::vector<int>& variable_weights() const { return variable_weights_; }
|
2012-09-13 16:25:28 +00:00
|
|
|
|
|
|
|
|
void Parse();
|
|
|
|
|
|
2020-10-22 23:36:58 +02:00
|
|
|
private:
|
2016-10-05 14:08:27 +02:00
|
|
|
const std::string filename_;
|
2023-06-21 17:31:06 +02:00
|
|
|
static constexpr int kConstraintCoefficientNo = 4;
|
|
|
|
|
static constexpr int kVariableCoefficientNo = 4;
|
|
|
|
|
static constexpr int kCoefficientNo = 8;
|
2016-10-05 14:08:27 +02:00
|
|
|
std::string objective_;
|
2012-09-13 16:25:28 +00:00
|
|
|
std::vector<int> constraint_weights_;
|
|
|
|
|
std::vector<int> variable_weights_;
|
|
|
|
|
};
|
|
|
|
|
|
2016-10-05 14:08:27 +02:00
|
|
|
// Function that finds the disjoint sub-graphs of the graph of the instance.
|
2025-12-01 10:22:54 +01:00
|
|
|
void FindComponents(absl::Span<const FapConstraint> constraints,
|
2023-02-01 14:14:30 +01:00
|
|
|
const absl::btree_map<int, FapVariable>& variables,
|
2023-06-21 17:31:06 +02:00
|
|
|
int maximum_variable_id,
|
2020-10-29 14:25:39 +01:00
|
|
|
absl::flat_hash_map<int, FapComponent>* components);
|
2016-10-05 14:08:27 +02:00
|
|
|
|
|
|
|
|
// Function that computes the impact of a constraint.
|
2023-02-01 14:14:30 +01:00
|
|
|
int EvaluateConstraintImpact(const absl::btree_map<int, FapVariable>& variables,
|
2023-06-21 17:31:06 +02:00
|
|
|
int max_weight_cost, FapConstraint constraint);
|
2016-10-05 14:08:27 +02:00
|
|
|
|
2012-09-13 16:25:28 +00:00
|
|
|
// Function that parses an instance of frequency assignment problem.
|
2020-10-29 14:25:39 +01:00
|
|
|
void ParseInstance(const std::string& data_directory, bool find_components,
|
2023-02-01 14:14:30 +01:00
|
|
|
absl::btree_map<int, FapVariable>* variables,
|
2020-10-29 14:25:39 +01:00
|
|
|
std::vector<FapConstraint>* constraints,
|
|
|
|
|
std::string* objective, std::vector<int>* frequencies,
|
|
|
|
|
absl::flat_hash_map<int, FapComponent>* components);
|
2020-10-22 23:36:58 +02:00
|
|
|
} // namespace operations_research
|
2025-11-05 11:34:49 +01:00
|
|
|
#endif // ORTOOLS_EXAMPLES_FAP_PARSER_H_
|
