Performance of algorithms

[odow]

Xavier says

I recently tried to solve an instance with TambyVanderpooten, MOKP_p-6_n-30_1.dat, which is on Tamby's repo and presented as solved by their algorithm in the paper. It does not run on the MOA implementation (nothing after 24 hours)

Here's my Julia code:

using JuMP, HiGHS
import MultiObjectiveAlgorithms as MOA

function solve_tamby_mokp(filename)
    lines = readlines(filename)
    p = parse(Int, lines[1])
    n = parse(Int, lines[2])
    b = parse(Float64, lines[3])
    C = collect(reduce(hcat, Float64.(x.args) for x in Meta.parse(lines[4]).args)')
    w = Meta.parse(lines[5]).args
    model = Model(() -> MOA.Optimizer(HiGHS.Optimizer))
    set_attribute(model, MOA.Algorithm(), MOA.TambyVanderpooten())
    @variable(model, x[1:n], Bin)
    @constraint(model, w' * x <= b)
    @objective(model, Max, C * x)
    optimize!(model)
    assert_is_solved_and_feasible(model)
    return [value.(x; result) for result in 1:result_count(model)]
end


solve_tamby_mokp(
    "/Users/odow/git/tambysatya/TamVan19/Instances/MOKP/MOKP_p-6_n-30_1.dat"
)

Output is

julia> using JuMP, HiGHS

julia> import MultiObjectiveAlgorithms as MOA

julia> function solve_tamby_mokp(filename)
           lines = readlines(filename)
           p = parse(Int, lines[1])
           n = parse(Int, lines[2])
           b = parse(Float64, lines[3])
           C = collect(reduce(hcat, Float64.(x.args) for x in Meta.parse(lines[4]).args)')
           w = Meta.parse(lines[5]).args
           model = Model(() -> MOA.Optimizer(HiGHS.Optimizer))
           set_attribute(model, MOA.Algorithm(), MOA.TambyVanderpooten())
           @variable(model, x[1:n], Bin)
           @constraint(model, w' * x <= b)
           @objective(model, Max, C * x)
           optimize!(model)
           assert_is_solved_and_feasible(model)
           return [value.(x; result) for result in 1:result_count(model)]
       end
solve_tamby_mokp (generic function with 1 method)

julia> solve_tamby_mokp(
           "/Users/odow/git/tambysatya/TamVan19/Instances/MOKP/MOKP_p-6_n-30_1.dat"
       )
--------------------------------------------------------------------------------------------------
        MultiObjectiveAlgorithms.jl
--------------------------------------------------------------------------------------------------
Algorithm: TambyVanderpooten
--------------------------------------------------------------------------------------------------
solve #     Obj. 1       Obj. 2       Obj. 3       Obj. 4       Obj. 5       Obj. 6       Time    
--------------------------------------------------------------------------------------------------
    1   -1.17700e+03 -1.03200e+03 -1.07100e+03 -8.85000e+02 -8.46000e+02 -1.14100e+03  1.42563e+00
    2   -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00  1.42763e+00
    3   -1.07200e+03 -1.22100e+03 -1.18100e+03 -9.83000e+02 -8.90000e+02 -1.13000e+03  1.43889e+00
    4   -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00  1.43945e+00
    5   -8.84000e+02 -1.05600e+03 -1.37000e+03 -9.59000e+02 -8.78000e+02 -9.51000e+02  1.44168e+00
    6   -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00  1.44223e+00
    7   -8.95000e+02 -9.81000e+02 -1.09800e+03 -1.14300e+03 -6.92000e+02 -1.04800e+03  1.44480e+00
    8   -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00  1.44535e+00
    9   -9.14000e+02 -1.00700e+03 -1.11600e+03 -8.59000e+02 -1.11800e+03 -1.15500e+03  1.44794e+00
   10   -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00  1.44849e+00
   11   -9.23000e+02 -1.01000e+03 -9.91000e+02 -8.57000e+02 -7.84000e+02 -1.41500e+03  1.45187e+00
   12   -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00 -0.00000e+00  1.45241e+00
   13  auxillary subproblem                                                            1.49690e+00
   14   -1.17700e+03 -1.03200e+03 -1.07100e+03 -8.85000e+02 -8.46000e+02 -1.14100e+03  1.69627e+00
   15  auxillary subproblem                                                            1.91702e+00
   16   -9.14000e+02 -1.00700e+03 -1.11600e+03 -8.59000e+02 -1.11800e+03 -1.15500e+03  1.91964e+00
   17  auxillary subproblem                                                            1.92204e+00
   18   -8.95000e+02 -9.81000e+02 -1.09800e+03 -1.14300e+03 -6.92000e+02 -1.04800e+03  1.92448e+00
   19  auxillary subproblem                                                            1.93331e+00
   20   -1.07200e+03 -1.22100e+03 -1.18100e+03 -9.83000e+02 -8.90000e+02 -1.13000e+03  1.93606e+00
   21  auxillary subproblem                                                            1.93798e+00
   22   -8.84000e+02 -1.05600e+03 -1.37000e+03 -9.59000e+02 -8.78000e+02 -9.51000e+02  1.94063e+00
   23  auxillary subproblem                                                            1.94374e+00
   24   -9.23000e+02 -1.01000e+03 -9.91000e+02 -8.57000e+02 -7.84000e+02 -1.41500e+03  1.95118e+00
   25  auxillary subproblem                                                            1.96168e+00
   26   -9.16000e+02 -1.00000e+03 -1.15100e+03 -1.13100e+03 -6.99000e+02 -1.02500e+03  1.97200e+00
   27  auxillary subproblem                                                            1.99172e+00
   28   -8.72000e+02 -1.04100e+03 -1.13500e+03 -1.12900e+03 -7.53000e+02 -9.86000e+02  1.99935e+00
   29  auxillary subproblem                                                            2.01168e+00
   30   -9.66000e+02 -9.78000e+02 -1.14400e+03 -1.12600e+03 -7.60000e+02 -1.01700e+03  2.02175e+00
   31  auxillary subproblem                                                            2.04473e+00
   32   -8.70000e+02 -1.06700e+03 -1.20700e+03 -1.12200e+03 -7.63000e+02 -1.04500e+03  2.06123e+00
   33  auxillary subproblem                                                            2.08916e+00
   34   -9.15000e+02 -1.06600e+03 -1.15200e+03 -1.12100e+03 -8.03000e+02 -1.14600e+03  2.09270e+00
   35  auxillary subproblem                                                            2.09913e+00
   36   -8.71000e+02 -9.77000e+02 -1.21300e+03 -1.12100e+03 -8.38000e+02 -1.02200e+03  2.10892e+00
   37  auxillary subproblem                                                            2.11703e+00
   38   -9.04000e+02 -1.09700e+03 -1.36600e+03 -9.91000e+02 -8.93000e+02 -1.09800e+03  2.11984e+00
   39  auxillary subproblem                                                            2.17713e+00
   40   -9.15000e+02 -1.06600e+03 -1.15200e+03 -1.12100e+03 -8.03000e+02 -1.14600e+03  2.18210e+00
   41  auxillary subproblem                                                            2.18672e+00
   42   -9.04000e+02 -1.00700e+03 -1.15700e+03 -8.87000e+02 -1.11300e+03 -1.08400e+03  2.18866e+00
   43  auxillary subproblem                                                            2.20184e+00
   44   -9.96000e+02 -1.16100e+03 -1.29700e+03 -1.11800e+03 -8.49000e+02 -1.10800e+03  2.20434e+00
   45  auxillary subproblem                                                            2.21396e+00
   46   -9.93000e+02 -1.03700e+03 -1.06000e+03 -8.98000e+02 -8.36000e+02 -1.41200e+03  2.22656e+00
   47  auxillary subproblem                                                            2.25049e+00
   48   -9.38000e+02 -1.05300e+03 -1.18700e+03 -1.11400e+03 -8.50000e+02 -1.08400e+03  2.25784e+00
   49  auxillary subproblem                                                            2.30797e+00
   50   -1.00700e+03 -1.11300e+03 -1.22100e+03 -1.10800e+03 -8.58000e+02 -1.15600e+03  2.31168e+00
  ... lines omitted ...
  977  auxillary subproblem                                                            1.39737e+02
  978   -9.96000e+02 -1.16100e+03 -1.29700e+03 -1.11800e+03 -8.49000e+02 -1.10800e+03  1.39740e+02
  979  auxillary subproblem                                                            1.40425e+02
  980   -9.96000e+02 -1.16100e+03 -1.29700e+03 -1.11800e+03 -8.49000e+02 -1.10800e+03  1.40427e+02
  981  auxillary subproblem                                                            1.41089e+02
  982   -9.96000e+02 -1.16100e+03 -1.29700e+03 -1.11800e+03 -8.49000e+02 -1.10800e+03  1.41092e+02
^C--------------------------------------------------------------------------------------------------
TerminationStatus: INTERRUPTED
ResultCount: 276
--------------------------------------------------------------------------------------------------
ERROR: The model was not solved correctly. Here is the output of `solution_summary` to help debug why this happened:

solution_summary(; result = 1, verbose = false)
├ solver_name          : MOA[algorithm=MultiObjectiveAlgorithms.TambyVanderpooten, optimizer=HiGHS]
├ Termination
│ ├ termination_status : INTERRUPTED
│ ├ result_count       : 276
│ ├ raw_status         : Solve complete. Found 276 solution(s)
│ └ objective_bound    : [1.17700e+03,1.22100e+03,1.37000e+03,1.14300e+03,1.11800e+03,1.41500e+03]
├ Solution (result = 1)
│ ├ primal_status        : FEASIBLE_POINT
│ ├ dual_status          : NO_SOLUTION
│ └ objective_value      : [1.17700e+03,1.03200e+03,1.07100e+03,8.85000e+02,8.46000e+02,1.14100e+03]
└ Work counters
  └ solve_time (sec)   : 1.41759e+02

Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:44
 [2] #assert_is_solved_and_feasible#103
   @ ~/.julia/packages/JuMP/e83v9/src/optimizer_interface.jl:1008 [inlined]
 [3] assert_is_solved_and_feasible
   @ ~/.julia/packages/JuMP/e83v9/src/optimizer_interface.jl:1002 [inlined]
 [4] solve_tamby_mokp(filename::String)
   @ Main ./REPL[4]:14
 [5] top-level scope
   @ REPL[5]:1

I don't know if this is expected behaviour of if we're not excluding some of the search boxes correctly.

[odow]

Here are their results

Their large ones are long, but we're much slower, even for the small cases.

We should profile where the time is being spent.

[odow]

Profile shows 99.99% of the time is being spent inside HiGHS:

So I think HiGHS is just slow at this particular problem. It doesn't exploit knapsack problems.

[odow]

If I run with Gurobi, I get

Julia> times = map(1:10) do i
           filename = "/Users/odow/git/tambysatya/TamVan19/Instances/MOKP/MOKP_p-2_n-200_$i.dat"
           return @elapsed solve_tamby_mokp(filename)
       end;

julia> times
10-element Vector{Float64}:
  8.112646917
  9.263961084
 11.470410792
  9.949387208
 11.309914208
 16.189289166
 20.0379645
 16.238183541
 16.323672583
 15.724351166

julia> import Statistics

julia> Statistics.mean(times)
13.461978116500001

Which is pretty much bang-on what they report (12.2 sec), and I could building the JuMP model, etc.

So I vote: our algorithm is pretty much identical. The sub-solver matters beyond anything else.

[odow]

We do get slightly different $|Y_{ND}|$

10-element Vector{@NamedTuple{solve_time::Float64, result_count::Int64, subproblem_count::Int64}}:
 (solve_time = 7.609483003616333, result_count = 318, subproblem_count = 642)
 (solve_time = 9.086111068725586, result_count = 317, subproblem_count = 640)
 (solve_time = 11.524394989013672, result_count = 400, subproblem_count = 806)
 (solve_time = 10.208057880401611, result_count = 316, subproblem_count = 638)
 (solve_time = 11.512331008911133, result_count = 358, subproblem_count = 722)
 (solve_time = 16.278954029083252, result_count = 464, subproblem_count = 934)
 (solve_time = 20.590292930603027, result_count = 521, subproblem_count = 1048)
 (solve_time = 17.077609062194824, result_count = 475, subproblem_count = 956)
 (solve_time = 17.883409023284912, result_count = 462, subproblem_count = 930)
 (solve_time = 18.119823932647705, result_count = 430, subproblem_count = 866)

julia> import Statistics

julia> Statistics.mean(map(r -> r.solve_time, ret))
13.989046692848206

julia> Statistics.mean(map(r -> r.result_count, ret))
406.1

julia> Statistics.mean(map(r -> r.subproblem_count, ret))
818.2

It's a bit hard to compare because they present only the means. Our subproblem count is consistent. It's roughly 2x the result count because we could the auxiliary subproblem, and we also count the initial solves to compute the ideal/nadir point.

We have 7 extra non-dominated points, but I don't know if that is one instance with more points, or 1 point scattered across 7 instances.

[odow]

The 7 extra solutions were wrong because we weren't filtering the solutions: #168

julia> for i in 1:10
           points = MOA.SolutionPoint.((Dict(),), ret[i].Y)
           new_points = MOA.filter_nondominated(MOI.MAX_SENSE, points)
           @show length(points), length(new_points)
       end
(length(points), length(new_points)) = (318, 317)  # 1
(length(points), length(new_points)) = (317, 316)  # 1
(length(points), length(new_points)) = (400, 399) # 1
(length(points), length(new_points)) = (316, 316)
(length(points), length(new_points)) = (358, 358)
(length(points), length(new_points)) = (464, 464)
(length(points), length(new_points)) = (521, 518) # 3
(length(points), length(new_points)) = (475, 475)
(length(points), length(new_points)) = (462, 462)
(length(points), length(new_points)) = (430, 429) # 1

7 extra as expected.

[kofgokhan]

What about memory?

[odow]

What about memory? I think the issue is that HiGHS is tuned for larger MIPs. It doesn’t exploit small ones like this

[kofgokhan]

The authors say they ran their implementation 7.8 GB of ram so I was wondering how much we are using because I was not able to replicate their implementation with 16 GB.

[odow]

Hmm with what solver?

[kofgokhan]

CPLEX in Haskell

[odow]

You used CPLEX in Haskell or HiGHS+MOA? (I know they used Haskell+CPLEX.)

[kofgokhan]

I tried their implementation in Haskell with CPLEX and I ran out of memory. With MOA, I never ran out of memory.

[kofgokhan]

Also, evaluating the performance between a general purpose solver and a specific implementation designed to work for only discrete problems is unfair in the sense that the authors know for sure that the nondominated points will be integer points so they can use things like lookup tables while in MOA we have to check each nondominated point with tolerances.

[odow]

With MOA, I never ran out of memory.

Good, yes, I expected that.

My sense from profiling is that all of the time we spend in MOA is ~0% of the run-time. It's entirely dominated by the sub-solvers. So checking with tolerances isn't a performance issue.

I think CPLEX probably just has a heuristic that can detect knapsack constraints and solve with dynamic programming.