quantrs2_anneal/
csp_compiler.rs

1//! Constraint Satisfaction Problem (CSP) compiler
2//!
3//! This module provides a compiler that translates constraint satisfaction problems
4//! into QUBO formulations that can be solved using quantum annealing.
5
6use std::collections::{HashMap, HashSet};
7use std::fmt;
8use thiserror::Error;
9
10use crate::ising::QuboModel;
11use crate::qubo::{QuboBuilder, QuboFormulation};
12
13/// Errors that can occur during CSP compilation
14#[derive(Error, Debug)]
15pub enum CspError {
16    /// Invalid variable definition
17    #[error("Invalid variable: {0}")]
18    InvalidVariable(String),
19
20    /// Invalid constraint definition
21    #[error("Invalid constraint: {0}")]
22    InvalidConstraint(String),
23
24    /// Compilation failed
25    #[error("Compilation failed: {0}")]
26    CompilationFailed(String),
27
28    /// Unsupported constraint type
29    #[error("Unsupported constraint type: {0}")]
30    UnsupportedConstraint(String),
31
32    /// Domain error
33    #[error("Domain error: {0}")]
34    DomainError(String),
35}
36
37/// Result type for CSP operations
38pub type CspResult<T> = Result<T, CspError>;
39
40/// Variable domain specification
41#[derive(Debug, Clone, PartialEq, Eq)]
42pub enum Domain {
43    /// Boolean domain {0, 1}
44    Boolean,
45
46    /// Integer range [min, max]
47    IntegerRange { min: i32, max: i32 },
48
49    /// Discrete set of values
50    Discrete(Vec<i32>),
51
52    /// Finite set of strings/labels
53    Categorical(Vec<String>),
54}
55
56impl Domain {
57    /// Get the size of the domain
58    #[must_use]
59    pub fn size(&self) -> usize {
60        match self {
61            Self::Boolean => 2,
62            Self::IntegerRange { min, max } => ((max - min + 1) as usize).max(0),
63            Self::Discrete(values) => values.len(),
64            Self::Categorical(labels) => labels.len(),
65        }
66    }
67
68    /// Check if a value is in the domain
69    #[must_use]
70    pub fn contains(&self, value: &CspValue) -> bool {
71        match (self, value) {
72            (Self::Boolean, CspValue::Boolean(_)) => true,
73            (Self::IntegerRange { min, max }, CspValue::Integer(v)) => v >= min && v <= max,
74            (Self::Discrete(values), CspValue::Integer(v)) => values.contains(v),
75            (Self::Categorical(labels), CspValue::String(s)) => labels.contains(s),
76            _ => false,
77        }
78    }
79
80    /// Convert to list of values
81    pub fn values(&self) -> Vec<CspValue> {
82        match self {
83            Self::Boolean => vec![CspValue::Boolean(false), CspValue::Boolean(true)],
84            Self::IntegerRange { min, max } => (*min..=*max).map(CspValue::Integer).collect(),
85            Self::Discrete(values) => values.iter().map(|&v| CspValue::Integer(v)).collect(),
86            Self::Categorical(labels) => {
87                labels.iter().map(|s| CspValue::String(s.clone())).collect()
88            }
89        }
90    }
91}
92
93/// CSP variable value
94#[derive(Debug, Clone, PartialEq, Eq, Hash)]
95pub enum CspValue {
96    Boolean(bool),
97    Integer(i32),
98    String(String),
99}
100
101impl fmt::Display for CspValue {
102    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
103        match self {
104            Self::Boolean(b) => write!(f, "{b}"),
105            Self::Integer(i) => write!(f, "{i}"),
106            Self::String(s) => write!(f, "{s}"),
107        }
108    }
109}
110
111/// CSP variable definition
112#[derive(Debug, Clone)]
113pub struct CspVariable {
114    /// Variable name
115    pub name: String,
116
117    /// Variable domain
118    pub domain: Domain,
119
120    /// Variable description
121    pub description: Option<String>,
122}
123
124impl CspVariable {
125    /// Create a new CSP variable
126    #[must_use]
127    pub const fn new(name: String, domain: Domain) -> Self {
128        Self {
129            name,
130            domain,
131            description: None,
132        }
133    }
134
135    /// Add description to the variable
136    #[must_use]
137    pub fn with_description(mut self, description: String) -> Self {
138        self.description = Some(description);
139        self
140    }
141}
142
143/// CSP constraint types
144pub enum CspConstraint {
145    /// All different constraint: all variables must have different values
146    AllDifferent { variables: Vec<String> },
147
148    /// Linear constraint: sum of weighted variables with comparison
149    Linear {
150        terms: Vec<(String, f64)>, // (variable, coefficient)
151        comparison: ComparisonOp,
152        rhs: f64,
153    },
154
155    /// Exactly one constraint: exactly one variable is true/active
156    ExactlyOne { variables: Vec<String> },
157
158    /// At most one constraint: at most one variable is true/active
159    AtMostOne { variables: Vec<String> },
160
161    /// Element constraint: var\\[index\\] = value
162    Element {
163        array_var: String,
164        index_var: String,
165        value_var: String,
166    },
167
168    /// Global cardinality constraint
169    GlobalCardinality {
170        variables: Vec<String>,
171        values: Vec<CspValue>,
172        min_counts: Vec<usize>,
173        max_counts: Vec<usize>,
174    },
175
176    /// Table constraint: allowed/forbidden tuples
177    Table {
178        variables: Vec<String>,
179        tuples: Vec<Vec<CspValue>>,
180        allowed: bool, // true for allowed, false for forbidden
181    },
182
183    /// Custom constraint with penalty function
184    Custom {
185        name: String,
186        variables: Vec<String>,
187        penalty_function: Box<dyn Fn(&HashMap<String, CspValue>) -> f64 + Send + Sync>,
188    },
189}
190
191impl fmt::Debug for CspConstraint {
192    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
193        match self {
194            Self::AllDifferent { variables } => f
195                .debug_struct("AllDifferent")
196                .field("variables", variables)
197                .finish(),
198            Self::Linear {
199                terms,
200                comparison,
201                rhs,
202            } => f
203                .debug_struct("Linear")
204                .field("terms", terms)
205                .field("comparison", comparison)
206                .field("rhs", rhs)
207                .finish(),
208            Self::ExactlyOne { variables } => f
209                .debug_struct("ExactlyOne")
210                .field("variables", variables)
211                .finish(),
212            Self::AtMostOne { variables } => f
213                .debug_struct("AtMostOne")
214                .field("variables", variables)
215                .finish(),
216            Self::Element {
217                array_var,
218                index_var,
219                value_var,
220            } => f
221                .debug_struct("Element")
222                .field("array_var", array_var)
223                .field("index_var", index_var)
224                .field("value_var", value_var)
225                .finish(),
226            Self::GlobalCardinality {
227                variables,
228                values,
229                min_counts,
230                max_counts,
231            } => f
232                .debug_struct("GlobalCardinality")
233                .field("variables", variables)
234                .field("values", values)
235                .field("min_counts", min_counts)
236                .field("max_counts", max_counts)
237                .finish(),
238            Self::Table {
239                variables,
240                tuples,
241                allowed,
242            } => f
243                .debug_struct("Table")
244                .field("variables", variables)
245                .field("tuples", tuples)
246                .field("allowed", allowed)
247                .finish(),
248            Self::Custom {
249                name, variables, ..
250            } => f
251                .debug_struct("Custom")
252                .field("name", name)
253                .field("variables", variables)
254                .field("penalty_function", &"<function>")
255                .finish(),
256        }
257    }
258}
259
260/// Comparison operators for linear constraints
261#[derive(Debug, Clone, PartialEq, Eq)]
262pub enum ComparisonOp {
263    Equal,
264    LessEqual,
265    GreaterEqual,
266    Less,
267    Greater,
268}
269
270/// CSP problem definition
271#[derive(Debug)]
272pub struct CspProblem {
273    /// Variables in the problem
274    variables: HashMap<String, CspVariable>,
275
276    /// Constraints in the problem
277    constraints: Vec<CspConstraint>,
278
279    /// Objective function (optional)
280    objective: Option<CspObjective>,
281
282    /// Compilation parameters
283    compilation_params: CompilationParams,
284}
285
286/// CSP objective function
287pub enum CspObjective {
288    /// Minimize/maximize linear combination of variables
289    Linear {
290        terms: Vec<(String, f64)>,
291        minimize: bool,
292    },
293
294    /// Minimize/maximize custom function
295    Custom {
296        function: Box<dyn Fn(&HashMap<String, CspValue>) -> f64 + Send + Sync>,
297        minimize: bool,
298    },
299}
300
301impl fmt::Debug for CspObjective {
302    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
303        match self {
304            Self::Linear { terms, minimize } => f
305                .debug_struct("Linear")
306                .field("terms", terms)
307                .field("minimize", minimize)
308                .finish(),
309            Self::Custom { minimize, .. } => f
310                .debug_struct("Custom")
311                .field("function", &"<function>")
312                .field("minimize", minimize)
313                .finish(),
314        }
315    }
316}
317
318/// Parameters for CSP compilation
319#[derive(Debug, Clone)]
320pub struct CompilationParams {
321    /// Penalty weight for constraint violations
322    pub constraint_penalty: f64,
323
324    /// Use logarithmic encoding for large domains
325    pub use_log_encoding: bool,
326
327    /// Maximum domain size for one-hot encoding
328    pub max_onehot_size: usize,
329
330    /// Slack variable penalty for inequality constraints
331    pub slack_penalty: f64,
332}
333
334impl Default for CompilationParams {
335    fn default() -> Self {
336        Self {
337            constraint_penalty: 10.0,
338            use_log_encoding: true,
339            max_onehot_size: 16,
340            slack_penalty: 1.0,
341        }
342    }
343}
344
345/// CSP solution
346#[derive(Debug, Clone)]
347pub struct CspSolution {
348    /// Variable assignments
349    pub assignments: HashMap<String, CspValue>,
350
351    /// Objective value (if any)
352    pub objective_value: Option<f64>,
353
354    /// Constraint violations
355    pub violations: Vec<ConstraintViolation>,
356
357    /// QUBO objective value
358    pub qubo_objective: f64,
359}
360
361/// Constraint violation information
362#[derive(Debug, Clone)]
363pub struct ConstraintViolation {
364    /// Constraint index
365    pub constraint_index: usize,
366
367    /// Violation description
368    pub description: String,
369
370    /// Penalty incurred
371    pub penalty: f64,
372}
373
374impl CspProblem {
375    /// Create a new CSP problem
376    #[must_use]
377    pub fn new() -> Self {
378        Self {
379            variables: HashMap::new(),
380            constraints: Vec::new(),
381            objective: None,
382            compilation_params: CompilationParams::default(),
383        }
384    }
385
386    /// Add a variable to the problem
387    pub fn add_variable(&mut self, variable: CspVariable) -> CspResult<()> {
388        if self.variables.contains_key(&variable.name) {
389            return Err(CspError::InvalidVariable(format!(
390                "Variable '{}' already exists",
391                variable.name
392            )));
393        }
394
395        self.variables.insert(variable.name.clone(), variable);
396        Ok(())
397    }
398
399    /// Add a constraint to the problem
400    pub fn add_constraint(&mut self, constraint: CspConstraint) -> CspResult<()> {
401        // Validate constraint variables exist
402        let var_names = self.get_constraint_variables(&constraint);
403        for var_name in &var_names {
404            if !self.variables.contains_key(var_name) {
405                return Err(CspError::InvalidConstraint(format!(
406                    "Unknown variable '{var_name}' in constraint"
407                )));
408            }
409        }
410
411        self.constraints.push(constraint);
412        Ok(())
413    }
414
415    /// Set the objective function
416    pub fn set_objective(&mut self, objective: CspObjective) -> CspResult<()> {
417        // Validate objective variables exist
418        let var_names = self.get_objective_variables(&objective);
419        for var_name in &var_names {
420            if !self.variables.contains_key(var_name) {
421                return Err(CspError::InvalidConstraint(format!(
422                    "Unknown variable '{var_name}' in objective"
423                )));
424            }
425        }
426
427        self.objective = Some(objective);
428        Ok(())
429    }
430
431    /// Set compilation parameters
432    pub const fn set_compilation_params(&mut self, params: CompilationParams) {
433        self.compilation_params = params;
434    }
435
436    /// Compile the CSP to a QUBO formulation
437    pub fn compile_to_qubo(&self) -> CspResult<(QuboModel, CspCompilationInfo)> {
438        let mut builder = QuboBuilder::new();
439        let mut info = CspCompilationInfo::new();
440
441        // Step 1: Create binary variables for CSP variables
442        let var_encoding = self.create_variable_encoding(&mut builder, &mut info)?;
443
444        // Step 2: Add constraint penalties
445        self.add_constraint_penalties(&mut builder, &var_encoding, &mut info)?;
446
447        // Step 3: Add objective function
448        if let Some(ref objective) = self.objective {
449            self.add_objective_function(&mut builder, &var_encoding, objective, &mut info)?;
450        }
451
452        // Step 4: Set constraint penalty weight
453        builder
454            .set_constraint_weight(self.compilation_params.constraint_penalty)
455            .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
456
457        Ok((builder.build(), info))
458    }
459
460    /// Create binary variable encoding for CSP variables
461    fn create_variable_encoding(
462        &self,
463        builder: &mut QuboBuilder,
464        info: &mut CspCompilationInfo,
465    ) -> CspResult<HashMap<String, VariableEncoding>> {
466        let mut encodings = HashMap::new();
467
468        for (var_name, csp_var) in &self.variables {
469            let encoding = if csp_var.domain == Domain::Boolean {
470                let qubo_var = builder
471                    .add_variable(var_name.clone())
472                    .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
473                VariableEncoding::Direct(qubo_var)
474            } else {
475                let domain_size = csp_var.domain.size();
476
477                if domain_size <= self.compilation_params.max_onehot_size
478                    && !self.compilation_params.use_log_encoding
479                {
480                    // One-hot encoding
481                    let mut qubo_vars = Vec::new();
482                    for (i, value) in csp_var.domain.values().iter().enumerate() {
483                        let var_name_encoded = format!("{var_name}_{i}");
484                        let qubo_var = builder
485                            .add_variable(var_name_encoded)
486                            .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
487                        qubo_vars.push((qubo_var, value.clone()));
488                    }
489
490                    // Add exactly-one constraint for one-hot encoding
491                    let vars_only: Vec<_> = qubo_vars.iter().map(|(var, _)| var.clone()).collect();
492                    builder
493                        .constrain_one_hot(&vars_only)
494                        .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
495
496                    VariableEncoding::OneHot(qubo_vars)
497                } else {
498                    // Binary/logarithmic encoding
499                    let num_bits = (domain_size as f64).log2().ceil() as usize;
500                    let mut qubo_vars = Vec::new();
501
502                    for i in 0..num_bits {
503                        let var_name_bit = format!("{var_name}_bit_{i}");
504                        let qubo_var = builder
505                            .add_variable(var_name_bit)
506                            .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
507                        qubo_vars.push(qubo_var);
508                    }
509
510                    VariableEncoding::Binary {
511                        bits: qubo_vars,
512                        domain_values: csp_var.domain.values(),
513                    }
514                }
515            };
516
517            encodings.insert(var_name.clone(), encoding);
518            info.add_variable_info(var_name.clone(), csp_var.domain.size());
519        }
520
521        Ok(encodings)
522    }
523
524    /// Add constraint penalties to the QUBO
525    fn add_constraint_penalties(
526        &self,
527        builder: &mut QuboBuilder,
528        var_encoding: &HashMap<String, VariableEncoding>,
529        info: &mut CspCompilationInfo,
530    ) -> CspResult<()> {
531        for (i, constraint) in self.constraints.iter().enumerate() {
532            match constraint {
533                CspConstraint::AllDifferent { variables } => {
534                    self.add_all_different_constraint(builder, var_encoding, variables, info)?;
535                }
536
537                CspConstraint::Linear {
538                    terms,
539                    comparison,
540                    rhs,
541                } => {
542                    self.add_linear_constraint(
543                        builder,
544                        var_encoding,
545                        terms,
546                        comparison,
547                        *rhs,
548                        info,
549                    )?;
550                }
551
552                CspConstraint::ExactlyOne { variables } => {
553                    self.add_exactly_one_constraint(builder, var_encoding, variables, info)?;
554                }
555
556                CspConstraint::AtMostOne { variables } => {
557                    self.add_at_most_one_constraint(builder, var_encoding, variables, info)?;
558                }
559
560                _ => {
561                    return Err(CspError::UnsupportedConstraint(format!(
562                        "Constraint type not yet implemented: constraint {i}"
563                    )));
564                }
565            }
566
567            info.constraints_compiled += 1;
568        }
569
570        Ok(())
571    }
572
573    /// Add all-different constraint
574    fn add_all_different_constraint(
575        &self,
576        builder: &mut QuboBuilder,
577        var_encoding: &HashMap<String, VariableEncoding>,
578        variables: &[String],
579        _info: &mut CspCompilationInfo,
580    ) -> CspResult<()> {
581        // For each pair of variables, penalize if they have the same value
582        for i in 0..variables.len() {
583            for j in (i + 1)..variables.len() {
584                let var1 = &variables[i];
585                let var2 = &variables[j];
586
587                self.add_not_equal_penalty(builder, var_encoding, var1, var2)?;
588            }
589        }
590
591        Ok(())
592    }
593
594    /// Add penalty for two variables being equal
595    fn add_not_equal_penalty(
596        &self,
597        builder: &mut QuboBuilder,
598        var_encoding: &HashMap<String, VariableEncoding>,
599        var1: &str,
600        var2: &str,
601    ) -> CspResult<()> {
602        let encoding1 = &var_encoding[var1];
603        let encoding2 = &var_encoding[var2];
604
605        match (encoding1, encoding2) {
606            (VariableEncoding::Direct(q1), VariableEncoding::Direct(q2)) => {
607                // Penalty for both being 1: x1 * x2
608                builder
609                    .set_quadratic_term(q1, q2, self.compilation_params.constraint_penalty)
610                    .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
611                // Penalty for both being 0: (1-x1) * (1-x2) = 1 - x1 - x2 + x1*x2
612                // This becomes: 1 - x1 - x2 + 2*x1*x2 (since we already have x1*x2)
613                builder
614                    .set_linear_term(q1, -self.compilation_params.constraint_penalty)
615                    .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
616                builder
617                    .set_linear_term(q2, -self.compilation_params.constraint_penalty)
618                    .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
619                builder
620                    .set_quadratic_term(q1, q2, self.compilation_params.constraint_penalty)
621                    .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
622            }
623
624            (VariableEncoding::OneHot(vars1), VariableEncoding::OneHot(vars2)) => {
625                // For each matching value, penalize if both variables have that value
626                let values1: HashMap<_, _> = vars1.iter().map(|(var, val)| (val, var)).collect();
627                let values2: HashMap<_, _> = vars2.iter().map(|(var, val)| (val, var)).collect();
628
629                for (value, qubo_var1) in &values1 {
630                    if let Some(qubo_var2) = values2.get(value) {
631                        builder
632                            .set_quadratic_term(
633                                qubo_var1,
634                                qubo_var2,
635                                self.compilation_params.constraint_penalty,
636                            )
637                            .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
638                    }
639                }
640            }
641
642            _ => {
643                return Err(CspError::UnsupportedConstraint(
644                    "All-different constraint with mixed encoding types not supported".to_string(),
645                ));
646            }
647        }
648
649        Ok(())
650    }
651
652    /// Add linear constraint
653    fn add_linear_constraint(
654        &self,
655        _builder: &mut QuboBuilder,
656        _var_encoding: &HashMap<String, VariableEncoding>,
657        _terms: &[(String, f64)],
658        _comparison: &ComparisonOp,
659        _rhs: f64,
660        _info: &mut CspCompilationInfo,
661    ) -> CspResult<()> {
662        // This would require implementing slack variables and penalty methods
663        // For now, return unsupported
664        Err(CspError::UnsupportedConstraint(
665            "Linear constraints not yet implemented".to_string(),
666        ))
667    }
668
669    /// Add exactly-one constraint
670    fn add_exactly_one_constraint(
671        &self,
672        builder: &mut QuboBuilder,
673        var_encoding: &HashMap<String, VariableEncoding>,
674        variables: &[String],
675        _info: &mut CspCompilationInfo,
676    ) -> CspResult<()> {
677        let mut qubo_vars = Vec::new();
678
679        for var_name in variables {
680            match &var_encoding[var_name] {
681                VariableEncoding::Direct(qubo_var) => {
682                    qubo_vars.push(qubo_var.clone());
683                }
684                _ => {
685                    return Err(CspError::UnsupportedConstraint(
686                        "Exactly-one constraint only supports boolean variables".to_string(),
687                    ));
688                }
689            }
690        }
691
692        builder
693            .constrain_one_hot(&qubo_vars)
694            .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
695
696        Ok(())
697    }
698
699    /// Add at-most-one constraint
700    fn add_at_most_one_constraint(
701        &self,
702        builder: &mut QuboBuilder,
703        var_encoding: &HashMap<String, VariableEncoding>,
704        variables: &[String],
705        _info: &mut CspCompilationInfo,
706    ) -> CspResult<()> {
707        // At most one: penalize any pair being true simultaneously
708        let mut qubo_vars = Vec::new();
709
710        for var_name in variables {
711            match &var_encoding[var_name] {
712                VariableEncoding::Direct(qubo_var) => {
713                    qubo_vars.push(qubo_var.clone());
714                }
715                _ => {
716                    return Err(CspError::UnsupportedConstraint(
717                        "At-most-one constraint only supports boolean variables".to_string(),
718                    ));
719                }
720            }
721        }
722
723        // Penalize all pairs
724        for i in 0..qubo_vars.len() {
725            for j in (i + 1)..qubo_vars.len() {
726                builder
727                    .set_quadratic_term(
728                        &qubo_vars[i],
729                        &qubo_vars[j],
730                        self.compilation_params.constraint_penalty,
731                    )
732                    .map_err(|e| CspError::CompilationFailed(e.to_string()))?;
733            }
734        }
735
736        Ok(())
737    }
738
739    /// Add objective function
740    fn add_objective_function(
741        &self,
742        _builder: &mut QuboBuilder,
743        _var_encoding: &HashMap<String, VariableEncoding>,
744        _objective: &CspObjective,
745        _info: &mut CspCompilationInfo,
746    ) -> CspResult<()> {
747        // Implementation would depend on objective type and variable encodings
748        // For now, return unsupported
749        Err(CspError::UnsupportedConstraint(
750            "Objective functions not yet implemented".to_string(),
751        ))
752    }
753
754    /// Get variables involved in a constraint
755    fn get_constraint_variables(&self, constraint: &CspConstraint) -> Vec<String> {
756        match constraint {
757            CspConstraint::AllDifferent { variables } => variables.clone(),
758            CspConstraint::Linear { terms, .. } => {
759                terms.iter().map(|(var, _)| var.clone()).collect()
760            }
761            CspConstraint::ExactlyOne { variables } => variables.clone(),
762            CspConstraint::AtMostOne { variables } => variables.clone(),
763            CspConstraint::Element {
764                array_var,
765                index_var,
766                value_var,
767            } => {
768                vec![array_var.clone(), index_var.clone(), value_var.clone()]
769            }
770            CspConstraint::GlobalCardinality { variables, .. } => variables.clone(),
771            CspConstraint::Table { variables, .. } => variables.clone(),
772            CspConstraint::Custom { variables, .. } => variables.clone(),
773        }
774    }
775
776    /// Get variables involved in an objective
777    fn get_objective_variables(&self, objective: &CspObjective) -> Vec<String> {
778        match objective {
779            CspObjective::Linear { terms, .. } => {
780                terms.iter().map(|(var, _)| var.clone()).collect()
781            }
782            CspObjective::Custom { .. } => Vec::new(), // Cannot determine statically
783        }
784    }
785}
786
787impl Default for CspProblem {
788    fn default() -> Self {
789        Self::new()
790    }
791}
792
793/// Variable encoding in QUBO
794#[derive(Debug, Clone)]
795enum VariableEncoding {
796    /// Direct binary variable
797    Direct(crate::qubo::Variable),
798
799    /// One-hot encoding
800    OneHot(Vec<(crate::qubo::Variable, CspValue)>),
801
802    /// Binary/logarithmic encoding
803    Binary {
804        bits: Vec<crate::qubo::Variable>,
805        domain_values: Vec<CspValue>,
806    },
807}
808
809/// Information about CSP compilation
810#[derive(Debug, Clone)]
811pub struct CspCompilationInfo {
812    /// Number of CSP variables
813    pub csp_variables: usize,
814
815    /// Number of QUBO variables created
816    pub qubo_variables: usize,
817
818    /// Number of constraints compiled
819    pub constraints_compiled: usize,
820
821    /// Variable encoding information
822    pub variable_info: HashMap<String, VariableInfo>,
823}
824
825/// Information about how a CSP variable was encoded
826#[derive(Debug, Clone)]
827pub struct VariableInfo {
828    /// Original domain size
829    pub domain_size: usize,
830
831    /// Number of QUBO variables used
832    pub qubo_variables_used: usize,
833
834    /// Encoding type used
835    pub encoding_type: String,
836}
837
838impl CspCompilationInfo {
839    fn new() -> Self {
840        Self {
841            csp_variables: 0,
842            qubo_variables: 0,
843            constraints_compiled: 0,
844            variable_info: HashMap::new(),
845        }
846    }
847
848    fn add_variable_info(&mut self, name: String, domain_size: usize) {
849        let qubo_vars_used = if domain_size == 2 { 1 } else { domain_size };
850        let encoding_type = if domain_size == 2 {
851            "Direct".to_string()
852        } else if domain_size <= 16 {
853            "OneHot".to_string()
854        } else {
855            "Binary".to_string()
856        };
857
858        self.variable_info.insert(
859            name,
860            VariableInfo {
861                domain_size,
862                qubo_variables_used: qubo_vars_used,
863                encoding_type,
864            },
865        );
866
867        self.csp_variables += 1;
868        self.qubo_variables += qubo_vars_used;
869    }
870}
871
872#[cfg(test)]
873mod tests {
874    use super::*;
875
876    #[test]
877    fn test_domain_creation() {
878        let bool_domain = Domain::Boolean;
879        assert_eq!(bool_domain.size(), 2);
880
881        let int_domain = Domain::IntegerRange { min: 1, max: 5 };
882        assert_eq!(int_domain.size(), 5);
883
884        let discrete_domain = Domain::Discrete(vec![1, 3, 7, 9]);
885        assert_eq!(discrete_domain.size(), 4);
886    }
887
888    #[test]
889    fn test_csp_variable() {
890        let var = CspVariable::new("x".to_string(), Domain::Boolean)
891            .with_description("Test variable".to_string());
892
893        assert_eq!(var.name, "x");
894        assert_eq!(var.domain, Domain::Boolean);
895        assert_eq!(var.description, Some("Test variable".to_string()));
896    }
897
898    #[test]
899    fn test_simple_csp_problem() {
900        let mut problem = CspProblem::new();
901
902        // Add variables
903        let x = CspVariable::new("x".to_string(), Domain::Boolean);
904        let y = CspVariable::new("y".to_string(), Domain::Boolean);
905
906        problem.add_variable(x).expect("should add variable x");
907        problem.add_variable(y).expect("should add variable y");
908
909        // Add exactly-one constraint
910        let constraint = CspConstraint::ExactlyOne {
911            variables: vec!["x".to_string(), "y".to_string()],
912        };
913        problem
914            .add_constraint(constraint)
915            .expect("should add exactly-one constraint");
916
917        // Compile to QUBO
918        let (qubo_formulation, info) = problem.compile_to_qubo().expect("should compile to QUBO");
919
920        assert_eq!(info.csp_variables, 2);
921        assert_eq!(info.qubo_variables, 2);
922        assert_eq!(info.constraints_compiled, 1);
923
924        let qubo_model = qubo_formulation.to_qubo_model();
925        assert_eq!(qubo_model.num_variables, 2);
926    }
927
928    #[test]
929    fn test_all_different_constraint() {
930        let mut problem = CspProblem::new();
931
932        // Add three boolean variables
933        for i in 0..3 {
934            let var = CspVariable::new(format!("x{}", i), Domain::Boolean);
935            problem
936                .add_variable(var)
937                .expect("should add boolean variable");
938        }
939
940        // Add all-different constraint (only one can be true for boolean vars)
941        let constraint = CspConstraint::AllDifferent {
942            variables: vec!["x0".to_string(), "x1".to_string(), "x2".to_string()],
943        };
944        problem
945            .add_constraint(constraint)
946            .expect("should add all-different constraint");
947
948        let (_, info) = problem.compile_to_qubo().expect("should compile to QUBO");
949        assert_eq!(info.constraints_compiled, 1);
950    }
951
952    #[test]
953    fn test_one_hot_encoding() {
954        let mut problem = CspProblem::new();
955
956        // Add variable with small discrete domain
957        let var = CspVariable::new("color".to_string(), Domain::Discrete(vec![1, 2, 3]));
958        problem
959            .add_variable(var)
960            .expect("should add discrete variable");
961
962        let (_, info) = problem.compile_to_qubo().expect("should compile to QUBO");
963
964        // Should use one-hot encoding: 3 QUBO variables for 3 domain values
965        assert_eq!(info.variable_info["color"].qubo_variables_used, 3);
966        assert_eq!(info.variable_info["color"].encoding_type, "OneHot");
967    }
968}
quantrs2_anneal/csp_compiler.rs

quantrs2_anneal/
csp_compiler.rs
