MyNixOS website logo
Description

Multiple Knapsack Problem Solver.

Package solves multiple knapsack optimisation problem. Given a set of items, each with volume and value, it will allocate them to knapsacks of a given size in a way that value of top N knapsacks is as large as possible.

Build Status codecov.io

mknapsack

This package solves multiple knapsack problem by assigning items optimally to knapsacks using Mixed Integer Linear Programming (MILP) solver of choice.

Definition of the mknapsack problem

We start with a list of items that we want to order with each assigned a:

  • sku - this is an id of the product / item that we want to order.
  • profit - expected profit from sales of this item
  • volume - this can be m3 of the box for example
  • moq - mininum order quanity (MOQ)
  • sold - flag that defines if this item must be added as highest priority prior to othe items

Those items should be optimally packed into multiple containers of the a given size (cap). Items should be aded to containers in the way that each container is more profitable than the following one.

Supported solvers

Package implements interface to several solvers which can be set via mknapsack.solver option.

Currently you can choose from those options:

lpsolve is default option.

Example

Solve problem with CBC COIN-OR solver:

set.seed(100)
devtools::install_github("dirkschumacher/rcbc")
devtools::install_github("dirkschumacher/ROI.plugin.cbc")
devtools::install_github("madedotcom/mknapsack")
library(rcbc)
library(ROI)
library(ROI.plugin.cbc)
library(data.table)
library(mknapsack)
options(mknapsack.solver = "cbc")

items <- data.table(
  volume = pmin(rlnorm(100, log(2), log(3)), 15),
  profit = rgamma(100, shape = 1, scale = 100) - 25
)

items[, knapsack := 
  mknapsack(
    profit = profit, 
    volume = volume, 
    cap = 65
  )]

#Aggregate solution to knapsacks
knapsacks <- items[order(knapsack), 
                    .(volume = sum(volume), profit = sum(profit)), 
                    by = knapsack]
knapsacks

#    knapsack volume   profit
# 1:        1 64.89659 5000.27608
# 2:        2 64.40358 1540.40302
# 3:        3 64.97235  340.92516
# 4:        4 53.33824   88.02793
# 5:       NA 91.13399 -272.54349
# 

Metadata

Version

0.1.0

License

Unknown

Platforms (75)

    Darwin
    FreeBSD
    Genode
    GHCJS
    Linux
    MMIXware
    NetBSD
    none
    OpenBSD
    Redox
    Solaris
    WASI
    Windows
Show all
  • aarch64-darwin
  • aarch64-genode
  • aarch64-linux
  • aarch64-netbsd
  • aarch64-none
  • aarch64_be-none
  • arm-none
  • armv5tel-linux
  • armv6l-linux
  • armv6l-netbsd
  • armv6l-none
  • armv7a-darwin
  • armv7a-linux
  • armv7a-netbsd
  • armv7l-linux
  • armv7l-netbsd
  • avr-none
  • i686-cygwin
  • i686-darwin
  • i686-freebsd
  • i686-genode
  • i686-linux
  • i686-netbsd
  • i686-none
  • i686-openbsd
  • i686-windows
  • javascript-ghcjs
  • loongarch64-linux
  • m68k-linux
  • m68k-netbsd
  • m68k-none
  • microblaze-linux
  • microblaze-none
  • microblazeel-linux
  • microblazeel-none
  • mips-linux
  • mips-none
  • mips64-linux
  • mips64-none
  • mips64el-linux
  • mipsel-linux
  • mipsel-netbsd
  • mmix-mmixware
  • msp430-none
  • or1k-none
  • powerpc-netbsd
  • powerpc-none
  • powerpc64-linux
  • powerpc64le-linux
  • powerpcle-none
  • riscv32-linux
  • riscv32-netbsd
  • riscv32-none
  • riscv64-linux
  • riscv64-netbsd
  • riscv64-none
  • rx-none
  • s390-linux
  • s390-none
  • s390x-linux
  • s390x-none
  • vc4-none
  • wasm32-wasi
  • wasm64-wasi
  • x86_64-cygwin
  • x86_64-darwin
  • x86_64-freebsd
  • x86_64-genode
  • x86_64-linux
  • x86_64-netbsd
  • x86_64-none
  • x86_64-openbsd
  • x86_64-redox
  • x86_64-solaris
  • x86_64-windows