I am trying to learn Julia for educational purposes. Specially, I trying to use Julia and the package JuMP to solve operational research problems.
I was watching this great video from youtube. A guy, named Philip Thomas, shows a didatic example. However, this video was produced in 2014. Since then, Julia has evolved.
He used this code:
#=
We are going to the thrift store and need 99 cents. What is the least amount of
weight we need to carry?
i.e. a knapsack problem
We specify that you need at least 99 cents - does the answer change if you need exact change?
=#
using JuMP
using Cbc # Open source solver. Must support integer programming.
m = Model(solver=CbcSolver())
# Variables represent how many of each coin we want to carry
@defVar(m, pennies >= 0, Int)
@defVar(m, nickels >= 0, Int)
@defVar(m, dimes >= 0, Int)
@defVar(m, quarters >= 0, Int)
# We need at least 99 cents
@addConstraint(m, 1 * pennies + 5 * nickels + 10 * dimes + 25 * quarters >= 99)
# Minimize mass (Grams)
# (source: US Mint)
@setObjective(m, Min, 2.5 * pennies + 5 * nickels + 2.268 * dimes + 5.670 * quarters)
# Solve
status = solve(m)
println("Minimum weight: ", getObjectiveValue(m), " grams")
println("using:")
println(round(getValue(pennies)), " pennies") # "round" to cast as integer
println(round(getValue(nickels)), " nickels")
println(round(getValue(dimes)), " dimes")
println(round(getValue(quarters)), " quarters")
His code returns this result:
Minimum weight: 22.68 grams
using:
0.0 pennies
0.0 nickels
0.0 dimes
4.0 quarters
I am using the current version of Julia (1.0). Moreover, I am using the current version of JUMP. There are syntactic differences between the current version of Julia and the code above. After some trial and error, I was able to properly translate the code to make it run in Julia 1.0:
#=
We are going to the thrift store and need 99 cents. What is the least amount of
weight we need to carry?
i.e. a knapsack problem
We specify that you need at least 99 cents - does the answer change if you need exact change?
=#
using JuMP
using GLPK
using Cbc # Open source solver. Must support integer programming.
model = Model(with_optimizer(GLPK.Optimizer))
# Variables represent how many of each coin we want to carry
@variable(model, pennies >= 0, Int)
@variable(model, nickels >= 0, Int)
@variable(model, dimes >= 0, Int)
@variable(model, quarters >= 0, Int)
# We need at least 99 cents
@constraint(model, 1 * pennies + 5 * nickels + 10 * dimes + 25 * quarters >= 99)
# Minimize mass (Grams)
# (source: US Mint)
@objective(model, Min, 2.5 * pennies + 5 * nickels + 2.268 * dimes + 5.670 * quarters)
# Solve
optimize!(model)
println("Minimum weight: ", objective_value(model), " grams")
println("using:")
println(round(value(pennies)), " pennies") # "round" to cast as integer
println(round(value(nickels)), " nickels")
println(round(value(dimes)), " dimes")
println(round(value(quarters)), " quarters")
The interesting thing is the result the terminal returned:
Minimum weight: 22.68 grams
using:
0.0 pennies
0.0 nickels
0.0 dimes
4.0 quarters
As you can see, the final result concerning the minimum weight remains the same. However, the decision about what coin to get changes from 10 dimes to 4 quarters.
Besides the syntactic changes, I modified the solver because, initially, I was not being able to run Cbc.
After that, I changed again to Cbc with this simple modification:
model = Model(with_optimizer(Cbc.Optimizer))
After the modification above the "code translation" was closer to the original with Cbc as the chosen solver. Curiously, the program returns the expected result:
Minimum weight: 22.68 grams
using:
0.0 pennies
0.0 nickels
10.0 dimes
0.0 quarters
However, I am still confused. According to the documentation both solvers can solve MILP (Mixed Integer Linear Problems).
Why this happens? Why different solvers return different results if they both have a similar profile? Did I miss some detail during the code translation?
Thanks in advance.
As you already discovered the value of the target function is the same for both solutions. Which solution is reached depends on the path that the solver went through to reach it.
Differences in the path may arise in the Simplex optimizer used to solve individual LP subproblems. Switching the sequence of variables or rows may be sufficient to end up in another point of the solution set. Some solver even use a random number generator to determine which variable enters the base in the Simplex algorithm first (but not GLPK).
Another reason for reaching a different solution may be the sequence in which the search tree for the integer variables is searched. This is influenced amongst others by the search strategy (e.g. depth first vs breadth first).