problemreductions/models/set/
integer_knapsack.rs

1//! Integer Knapsack problem implementation.
2//!
3//! The Integer Knapsack problem generalizes the 0-1 Knapsack by allowing
4//! each item to be selected with a non-negative integer multiplicity.
5
6use crate::registry::ConstructionError;
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::solvers::BruteForceProblem as _;
9use crate::traits::Problem;
10use crate::types::Max;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "IntegerKnapsack",
16        display_name: "Integer Knapsack",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Set,
20        module_path: module_path!(),
21        description: "Select items with integer multiplicities to maximize total value subject to capacity constraint",
22        fields: &[
23            FieldInfo { name: "sizes", type_name: "Vec<i64>", description: "Positive item sizes s(u)" },
24            FieldInfo { name: "values", type_name: "Vec<i64>", description: "Positive item values v(u)" },
25            FieldInfo { name: "capacity", type_name: "i64", description: "Nonnegative knapsack capacity B" },
26        ],
27    }
28}
29
30/// The Integer Knapsack problem.
31///
32/// Given `n` items, each with positive size `s_i` and positive value `v_i`,
33/// and a nonnegative capacity `B`,
34/// find non-negative integer multiplicities `c_0, ..., c_{n-1}` such that
35/// `sum c_i * s_i <= B`, maximizing `sum c_i * v_i`.
36///
37/// # Representation
38///
39/// Variable `i` has domain `{0, ..., floor(B / s_i)}` representing the
40/// multiplicity of item `i`.
41///
42/// # Example
43///
44/// ```
45/// use problemreductions::models::set::IntegerKnapsack;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// let problem = IntegerKnapsack::new(vec![3, 4, 5, 2, 7], vec![4, 5, 7, 3, 9], 15).unwrap();
49/// let solver = BruteForce::new();
50/// let solution = solver.solve(&problem).unwrap();
51/// assert!(solution.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize)]
54#[serde(into = "RawIntegerKnapsack")]
55pub struct IntegerKnapsack {
56    sizes: Vec<i64>,
57    values: Vec<i64>,
58    capacity: i64,
59}
60
61impl IntegerKnapsack {
62    /// Create a new IntegerKnapsack instance.
63    ///
64    pub fn new(
65        sizes: Vec<i64>,
66        values: Vec<i64>,
67        capacity: i64,
68    ) -> Result<Self, ConstructionError> {
69        Self::try_from(RawIntegerKnapsack {
70            sizes,
71            values,
72            capacity,
73        })
74    }
75
76    /// Returns the item sizes.
77    pub fn sizes(&self) -> &[i64] {
78        &self.sizes
79    }
80
81    /// Returns the item values.
82    pub fn values(&self) -> &[i64] {
83        &self.values
84    }
85
86    /// Returns the knapsack capacity.
87    pub fn capacity(&self) -> i64 {
88        self.capacity
89    }
90
91    /// Returns the number of items.
92    pub fn num_items(&self) -> usize {
93        self.sizes.len()
94    }
95}
96
97impl Problem for IntegerKnapsack {
98    const NAME: &'static str = "IntegerKnapsack";
99    type Solution = Vec<usize>;
100    type Value = Max<i64>;
101
102    crate::problem_parameters![("capacity", capacity), ("num_items", num_items),];
103
104    fn variant() -> Vec<(&'static str, &'static str)> {
105        crate::variant_params![]
106    }
107
108    fn evaluate(
109        &self,
110        config: &Self::Solution,
111    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
112        Ok({
113            if config.len() != self.num_items() {
114                return Err(crate::traits::EvaluationError::InvalidConfiguration(
115                    "multiplicity-vector length does not match the items".into(),
116                ));
117            }
118            let dims = self.dimensions();
119            if config
120                .iter()
121                .zip(&dims)
122                .any(|(&count, &dimension)| count >= dimension)
123            {
124                return Err(crate::traits::EvaluationError::InvalidConfiguration(
125                    "multiplicity vector contains an out-of-range count".into(),
126                ));
127            }
128            let total_size = config
129                .iter()
130                .enumerate()
131                .try_fold(0_i64, |total, (i, &c)| {
132                    let count = i64::try_from(c).map_err(|_| {
133                        crate::traits::EvaluationError::IntegerOverflow(
134                            "converting knapsack item count to i64".into(),
135                        )
136                    })?;
137                    let contribution = count.checked_mul(self.sizes[i]).ok_or_else(|| {
138                        crate::traits::EvaluationError::IntegerOverflow(
139                            "multiplying knapsack item count by size".into(),
140                        )
141                    })?;
142                    total.checked_add(contribution).ok_or_else(|| {
143                        crate::traits::EvaluationError::IntegerOverflow(
144                            "summing knapsack item sizes".into(),
145                        )
146                    })
147                })?;
148            if total_size > self.capacity {
149                return Ok(Max(None));
150            }
151            let total_value = config
152                .iter()
153                .enumerate()
154                .try_fold(0_i64, |total, (i, &c)| {
155                    let count = i64::try_from(c).map_err(|_| {
156                        crate::traits::EvaluationError::IntegerOverflow(
157                            "converting knapsack item count to i64".into(),
158                        )
159                    })?;
160                    let contribution = count.checked_mul(self.values[i]).ok_or_else(|| {
161                        crate::traits::EvaluationError::IntegerOverflow(
162                            "multiplying knapsack item count by value".into(),
163                        )
164                    })?;
165                    total.checked_add(contribution).ok_or_else(|| {
166                        crate::traits::EvaluationError::IntegerOverflow(
167                            "summing knapsack item values".into(),
168                        )
169                    })
170                })?;
171            Max(Some(total_value))
172        })
173    }
174}
175
176impl crate::solvers::BruteForceProblem for IntegerKnapsack {
177    fn dimensions(&self) -> Vec<usize> {
178        self.sizes
179            .iter()
180            .map(|&s| {
181                let dimension = i128::from(self.capacity) / i128::from(s) + 1;
182                usize::try_from(dimension)
183                    .expect("validated integer-knapsack dimension must fit usize")
184            })
185            .collect()
186    }
187}
188
189crate::declare_variants! {
190    default IntegerKnapsack => "(capacity + 1)^num_items",
191}
192
193crate::register_brute_force! {
194    IntegerKnapsack,
195}
196
197/// Raw representation for serde deserialization with full validation.
198#[derive(Deserialize, Serialize)]
199struct RawIntegerKnapsack {
200    sizes: Vec<i64>,
201    values: Vec<i64>,
202    capacity: i64,
203}
204
205impl From<IntegerKnapsack> for RawIntegerKnapsack {
206    fn from(ik: IntegerKnapsack) -> Self {
207        RawIntegerKnapsack {
208            sizes: ik.sizes,
209            values: ik.values,
210            capacity: ik.capacity,
211        }
212    }
213}
214
215impl TryFrom<RawIntegerKnapsack> for IntegerKnapsack {
216    type Error = ConstructionError;
217
218    fn try_from(raw: RawIntegerKnapsack) -> Result<Self, Self::Error> {
219        if raw.sizes.len() != raw.values.len() {
220            return Err(ConstructionError::Conversion(format!(
221                "sizes and values must have the same length, got {} and {}",
222                raw.sizes.len(),
223                raw.values.len()
224            )));
225        }
226        if let Some(&s) = raw.sizes.iter().find(|&&s| s <= 0) {
227            return Err(ConstructionError::Conversion(format!(
228                "expected positive sizes, got {s}"
229            )));
230        }
231        if let Some(&v) = raw.values.iter().find(|&&v| v <= 0) {
232            return Err(ConstructionError::Conversion(format!(
233                "expected positive values, got {v}"
234            )));
235        }
236        if raw.capacity < 0 {
237            return Err(ConstructionError::Conversion(format!(
238                "expected nonnegative capacity, got {}",
239                raw.capacity
240            )));
241        }
242        for &size in &raw.sizes {
243            let dimension = i128::from(raw.capacity) / i128::from(size) + 1;
244            usize::try_from(dimension).map_err(|_| {
245                ConstructionError::IntegerOverflow(format!(
246                    "knapsack dimension for capacity {} and item size {size} does not fit usize",
247                    raw.capacity
248                ))
249            })?;
250        }
251        Ok(IntegerKnapsack {
252            sizes: raw.sizes,
253            values: raw.values,
254            capacity: raw.capacity,
255        })
256    }
257}
258
259impl<'de> Deserialize<'de> for IntegerKnapsack {
260    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
261    where
262        D: serde::Deserializer<'de>,
263    {
264        let raw = RawIntegerKnapsack::deserialize(deserializer)?;
265        IntegerKnapsack::try_from(raw).map_err(serde::de::Error::custom)
266    }
267}
268
269#[cfg(feature = "example-db")]
270pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
271    // 5 items: sizes [3,4,5,2,7], values [4,5,7,3,9], capacity 15
272    // Optimal: c=(0,0,1,5,0) → total_size=5+10=15, total_value=7+15=22
273    vec![crate::example_db::specs::ModelExampleSpec {
274        id: "integer-knapsack",
275        instance: Box::new(
276            IntegerKnapsack::new(vec![3, 4, 5, 2, 7], vec![4, 5, 7, 3, 9], 15).unwrap(),
277        ),
278        optimal_config: serde_json::json!(vec![0, 0, 1, 5, 0]),
279        optimal_value: serde_json::json!(22),
280    }]
281}
282
283#[cfg(test)]
284#[path = "../../unit_tests/models/set/integer_knapsack.rs"]
285mod tests;
problemreductions/models/set/integer_knapsack.rs

problemreductions/models/set/
integer_knapsack.rs
