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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
use super::*;
use crate::ATol;
use anyhow::{anyhow, Result};
impl Instance {
pub fn relax_constraint(
&mut self,
id: ConstraintID,
removed_reason: String,
parameters: impl IntoIterator<Item = (String, String)>,
) -> Result<()> {
let c = self
.constraints
.remove(&id)
.ok_or_else(|| anyhow!("Constraint with ID {:?} not found", id))?;
self.removed_constraints.insert(
id,
RemovedConstraint {
constraint: c,
removed_reason,
removed_reason_parameters: parameters.into_iter().collect(),
},
);
// Invalidate constraint hints that reference the removed constraint
self.constraint_hints
.one_hot_constraints
.retain(|hint| hint.id != id);
self.constraint_hints.sos1_constraints.retain(|hint| {
hint.binary_constraint_id != id && !hint.big_m_constraint_ids.contains(&id)
});
Ok(())
}
pub fn restore_constraint(&mut self, id: ConstraintID) -> Result<()> {
let rc = self
.removed_constraints
.get(&id)
.ok_or_else(|| anyhow!("Removed constraint with ID {:?} not found", id))?;
// Clone the constraint first to avoid data loss if transformations fail
let mut constraint = rc.constraint.clone();
// 1. Substitute dependent variables first
// Dependency expansion may introduce fixed variables (e.g., x3 = x1 + x2 where x1 is fixed),
// so this must happen before partial_evaluate.
if !self.decision_variable_dependency.is_empty() {
crate::substitute_acyclic(
&mut constraint.function,
&self.decision_variable_dependency,
)?;
}
// 2. Substitute fixed variables (those with substituted_value set)
// This comes after dependency substitution to handle variables introduced by expansion.
let fixed_state: v1::State = v1::State {
entries: self
.decision_variables
.iter()
.filter_map(|(id, dv)| dv.substituted_value().map(|v| (id.into_inner(), v)))
.collect(),
};
if !fixed_state.entries.is_empty() {
constraint.partial_evaluate(&fixed_state, ATol::default())?;
}
// Only remove from removed_constraints after all transformations succeed
self.removed_constraints.remove(&id);
self.constraints.insert(id, constraint);
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{coeff, constraint::Equality, linear, DecisionVariable, Sense, Substitute};
use std::collections::BTreeMap;
/// Test that restore_constraint correctly substitutes fixed variables.
///
/// Scenario:
/// 1. Create an Instance with variables x1 and x2
/// 2. Add a constraint using x1: x1 + x2 <= 10
/// 3. Relax the constraint
/// 4. Set x1's substituted_value to 3.0
/// 5. Restore the constraint
/// 6. Verify the restored constraint has x1 substituted: x2 + 3 <= 10 (i.e., x2 - 7 <= 0)
#[test]
fn test_restore_constraint_with_fixed_variable() {
// Create decision variables
let mut decision_variables = BTreeMap::new();
decision_variables.insert(
VariableID::from(1),
DecisionVariable::continuous(VariableID::from(1)),
);
decision_variables.insert(
VariableID::from(2),
DecisionVariable::continuous(VariableID::from(2)),
);
// Create constraint: x1 + x2 - 10 <= 0
let constraint_function = Function::from(linear!(1) + linear!(2) + coeff!(-10.0));
let mut constraints = BTreeMap::new();
let constraint = Constraint {
id: ConstraintID::from(1),
function: constraint_function,
equality: Equality::LessThanOrEqualToZero,
name: None,
subscripts: Vec::new(),
parameters: Default::default(),
description: None,
};
constraints.insert(ConstraintID::from(1), constraint);
// Create instance
let objective = Function::from(linear!(1) + linear!(2));
let mut instance =
Instance::new(Sense::Minimize, objective, decision_variables, constraints).unwrap();
// Relax the constraint
instance
.relax_constraint(ConstraintID::from(1), "test".to_string(), [])
.unwrap();
// Verify constraint is removed
assert!(instance.constraints.is_empty());
assert_eq!(instance.removed_constraints.len(), 1);
// Fix x1 to 3.0 using partial_evaluate on the instance
let fix_state = v1::State {
entries: [(1, 3.0)].into_iter().collect(),
};
instance
.partial_evaluate(&fix_state, ATol::default())
.unwrap();
// Verify x1 has substituted_value set
assert_eq!(
instance
.decision_variables
.get(&VariableID::from(1))
.unwrap()
.substituted_value(),
Some(3.0)
);
// Restore the constraint
instance.restore_constraint(ConstraintID::from(1)).unwrap();
// Verify constraint is restored
assert_eq!(instance.constraints.len(), 1);
assert!(instance.removed_constraints.is_empty());
// Check the restored constraint has x1 substituted
// Original: x1 + x2 - 10
// After substituting x1=3: 3 + x2 - 10 = x2 - 7
let restored_constraint = instance.constraints.get(&ConstraintID::from(1)).unwrap();
let required_ids = restored_constraint.required_ids();
// x1 should NOT be in the required IDs (it's been substituted)
assert!(!required_ids.contains(&VariableID::from(1)));
// x2 should still be in the required IDs
assert!(required_ids.contains(&VariableID::from(2)));
}
/// Test that restore_constraint correctly substitutes dependent variables.
///
/// Scenario:
/// 1. Create an Instance with variables x1, x2, x3
/// 2. Add a constraint using x3: x3 <= 10
/// 3. Relax the constraint
/// 4. Add dependency x3 = x1 + x2
/// 5. Restore the constraint
/// 6. Verify the restored constraint has x3 substituted: x1 + x2 <= 10
#[test]
fn test_restore_constraint_with_dependent_variable() {
// Create decision variables
let mut decision_variables = BTreeMap::new();
decision_variables.insert(
VariableID::from(1),
DecisionVariable::continuous(VariableID::from(1)),
);
decision_variables.insert(
VariableID::from(2),
DecisionVariable::continuous(VariableID::from(2)),
);
decision_variables.insert(
VariableID::from(3),
DecisionVariable::continuous(VariableID::from(3)),
);
// Create constraint: x3 - 10 <= 0
let constraint_function = Function::from(linear!(3) + coeff!(-10.0));
let mut constraints = BTreeMap::new();
let constraint = Constraint {
id: ConstraintID::from(1),
function: constraint_function,
equality: Equality::LessThanOrEqualToZero,
name: None,
subscripts: Vec::new(),
parameters: Default::default(),
description: None,
};
constraints.insert(ConstraintID::from(1), constraint);
// Create instance
let objective = Function::from(linear!(1) + linear!(2) + linear!(3));
let mut instance =
Instance::new(Sense::Minimize, objective, decision_variables, constraints).unwrap();
// Relax the constraint
instance
.relax_constraint(ConstraintID::from(1), "test".to_string(), [])
.unwrap();
// Verify constraint is removed
assert!(instance.constraints.is_empty());
assert_eq!(instance.removed_constraints.len(), 1);
// Add dependency x3 = x1 + x2 using substitute_one on the instance
// This will add the dependency to decision_variable_dependency
let substitution = Function::from(linear!(1) + linear!(2));
instance = instance
.substitute_one(VariableID::from(3), &substitution)
.unwrap();
// Verify dependency is set
assert_eq!(instance.decision_variable_dependency.len(), 1);
assert!(instance
.decision_variable_dependency
.get(&VariableID::from(3))
.is_some());
// Restore the constraint
instance.restore_constraint(ConstraintID::from(1)).unwrap();
// Verify constraint is restored
assert_eq!(instance.constraints.len(), 1);
assert!(instance.removed_constraints.is_empty());
// Check the restored constraint has x3 substituted with x1 + x2
// Original: x3 - 10
// After substituting x3 = x1 + x2: x1 + x2 - 10
let restored_constraint = instance.constraints.get(&ConstraintID::from(1)).unwrap();
let required_ids = restored_constraint.required_ids();
// x3 should NOT be in the required IDs (it's been substituted)
assert!(!required_ids.contains(&VariableID::from(3)));
// x1 and x2 should be in the required IDs
assert!(required_ids.contains(&VariableID::from(1)));
assert!(required_ids.contains(&VariableID::from(2)));
}
/// Test that restore_constraint correctly handles the case where
/// dependency expansion introduces fixed variables.
///
/// Scenario:
/// 1. Create an Instance with variables x1, x2, x3
/// 2. Add a constraint using x3: x3 <= 10
/// 3. Relax the constraint
/// 4. Fix x1 to 3.0 (set substituted_value)
/// 5. Add dependency x3 = x1 + x2
/// 6. Restore the constraint
/// 7. Expected: constraint should have both x3 and x1 substituted
/// Original: x3 - 10
/// After x3 = x1 + x2: x1 + x2 - 10
/// After x1 = 3: x2 + 3 - 10 = x2 - 7
#[test]
fn test_restore_constraint_with_fixed_variable_in_dependency() {
// Create decision variables
let mut decision_variables = BTreeMap::new();
decision_variables.insert(
VariableID::from(1),
DecisionVariable::continuous(VariableID::from(1)),
);
decision_variables.insert(
VariableID::from(2),
DecisionVariable::continuous(VariableID::from(2)),
);
decision_variables.insert(
VariableID::from(3),
DecisionVariable::continuous(VariableID::from(3)),
);
// Create constraint: x3 - 10 <= 0
let constraint_function = Function::from(linear!(3) + coeff!(-10.0));
let mut constraints = BTreeMap::new();
let constraint = Constraint {
id: ConstraintID::from(1),
function: constraint_function,
equality: Equality::LessThanOrEqualToZero,
name: None,
subscripts: Vec::new(),
parameters: Default::default(),
description: None,
};
constraints.insert(ConstraintID::from(1), constraint);
// Create instance
let objective = Function::from(linear!(1) + linear!(2) + linear!(3));
let mut instance =
Instance::new(Sense::Minimize, objective, decision_variables, constraints).unwrap();
// Relax the constraint
instance
.relax_constraint(ConstraintID::from(1), "test".to_string(), [])
.unwrap();
// Fix x1 to 3.0 BEFORE adding the dependency
let fix_state = v1::State {
entries: [(1, 3.0)].into_iter().collect(),
};
instance
.partial_evaluate(&fix_state, ATol::default())
.unwrap();
// Add dependency x3 = x1 + x2 AFTER fixing x1
// This means when we expand x3, we get x1 + x2, and x1 should also be substituted
let substitution = Function::from(linear!(1) + linear!(2));
instance = instance
.substitute_one(VariableID::from(3), &substitution)
.unwrap();
// Restore the constraint
instance.restore_constraint(ConstraintID::from(1)).unwrap();
// Check the restored constraint has both x3 and x1 substituted
// Original: x3 - 10
// After x3 = x1 + x2: x1 + x2 - 10
// After x1 = 3: x2 - 7
let restored_constraint = instance.constraints.get(&ConstraintID::from(1)).unwrap();
let required_ids = restored_constraint.required_ids();
// x3 should NOT be in the required IDs (it's been substituted)
assert!(!required_ids.contains(&VariableID::from(3)));
// x1 should NOT be in the required IDs (it's been substituted via fixed value)
assert!(
!required_ids.contains(&VariableID::from(1)),
"x1 should be substituted because it was fixed before dependency was added"
);
// x2 should still be in the required IDs
assert!(required_ids.contains(&VariableID::from(2)));
}
}