use std::marker::PhantomData;
use std::path::Path;
use std::sync::Arc;
use burn::tensor::activation::softmax;
use burn::tensor::backend::Backend;
use burn::tensor::{Distribution, Int, Tensor};
use rand::rngs::StdRng;
use crate::destroy::{DestroyKind, DestroyOperator};
use crate::mdd::arena::MddCompilationConfig;
use crate::modelling::Problem;
use crate::modelling::Solution;
use crate::neural::consformer::{ConsFormer, ConsFormerBatch, ConsFormerConfig};
use crate::neural::{Batch, Network, load_network};
use crate::sampling::DecodeMode;
use crate::utils::tensor::{rows_to_tensor, to_rows};
use super::repair::{BatchRepair, MddRepair};
use super::{
LocalSearch, SearchArchitecture, SearchConfig, SearchState, SolveConfig, destroy_rows,
row_seeds, run_batched,
};
#[derive(Debug, Clone)]
pub struct NeuralPriorSearchConfig {
pub destroy_kind: DestroyKind,
pub destroy_fraction: f64,
pub stochastic: bool,
pub temperature: f64,
}
impl Default for NeuralPriorSearchConfig {
fn default() -> Self {
Self {
destroy_kind: DestroyKind::default(),
destroy_fraction: 1.0,
stochastic: false,
temperature: 1.0,
}
}
}
#[derive(Debug, Clone)]
pub struct NeuralPriorBpSearchConfig {
pub destroy_kind: DestroyKind,
pub destroy_fraction: f64,
pub stochastic: bool,
pub bp_iterations: usize,
}
impl Default for NeuralPriorBpSearchConfig {
fn default() -> Self {
Self {
destroy_kind: DestroyKind::default(),
destroy_fraction: 1.0,
stochastic: false,
bp_iterations: 1,
}
}
}
struct Core<B: Backend, Ba, N> {
network: N,
destroy_op: Box<dyn DestroyOperator>,
device: B::Device,
batch: PhantomData<fn() -> Ba>,
}
struct Proposal<B: Backend> {
destroyed: Vec<Vec<usize>>,
current: Tensor<B, 2, Int>,
destroy_mask: Tensor<B, 2, Int>,
logits: Tensor<B, 3>,
}
impl<B, Ba, N> Core<B, Ba, N>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba>,
{
fn propose(
&self,
problems: &[Arc<Problem>],
assignments: &[Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
) -> Proposal<B> {
let rows = problems.len();
let n = problems[0].number_variables();
let destroyed = destroy_rows(
self.destroy_op.as_ref(),
problems,
assignments,
pending,
rng,
);
let mut mask_data = vec![0i64; rows * n];
for (row, free) in destroyed.iter().enumerate() {
for &var in free {
mask_data[row * n + var] = 1;
}
}
let destroy_mask: Tensor<B, 2, Int> =
Tensor::<B, 1, Int>::from_data(mask_data.as_slice(), &self.device).reshape([rows, n]);
let current = rows_to_tensor(assignments, n, &self.device);
let batch = Ba::for_assignments(
problems,
current.clone(),
destroy_mask.clone(),
&self.device,
);
let logits = self.network.forward(&batch);
Proposal {
destroyed,
current,
destroy_mask,
logits,
}
}
}
enum Decoder {
Argmax,
Sampling {
temperature: f64,
},
}
impl Decoder {
fn decode<B: Backend>(
&self,
logits: Tensor<B, 3>,
destroy_mask: Tensor<B, 2, Int>,
current: Tensor<B, 2, Int>,
) -> Tensor<B, 2, Int> {
let proposed: Tensor<B, 2, Int> = match self {
Decoder::Argmax => logits.argmax(2).squeeze_dim(2),
Decoder::Sampling { temperature } => {
let device = logits.device();
let u = Tensor::<B, 3>::random(
logits.dims(),
Distribution::Uniform(1e-20, 1.0),
&device,
);
let neg_log_u = -u.log(); let gumbel = -neg_log_u.log(); let scaled = logits.div_scalar(*temperature) + gumbel;
scaled.argmax(2).squeeze_dim(2)
}
};
current.mask_where(destroy_mask.equal_elem(1), proposed)
}
}
pub struct NeuralPriorSearch<B: Backend, Ba, N> {
core: Core<B, Ba, N>,
decoder: Decoder,
}
impl<B, Ba, N> NeuralPriorSearch<B, Ba, N>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba>,
{
pub fn new(network: N, config: &NeuralPriorSearchConfig, device: B::Device) -> Self {
Self {
core: Core {
network,
destroy_op: config.destroy_kind.build(config.destroy_fraction),
device,
batch: PhantomData,
},
decoder: if config.stochastic {
Decoder::Sampling {
temperature: config.temperature,
}
} else {
Decoder::Argmax
},
}
}
}
impl<B, Ba, N> SearchArchitecture for NeuralPriorSearch<B, Ba, N>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba>,
{
fn setup<'a>(&'a self, problems: &[Arc<Problem>]) -> Result<Box<dyn SearchState + 'a>, String> {
Ba::check_problems(problems)?;
Ok(Box::new(NeuralPriorState { search: self }))
}
}
struct NeuralPriorState<'a, B: Backend, Ba, N> {
search: &'a NeuralPriorSearch<B, Ba, N>,
}
impl<B, Ba, N> SearchState for NeuralPriorState<'_, B, Ba, N>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba>,
{
fn step(
&mut self,
problems: &[Arc<Problem>],
assignments: &mut [Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
) {
let proposal = self
.search
.core
.propose(problems, assignments, pending, rng);
let next =
self.search
.decoder
.decode(proposal.logits, proposal.destroy_mask, proposal.current);
let n = assignments.first().map_or(0, Vec::len);
for (row, values) in assignments
.iter_mut()
.zip(to_rows(&next, problems.len(), n))
{
*row = values;
}
}
}
pub struct NeuralPriorBpSearch<B: Backend, Ba, N> {
core: Core<B, Ba, N>,
bp_iterations: usize,
mode: DecodeMode,
}
impl<B, Ba, N> NeuralPriorBpSearch<B, Ba, N>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba>,
{
pub fn new(network: N, config: &NeuralPriorBpSearchConfig, device: B::Device) -> Self {
Self {
core: Core {
network,
destroy_op: config.destroy_kind.build(config.destroy_fraction),
device,
batch: PhantomData,
},
bp_iterations: config.bp_iterations,
mode: if config.stochastic {
DecodeMode::Sample
} else {
DecodeMode::Greedy
},
}
}
}
impl<B, Ba, N> SearchArchitecture for NeuralPriorBpSearch<B, Ba, N>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba>,
{
fn setup<'a>(&'a self, problems: &[Arc<Problem>]) -> Result<Box<dyn SearchState + 'a>, String> {
Ba::check_problems(problems)?;
let repair = MddRepair::new(
MddCompilationConfig::default(),
MddRepair::domain_size_covering(problems),
self.mode,
self.bp_iterations,
);
Ok(Box::new(NeuralPriorBpState {
search: self,
repair: BatchRepair::new(repair, problems),
}))
}
}
struct NeuralPriorBpState<'a, B: Backend, Ba, N> {
search: &'a NeuralPriorBpSearch<B, Ba, N>,
repair: BatchRepair,
}
impl<B, Ba, N> SearchState for NeuralPriorBpState<'_, B, Ba, N>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba>,
{
fn step(
&mut self,
problems: &[Arc<Problem>],
assignments: &mut [Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
) {
let proposal = self
.search
.core
.propose(problems, assignments, pending, rng);
let seeds = row_seeds(problems.len(), rng);
let [_, n, domain_width] = proposal.logits.dims();
let probs: Vec<f32> = softmax(proposal.logits, 2)
.into_data()
.to_vec::<f32>()
.expect("softmax output should be f32-convertible");
self.repair.repair_rows(
problems,
assignments,
&proposal.destroyed,
&seeds,
|row, variable, value| {
if value < domain_width {
probs[row * n * domain_width + variable * domain_width + value] as f64
} else {
0.0
}
},
);
}
fn solved(&mut self, solved: &[bool]) {
self.repair.solved(solved);
}
fn retain(&mut self, keep: &[bool]) {
self.repair.retain(keep);
}
}
pub(super) fn solve_with_consformer(
problems: &[Arc<Problem>],
config: &SolveConfig,
checkpoint_dir: Option<&Path>,
seed: u64,
) -> Result<Vec<Solution>, String> {
let dir = checkpoint_dir.ok_or("a neural search needs a checkpoint_dir")?;
crate::neural::dispatch_backend!(
inference,
solve_with_checkpoint,
problems,
config,
dir,
seed
)
}
fn solve_with_checkpoint<B: Backend>(
device: B::Device,
problems: &[Arc<Problem>],
config: &SolveConfig,
dir: &Path,
seed: u64,
) -> Result<Vec<Solution>, String> {
ConsFormerBatch::<B>::check_problems(problems)?;
let (_, network) =
load_network::<B, ConsFormerConfig>(dir, problems, &device).map_err(|e| {
format!(
"failed to load network from checkpoint {}: {e}",
dir.display()
)
})?;
solve_with_network::<B, ConsFormerBatch<B>, ConsFormer<B>>(
network, device, problems, config, seed,
)
}
pub fn solve_with_network<B, Ba, N>(
network: N,
device: B::Device,
problems: &[Arc<Problem>],
config: &SolveConfig,
seed: u64,
) -> Result<Vec<Solution>, String>
where
B: Backend,
Ba: Batch<B>,
N: Network<B, Ba> + 'static,
{
let engine = match &config.search {
SearchConfig::NeuralPrior(c) => LocalSearch::new(Box::new(
NeuralPriorSearch::<B, Ba, N>::new(network, c, device),
)),
SearchConfig::NeuralPriorBp(c) => LocalSearch::new(Box::new(
NeuralPriorBpSearch::<B, Ba, N>::new(network, c, device),
)),
SearchConfig::BeliefPropagation(_) => {
return Err("the belief-propagation search uses no network".to_string());
}
};
run_batched(&engine, problems, config.batch_size, config.budget, seed)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::all_different;
use crate::local_search::{Budget, LocalSearch};
use crate::neural::NetworkConfig;
use crate::neural::consformer::{ConsFormer, ConsFormerBatch, ConsFormerConfig};
use burn::backend::NdArray;
use burn::backend::ndarray::NdArrayDevice;
type Net = ConsFormer<NdArray>;
type Batch = ConsFormerBatch<NdArray>;
fn clique(size: usize, colours: usize) -> Arc<Problem> {
let mut problem = Problem::default();
let vars = problem.add_variables(size, (0..colours as isize).collect());
all_different(&mut problem, vars);
Arc::new(problem)
}
fn network(problems: &[Arc<Problem>]) -> Net {
let config = ConsFormerConfig::new(3, 4, 4, 1, 4, 0, 0.5, 1.0).with_num_layers(1);
NetworkConfig::<NdArray>::init(&config, problems, &NdArrayDevice::default())
}
fn engines(problems: &[Arc<Problem>]) -> Vec<LocalSearch> {
let device = NdArrayDevice::default();
let prior = NeuralPriorSearch::<NdArray, Batch, Net>::new(
network(problems),
&NeuralPriorSearchConfig::default(),
device,
);
let with_bp = NeuralPriorBpSearch::<NdArray, Batch, Net>::new(
network(problems),
&NeuralPriorBpSearchConfig::default(),
device,
);
vec![
LocalSearch::new(Box::new(prior)),
LocalSearch::new(Box::new(with_bp)),
]
}
#[test]
fn both_refuse_problems_with_different_numbers_of_variables() {
let problems = vec![clique(3, 3), clique(4, 3)];
for engine in engines(&problems[..1]) {
let error = engine
.run(&problems, Budget::default(), 0, None)
.expect_err("the problems cannot be searched together");
assert!(error.contains("same number of variables"), "{error}");
}
}
#[test]
fn both_stay_in_the_domain_over_a_batch() {
let problems = vec![clique(3, 3), clique(3, 3)];
for engine in engines(&problems) {
let budget = Budget {
iteration_limit: 30,
..Budget::default()
};
let solutions = engine.run(&problems, budget, 0, None).unwrap();
assert_eq!(solutions.len(), 2);
for solution in solutions {
if let Some(values) = solution.assignment() {
assert!(values.iter().all(|v| (0..3).contains(v)));
}
}
}
}
#[test]
fn decoding_only_changes_the_flagged_positions() {
let device = NdArrayDevice::default();
let logits = Tensor::<NdArray, 3>::from_data(
burn::tensor::TensorData::new([0.0f32, 0.0, 1.0].repeat(3), [1, 3, 3]),
&device,
);
let mask = Tensor::<NdArray, 2, Int>::from_data([[1, 0, 1]], &device);
let current = Tensor::<NdArray, 2, Int>::from_data([[0, 1, 0]], &device);
let next = Decoder::Argmax.decode(logits, mask, current);
let values: Vec<i64> = next.into_data().to_vec().unwrap();
assert_eq!(values, [2, 1, 2]);
}
}