Objectives¶

First, the objectives can be classified in two categories:

input minimization: pack/cut all items using as few space as possible
output maximization: pack/cut as many items as possible inside all the provided containers

There is a single output maximization objective called knapsack.

There is also a feasibility objective that simply checks whether a valid packing exists.

For input minimization, there are 3 objective types:

Open-dimension: there is a single bin and the objective is to minimize the space used in this bin
Bin packing: there are multiple bins, the objective is to use as few bins as possible; bins must be used in the order they are provided
Variable-sized bin packing: there are multiple bins, the objective is to use as few bins as possible; there is no constraint in the order bins are used

The objective of an instance is set as follows (here, bin packing; the examples below use the rectangle problem type):

Online solver

Choose the Objective of the project.

JSON

In the instance: "objective": "bin-packing".

Python

instance_builder.set_objective(psr.Objective.BinPacking)

C++

instance_builder.set_objective(Objective::BinPacking);

Bin packing¶

In bin packing problems, the objective is to pack/cut all items in as few bins as possible. Bins must be used in the order they are provided.

PackingSolver supports two variants of this type of objective:

bin-packing: minimize the number of bins
bin-packing-with-leftovers: minimize the number of bins; and then maximize the value of the leftover of the last bin of the solution

Example

In this example, there are two bin types. The first bin type has 10 copies. To use bins of the second bin type, the solution should already contain the first 10 copies of the first bin type. The solver only needs to use 2 copies of the first bin type to pack all items. Therefore, only the first bin type is used. Since the objective is bin packing with leftovers, the solver optimizes the leftover of the last bin of the solution.

_images/objective_bin_packing_with_leftovers_solution.png

Online solver

Open the example in the online solver: Objectives: bin packing with leftovers.

JSON

Objectives: bin packing with leftovers¶

{
    "objective": "bin-packing-with-leftovers",
    "bin_types": [
        {"x": 1000, "y": 500, "copies": 10},
        {"x": 700, "y": 400, "copies": 10}
    ],
    "item_types": [
        {"x": 250, "y": 150, "copies": 10},
        {"x": 200, "y": 100, "copies": 12},
        {"x": 175, "y": 75, "copies": 12}
    ]
}

Python

Objectives: bin packing with leftovers¶

import packingsolver.rectangle as psr

instance_builder = psr.InstanceBuilder()
instance_builder.set_objective(psr.Objective.BinPackingWithLeftovers)
instance_builder.add_bin_type(1000, 500, copies=10)
instance_builder.add_bin_type(700, 400, copies=10)
instance_builder.add_item_type(250, 150, copies=10)
instance_builder.add_item_type(200, 100, copies=12)
instance_builder.add_item_type(175, 75, copies=12)
instance = instance_builder.build()

C++

Objectives: bin packing with leftovers¶

#include "packingsolver/rectangle/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::rectangle;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(1000, 500);
instance_builder.set_bin_type_copies(bin_type_id, 10);
bin_type_id = instance_builder.add_bin_type(700, 400);
instance_builder.set_bin_type_copies(bin_type_id, 10);
ItemTypeId item_type_id = instance_builder.add_item_type(250, 150);
instance_builder.set_item_type_copies(item_type_id, 10);
item_type_id = instance_builder.add_item_type(200, 100);
instance_builder.set_item_type_copies(item_type_id, 12);
item_type_id = instance_builder.add_item_type(175, 75);
instance_builder.set_item_type_copies(item_type_id, 12);
Instance instance = instance_builder.build();

Variable-sized bin packing¶

In variable-sized bin packing problems, the objective is to pack/cut all items in the cheapest bins as possible. There is no constraint in the order bins are used.

Each bin has an associated cost. If no cost is provided, then the cost of a bin is its space (length, area, volume).

Example

The input is the same as the previous one. With the variable-sized bin packing objective, the solver can use the second bin type to minimize the overall waste.

_images/objective_variable_sized_bin_packing_solution.png

Online solver

Open the example in the online solver: Objectives: variable-sized bin packing.

JSON

Objectives: variable-sized bin packing¶

{
    "objective": "variable-sized-bin-packing",
    "bin_types": [
        {"x": 1000, "y": 500, "copies": 10},
        {"x": 700, "y": 400, "copies": 10}
    ],
    "item_types": [
        {"x": 250, "y": 150, "copies": 10},
        {"x": 200, "y": 100, "copies": 12},
        {"x": 175, "y": 75, "copies": 12}
    ]
}

Python

Objectives: variable-sized bin packing¶

import packingsolver.rectangle as psr

instance_builder = psr.InstanceBuilder()
instance_builder.set_objective(psr.Objective.VariableSizedBinPacking)
instance_builder.add_bin_type(1000, 500, copies=10)
instance_builder.add_bin_type(700, 400, copies=10)
instance_builder.add_item_type(250, 150, copies=10)
instance_builder.add_item_type(200, 100, copies=12)
instance_builder.add_item_type(175, 75, copies=12)
instance = instance_builder.build()

C++

Objectives: variable-sized bin packing¶

#include "packingsolver/rectangle/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::rectangle;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::VariableSizedBinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(1000, 500);
instance_builder.set_bin_type_copies(bin_type_id, 10);
bin_type_id = instance_builder.add_bin_type(700, 400);
instance_builder.set_bin_type_copies(bin_type_id, 10);
ItemTypeId item_type_id = instance_builder.add_item_type(250, 150);
instance_builder.set_item_type_copies(item_type_id, 10);
item_type_id = instance_builder.add_item_type(200, 100);
instance_builder.set_item_type_copies(item_type_id, 12);
item_type_id = instance_builder.add_item_type(175, 75);
instance_builder.set_item_type_copies(item_type_id, 12);
Instance instance = instance_builder.build();

Open-dimension¶

In open-dimension problems, the objective is to pack/cut all items in a single bin using as few space as possible on the bin. As few space as possible may for example mean:

minimize the width used
minimize the height used
minimize the rectangular area used
minimize the circular area used

PackingSolver currently supports the objectives:

open-dimension-x: minimize the width used
open-dimension-y: minimize the height used
open-dimension-z: minimize the height used, for the box problem type
open-dimension-xy: minimize the area used, with a given aspect ratio, for the irregular problem type

The open-dimension objectives are available for all the problem types except one-dimensional.

Example

_images/objective_open_dimension_x_solution.png

Online solver

Open the example in the online solver: Objectives: open dimension X.

JSON

Objectives: open dimension X¶

{
    "objective": "open-dimension-x",
    "bin_types": [
        {"x": 2000, "y": 500}
    ],
    "item_types": [
        {"x": 250, "y": 150, "copies": 10},
        {"x": 200, "y": 100, "copies": 12},
        {"x": 175, "y": 75, "copies": 12}
    ]
}

Python

Objectives: open dimension X¶

import packingsolver.rectangle as psr

instance_builder = psr.InstanceBuilder()
instance_builder.set_objective(psr.Objective.OpenDimensionX)
instance_builder.add_bin_type(2000, 500)
instance_builder.add_item_type(250, 150, copies=10)
instance_builder.add_item_type(200, 100, copies=12)
instance_builder.add_item_type(175, 75, copies=12)
instance = instance_builder.build()

C++

Objectives: open dimension X¶

#include "packingsolver/rectangle/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::rectangle;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::OpenDimensionX);
instance_builder.add_bin_type(2000, 500);
ItemTypeId item_type_id = instance_builder.add_item_type(250, 150);
instance_builder.set_item_type_copies(item_type_id, 10);
item_type_id = instance_builder.add_item_type(200, 100);
instance_builder.set_item_type_copies(item_type_id, 12);
item_type_id = instance_builder.add_item_type(175, 75);
instance_builder.set_item_type_copies(item_type_id, 12);
Instance instance = instance_builder.build();

Knapsack¶

In knapsack problems, the objective is to maximize the value of the items packed/cut inside all the provided containers.

Each item has an associated profit. If no profit is provided, then the profit of an item is its space (length, area, volume).

Example

The items are the same as in the previous examples. Only 2 copies of the small bin type are available. This is not enough to pack all the items.

Online solver

Open the example in the online solver: Objectives: knapsack.

JSON

Objectives: knapsack¶

{
    "objective": "knapsack",
    "bin_types": [
        {"x": 700, "y": 400, "copies": 2}
    ],
    "item_types": [
        {"x": 250, "y": 150, "copies": 10},
        {"x": 200, "y": 100, "copies": 12},
        {"x": 175, "y": 75, "copies": 12}
    ]
}

Python

Objectives: knapsack¶

import packingsolver.rectangle as psr

instance_builder = psr.InstanceBuilder()
instance_builder.set_objective(psr.Objective.Knapsack)
instance_builder.add_bin_type(700, 400, copies=2)
instance_builder.add_item_type(250, 150, copies=10)
instance_builder.add_item_type(200, 100, copies=12)
instance_builder.add_item_type(175, 75, copies=12)
instance = instance_builder.build()

C++

Objectives: knapsack¶

#include "packingsolver/rectangle/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::rectangle;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::Knapsack);
BinTypeId bin_type_id = instance_builder.add_bin_type(700, 400);
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type(250, 150);
instance_builder.set_item_type_copies(item_type_id, 10);
item_type_id = instance_builder.add_item_type(200, 100);
instance_builder.set_item_type_copies(item_type_id, 12);
item_type_id = instance_builder.add_item_type(175, 75);
instance_builder.set_item_type_copies(item_type_id, 12);
Instance instance = instance_builder.build();

Feasibility¶

In feasibility problems, the objective is simply to determine whether a valid packing exists — no optimization is performed.

The solver returns a solution as soon as it finds one valid placement of all items, or reports that no feasible packing was found.