Expand description
This library provides a metaheuristic framework for solving combinatorial optimization problems.
§Overview
§Metaheuristics
The following metaheuristics are included:
- local search (with recursion and several neighborhood exploration strategies, supports recursion for multiple modifactions in one step)
- parallel local search (the neighborhood is explored in
parallel using
rayon, supports recursion) - threshold accepting
- simulated annealing
- tabu search (and a faster parallel version)
§Hierarchical Objective
The framework supports hierarchical objective, i.e., objectives that consists of multiple levels of linear combinations. The first level is first minimized and only for tie-breaks the next level is considered. This is useful to model hard-constraints as high-priority soft-constraints (via a violation measure), such that normally infeasible solutions are considered feasible. The solver than minimizes these constraints first until the violation is zero and then starts to optimize the remaining objective levels.
§Examples
As an example we provide a simple implementation of the Traveling Salesman Problem (TSP) with the 3-opt neighborhood.
§How to use this library (step-by-step example)
Suppose you have given a combinatorial optimization problem and defined a solution type. To run a local search solver you need to do the following four steps:
- Define the
Objectivefor your problem by definingIndicatorsand build a hierarchical objective ofLinearCombinationsof these indicators. - Define modifications for your solution type. The solution type should not be mutable, instead a modified clone should be returned.
- Implement the
Neighborhoodfor the local search. - Initialize the
LocalSearchSolverand run it.
We demonstrate these steps on a simple (but totally artificial) example, where the solution type consists of a fixed-size vector of integers.
struct Solution(Vec<i64>);§1. Define the Objective for your problem.
For the example, we want to find permutation (i.e., 0 to 10 should appear exactly once) where the sum of squared differences between consecutive elements (cyclic) is minimized.
Hence, we define two Indicators, namely PermutationViolation and
SquaredDifference, and build a hierarchical
objective where PermutationViolation is minimized first and only for tie-breaks
SquaredDifference is considered.
use rapid_solve::objective::{BaseValue, Indicator, Objective};
struct PermutationViolation;
impl Indicator<Solution> for PermutationViolation {
fn evaluate(&self, solution: &Solution) -> BaseValue {
let violation: i64 = (0..solution.0.len())
.map(|i| (solution.0.iter().filter(|&n| *n == i as i64).count() as i64 - 1).abs())
.sum();
BaseValue::Integer(violation)
}
fn name(&self) -> String {
String::from("PermutationViolation")
}
}
struct SquaredDifference;
impl Indicator<Solution> for SquaredDifference {
fn evaluate(&self, solution: &Solution) -> BaseValue {
let squared_diff: i64 = (0..solution.0.len())
.map(|i| (solution.0[i] - solution.0[(i + 1) % solution.0.len()]).pow(2))
.sum();
BaseValue::Integer(squared_diff)
}
fn name(&self) -> String {
String::from("SquaredDifference")
}
}
fn build_objective() -> Objective<Solution> {
Objective::new_single_indicator_per_level(vec![
Box::new(PermutationViolation),
Box::new(SquaredDifference),
])
}§2. Define modifications for your solution type.
In our example we use two modifications:
- Changing one entry to a number between 0 and 10.
- Swapping two entries.
The solution type should not be mutable, instead a modified clone should be returned.
For larger solution types the immutable data structures crate im might increase
performance.
impl Solution {
fn change_entry(&self, index: usize, new_value: i64) -> Self {
let mut new_values = self.0.clone();
new_values[index] = new_value;
Solution(new_values)
}
fn swap(&self, index1: usize, index2: usize) -> Self {
let mut new_values = self.0.clone();
new_values.swap(index1, index2);
Solution(new_values)
}
}§3. Implement the Neighborhood.
In our example we want to first try to change all entries and then try all swaps.
use rapid_solve::heuristics::common::Neighborhood;
struct ChangeEntryThenSwapNeighborhood;
impl Neighborhood<Solution> for ChangeEntryThenSwapNeighborhood {
fn neighbors_of<'a>(
&'a self,
solution: &'a Solution,
) -> Box<dyn Iterator<Item = Solution> + Send + Sync + 'a> {
let change_entry = (0..solution.0.len()).flat_map(move |i| {
(0..10).map(move |new_value| solution.change_entry(i, new_value))
});
let swap = (0..solution.0.len())
.flat_map(move |i| (0..solution.0.len()).map(move |j| solution.swap(i, j)));
Box::new(change_entry.chain(swap))
}
}§4. Initialize the LocalSearchSolver and run it.
In the example only a local optimum is found, which is worse than the global optimum.
use rapid_solve::heuristics::Solver;
use rapid_solve::heuristics::local_search::LocalSearchSolver;
use std::sync::Arc;
let objective = Arc::new(build_objective());
let neighborhood = Arc::new(ChangeEntryThenSwapNeighborhood);
let solver = LocalSearchSolver::initialize(neighborhood, objective);
let initial_solution = Solution(vec![0; 10]);
let evaluated_local_minimum = solver.solve(initial_solution);
assert_eq!(
*evaluated_local_minimum.objective_value().as_vec(),
vec![BaseValue::Integer(0), BaseValue::Integer(36)]
);
assert_eq!(
*evaluated_local_minimum.solution().0,
vec![1, 0, 2, 4, 5, 7, 9, 8, 6, 3]
);
// one global optimum is [0, 2, 4, 6, 8, 9, 7, 5, 3, 1] with a squared differences of 34.For a more less artificial demonstration, we refer to the tsp-example.