∇ProvenDecisions
Ctrl K

Capacitated facility location: an integer programming example, solved and checked

The capacitated facility location is a classic integer programming problem. Here it is solved by a real solver (HIGHS) and checked: every constraint, the dual, and the optimality certificate. Change the numbers below and solve your own.

Answer. The smallest objective value is 160, at x11 = 15, x12 = 5, x13 = 0, y1 = 1, x21 = 0, x22 = 15, x23 = 10, y2 = 1. All 11 constraints are satisfied exactly. Optimal within gap tolerance.

Solve your own version free, no account needed

The problem

Two depots cost $20 and $25 to open and can ship 30 and 25 units. Three stores need 15, 20 and 10 units. Shipping one unit costs $2, $4 and $5 from depot 1 to stores 1, 2 and 3, and $5, $3 and $2 from depot 2. Minimize opening plus shipping cost.

How the model was built

The objective as written from the problem, before the numbers are multiplied out:

The model

Each line has a plain-language note on the right.

make as small as possible: total depot opening cost plus shipping cost ($)
limit 1: left side cannot exceed the right side
limit 2: left side cannot exceed the right side
limit 3: left side must equal 15
limit 4: left side must equal 20
limit 5: left side must equal 10
units shipped from depot 1 to store 1 (units) cannot be negative
units shipped from depot 1 to store 2 (units) cannot be negative
units shipped from depot 1 to store 3 (units) cannot be negative
units shipped from depot 2 to store 1 (units) cannot be negative
units shipped from depot 2 to store 2 (units) cannot be negative
units shipped from depot 2 to store 3 (units) cannot be negative
yes (1) or no (0)

In matrix form

With its numbers:

What is being decided

There are 8 decision variables.

VariableTypeMeaning
x11real numberunits shipped from depot 1 to store 1 (units)
x12real numberunits shipped from depot 1 to store 2 (units)
x13real numberunits shipped from depot 1 to store 3 (units)
y1binary (0 or 1)1 if depot 1 is opened, else 0 (yes/no)
x21real numberunits shipped from depot 2 to store 1 (units)
x22real numberunits shipped from depot 2 to store 2 (units)
x23real numberunits shipped from depot 2 to store 3 (units)
y2binary (0 or 1)1 if depot 2 is opened, else 0 (yes/no)

Goal and limits

Minimize total depot opening cost plus shipping cost ($) subject to 11 constraints, of which 6 are simple bounds on a single variable.

Problem type

MILP, complexity level 5: integer variables with linear objective and constraints. Solved with HIGHS at the Medium solver tier.

The answer at a glance

The optimal value of each decision, as the solver returned it.

x1115x125x130y11x210x2215x2310y21

Which constraints hold the answer in place

Binding (no slack left): (2) x21 + x22 + x23 <= 25*y2; (3) x11 + x21 = 15; (4) x12 + x22 = 20; (5) x13 + x23 = 10; (8) x13 >= 0; (9) x21 >= 0. Changing a binding constraint changes the answer; a slack one can move a little without effect.

#ConstraintValueLimitSlackBinding
1x11 + x12 + x13 <= 30*y1203010
2x21 + x22 + x23 <= 25*y225250yes
3x11 + x21 = 1515150yes
4x12 + x22 = 2020200yes
5x13 + x23 = 1010100yes
6x11 >= 015015
7x12 >= 0505
8x13 >= 0000yes
9x21 >= 0000yes
10x22 >= 015015
11x23 >= 010010

Algebraic model (low level)

Decision variables, objective and every constraint written out; this is exactly what the solver receives.

Standard form

As a linear program: minimize cᵀx subject to A x ≤ b (the inequality rows) and A_eq x = b_eq (the equations); a maximization is written as minimizing the negative.

Model code (cvxpy)

The same model in cvxpy, ready to run.

import cvxpy as cp

x11 = cp.Variable(name='x11')  # units shipped from depot 1 to store 1 (units)
x12 = cp.Variable(name='x12')  # units shipped from depot 1 to store 2 (units)
x13 = cp.Variable(name='x13')  # units shipped from depot 1 to store 3 (units)
y1 = cp.Variable(name='y1', boolean=True)  # 1 if depot 1 is opened, else 0 (yes/no)
x21 = cp.Variable(name='x21')  # units shipped from depot 2 to store 1 (units)
x22 = cp.Variable(name='x22')  # units shipped from depot 2 to store 2 (units)
x23 = cp.Variable(name='x23')  # units shipped from depot 2 to store 3 (units)
y2 = cp.Variable(name='y2', boolean=True)  # 1 if depot 2 is opened, else 0 (yes/no)

objective = cp.Minimize(2*x11 + 4*x12 + 5*x13 + 5*x21 + 3*x22 + 2*x23 + 20*y1 + 25*y2)
constraints = [
    x11 + x12 + x13 <= 30*y1,
    x21 + x22 + x23 <= 25*y2,
    x11 + x21 == 15,
    x12 + x22 == 20,
    x13 + x23 == 10,
    x11 >= 0,
    x12 >= 0,
    x13 >= 0,
    x21 >= 0,
    x22 >= 0,
    x23 >= 0,
]
problem = cp.Problem(objective, constraints)
problem.solve(solver='HIGHS')
print(problem.status, problem.value)
print('x11 =', x11.value)
print('x12 =', x12.value)
print('x13 =', x13.value)
print('y1 =', y1.value)
print('x21 =', x21.value)
print('x22 =', x22.value)
print('x23 =', x23.value)
print('y2 =', y2.value)

The dual problem

Every constraint of the original (primal) problem gets a price, and every primal variable becomes a constraint on those prices. Integer variables are relaxed: this is the dual of the continuous (LP) relaxation, which gives a bound on the integer optimum, not its exact value. Only weak duality: the dual of the continuous relaxation gives an lower bound of 153.333 on the integer optimum 160, a duality gap of 6.66667. Integer problems generally have a gap.

Dual variablePricesValue
y1price of constraint 'x11 + x12 + x13 <= 30*y1' (objective change per extra unit of its right-hand side)-0.666667
y2price of constraint 'x21 + x22 + x23 <= 25*y2' (objective change per extra unit of its right-hand side)-1.66667
y3price of constraint 'x11 + x21 = 15' (objective change per extra unit of its right-hand side)2.66667
y4price of constraint 'x12 + x22 = 20' (objective change per extra unit of its right-hand side)4.66667
y5price of constraint 'x13 + x23 = 10' (objective change per extra unit of its right-hand side)3.66667
y6price of constraint 'y1 <= 1' (objective change per extra unit of its right-hand side)0
y7price of constraint 'y2 <= 1' (objective change per extra unit of its right-hand side)-16.6667

Solve your own

This is the model as the app reads it. Change any number and solve it in the free box on the front page (no account needed).

minimize 20*y1 + 25*y2 + 2*x11 + 4*x12 + 5*x13 + 5*x21 + 3*x22 + 2*x23
subject to
x11 + x12 + x13 <= 30*y1
x21 + x22 + x23 <= 25*y2
x11 + x21 = 15
x12 + x22 = 20
x13 + x23 = 10
x11, x12, x13, x21, x22, x23 >= 0
binary: y1, y2
# y1 = 1 if depot 1 is opened, else 0 (yes/no)
# y2 = 1 if depot 2 is opened, else 0 (yes/no)
# x11 = units shipped from depot 1 to store 1 (units)
# x12 = units shipped from depot 1 to store 2 (units)
# x13 = units shipped from depot 1 to store 3 (units)
# x21 = units shipped from depot 2 to store 1 (units)
# x22 = units shipped from depot 2 to store 2 (units)
# x23 = units shipped from depot 2 to store 3 (units)
# objective = total depot opening cost plus shipping cost ($)

Change the numbers and solve it

Checked: the app's answer matches the reference answer in our test set, which two solvers (HIGHS, SCIP) agree on. Built 2026-11-10.

Related examples

All 50 solved examples

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: