Get Started

Get started with Mixed Integer Programming (MIP)

A tutorial for getting started with Mixed Integer Programming (MIP).

I want an interesting synonym
To describe this thing
That you say we're all grandfathered in
I'll use the search engine (we've got much to discuss)
Too much to discuss
Over a bucket of balls
I can recall the glow of your low beams
It's the big night in Tinsel City
Life became a spectator sport
I launch my fragrance called "Integrity"
I sell the fact that I can't be bought
Have I told you all about the time
That I got sucked into a hole through a hand held device?
I will flashback now and again but I'm usually alright
Thankfully the process has been simplified
Since the last time you tried

-- Alex Turner

Nextmv offers a comprehensive set of tools for solving Mixed Integer Programs (MIP). To get started with MIP you have two alternatives:

  1. Marketplace app: work with a ready-to-use solution.
  2. Platform: get access to a fully customizable solution.

After familiarizing yourself with the two alternatives, please continue with these next steps:

  • Explore examples for more complex problems.

Marketplace app

Subscribe to our newsletter to be the first to hear when MIP becomes a marketplace app! 💡

Platform

Please make sure you already completed the steps described in the 5-minute getting started experience.

To test that the Nextmv CLI is correctly configured, please run the following command on your terminal. It will get some files that are necessary to work with the Nextmv Platform. You can see the expected output as well.

nextmv sdk install
Copy

To get started with MIP, consider the knapsack problem, which is a classical example of a MIP:

Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

This problem can be formulated as follows:

maximize    ∑(v_i · x_i) for all i in I
subject to  ∑(w_i · x_i) for all i in I <= W;
                                    x_i in {0, 1}, for all i in I.
Copy

Where:

  • I is the set of items.
  • v_i is the value of item i in I.
  • w_i is the weight of item i in I.
  • W is the capacity of the knapsack.
  • x_i is a binary variable that takes value 1 if item i in I is selected, and 0 otherwise.

Get started by initializing the mip template:

nextmv sdk init -t mip
Copy

Change directories into the mip folder.

cd mip
Copy

You should see the input.json and main.go files, similar to these ones:

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

Run the code, specifying the file to be used as input, and the file to be used as output, along with other options.

nextmv sdk run . -- -runner.input.path input.json -runner.output.path output.json -solve.duration 10s
Copy

After running, an output.json file should have been created with the solution, similar to this one:

{
  "options": {
    "solve": {
      "control": {
        "bool": [],
        "float": [],
        "int": [],
        "string": []
      },
      "duration": 10000000000,
      "mip": {
        "gap": {
          "absolute": 0.000001,
          "relative": 0.0001
        }
      },
      "verbosity": "off"
    }
  },
  "solutions": [
    {
      "items": [
        {
          "item_id": "cat",
          "value": 100,
          "weight": 20
        },
        {
          "item_id": "water",
          "value": 40,
          "weight": 2
        },
        {
          "item_id": "phone",
          "value": 6,
          "weight": 1
        },
        {
          "item_id": "book",
          "value": 63,
          "weight": 10
        },
        {
          "item_id": "rx",
          "value": 81,
          "weight": 1
        },
        {
          "item_id": "coat",
          "value": 44,
          "weight": 9
        },
        {
          "item_id": "keys",
          "value": 92,
          "weight": 1
        },
        {
          "item_id": "nuts",
          "value": 18,
          "weight": 4
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "constraints": 1,
        "provider": "highs",
        "status": "optimal",
        "variables": 11
      },
      "duration": 0.000501042,
      "value": 444
    },
    "run": {
      "duration": 0.000501042
    },
    "schema": "v1"
  },
  "version": {
    "sdk": "VERSION"
  }
}
Copy

In general, the steps to solve a MIP are:

  • Create a Model.
  • Add Variables to the model, by calling methods on the Model directly.
  • Set the Objective of the model, and the sense (max or min), by calling methods on the Model directly.
  • Add Constraints to the model, by calling methods on the Model directly. For each Constraint, you define the sense, the right hand side and add terms to it.
  • Solve the MIP defined in the Model by using a Solver.

These are the supported solvers for Mixed Integer Programming (MIP):

ProviderDescriptionUse with
HiGHSOpen-source solver.Nextmv platform & SDK
FICO XpressCommercial solver.Nextmv platform & SDK
OR-ToolsOpen-source solver.Nextmv platform & Python

Please note that HiGHS is used as the default solver provider. To use a different one, please visit the supported solvers page to learn more about working with different providers.

🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉

You are all set to keep exploring!

Here are the next steps to continue your journey:

Page last updated

Contents

Go to on-page nav menu