Knapsack

The knapsack app is available in three modeling languages as a Mixed Integer Problem (MIP). You can also choose to make customizations to the model by instantiating the app first.

OR-Tools
- Default solver: SCIP
- Marketplace subscription app IDs
  - Python: nextmv-knapsack.ortools
  - Java: nextmv-knapsack.jortools

Bash (Python app)
Bash (Java app)

nextmv community clone -a knapsack-ortools

Pyomo
- Default solver: CBC
- Marketplace subscription app IDs
  - Python: nextmv-knapsack.pyomo

Bash

nextmv community clone -a knapsack-pyomo

Nextmv SDK
- Default solver: HiGHS
- Marketplace subscription app IDs
  - Go: nextmv-knapsack.gosdk

Bash

nextmv community clone -a knapsack-gosdk

Once you have the code locally, you can customize the model, run it locally and deploy it to Nextmv Platform.

Input

The input schema is a JSON payload defining the available items and the weight capacity of the knapsack for the knapsack problem. Nextmv's tools are designed to operate directly on business data (in JSON) to produce decisions that are actionable by software systems. This makes decisions more interpretable and easier to test. It also makes integration with data warehouses and business intelligence platforms significantly easier. An input contains the following components:

Field name	Required	Data type	SI Unit	Description	Example
`items`	Yes	`array` of `item`	NA	Possible items to select into the knapsack.	See `item`
`weight_capacity`	Yes	`int`	NA	The weight capacity of the knapsack.	`{"weight_capacity": 50}`

Here you can find a sample .json with the input schema:

JSON

{
  "items": [
    {
      "id": "cat",
      "value": 100,
      "weight": 20
    },
    {
      "id": "dog",
      "value": 20,
      "weight": 45
    },
    {
      "id": "water",
      "value": 40,
      "weight": 2
    },
    {
      "id": "phone",
      "value": 6,
      "weight": 1
    },
    {
      "id": "book",
      "value": 63,
      "weight": 10
    },
    {
      "id": "rx",
      "value": 81,
      "weight": 1
    },
    {
      "id": "tablet",
      "value": 28,
      "weight": 8
    },
    {
      "id": "coat",
      "value": 44,
      "weight": 9
    },
    {
      "id": "laptop",
      "value": 51,
      "weight": 13
    },
    {
      "id": "keys",
      "value": 92,
      "weight": 1
    },
    {
      "id": "nuts",
      "value": 18,
      "weight": 4
    }
  ],
  "weight_capacity": 50
}

Item

An item is used in the input schema.

Field name	Required	Data type	Description	Example
`id`	Yes	`string`	ID for the item.	`{"id": "cat"}`
`value`	Yes	`int`	The value of the item.	`{"value": "100"}`
`weight`	Yes	`int`	The weight of the item.	`{"weight": 20}`

Output

The output schema defines the solution to the knapsack problem in JSON format. The output schema contains the following components.

Field name	Always present	Data type	SI Unit	Description	Example
`solutions`	Yes	`array` of `solution`	NA	Solutions to the knapsack problem.	`{"solutions": []}`
`statistics`	Yes	`statistics`	NA	Summary statistics of the solution.	`{"statistics": {"total_cost": 123}}`

JSON

{
  "solutions": [
    {
      "items": [
        {
          "id": "cat",
          "value": 100,
          "weight": 20
        },
        {
          "id": "water",
          "value": 40,
          "weight": 2
        },
        {
          "id": "phone",
          "value": 6,
          "weight": 1
        },
        {
          "id": "book",
          "value": 63,
          "weight": 10
        },
        {
          "id": "rx",
          "value": 81,
          "weight": 1
        },
        {
          "id": "coat",
          "value": 44,
          "weight": 9
        },
        {
          "id": "keys",
          "value": 92,
          "weight": 1
        },
        {
          "id": "nuts",
          "value": 18,
          "weight": 4
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "constraints": 1,
        "provider": "SCIP",
        "status": "optimal",
        "variables": 11
      },
      "duration": 0.123,
      "value": 444
    },
    "run": {
      "duration": 0.123
    },
    "schema": "v1"
  }
}

Solution

Field name	Always present	Data type	SI Unit	Description	Example
`items`	Yes	`array` of `item` selected into the knapsack	NA	Solution to the knapsack problem.	`{"items": []}`

Statistics

Field name	Always present	Data type	SI Unit	Description	Example
`result`	No	`result`	NA	Final result of the solutions.	See `result`
`run`	Yes	`run`	NA	Information about the run.	See `run`
`schema`	Yes	`string`	NA	Schema of the statistics.	`{"schema": "v1"}`

Here you can find additional definitions used in the statistics schema:

result

Field name	Always present	Data type	SI Unit	Description	Example
`duration`	Yes	`float`	`seconds`	Time duration to get to the final result.	`{"duration": 0.123}`
`value`	Yes	`float`	NA	Value of the final result.	`{"value": 0.123}`
`custom`	Yes	`any`	NA	Custom solver metrics.	See `custom`

run
Field name Always present Data type SI Unit Description Example
duration Yes float seconds Time duration of the run. {"duration": 0.123}

Field name	Always present	Data type	SI Unit	Description	Example
`duration`	Yes	`float`	`seconds`	Time duration of the run.	`{"duration": 0.123}`

custom

Field name	Always present	Data type	SI Unit	Description	Example
`constraints`	Yes	`int`	NA	Number of constraints.	`{"constraints": 123}`
`provider`	Yes	`string`	NA	Solver provider.	`{"provider": "highs"}`
`status`	Yes	`string`	NA	Solver status.	`{"status": "optimal"}`
`variables`	Yes	`int`	NA	Number of variables.	`{"variables": 123}`

Run options

usage: main.py [-h] [-input INPUT] [-output OUTPUT] [-duration DURATION]

Solve problems with OR-Tools.

options:
  -h, --help          show this help message and exit
  -input INPUT        Path to input file. Default is stdin.
  -output OUTPUT      Path to output file. Default is stdout.
  -duration DURATION  Max runtime duration (in seconds). Default is 30.

A how-to guide for specifying the input and output schemas in knapsack.

Input

Item

Output

Solution

Statistics

Run options

Cost flow

Routing without constraints

Contents