Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Performance of algorithms

Abierto
  • ¿Algo no está bien?
#167 29 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
35/100
Tipo de issue
Error
Claridad
Bastante claro
Estado de actividad
Estancado
Stack tecnológico
julia
Área
tooling

Línea de trabajo

Reproduce la ejecución informada con el código de Julia, HiGHS, el algoritmo TambyVanderpooten de MOA y MOKP_p-6_n-30_1.dat. Inspecciona el comportamiento de exclusión de la caja de búsqueda del algoritmo y el estado de terminación; se considera terminado cuando se determine si la ejecución larga y el resultado interrumpido son esperados, o se identifique el comportamiento incorrecto que debe corregirse.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
Julia
Estrellas
87
Forks
10
Sin PR fusionados en 30 d

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de jump-dev/MultiObjectiveAlgorithms.jl

Todos los issues de jump-dev/MultiObjectiveAlgorithms.jl

Issues similares

Más issues de Julia

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.