Knapsacks

Julia package to solve Knapsack problems

https://github.com/rafaelmartinelli/knapsacks.jl

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
○
DOI references
○
Academic publication links
○
Committers with academic emails
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (14.9%) to scientific vocabulary

Keywords

julia knapsack optimization

Keywords from Contributors

interpretability standardization animal hack

Last synced: 6 months ago · JSON representation ·

Repository

Julia package to solve Knapsack problems

Basic Info

Host: GitHub
Owner: rafaelmartinelli
License: mit
Language: Julia
Default Branch: main
Homepage:
Size: 244 KB

Statistics

Stars: 22
Watchers: 2
Forks: 6
Open Issues: 3
Releases: 8

Topics

julia knapsack optimization

Created almost 5 years ago · Last pushed over 2 years ago

Metadata Files

Readme License Citation

Knapsacks.jl

This package solves Knapsack Problems (KPs) using different algorithms.

Usage

First, the package defines the Knapsack type:

julia struct Knapsack capacity::Int64 # Knapsack capacity weights ::Vector{Int64} # Items' weights profits ::Vector{Int64} # Items' profits end

Then, there are four available solvers, called from a single function which takes a Knapsack instance, and returns the optimal/best value and an Array with the selected items:

julia function solveKnapsack(data::KnapsackData, algorithm::Symbol = :ExpandingCore; optimizer = nothing)

Where algorithm must be one of the following:

DynamicProgramming: Solves KP using a naïve dynamic programming.
BinaryModel: Solves KP using a binary programming model.
ExpandingCore: Solves KP using Pisinger's expanding core algorithm.
Heuristic: Solves KP using a simple heuristic.

Algorithm BinaryModel uses JuMP, and the user must pass the optimizer.

For example, given a Knapsack instance data:

julia optimal, selected = solveKnapsack(data, :DynamicProgramming) optimal, selected = solveKnapsack(data, :BinaryModel; optimizer = GLPK.Optimizer) optimal, selected = solveKnapsack(data, :ExpandingCore) value, selected = solveKnapsack(data, :Heuristic)

Instance generator

The package is able to generate random instances of Knapsack with the following function (based on this code):

julia function generateKnapsack(num_items::Int64, range::Int64 = 1000; type::Symbol = :Uncorrelated, seed::Int64 = 42, num_tests::Int64 = 1000)::Knapsack

Where:

num_items: Number of items.
range: Maximum weight value.
type: Profit type (:Uncorrelated, :WeakCorrelated, :StrongCorrelated, :SubsetSum).
seed: Random seed value.
num_tests: Check source code or original code.

Installation

This package is a registered Julia Package, and can be installed through the Julia package manager.
Open Julia's interactive session (REPL) and type:

julia ] add Knapsacks

Benchmark

Benchmark results (time in seconds) for different maximum values for weights and profits, number of items and algorithms. Average times for 10 runs and using @timed (BinaryModel using GLPK.jl).

```text

MaxV\Items 10 100 500 1000 2000 4000 Algorithm

         0.0000022  0.0000111  0.0000565  0.0001892  0.0007063  0.0026810  DynamicProgramming
     10  0.0001429  0.0003092  0.0009412  0.0019578  0.0039707  0.0122269  BinaryModel
         0.0000072  0.0000293  0.0001384  0.0003038  0.0006792  0.0013258  ExpandingCore
         0.0000016  0.0000052  0.0000235  0.0000478  0.0001008  0.0002182  Heuristic

         0.0000062  0.0000499  0.0003760  0.0011797  0.0110915  0.0434132  DynamicProgramming
    100  0.0001357  0.0004809  0.0017649  0.0040757  0.0093222  0.0269660  BinaryModel
         0.0000095  0.0000600  0.0002152  0.0003791  0.0007064  0.0010730  ExpandingCore
         0.0000013  0.0000050  0.0000192  0.0000409  0.0000928  0.0001957  Heuristic

         0.0000167  0.0001582  0.0013383  0.0115258  0.0674425  0.3561994  DynamicProgramming
    500  0.0001290  0.0006400  0.0017707  0.0056317  0.0174576  0.0483382  BinaryModel
         0.0000090  0.0000473  0.0002074  0.0003911  0.0006959  0.0014079  ExpandingCore
         0.0000013  0.0000044  0.0000191  0.0000417  0.0000866  0.0001854  Heuristic

         0.0000306  0.0003130  0.0063493  0.0296504  0.1574919  0.7645551  DynamicProgramming
   1000  0.0001279  0.0003963  0.0021209  0.0089878  0.0247364  0.0634847  BinaryModel
         0.0000084  0.0000498  0.0002309  0.0004473  0.0010606  0.0015858  ExpandingCore
         0.0000014  0.0000043  0.0000209  0.0000423  0.0000873  0.0001845  Heuristic

         0.0000616  0.0007209  0.0174228  0.0695316  0.3422440  1.6595295  DynamicProgramming
   2000  0.0001297  0.0004131  0.0024877  0.0062686  0.0211603  0.0714104  BinaryModel
         0.0000090  0.0000538  0.0002315  0.0004709  0.0008501  0.0018993  ExpandingCore
         0.0000014  0.0000045  0.0000225  0.0000422  0.0000866  0.0001845  Heuristic

```

Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz, 64GB RAM, using Julia 1.7.2 on Ubuntu 20.04 LTS.

How to cite this package

You can use the bibtex file available in the project.

Don't forget to star our package!

Other packages

BPPLib.jl: Bin Packing Problem and Cutting Stock Problem Lib
GAPLib.jl: Generalized Assignment Problem Lib
FacilityLocationProblems.jl: Capacitated Facility Location Problem Lib
CARPData.jl: Capacitated Arc Routing Problem Lib

Owner

Name: Rafael Martinelli
Login: rafaelmartinelli
Kind: user
Location: Rio de Janeiro
Company: PUC-Rio

Website: http://www.ind.puc-rio.br/equipe/rafael-martinelli/
Twitter: rafaelmartinel8
Repositories: 7
Profile: https://github.com/rafaelmartinelli

Rafael Martinelli is professor at the Department of Industrial Engineering of the Pontifical Catholic University of Rio de Janeiro (PUC-Rio), Brazil.

Citation (citation.bib)

@misc{Knapsacks2021,
  author = {Rafael Martinelli},
  title  = {{Knapsacks.jl: Julia package to solve Knapsack problems}},
  year   = 2021,
  note   = {\url{https://github.com/rafaelmartinelli/Knapsacks.jl}}
}

GitHub Events

Total

Watch event: 3
Fork event: 1

Last Year

Watch event: 3
Fork event: 1

Committers

Last synced: 8 months ago

All Time

Total Commits: 30
Total Committers: 3
Avg Commits per committer: 10.0
Development Distribution Score (DDS): 0.067

Past Year

Commits: 0
Committers: 0
Avg Commits per committer: 0.0
Development Distribution Score (DDS): 0.0

Top Committers

Name	Email	Commits
Rafael Martinelli	m**i@p**r	28
github-actions[bot]	4****]	1
SundaraRaman R	s**n@g**m	1

Committer Domains (Top 20 + Academic)

puc-rio.br: 1

Issues and Pull Requests

Last synced: 6 months ago

All Time

Total issues: 10
Total pull requests: 12
Average time to close issues: about 2 months
Average time to close pull requests: 25 minutes
Total issue authors: 3
Total pull request authors: 3
Average comments per issue: 0.4
Average comments per pull request: 0.67
Merged pull requests: 11
Bot issues: 0
Bot pull requests: 1

Past Year

Issues: 0
Pull requests: 0
Average time to close issues: N/A
Average time to close pull requests: N/A
Issue authors: 0
Pull request authors: 0
Average comments per issue: 0
Average comments per pull request: 0
Merged pull requests: 0
Bot issues: 0
Bot pull requests: 0

View more stats

Top Authors

Issue Authors

rafaelmartinelli (8)
JuliaTagBot (1)
jlchan (1)

Pull Request Authors

rafaelmartinelli (10)
github-actions[bot] (1)
digital-carver (1)

Top Labels

Issue Labels

enhancement (7) bug (2)

Pull Request Labels

enhancement (7) bug (3)

Packages

Total packages: 1
Total downloads:
- julia 1 total

Total dependent packages: 0
Total dependent repositories: 0
Total versions: 1

juliahub.com: Knapsacks

Julia package to solve Knapsack problems

Documentation: https://docs.juliahub.com/General/Knapsacks/stable/
License: MIT
Latest release: 1.1.0
published over 3 years ago

Versions: 1
Dependent Packages: 0
Dependent Repositories: 0
Downloads: 1 Total

Rankings

Dependent repos count: 9.9%

Average: 26.7%

Forks count: 28.1%

Stargazers count: 29.9%

Dependent packages count: 38.9%

Last synced: 6 months ago

Dependencies

.github/workflows/CI.yml actions

actions/cache v1 composite
actions/checkout v2 composite
codecov/codecov-action v1 composite
julia-actions/julia-buildpkg v1 composite
julia-actions/julia-processcoverage v1 composite
julia-actions/julia-runtest v1 composite
julia-actions/setup-julia v1 composite

.github/workflows/CompatHelper.yml actions

.github/workflows/TagBot.yml actions

JuliaRegistries/TagBot v1 composite

Knapsacks

Science Score: 44.0%

Keywords

Keywords from Contributors

Repository

Basic Info

Statistics

Topics

Metadata Files

README.md

Knapsacks.jl

Usage

Instance generator

Installation

Benchmark

```text

MaxV\Items 10 100 500 1000 2000 4000 Algorithm

How to cite this package

Related links

Other packages

Owner

Citation (citation.bib)

GitHub Events

Total

Last Year

Committers

All Time

Past Year

Top Committers

Committer Domains (Top 20 + Academic)

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels

Packages

juliahub.com: Knapsacks

Rankings

Dependencies