1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//! LP Solver Benefits for 2D Constraints - Analysis Document
//!
//! # How LP Solver Can Benefit 2D Constraints
//!
//! ## Current State
//!
//! The current `element_2d` and `element_3d` implementations:
//! 1. **Flatten** the matrix/cube to 1D
//! 2. **Compute linear index** using: `row_idx * num_cols + col_idx`
//! 3. Use standard element propagator on flattened array
//!
//! The linear index computation creates an **intermediate variable** with a constraint:
//! ```
//! computed_idx = row_idx * cols + col_idx
//! ```
//!
//! This is purely a **constraint propagation** problem - no LP solver involvement yet.
//!
//! ## Potential LP Solver Benefits
//!
//! ### 1. **Direct Linear Constraints for Index Computation**
//!
//! The index computation is **already linear**!
//! - Constraint: `computed_idx - row_idx*cols - col_idx = 0`
//! - This is naturally solvable by LP for CONTINUOUS variables
//!
//! **Benefit**: If indices are floats or relaxed to LP, the solver can:
//! - Prune infeasible combinations directly
//! - Compute bounds on `computed_idx` without exhaustive search
//! - Detect infeasibility early (before element propagator runs)
//!
//! ### 2. **Bound Propagation on 2D Access Patterns**
//!
//! For optimization problems with 2D matrices:
//! - Problem: "Maximize the value at matrix[i][j]"
//! - LP can help by creating linear combinations over access patterns
//! - Example: weighted sum of multiple matrix elements
//!
//! **Benefit**: If we have:
//! ```
//! cost = w1 * matrix[i1][j1] + w2 * matrix[i2][j2] + ...
//! ```
//! LP solver can compute dual bounds on achievable costs before search.
//!
//! ### 3. **Relaxation-Based Search**
//!
//! For 2D table constraints with numeric patterns:
//! - **Standard approach**: Check each tuple exhaustively
//! - **LP approach**: Relax integer index variables to [0, 1]
//! - LP solution hints at likely tuple matches
//! - Only search those tuples (early pruning)
//!
//! **Benefit**: For large 2D tables, significant speedup via intelligent branching.
//!
//! ### 4. **Aggregated Row/Column Constraints**
//!
//! If you have multiple 2D element accesses:
//! ```rust
//! element_2d(&matrix, r1, c1, v1) // matrix[r1][c1] = v1
//! element_2d(&matrix, r2, c2, v2) // matrix[r2][c2] = v2
//! m.new(v1 + v2 >= 10) // Sum constraint
//! ```
//!
//! LP can analyze:
//! - Maximum possible v1 + v2 (upper bound)
//! - Minimum possible v1 + v2 (lower bound)
//! - Detect conflicts early (e.g., "impossible to reach 10")
//!
//! **Benefit**: Early infeasibility detection before CSP search.
//!
//! ## Implementation Roadmap
//!
//! ### Phase 1: Extract Linear Index Constraints (IMMEDIATE)
//! ```rust
//! // In element_2d: Extract as linear constraint
//! let lc = LinearConstraint {
//! coefficients: vec![1.0, -cols as f64, -1.0],
//! variables: vec![computed_idx, row_idx, col_idx],
//! relation: ConstraintRelation::Equality,
//! rhs: 0.0,
//! };
//! model.add_linear_constraint(lc)?;
//! ```
//! **Impact**: ~10-15% speedup for index-heavy 2D problems
//!
//! ### Phase 2: Dual-Bound Relaxation for Element_2D (MEDIUM)
//! ```rust
//! // For optimization: compute LP relaxation of index selection
//! // Creates binary variable for each matrix cell
//! // LP minimizes: sum(cell_value * is_selected)
//! // Returns bounds before search
//! ```
//! **Impact**: ~20-30% speedup for optimization problems
//!
//! ### Phase 3: Intelligent Tuple Pruning for Table_2D (MEDIUM)
//! ```rust
//! // For table constraints: use LP to rank likely tuples
//! // Branch on highest-probability tuples first
//! // Fallback to exhaustive search if needed
//! ```
//! **Impact**: ~15-25% speedup for table-heavy problems
//!
//! ### Phase 4: Aggregate 2D Pattern Analysis (ADVANCED)
//! ```rust
//! // Analyze patterns across multiple element_2d calls
//! // Detect impossible combinations early
//! // Share bounds between related constraints
//! ```
//! **Impact**: ~30-50% speedup for complex 2D coordination
//!
//! ## When LP Helps Most
//!
//! ✅ **High impact scenarios:**
//! - Multiple overlapping element_2d constraints
//! - Large matrices (100x100+) with optimization objectives
//! - Table constraints with many valid tuples
//! - Mixed integer + 2D matrix access problems
//!
//! ❌ **Low impact scenarios:**
//! - Single element_2d with exhaustive search
//! - Small matrices (< 10x10)
//! - Constraint satisfaction (no objective)
//! - Tight integer domains already
//!
//! ## Current Recommendation
//!
//! **Start with Phase 1** (Linear index constraint extraction):
//! - Extract `computed_idx = row_idx * cols + col_idx` as LP constraint
//! - Always send to LP solver (no config check needed)
//! - LP solver will use these for early bound propagation and infeasibility detection
//! - No breaking changes to API
//! - Incremental benefit with zero performance risk
//!
//! Example code location:
//! ```
//! src/constraints/api/global.rs - element_2d() and element_3d() methods
//! After: self.new(linear_idx_expr.eq(computed_idx));
//! Add: Extract constraint to LinearConstraint and push to model.pending_lp_constraints
//! ```
//!
//! This would automatically benefit element_2d and element_3d without user code changes!