Knapsacks.jl - GitLite

KO | EN

gitlite — search

#android #data-science #machine-learning #docker #list #codex #cli #awesome #ai-agent #golang

Knapsacks.jl

(★ 26)

Julia package to solve Knapsack problems

File Explorer

ZIP Download

- - bug_report.md
  - feature_request.md
- - CI.yml
  - CompatHelper.yml
  - TagBot.yml
- - index.md
- make.jl
- Project.toml
- Data.jl
- ExpandingCore.jl
- Generator.jl
- Heuristic.jl
- Knapsacks.jl
- Model.jl
- Naive.jl
- Solver.jl
- compare.jl
- Project.toml
- runtests.jl
.gitignore
citation.bib
LICENSE
Project.toml
README.md

# Use via CDN

jsDelivr

jsDelivr serves any public GitHub repository as a CDN with zero setup. Pick a version and a file to get a ready-to-paste link and snippet.

Version

File

Link

Example

Command Glossary

Commands referenced in this DOCs, explained below.

🔍

`timed`

View Details ▼

Service that synchronizes system time (e.g. using NTP).
Note: It should not be invoked manually.

timed

Start the daemon:

# Project Badges

Stable Visit
Dev Visit
Build Status Visit
Coverage Visit
Project Status: Active – The project has reached a stable, usable state and is being actively developed. Visit

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

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](https://jump.dev/), 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](http://hjemmesider.diku.dk/~pisinger/generator.c)):

```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](https://github.com/rafaelmartinelli/Knapsacks.jl/blob/main/citation.bib) available in the project.

Don't forget to star our package!

## Related links

- [David Pisinger's optimization codes](http://hjemmesider.diku.dk/~pisinger/codes.html)

## Other packages

- [BPPLib.jl](https://github.com/rafaelmartinelli/BPPLib.jl): Bin Packing Problem and Cutting Stock Problem Lib
- [GAPLib.jl](https://github.com/rafaelmartinelli/GAPLib.jl): Generalized Assignment Problem Lib
- [FacilityLocationProblems.jl](https://github.com/rafaelmartinelli/FacilityLocationProblems.jl): Capacitated Facility Location Problem Lib
- [CARPData.jl](https://github.com/rafaelmartinelli/CARPData.jl): Capacitated Arc Routing Problem Lib