Knapsack

Knapsack

A how-to guide for specifying the input and output schemas in 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.

nextmv community clone -a python-ortools-knapsack
Copy
nextmv community clone -a python-pyomo-knapsack
Copy
nextmv community clone -a go-highs-knapsack
Copy

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 nameRequiredData typeSI UnitDescriptionExample
itemsYesarray of itemNAPossible items to select into the knapsack.See item
weight_capacityYesintNAThe weight capacity of the knapsack.{"weight_capacity": 50}

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

{
  "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
}
Copy

Item

An item is used in the input schema.

Field nameRequiredData typeDescriptionExample
idYesstringID for the item.{"id": "cat"}
valueYesintThe value of the item.{"value": "100"}
weightYesintThe 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 nameAlways presentData typeSI UnitDescriptionExample
solutionsYesarray of solutionNASolutions to the knapsack problem.{"solutions": []}
statisticsYesstatisticsNASummary statistics of the solution.{"statistics": {"total_cost": 123}}
{
  "options": {
    "duration": 30,
    "input": "input.json",
    "output": "output.json",
    "provider": "SCIP"
  },
  "solution": {
    "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,
        "status": "optimal",
        "variables": 11
      },
      "duration": 0.123,
      "value": 444
    },
    "run": {
      "duration": 0.123
    },
    "schema": "v1"
  }
}
Copy

Solution

Field nameAlways presentData typeSI UnitDescriptionExample
itemsYesarray of item selected into the knapsackNASolution to the knapsack problem.{"items": []}

Statistics

Field nameAlways presentData typeSI UnitDescriptionExample
resultNoresultNAFinal result of the solutions.See result
runYesrunNAInformation about the run.See run
schemaYesstringNASchema of the statistics.{"schema": "v1"}

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

  • result

    Field nameAlways presentData typeSI UnitDescriptionExample
    durationYesfloatsecondsTime duration to get to the final result.{"duration": 0.123}
    valueYesfloatNAValue of the final result.{"value": 0.123}
    customYesanyNACustom solver metrics.See custom
  • run

    Field nameAlways presentData typeSI UnitDescriptionExample
    durationYesfloatsecondsTime duration of the run.{"duration": 0.123}
  • custom

    Field nameAlways presentData typeSI UnitDescriptionExample
    constraintsYesintNANumber of constraints.{"constraints": 123}
    providerYesstringNASolver provider.{"provider": "highs"}
    statusYesstringNASolver status.{"status": "optimal"}
    variablesYesintNANumber of variables.{"variables": 123}

Run options

usage: main.py [options]

Options for main.py. Use command-line arguments (highest precedence) or
environment variables.

options:
  -h, --help            show this help message and exit
  -input INPUT, --input INPUT
                        [env var: INPUT] (default: ) (type: str): Path to
                        input file. Default is stdin.
  -output OUTPUT, --output OUTPUT
                        [env var: OUTPUT] (default: ) (type: str): Path to
                        output file. Default is stdout.
  -duration DURATION, --duration DURATION
                        [env var: DURATION] (default: 30) (type: int): Max
                        runtime duration (in seconds).
  -provider PROVIDER, --provider PROVIDER
                        [env var: PROVIDER] (default: SCIP) (type: str):
                        Solver provider.
Copy

Page last updated

Go to on-page nav menu