vrp_multiple_knapsack - Experimental

Warning

Possible server crash

  • These functions might create a server crash

Warning

Experimental functions

  • They are not officially of the current release.

  • They likely will not be officially be part of the next release:

    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL

    • Name might change.

    • Signature might change.

    • Functionality might change.

    • pgTap tests might be missing.

    • Might need c/c++ coding.

    • May lack documentation.

    • Documentation if any might need to be rewritten.

    • Documentation examples might need to be automatically generated.

    • Might need a lot of feedback from the comunity.

    • Might depend on a proposed function of vrpRouting

    • Might depend on a deprecated function of vrpRouting

Availability

Version 0.4.0

Description

The multiple knapsack problem is a problem in combinatorial optimization: it is a more general verison of the classic knapsack problem where instead of a single knapsack, you will be given multiple knapsacks and your goal is maximise the total value of packed items in all knapsacks.

Signatures

vrp_multiple_knapsack(
  Weights_Costs SQL, capacities ARRAY[ANY-INTEGER], [, max_rows])

RETURNS SET OF
(knapsack_number, item_id)

Parameters

Parameter

Type

Description

Weights_Costs SQL

TEXT

Weights_Costs SQL query describing the weight of each item

Capacities

ARRAY[ANY-INTEGER]

An array describing the capacity of each knapsack

Optional Parameters

Parameter

Type

Default

Description

max_rows

ANY-INTEGER

\(100000\)

Maximum items(rows) to fetch from bin_packing_data table

Inner Queries

Weights_Costs SQL

A SELECT statement that returns the following columns:

id, weight, cost

Column

Type

Default

Description

id

ANY-INTEGER

unique identifier of the item.

weight

ANY-INTEGER

weight of the item.

cost

ANY-INTEGER

cost of the item.

Result Columns

Returns set of

(knapsack_number, item_id)

Column

Type

Description

knapsack_number

ANY-INTEGER

Integer to uniquely identify a knapsack

item_id

ANY-INTEGER

Integer to uniquely identify an item in the bin

Example

SELECT * 
FROM multiple_knapsack_query;
 id | weight | cost 
----+--------+------
  1 |     48 |   10
  2 |     30 |   30
  3 |     42 |   25
  4 |     36 |   50
  5 |     36 |   35
  6 |     48 |   30
  7 |     42 |   15
  8 |     42 |   40
  9 |     36 |   30
 10 |     24 |   35
 11 |     30 |   45
 12 |     30 |   10
 13 |     42 |   20
 14 |     36 |   30
 15 |     36 |   25
(15 rows)

SELECT * 
FROM vrp_multiple_knapsack('SELECT id, weight, cost FROM multiple_knapsack_query', ARRAY[100,100,100,100,100]);
 knapsack_number | item_id 
-----------------+---------
               1 |       2
               1 |       4
               1 |      11
               2 |       3
               2 |      15
               3 |       5
               3 |      10
               3 |      14
               4 |       9
               4 |      13
               5 |       6
               5 |       8
(12 rows)