This how-to guide assumes you already completed the get started with MIP tutorial.
This example uses the Nextmv Go SDK to solve the incentive allocation problem.
The incentive allocation problem states the following:
There exists an estimation of the effect that a discount has on a user's purchase. Maximize the global effect that a set of incentives can have on users, limited to a budget.
This problem can be formulated as follows:
\begin{equation}
\max \sum_{\forall i \in I, j \in U}(e_{ij} \cdot x_{ij})
\end{equation}
Subject to:
\begin{flalign}
\sum_{\forall i \in I, j \in U}(c_{ij} \cdot x_{ij}) &\leq B; &&\\
\sum_{\forall i \in I}x_{ij} &\leq 1, &\forall j \in U; &&\\
x_{ij} &\in \set{0, 1}, &\forall i \in I, j \in U.
\end{flalign}
Where:
\begin{flalign}
-& I \text{ is the set of incentives.} &\\
-& U \text{ is the set of users.} &\\
-& B \text{ is the budget.} &\\
-& e_{ij} \text{ is the effect of incentive } i \in I \text{ on user } j \in U. &\\
-& c_{ij} \text{ is the cost of incentive } i \in I \text{ for user } j \in U. &\\
-& x_{ij} =
\begin{cases}
1 & \text{incentive } i \in I \text{ is applied to user } j \in U; \\
0 & \text{otherwise.}
\end{cases}
\end{flalign}
Get started by initializing the knapsack-gosdk community app:
Change directories into the knapsack-gosdk folder. Rename the directory if desired.
Replace the input.json contained in the app with sample data for the incentive allocation problem.
{
"budget": 220,
"users": [
{
"id": "user-1",
"incentives": [
{
"id": "5%-discount",
"effect": 5,
"cost": 1
},
{
"id": "7%-discount",
"effect": 11,
"cost": 2
},
{
"id": "10%-discount",
"effect": 25,
"cost": 3
}
]
},
{
"id": "user-2",
"incentives": [
{
"id": "5%-discount",
"effect": 3,
"cost": 2
},
{
"id": "11%-discount",
"effect": 5,
"cost": 3
}
]
},
{
"id": "user-3",
"incentives": [
{
"id": "5%-discount",
"effect": 28,
"cost": 3
},
{
"id": "7%-discount",
"effect": 32,
"cost": 4
},
{
"id": "10%-discount",
"effect": 34,
"cost": 5
},
{
"id": "12%-discount",
"effect": 36,
"cost": 8
}
]
},
{
"id": "user-4",
"incentives": [
{
"id": "7%-discount",
"effect": 11,
"cost": 5
},
{
"id": "10%-discount",
"effect": 13,
"cost": 6
}
]
},
{
"id": "user-5",
"incentives": [
{
"id": "5%-discount",
"effect": 14,
"cost": 5
},
{
"id": "7%-discount",
"effect": 17,
"cost": 6
},
{
"id": "10%-discount",
"effect": 25,
"cost": 7
}
]
},
{
"id": "user-6",
"incentives": [
{
"id": "5%-discount",
"effect": 22,
"cost": 6
},
{
"id": "10%-discount",
"effect": 27,
"cost": 8
}
]
},
{
"id": "user-7",
"incentives": [
{
"id": "5%-discount",
"effect": 5,
"cost": 7
},
{
"id": "7%-discount",
"effect": 8,
"cost": 8
},
{
"id": "10%-discount",
"effect": 11,
"cost": 9
}
]
},
{
"id": "user-8",
"incentives": [
{
"id": "5%-discount",
"effect": 15,
"cost": 8
},
{
"id": "7%-discount",
"effect": 18,
"cost": 9
},
{
"id": "10%-discount",
"effect": 20,
"cost": 10
}
]
},
{
"id": "user-9",
"incentives": [
{
"id": "5%-discount",
"effect": 3,
"cost": 9
},
{
"id": "7%-discount",
"effect": 11,
"cost": 10
},
{
"id": "10%-discount",
"effect": 14,
"cost": 11
}
]
},
{
"id": "user-10",
"incentives": [
{
"id": "5%-discount",
"effect": 19,
"cost": 10
},
{
"id": "7%-discount",
"effect": 21,
"cost": 11
},
{
"id": "10%-discount",
"effect": 25,
"cost": 12
}
]
},
{
"id": "user-11",
"incentives": [
{
"id": "5%-discount",
"effect": 33,
"cost": 11
},
{
"id": "7%-discount",
"effect": 34,
"cost": 12
},
{
"id": "10%-discount",
"effect": 37,
"cost": 13
}
]
},
{
"id": "user-12",
"incentives": [
{
"id": "5%-discount",
"effect": 21,
"cost": 12
},
{
"id": "7%-discount",
"effect": 23,
"cost": 13
},
{
"id": "10%-discount",
"effect": 25,
"cost": 14
}
]
},
{
"id": "user-13",
"incentives": [
{
"id": "5%-discount",
"effect": 25,
"cost": 13
},
{
"id": "7%-discount",
"effect": 27,
"cost": 14
},
{
"id": "10%-discount",
"effect": 29,
"cost": 15
}
]
},
{
"id": "user-14",
"incentives": [
{
"id": "5%-discount",
"effect": 7,
"cost": 14
},
{
"id": "7%-discount",
"effect": 11,
"cost": 15
},
{
"id": "10%-discount",
"effect": 20,
"cost": 16
}
]
},
{
"id": "user-15",
"incentives": [
{
"id": "5%-discount",
"effect": 21,
"cost": 15
},
{
"id": "7%-discount",
"effect": 24,
"cost": 16
},
{
"id": "10%-discount",
"effect": 25,
"cost": 17
}
]
},
{
"id": "user-16",
"incentives": [
{
"id": "5%-discount",
"effect": 3,
"cost": 16
},
{
"id": "7%-discount",
"effect": 6,
"cost": 17
},
{
"id": "10%-discount",
"effect": 9,
"cost": 18
}
]
},
{
"id": "user-17",
"incentives": [
{
"id": "5%-discount",
"effect": 11,
"cost": 17
},
{
"id": "7%-discount",
"effect": 9,
"cost": 18
},
{
"id": "10%-discount",
"effect": 13,
"cost": 19
}
]
},
{
"id": "user-18",
"incentives": [
{
"id": "5%-discount",
"effect": 3,
"cost": 18
},
{
"id": "7%-discount",
"effect": 7,
"cost": 19
},
{
"id": "10%-discount",
"effect": 12,
"cost": 20
}
]
},
{
"id": "user-19",
"incentives": [
{
"id": "5%-discount",
"effect": 25,
"cost": 19
},
{
"id": "7%-discount",
"effect": 26,
"cost": 20
},
{
"id": "10%-discount",
"effect": 33,
"cost": 21
}
]
},
{
"id": "user-20",
"incentives": [
{
"id": "5%-discount",
"effect": 21,
"cost": 20
},
{
"id": "7%-discount",
"effect": 23,
"cost": 21
},
{
"id": "10%-discount",
"effect": 32,
"cost": 22
}
]
}
]
}
Copy
Similarly, replace the main.go included in the app with the code to solve incentive allocation.
// © 2019-present nextmv.io inc
// package main holds the implementation of the mip incentive allocation
// template.
package main
import (
"context"
"log"
"math"
"github.com/nextmv-io/go-highs"
"github.com/nextmv-io/go-mip"
"github.com/nextmv-io/sdk/run"
"github.com/nextmv-io/sdk/run/schema"
)
// This template demonstrates how to solve a Mixed Integer Programming problem.
// To solve a mixed integer problem is to optimize a linear objective function
// of many variables, subject to linear constraints. We demonstrate this by
// solving a incentive allocation problem.
func main() {
err := run.CLI(solver).Run(context.Background())
if err != nil {
log.Fatal(err)
}
}
// The options for the solver.
type options struct {
Solve mip.SolveOptions `json:"solve,omitempty"`
}
// Input of the problem.
type input struct {
// Users for the problem including name and a cost/effect pair per
// available incentive.
Users []struct {
ID string `json:"id"`
// Incentives that can be applied to the user.
Incentives []struct {
ID string `json:"id"`
// Positive effect of the incentive.
Effect float64 `json:"effect"`
// Cost of the incentive that will be subtracted from the budget.
Cost float64 `json:"cost"`
} `json:"incentives"`
} `json:"users"`
Budget int `json:"budget"`
}
// assignments is used to print the solutio∑n and represents the
// combination of a user with the assigned incentive.
type assignments struct {
User string `json:"user"`
IncentiveID string `json:"incentive_id"`
Cost float64 `json:"cost"`
Effect float64 `json:"effect"`
}
// solution represents the decisions made by the solver.
type solution struct {
Assignments []assignments `json:"assignments,omitempty"`
}
// solver is the entrypoint of the program where a model is defined and solved.
func solver(_ context.Context, input input, options options) (schema.Output, error) {
// Translate the input to a MIP model.
model, variables := model(input)
// Create a solver using a provider. Please see the documentation on
// [mip.SolverProvider] for more information on the available providers.
solver := highs.NewSolver(model)
// Solve the model and get the solution.
solution, err := solver.Solve(options.Solve)
if err != nil {
return schema.Output{}, err
}
// Format the solution into the desired output format and add custom
// statistics.
output := mip.Format(options, format(input, solution, variables), solution)
output.Statistics.Result.Custom = mip.DefaultCustomResultStatistics(model, solution)
return output, nil
}
// model creates a MIP model from the input. It also returns the decision
// variables.
func model(input input) (mip.Model, map[string][]mip.Var) {
// We start by creating a MIP model.
model := mip.NewModel()
// We want to maximize the value of the problem.
model.Objective().SetMaximize()
// This constraint ensures the budget of the will not be exceeded.
budgetConstraint := model.NewConstraint(
mip.LessThanOrEqual,
float64(input.Budget),
)
// Create a map of user ID to a slice of decision variables, one for each
// incentive.
userIncentiveVariables := make(map[string][]mip.Var, len(input.Users))
for _, user := range input.Users {
// For each user, create the slice of variables based on the number of
// incentives.
userIncentiveVariables[user.ID] = make([]mip.Var, len(user.Incentives))
// This constraint ensures that each user is assigned at most one
// incentive.
oneIncentiveConstraint := model.NewConstraint(mip.LessThanOrEqual, 1.0)
for i, incentive := range user.Incentives {
// For each incentive, create a binary decision variable.
userIncentiveVariables[user.ID][i] = model.NewBool()
// Set the term of the variable on the objective, based on the
// effect the incentive has on the user.
model.Objective().NewTerm(
incentive.Effect,
userIncentiveVariables[user.ID][i],
)
// Set the term of the variable on the budget constraint, based on
// the cost of the incentive for the user.
budgetConstraint.NewTerm(
incentive.Cost,
userIncentiveVariables[user.ID][i],
)
// Set the term of the variable on the constraint that controls the
// number of incentives per user.
oneIncentiveConstraint.NewTerm(1, userIncentiveVariables[user.ID][i])
}
}
return model, userIncentiveVariables
}
// format the solution from the solver into the desired output format.
func format(
input input,
solverSolution mip.Solution,
userIncentiveVariables map[string][]mip.Var,
) solution {
if !solverSolution.IsOptimal() && !solverSolution.IsSubOptimal() {
return solution{}
}
assigned := []assignments{}
for i, user := range input.Users {
for j := range user.Incentives {
// If the variable is not assigned, skip it.
if int(math.Round(
solverSolution.Value(userIncentiveVariables[user.ID][j])),
) < 1 {
continue
}
assigned = append(
assigned,
assignments{
Cost: input.Users[i].Incentives[j].Cost,
Effect: input.Users[i].Incentives[j].Effect,
User: user.ID,
IncentiveID: input.Users[i].Incentives[j].ID,
},
)
}
}
return solution{
Assignments: assigned,
}
}
Copy
The code showcases several aspects when working with MIPs:
- How to define variables based on the input data.
- How to programmatically add terms to constraints and the objective by looping over input data.
- How to interact with solve options.
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.
Run the code, specifying the file to be used as input, and the file to be used as output, along with other options.
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": [
{
"assignments": [
{
"cost": 3,
"effect": 25,
"incentive_id": "10%-discount",
"user": "user-1"
},
{
"cost": 3,
"effect": 5,
"incentive_id": "11%-discount",
"user": "user-2"
},
{
"cost": 8,
"effect": 36,
"incentive_id": "12%-discount",
"user": "user-3"
},
{
"cost": 6,
"effect": 13,
"incentive_id": "10%-discount",
"user": "user-4"
},
{
"cost": 7,
"effect": 25,
"incentive_id": "10%-discount",
"user": "user-5"
},
{
"cost": 8,
"effect": 27,
"incentive_id": "10%-discount",
"user": "user-6"
},
{
"cost": 9,
"effect": 11,
"incentive_id": "10%-discount",
"user": "user-7"
},
{
"cost": 10,
"effect": 20,
"incentive_id": "10%-discount",
"user": "user-8"
},
{
"cost": 11,
"effect": 14,
"incentive_id": "10%-discount",
"user": "user-9"
},
{
"cost": 12,
"effect": 25,
"incentive_id": "10%-discount",
"user": "user-10"
},
{
"cost": 13,
"effect": 37,
"incentive_id": "10%-discount",
"user": "user-11"
},
{
"cost": 14,
"effect": 25,
"incentive_id": "10%-discount",
"user": "user-12"
},
{
"cost": 15,
"effect": 29,
"incentive_id": "10%-discount",
"user": "user-13"
},
{
"cost": 16,
"effect": 20,
"incentive_id": "10%-discount",
"user": "user-14"
},
{
"cost": 17,
"effect": 25,
"incentive_id": "10%-discount",
"user": "user-15"
},
{
"cost": 19,
"effect": 13,
"incentive_id": "10%-discount",
"user": "user-17"
},
{
"cost": 21,
"effect": 33,
"incentive_id": "10%-discount",
"user": "user-19"
},
{
"cost": 22,
"effect": 32,
"incentive_id": "10%-discount",
"user": "user-20"
}
]
}
],
"statistics": {
"result": {
"custom": {
"constraints": 21,
"provider": "HiGHS",
"status": "optimal",
"variables": 58
},
"duration": 0.123,
"value": 415
},
"run": {
"duration": 0.123
},
"schema": "v1"
},
"version": {
"go-mip": "VERSION",
"sdk": "VERSION"
}
}
Copy