CODEWITHSUNDEEP
julialinear-programmingjulia-jump
JKHA
JKHA

Reputation: 1896

JuMP - multiple solutions in Integer and 0-1 Programming

In JuMP, Julia v1.3.1,

using JuMP, GLPK


function example_basic(n = 4)
    model = Model(GLPK.Optimizer)
    @variable(model, x1, Bin)
    @variable(model, x2, Bin)
    @variable(model, C <= 1)

    @objective(model, Max,   C)

    @constraint(model, x1 + x2 <= C)

    # if verbose
    #     print(model)
    # end

    JuMP.optimize!(model)

    obj_value = JuMP.objective_value(model)
    # num_results = 1
    num_results = result_count(model)
    @show num_results

end

Returns 1. I just don't understand the programming behind this result. Because there are clearly 2 optimal solutions for this tiny linear problem:

(x1,x2)=(0,1)=(1,0)

How come JuMP returns 1?

My best guess is that GLPK doesn't support multiple solutions for Integer Programming because the documentation says:

Some solvers support returning multiple solutions. You can check how many solutions are available to query using result_count.

Then I tried another solver: Cbc, but the result was the same. If my issue is that both solvers don't support multiple solutions, how could I have the list of JuMP solvers that do?

Upvotes: 1

Views: 630

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

Traditionally MIP solvers just return one solution. Most (or even all) free solvers follow this approach and just return one solution. Some commercial solvers have something called a solution pool to hold multiple solutions.

There is a way to enumerate optimal or second best MIP solutions by adding a cut to the problem and resolve. See How to ask for second best solution to a MIP using JuMP.

Upvotes: 3

Related Questions