use std::sync::Arc;
use burn::data::dataloader::batcher::Batcher;
use burn::data::dataset::Dataset;
use burn::prelude::ElementConversion;
use burn::tensor::backend::Backend;
use burn::tensor::{Bool, Int, Tensor};
use rand::rngs::StdRng;
use rand::{RngExt, SeedableRng};
use rayon::prelude::*;
use crate::destroy::DestroyOperator;
use crate::modelling::{Problem, VariableIndex};
use crate::neural::Batch;
use super::ConsFormerInputs;
struct ConsFormerMaskData {
number_vars: usize,
flat_attention_mask: Vec<bool>,
is_var: Vec<bool>,
}
fn consformer_mask_data(problem: &Problem) -> ConsFormerMaskData {
let n = problem.number_variables();
let mut flat_attention_mask = vec![false; n * n];
for i in 0..n {
flat_attention_mask[i * n + i] = true;
}
for constraint in problem.iter_constraints() {
let scope = problem[constraint]
.iter_scope()
.collect::<Vec<VariableIndex>>();
for i in 0..scope.len() {
let u = *scope[i];
for v in scope.iter().skip(i + 1).copied() {
flat_attention_mask[u * n + *v] = true;
flat_attention_mask[*v * n + u] = true;
}
}
}
let is_var = problem
.iter_variables()
.map(|v| problem[v].domain_size() > 1)
.collect::<Vec<bool>>();
ConsFormerMaskData {
number_vars: n,
flat_attention_mask,
is_var,
}
}
impl ConsFormerMaskData {
fn into_tensors<B: Backend>(
self,
device: &B::Device,
) -> (Tensor<B, 2, Bool>, Tensor<B, 1, Bool>) {
let n = self.number_vars;
let attention_mask: Tensor<B, 2, Bool> =
Tensor::<B, 1, Bool>::from_data(self.flat_attention_mask.as_slice(), device)
.reshape([n, n]);
let var_mask = Tensor::from_data(self.is_var.as_slice(), device);
(attention_mask, var_mask)
}
}
pub(crate) fn consformer_masks<B: Backend>(
problem: &Problem,
device: &B::Device,
) -> (Tensor<B, 2, Bool>, Tensor<B, 1, Bool>) {
consformer_mask_data(problem).into_tensors::<B>(device)
}
#[derive(Clone)]
pub struct ConsFormerSample<B: Backend> {
problem: Arc<Problem>,
attention_mask: Tensor<B, 2, Bool>,
var_mask: Tensor<B, 1, Bool>,
}
impl<B: Backend> std::fmt::Debug for ConsFormerSample<B> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("ConsFormerSample")
.field("number_vars", &self.problem.number_variables())
.field("attention_mask", &self.attention_mask)
.field("var_mask", &self.var_mask)
.finish()
}
}
pub struct ConsFormerDataset<B: Backend> {
samples: Vec<ConsFormerSample<B>>,
}
impl<B: Backend> ConsFormerDataset<B> {
pub fn new(problems: Vec<Arc<Problem>>, device: &B::Device) -> Self {
let mask_data: Vec<ConsFormerMaskData> = crate::utils::worker_pool().install(|| {
problems
.par_iter()
.map(|problem| consformer_mask_data(problem))
.collect()
});
let samples = problems
.into_iter()
.zip(mask_data)
.map(|(problem, mask_data)| {
let (attention_mask, var_mask) = mask_data.into_tensors::<B>(device);
ConsFormerSample {
problem,
attention_mask,
var_mask,
}
})
.collect();
Self { samples }
}
}
impl<B: Backend> Dataset<ConsFormerSample<B>> for ConsFormerDataset<B> {
fn get(&self, index: usize) -> Option<ConsFormerSample<B>> {
self.samples.get(index).cloned()
}
fn len(&self) -> usize {
self.samples.len()
}
}
pub(crate) fn try_shared_number_variables(problems: &[Arc<Problem>]) -> Result<usize, String> {
let n = problems
.first()
.ok_or("a ConsFormer batch needs at least one problem")?
.number_variables();
if problems.iter().any(|p| p.number_variables() != n) {
return Err(
"ConsFormer needs every problem of a batch to have the same number of variables"
.to_string(),
);
}
Ok(n)
}
pub(super) fn shared_number_variables(problems: &[Arc<Problem>]) -> usize {
try_shared_number_variables(problems).unwrap_or_else(|e| panic!("{e}"))
}
fn stack_masks_and_sample_assignments<B: Backend>(
attention_mask_tensors: Vec<Tensor<B, 2, Bool>>,
var_mask_tensors: &[Tensor<B, 1, Bool>],
problems: &[Arc<Problem>],
mask_fraction: f64,
destroy: Option<&dyn DestroyOperator>,
device: &B::Device,
) -> (Tensor<B, 3, Bool>, Tensor<B, 2, Bool>, Tensor<B, 2, Int>) {
let attention_masks = Tensor::stack(attention_mask_tensors, 0);
let n = shared_number_variables(problems);
let (var_masks_data, init) = match destroy {
None => {
let masks = random_var_masks::<B>(var_mask_tensors, mask_fraction);
(masks, sample_initial_assignments(problems))
}
Some(destroy) => {
let init = sample_initial_assignments(problems);
(destroyed_var_masks(destroy, problems, &init, n), init)
}
};
let var_masks: Tensor<B, 2, Bool> =
Tensor::<B, 1, Bool>::from_data(var_masks_data.as_slice(), device)
.reshape([problems.len(), n]);
let assignments: Tensor<B, 2, Int> =
Tensor::<B, 1, Int>::from_data(init.as_slice(), device).reshape([problems.len(), n]);
(attention_masks, var_masks, assignments)
}
fn random_var_masks<B: Backend>(
var_mask_tensors: &[Tensor<B, 1, Bool>],
mask_fraction: f64,
) -> Vec<bool> {
let mut var_masks_data: Vec<bool> = Vec::new();
crate::utils::with_rng(|rng| {
for var_mask in var_mask_tensors {
let candidates: Vec<i64> = var_mask
.clone()
.int()
.into_data()
.to_vec::<B::IntElem>()
.expect("var mask should convert to int")
.into_iter()
.map(|v| v.elem::<i64>())
.collect();
var_masks_data.extend(
candidates
.into_iter()
.map(|is_candidate| is_candidate != 0 && rng.random_bool(mask_fraction)),
);
}
});
var_masks_data
}
fn sample_initial_assignments(problems: &[Arc<Problem>]) -> Vec<i64> {
problems
.iter()
.flat_map(|problem| {
crate::sampling::random_assignment(problem)
.into_iter()
.map(|value| value as i64)
})
.collect()
}
fn destroyed_var_masks(
destroy: &dyn DestroyOperator,
problems: &[Arc<Problem>],
init: &[i64],
n: usize,
) -> Vec<bool> {
let seeds: Vec<u64> =
crate::utils::with_rng(|rng| (0..problems.len()).map(|_| rng.random::<u64>()).collect());
let selected: Vec<Vec<usize>> = crate::utils::worker_pool().install(|| {
problems
.par_iter()
.zip(seeds.par_iter())
.enumerate()
.map(|(i, (problem, &seed))| {
let row: Vec<isize> = init[i * n..(i + 1) * n]
.iter()
.map(|&v| v as isize)
.collect();
let mut rng = StdRng::seed_from_u64(seed);
destroy.destroy(problem, &row, &mut rng)
})
.collect()
});
let mut masks = vec![false; problems.len() * n];
for (i, vars) in selected.into_iter().enumerate() {
for var in vars {
masks[i * n + var] = true;
}
}
masks
}
#[derive(Clone)]
pub struct ConsFormerBatcher {
pub mask_fraction: f64,
pub destroy: Option<Arc<dyn DestroyOperator>>,
}
#[derive(Clone)]
pub struct ConsFormerBatch<B: Backend> {
pub attention_masks: Tensor<B, 3, Bool>,
pub var_masks: Tensor<B, 2, Bool>,
pub problems: Vec<Arc<Problem>>,
pub assignments: Tensor<B, 2, Int>,
}
impl<B: Backend> std::fmt::Debug for ConsFormerBatch<B> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("ConsFormerBatch")
.field("attention_masks", &self.attention_masks)
.field("var_masks", &self.var_masks)
.field("problems", &format!("{} problem(s)", self.problems.len()))
.finish()
}
}
impl<B: Backend> Batcher<B, ConsFormerSample<B>, ConsFormerBatch<B>> for ConsFormerBatcher {
fn batch(&self, samples: Vec<ConsFormerSample<B>>, device: &B::Device) -> ConsFormerBatch<B> {
let attention_mask_tensors: Vec<Tensor<B, 2, Bool>> =
samples.iter().map(|s| s.attention_mask.clone()).collect();
let var_mask_tensors: Vec<Tensor<B, 1, Bool>> =
samples.iter().map(|s| s.var_mask.clone()).collect();
let problems: Vec<Arc<Problem>> = samples.into_iter().map(|s| s.problem).collect();
let (attention_masks, var_masks, assignments) = stack_masks_and_sample_assignments(
attention_mask_tensors,
&var_mask_tensors,
&problems,
self.mask_fraction,
self.destroy.as_deref(),
device,
);
ConsFormerBatch {
assignments,
attention_masks,
var_masks,
problems,
}
}
}
impl<B: Backend> ConsFormerInputs<B> for ConsFormerBatch<B> {
fn attention_masks(&self) -> Tensor<B, 3, Bool> {
self.attention_masks.clone()
}
}
impl<B: Backend> Batch<B> for ConsFormerBatch<B> {
fn problems(&self) -> &[Arc<Problem>] {
&self.problems
}
fn assignments(&self) -> Tensor<B, 2, Int> {
self.assignments.clone()
}
fn var_masks(&self) -> Tensor<B, 2, Bool> {
self.var_masks.clone()
}
fn check_problems(problems: &[Arc<Problem>]) -> Result<(), String> {
try_shared_number_variables(problems).map(|_| ())
}
fn decode(&self, logits: Tensor<B, 3>) -> Vec<Vec<isize>> {
let proposed: Tensor<B, 2, Int> = logits.argmax(2).squeeze_dim(2);
let assignment: Tensor<B, 2, Int> = self
.assignments
.clone()
.mask_where(self.var_masks.clone(), proposed);
let row_width = assignment.dims()[1];
let values: Vec<isize> = assignment
.into_data()
.to_vec::<B::IntElem>()
.expect("decoded assignment should be an integer tensor")
.into_iter()
.map(|v| v.elem::<i64>() as isize)
.collect();
values
.chunks(row_width)
.zip(&self.problems)
.map(|(row, problem)| row[..problem.number_variables()].to_vec())
.collect()
}
fn for_assignments(
problems: &[Arc<Problem>],
assignments: Tensor<B, 2, Int>,
destroy_mask: Tensor<B, 2, Int>,
device: &B::Device,
) -> Self {
shared_number_variables(problems);
let attention_masks = Tensor::cat(
problems
.iter()
.map(|problem| {
let (attention_mask, _) = consformer_masks::<B>(problem, device);
attention_mask.unsqueeze::<3>()
})
.collect(),
0,
);
ConsFormerBatch {
assignments,
attention_masks,
var_masks: destroy_mask.equal_elem(1),
problems: problems.to_vec(),
}
}
}
#[cfg(test)]
mod destroy_tests {
use super::*;
use crate::constraints::not_equals;
use burn::backend::ndarray::{NdArray, NdArrayDevice};
struct OnlyFirst;
impl DestroyOperator for OnlyFirst {
fn destroy(&self, _: &Problem, _: &[isize], _: &mut StdRng) -> Vec<usize> {
vec![0]
}
}
fn batch_with(destroy: Option<Arc<dyn DestroyOperator>>) -> ConsFormerBatch<NdArray> {
let device = NdArrayDevice::default();
let problems: Vec<Arc<Problem>> = (0..4)
.map(|_| {
let mut problem = Problem::default();
let vars: Vec<_> = (0..3)
.map(|_| problem.add_variable(vec![0, 1, 2]))
.collect();
not_equals(&mut problem, vars[0], vars[1]);
not_equals(&mut problem, vars[1], vars[2]);
Arc::new(problem)
})
.collect();
let dataset = ConsFormerDataset::<NdArray>::new(problems, &device);
let samples: Vec<_> = (0..dataset.len())
.map(|i| dataset.get(i).unwrap())
.collect();
ConsFormerBatcher {
mask_fraction: 1.0,
destroy,
}
.batch(samples, &device)
}
#[test]
fn a_training_destroy_operator_decides_which_variables_are_masked() {
let batch = batch_with(Some(Arc::new(OnlyFirst)));
let masks: Vec<bool> = batch.var_masks.into_data().to_vec().unwrap();
assert_eq!(masks, [true, false, false].repeat(4),);
}
#[test]
fn without_a_destroy_operator_the_mask_fraction_decides() {
let batch = batch_with(None);
let masks: Vec<bool> = batch.var_masks.into_data().to_vec().unwrap();
assert!(masks.iter().all(|&m| m));
}
#[test]
fn decode_takes_the_network_choice_only_where_variables_are_masked() {
let device = NdArrayDevice::default();
let batch = batch_with(Some(Arc::new(OnlyFirst)));
let logits = Tensor::<NdArray, 3>::from_data(
burn::tensor::TensorData::new([0.0f32, 0.0, 1.0].repeat(12), [4, 3, 3]),
&device,
);
let current: Vec<i64> = batch
.assignments()
.into_data()
.to_vec()
.expect("integer assignments");
let rows = batch.decode(logits);
assert_eq!(rows.len(), 4);
for (i, row) in rows.iter().enumerate() {
assert_eq!(row[0], 2);
assert_eq!(
row[1..],
[current[i * 3 + 1] as isize, current[i * 3 + 2] as isize]
);
}
}
}