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 knapsack-ortools
Copy
nextmv community clone -a knapsack-pyomo
Copy
nextmv community clone -a knapsack-gosdk
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}}

(UPDATE ME)

{
  "solutions": [
    {
      "planned_shifts": [
        {
          "count": 3,
          "end_time": "2023-11-20T14:00:00+02:00",
          "id": "welder_monday-early",
          "qualification": "welding",
          "shift_id": "welder",
          "start_time": "2023-11-20T06:00:00+02:00",
          "time_id": "monday-early"
        },
        {
          "count": 2,
          "end_time": "2023-11-20T22:00:00+02:00",
          "id": "welder_monday-late",
          "qualification": "welding",
          "shift_id": "welder",
          "start_time": "2023-11-20T14:00:00+02:00",
          "time_id": "monday-late"
        },
        {
          "count": 1,
          "end_time": "2023-11-21T06:00:00+02:00",
          "id": "welder_monday-night",
          "qualification": "welding",
          "shift_id": "welder",
          "start_time": "2023-11-20T22:00:00+02:00",
          "time_id": "monday-night"
        },
        {
          "count": 8,
          "end_time": "2023-11-20T14:00:00+02:00",
          "id": "normal_monday-early",
          "qualification": "",
          "shift_id": "normal",
          "start_time": "2023-11-20T06:00:00+02:00",
          "time_id": "monday-early"
        },
        {
          "count": 8,
          "end_time": "2023-11-20T22:00:00+02:00",
          "id": "normal_monday-late",
          "qualification": "",
          "shift_id": "normal",
          "start_time": "2023-11-20T14:00:00+02:00",
          "time_id": "monday-late"
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "constraints": 7,
        "has_solution": true,
        "over_supply": 154,
        "over_supply_cost": 15400,
        "planned_count": 22,
        "planned_shifts": 5,
        "provider": "SCIP",
        "shift_cost": 1450,
        "status": "optimal",
        "under_supply": 0,
        "under_supply_cost": 0,
        "variables": 13
      },
      "duration": 0.015,
      "value": 16850
    },
    "run": {
      "duration": 0.015
    },
    "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

These are the default options that are available with knapsack for OR-Tools and Pyomo:

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

For Go SDK you have:

Nextmv Hybrid Optimization Platform VERSION
Usage:
  -runner.input.path string
    	The input file path (env RUNNER_INPUT_PATH)
  -runner.output.path string
    	The output file path (env RUNNER_OUTPUT_PATH)
  -runner.output.solutions string
    	{all, last} (env RUNNER_OUTPUT_SOLUTIONS) (default "last")
  -runner.profile.cpu string
    	The CPU profile file path (env RUNNER_PROFILE_CPU)
  -runner.profile.memory string
    	The memory profile file path (env RUNNER_PROFILE_MEMORY)
  -solve.control.bool string
    	List of solver-specific control options (configurations) with bool values. Example: "name1=value1,name2=value2", where value1 and value2 are bool values. (env SOLVE_CONTROL_BOOL)
  -solve.control.float string
    	List of solver-specific control options (configurations) with float values. Example: "name1=value1,name2=value2", where value1 and value2 are float values. (env SOLVE_CONTROL_FLOAT)
  -solve.control.int string
    	List of solver-specific control options (configurations) with int values. Example: "name1=value1,name2=value2", where value1 and value2 are int values. (env SOLVE_CONTROL_INT)
  -solve.control.string string
    	List of solver-specific control options (configurations) with string values. Example: "name1=value1,name2=value2", where value1 and value2 are string values. (env SOLVE_CONTROL_STRING)
  -solve.duration duration
    	Maximum duration of the solver. (env SOLVE_DURATION) (default 30s)
  -solve.mip.gap.absolute float
    	Absolute gap stopping value. If the problem is an integer problem the solver will stop if the gap between the relaxed problem and the best found integer problem is less than this value. (env SOLVE_MIP_GAP_ABSOLUTE) (default 1e-06)
  -solve.mip.gap.relative float
    	Relative gap stopping value. If the problem is an integer problem the solver will stop if the relative gap between the relaxed problem and the best found integer problem is less than this value. (env SOLVE_MIP_GAP_RELATIVE) (default 0.0001)
  -solve.verbosity value
    	{off, low, medium, high} Verbosity of the solver in the console. (env SOLVE_VERBOSITY)
Copy

Those are the Java options:

Usage: java -jar basic_example.jar [OPTIONS]
Solve a simple linear program.

Supported options:
  -i, --input: path to the input file
  -o, --output: path to the output file
  -d, --duration: duration of the search in seconds
  -h, --help: print the help
Copy

Page last updated

Go to on-page nav menu