Examples

Incentive allocation

A how-to guide for solving incentive allocation problems.

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:

maximize    ∑(e_ij · x_ij) for all i in I, j in U
subject to  ∑(c_ij · x_ij) for all i in I, j in U <= B;
                           ∑(x_ij) for all i in I <= 1, for all j in U;
                                             x_ij in {0, 1}, for all i in I, j in U.
Copy

Where:

  • I is the set of incentives.
  • U is the set of users.
  • e_ij is the expected effect of incentive i in I on user j in U.
  • c_ij is the cost of incentive i in I for user j in U.
  • B is the budget.
  • x_ij is a binary variable that takes value 1 if incentive i in I is applied to user j in U, 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

Replace the input.json contained in the template 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 template with the code to solve incentive allocation.

// package main holds the implementation of the mip incentive allocation
// template.
package main

import (
	"context"
	"log"
	"math"

	"github.com/nextmv-io/sdk/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, err := mip.NewSolver(mip.Highs, model)
	if err != nil {
		return schema.Output{}, err
	}

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

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": [
    {
      "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.035140208,
      "value": 415
    },
    "run": {
      "duration": 0.035140208
    },
    "schema": "v1"
  },
  "version": {
    "sdk": "VERSION"
  }
}
Copy

Page last updated