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    /// Binary digit count of the capacity, with a minimum of one for zero.
92    pub fn capacity_bits(&self) -> u64 {
93        crate::types::max_numeric_magnitude_bits([self.capacity])
94    }
95
96    /// Returns the number of items.
97    pub fn num_items(&self) -> usize {
98        self.sizes.len()
99    }
100}
101
102impl Problem for IntegerKnapsack {
103    const NAME: &'static str = "IntegerKnapsack";
104    type Solution = Vec<usize>;
105    type Value = Max<i64>;
106
107    crate::problem_parameters![
108        ("capacity", capacity),
109        ("capacity_bits", capacity_bits),
110        ("num_items", num_items),
111    ];
112
113    fn variant() -> Vec<(&'static str, &'static str)> {
114        crate::variant_params![]
115    }
116
117    fn evaluate(
118        &self,
119        config: &Self::Solution,
120    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
121        Ok({
122            if config.len() != self.num_items() {
123                return Err(crate::traits::EvaluationError::InvalidConfiguration(
124                    "multiplicity-vector length does not match the items".into(),
125                ));
126            }
127            let dims = self.dimensions();
128            if config
129                .iter()
130                .zip(&dims)
131                .any(|(&count, &dimension)| count >= dimension)
132            {
133                return Err(crate::traits::EvaluationError::InvalidConfiguration(
134                    "multiplicity vector contains an out-of-range count".into(),
135                ));
136            }
137            let total_size = config
138                .iter()
139                .enumerate()
140                .try_fold(0_i64, |total, (i, &c)| {
141                    let count = i64::try_from(c).map_err(|_| {
142                        crate::traits::EvaluationError::IntegerOverflow(
143                            "converting knapsack item count to i64".into(),
144                        )
145                    })?;
146                    let contribution = count.checked_mul(self.sizes[i]).ok_or_else(|| {
147                        crate::traits::EvaluationError::IntegerOverflow(
148                            "multiplying knapsack item count by size".into(),
149                        )
150                    })?;
151                    total.checked_add(contribution).ok_or_else(|| {
152                        crate::traits::EvaluationError::IntegerOverflow(
153                            "summing knapsack item sizes".into(),
154                        )
155                    })
156                })?;
157            if total_size > self.capacity {
158                return Ok(Max(None));
159            }
160            let total_value = config
161                .iter()
162                .enumerate()
163                .try_fold(0_i64, |total, (i, &c)| {
164                    let count = i64::try_from(c).map_err(|_| {
165                        crate::traits::EvaluationError::IntegerOverflow(
166                            "converting knapsack item count to i64".into(),
167                        )
168                    })?;
169                    let contribution = count.checked_mul(self.values[i]).ok_or_else(|| {
170                        crate::traits::EvaluationError::IntegerOverflow(
171                            "multiplying knapsack item count by value".into(),
172                        )
173                    })?;
174                    total.checked_add(contribution).ok_or_else(|| {
175                        crate::traits::EvaluationError::IntegerOverflow(
176                            "summing knapsack item values".into(),
177                        )
178                    })
179                })?;
180            Max(Some(total_value))
181        })
182    }
183}
184
185impl crate::solvers::BruteForceProblem for IntegerKnapsack {
186    fn dimensions(&self) -> Vec<usize> {
187        self.sizes
188            .iter()
189            .map(|&s| {
190                let dimension = i128::from(self.capacity) / i128::from(s) + 1;
191                usize::try_from(dimension)
192                    .expect("validated integer-knapsack dimension must fit usize")
193            })
194            .collect()
195    }
196}
197
198crate::declare_variants! {
199    default IntegerKnapsack => "(capacity + 1)^num_items",
200}
201
202crate::register_brute_force! {
203    IntegerKnapsack,
204}
205
206/// Raw representation for serde deserialization with full validation.
207#[derive(Deserialize, Serialize)]
208struct RawIntegerKnapsack {
209    sizes: Vec<i64>,
210    values: Vec<i64>,
211    capacity: i64,
212}
213
214impl From<IntegerKnapsack> for RawIntegerKnapsack {
215    fn from(ik: IntegerKnapsack) -> Self {
216        RawIntegerKnapsack {
217            sizes: ik.sizes,
218            values: ik.values,
219            capacity: ik.capacity,
220        }
221    }
222}
223
224impl TryFrom<RawIntegerKnapsack> for IntegerKnapsack {
225    type Error = ConstructionError;
226
227    fn try_from(raw: RawIntegerKnapsack) -> Result<Self, Self::Error> {
228        if raw.sizes.len() != raw.values.len() {
229            return Err(ConstructionError::Conversion(format!(
230                "sizes and values must have the same length, got {} and {}",
231                raw.sizes.len(),
232                raw.values.len()
233            )));
234        }
235        if let Some(&s) = raw.sizes.iter().find(|&&s| s <= 0) {
236            return Err(ConstructionError::Conversion(format!(
237                "expected positive sizes, got {s}"
238            )));
239        }
240        if let Some(&v) = raw.values.iter().find(|&&v| v <= 0) {
241            return Err(ConstructionError::Conversion(format!(
242                "expected positive values, got {v}"
243            )));
244        }
245        if raw.capacity < 0 {
246            return Err(ConstructionError::Conversion(format!(
247                "expected nonnegative capacity, got {}",
248                raw.capacity
249            )));
250        }
251        for &size in &raw.sizes {
252            let dimension = i128::from(raw.capacity) / i128::from(size) + 1;
253            usize::try_from(dimension).map_err(|_| {
254                ConstructionError::IntegerOverflow(format!(
255                    "knapsack dimension for capacity {} and item size {size} does not fit usize",
256                    raw.capacity
257                ))
258            })?;
259        }
260        Ok(IntegerKnapsack {
261            sizes: raw.sizes,
262            values: raw.values,
263            capacity: raw.capacity,
264        })
265    }
266}
267
268impl<'de> Deserialize<'de> for IntegerKnapsack {
269    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
270    where
271        D: serde::Deserializer<'de>,
272    {
273        let raw = RawIntegerKnapsack::deserialize(deserializer)?;
274        IntegerKnapsack::try_from(raw).map_err(serde::de::Error::custom)
275    }
276}
277
278#[cfg(feature = "example-db")]
279pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
280    // 5 items: sizes [3,4,5,2,7], values [4,5,7,3,9], capacity 15
281    // Optimal: c=(0,0,1,5,0) → total_size=5+10=15, total_value=7+15=22
282    vec![crate::example_db::specs::ModelExampleSpec {
283        id: "integer-knapsack",
284        instance: Box::new(
285            IntegerKnapsack::new(vec![3, 4, 5, 2, 7], vec![4, 5, 7, 3, 9], 15).unwrap(),
286        ),
287        optimal_config: serde_json::json!(vec![0, 0, 1, 5, 0]),
288        optimal_value: serde_json::json!(22),
289    }]
290}
291
292#[cfg(test)]
293#[path = "../../unit_tests/models/set/integer_knapsack.rs"]
294mod tests;
problemreductions/models/set/integer_knapsack.rs

problemreductions/models/set/
integer_knapsack.rs
