Right solver for JuMP to find every solution of a linear system of equations with integer solutions

Specific Domains Optimization (Mathematical)
,
22

No problem.
While it’s fresh in my mind, here is a more general solution for future reference:

## Packages
using JuMP
using Gurobi

function example_big_sum(rowsum, colsum; verbose::Bool = true)
    ## Model:
    model = Model(Gurobi.Optimizer)
    @assert length(rowsum) == length(colsum)

    N = length(rowsum)
    INDEX = 1:N
    @variable(model, y[INDEX,INDEX] >= 0, Int)

    @constraint(model, rowCons[i=INDEX], sum(y[i,j] for j in INDEX) == rowsum[i])
    @constraint(model, colCons[j=INDEX], sum(y[i,j] for i in INDEX) == colsum[j])

    if verbose; print(model); end

    ## Gurobi parameters - see https://www.gurobi.com/documentation/9.0/refman/finding_multiple_solutions.html
    JuMP.set_optimizer_attribute(model, "PoolSearchMode", 2)   # exhaustive search mode
    JuMP.set_optimizer_attribute(model, "PoolSolutions", 100)  # 100 is an arbitrary (large enough) whole number

    if !verbose; JuMP.set_optimizer_attribute(model, "OutputFlag", 0); end

    ## Optimize:
    JuMP.optimize!(model)

    ## Results:
    num_results = result_count(model)
    if verbose; println("Number of results: ", num_results, "\n"); end

    Results = Array{Array{Int64},1}()  ## Note the conversion to Int64
    for n in 1:num_results
        sol = Array{Int64}(undef, N, N)
        for i in INDEX
            for j in INDEX
                sol[i,j] = JuMP.value(y[i,j]; result=n)
            end
        end

        push!(Results,sol)
        if verbose
            println(Results[n])
        end
    end

    return Results
end

μ = [0,2,3,1]
ν = [2,2,1,1]
solutions = example_big_sum(μ,ν);

FYI: 24 solutions found as other posts show.

6 Likes