Equality constraint with right-hand side variable

[wjholden]

Good morning! I am using Pumpkin-Solver to model part 2 of Advent of Code 2025 Day 10. I got it to work, but I have a question. The constraints::equals function expects an i32 in its right-hand side. For variables a, b, c, d, e, f, and z, we cannot model a + b + c + d + e + f = z directly. Instead, I had to build up the partial sums as intermediate variables using the constraints::plus function. Was there a better way to do this?

Here is my program:

use pumpkin_solver::{
    ConstraintOperationError, DefaultBrancher, Solver, constraints,
    optimisation::{OptimisationDirection, linear_sat_unsat::LinearSatUnsat},
    results::{OptimisationResult, ProblemSolution, SolutionReference},
    termination::Indefinite,
};

/// This is the first example from Part 2 of
/// [Advent of Code 2025 Day 10](https://adventofcode.com/2025/day/10#part2).
///
/// This program minimizes the sum of non-negative integers a, b, c, d, e, and
/// f such that the matrix product A times a vector x={a,b,c,d,e,f} is equal
/// to vector y={3,5,4,7}. In the Wolfram language,
///
/// ```mathematica
/// In[1]:= A := {{0, 0, 0, 0, 1, 1}, {0, 1, 0, 0, 0, 1}, {0, 0, 1, 1, 1, 0}, {1, 1, 0, 1, 0, 0}}
///
/// In[2]:= x := {a,b,c,d,e,f}
///
/// In[3]:= y := {3,5,4,7}
///
/// In[4]:= Minimize[Total[x], A.x == y, x, NonNegativeIntegers]
///
/// Out[4]= {10, {a -> 1, b -> 3, c -> 0, d -> 3, e -> 1, f -> 2}}
/// ```
fn main() -> Result<(), ConstraintOperationError> {
    let mut solver = Solver::default();

    let a = solver.new_bounded_integer(0, 100);
    let b = solver.new_bounded_integer(0, 100);
    let c = solver.new_bounded_integer(0, 100);
    let d = solver.new_bounded_integer(0, 100);
    let e = solver.new_bounded_integer(0, 100);
    let f = solver.new_bounded_integer(0, 100);

    // 3 = e + f
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals(vec![e, f], 3, tag))
        .post()?;

    // 5 = b + f
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals(vec![b, f], 5, tag))
        .post()?;

    // 4 = c + d + e
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals(vec![c, d, e], 4, tag))
        .post()?;

    // 7 = a + b + d
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals(vec![a, b, d], 7, tag))
        .post()?;

    // Our goal is to minimize a + b + c + d + e + f, but the function
    // `constraints::equals(terms, rhs, constraint_tag)` expects an i32 for the
    // right-hand side. You cannot put another variable in the right-hand side.
    //
    // Instead, you can use `constraints::plus(a, b, c, constraint_tag)` to
    // model the dependencies between variables a, b, and c.
    //
    // We build up the intermediate sums of dependent variables as
    // a + b + c + d + e + f = ((((a + b) + c) + d) + e) + f.
    let ab = solver.new_bounded_integer(0, 100);
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::plus(a, b, ab, tag))
        .post()?;

    let abc = solver.new_bounded_integer(0, 100);
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::plus(ab, c, abc, tag))
        .post()?;

    let abcd = solver.new_bounded_integer(0, 100);
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::plus(ab, d, abcd, tag))
        .post()?;

    let abcde = solver.new_bounded_integer(0, 100);
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::plus(abcd, e, abcde, tag))
        .post()?;

    // This is our minimization objective, a + b + c + d + e + f.
    let abcdef = solver.new_bounded_integer(0, 100);
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::plus(abcde, f, abcdef, tag))
        .post()?;

    // Copied from https://docs.rs/pumpkin-solver/0.2.2/pumpkin_solver/index.html#using-pumpkin
    let mut termination = Indefinite;
    let mut brancher = solver.default_brancher();
    let callback: fn(&pumpkin_solver::Solver, SolutionReference, &DefaultBrancher) = |_, _, _| {};
    let result = solver.optimise(
        &mut brancher,
        &mut termination,
        LinearSatUnsat::new(OptimisationDirection::Minimise, abcdef, callback),
    );

    match result {
        OptimisationResult::Optimal(solution) => println!("{}", solution.get_integer_value(abcdef)),
        OptimisationResult::Satisfiable(_) => unreachable!(),
        OptimisationResult::Unsatisfiable => panic!("Not satisfiable"),
        OptimisationResult::Unknown => panic!("No result from solver"),
    }

    Ok(())
}

[ImkoMarijnissen]

Thank you for your question. It is nice to see that you are using Pumpkin for the Advent of Code!

In general, we would recommend making use of views (see, for example, this paper) to implement this behaviour.

You can then implement the constraint a + b + c + d + e + f = z by rewriting it to a + b + c + d + e + f - z = 0 in the following way (note that z is scaled by -1 instead of 1):

    constraints::equals(
        [
            a.scaled(1),
            b.scaled(1),
            c.scaled(1),
            d.scaled(1),
            e.scaled(1),
            f.scaled(1),
            z.scaled(-1),
        ],
        0,
        tag,
    )
    .post(&mut solver)?;

I think you make a good point that we could either declare a function which takes these inputs, or clarify in the documentation!

If you have any additional questions, please don't hesitate to let us know.

[wjholden]

It works, thank you! Having fewer variables even gave me a modest performance boost. (This performance analysis is for my 174-line Advent of Code 2025 Day 10 puzzle, not the single problem described above.)

PS> hyperfine ".\day10-v1.exe" ".\day10-v2.exe"
Benchmark 1: .\day10-v1.exe
  Time (mean ± σ):     30.520 s ±  0.639 s    [User: 102.848 s, System: 0.638 s]
  Range (min … max):   29.449 s … 31.820 s    10 runs

Benchmark 2: .\day10-v2.exe
  Time (mean ± σ):     24.586 s ±  0.322 s    [User: 79.786 s, System: 0.612 s]
  Range (min … max):   24.098 s … 25.090 s    10 runs

Summary
  .\day10-v2.exe ran
    1.24 ± 0.03 times faster than .\day10-v1.exe

For anyone else reading, here is the improved algorithm:

use pumpkin_solver::{
    ConstraintOperationError, DefaultBrancher, Solver, constraints,
    optimisation::{OptimisationDirection, linear_sat_unsat::LinearSatUnsat},
    results::{OptimisationResult, ProblemSolution, SolutionReference},
    termination::Indefinite,
    variables::TransformableVariable,
};

fn main() -> Result<(), ConstraintOperationError> {
    let mut solver = Solver::default();

    let a = solver.new_bounded_integer(0, 100);
    let b = solver.new_bounded_integer(0, 100);
    let c = solver.new_bounded_integer(0, 100);
    let d = solver.new_bounded_integer(0, 100);
    let e = solver.new_bounded_integer(0, 100);
    let f = solver.new_bounded_integer(0, 100);

    // z is our minimization objective.
    let z = solver.new_bounded_integer(0, 100);

    // 3 = e + f
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals([e, f], 3, tag))
        .post()?;

    // 5 = b + f
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals([b, f], 5, tag))
        .post()?;

    // 4 = c + d + e
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals([c, d, e], 4, tag))
        .post()?;

    // 7 = a + b + d
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals([a, b, d], 7, tag))
        .post()?;

    // a + b + c + d + e + f = z, which means a + b + c + d + e + e - z = 0.
    let tag = solver.new_constraint_tag();
    solver
        .add_constraint(constraints::equals(
            [
                a.scaled(1),
                b.scaled(1),
                c.scaled(1),
                d.scaled(1),
                e.scaled(1),
                f.scaled(1),
                z.scaled(-1),
            ],
            0,
            tag,
        ))
        .post()?;

    let mut termination = Indefinite;
    let mut brancher = solver.default_brancher();
    let callback: fn(&pumpkin_solver::Solver, SolutionReference, &DefaultBrancher) = |_, _, _| {};
    let result = solver.optimise(
        &mut brancher,
        &mut termination,
        LinearSatUnsat::new(OptimisationDirection::Minimise, z, callback),
    );

    match result {
        OptimisationResult::Optimal(solution) => println!("{}", solution.get_integer_value(z)),
        OptimisationResult::Satisfiable(_) => unreachable!(),
        OptimisationResult::Unsatisfiable => panic!("Not satisfiable"),
        OptimisationResult::Unknown => panic!("No result from solver"),
    }

    Ok(())
}

Would this make a good contribution to the pumpkin-solver examples?

[ImkoMarijnissen]

I am glad to hear that it worked out!

I think having more examples would not hurt. However, it would need a bit more of an abstract description than is usually provided by the AoC. If you have such a description (it seems to be minimising a linear sum while putting constraints on certain partial sums), then that would be great!