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.1

  • Support for or-tools v9.10.4067

Version 0.4.0

  • New experimental function

    • vrp_knapsack

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(Weight Costs SQL, capacities, [,``max_rows``])
RETURNS SET OF (knapsack, id)
OR EMPTY SET
vrp_multiple_knapsack(
  Weights_Costs SQL, capacities ARRAY[ANY-INTEGER], [, max_rows])

RETURNS SET OF
(knapsack_number, item_id)

Parameters

Column

Type

Description

Weight Costs SQL

TEXT

Weight Costs SQL as described below

capacities

ARRAY[ ANY-INTEGER ]

An array describing the capacity of each knapsack.

Optional Parameters

Column

Type

Default

Description

max_rows

ANY-INTEGER

\(100000\)

Maximum items(rows) to fetch from bin_packing_data table.

Inner Queries

Weight Costs SQL

Column

Type

Description

id

ANY-INTEGER

Unique identifier of the item.

weight

ANY-INTEGER

Weight of the item.

cost

ANY-INTEGER

Cost of the item.

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

Result Columns

Column

Type

Description

knapsak

INTEGER

Indentifier of the knapsack.

id

INTEGER

Indentifier of an item in the knapsack.

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 vrp_multiple_knapsack($$SELECT id, weight, cost FROM ortools.multiple_knapsack$$, ARRAY[100,100,100,100,100]);
 knapsack | id
----------+----
        1 |  2
        1 |  9
        1 | 11
        2 |  4
        2 |  5
        2 | 10
        3 |  8
        3 | 13
        4 |  3
        4 |  6
        5 | 14
        5 | 15
(12 rows)

See Also

Indices and tables