Optimization

optimization-ai999x

Linear and integer programming, convex and nonlinear optimisation, assignment, transportation and shortest-route problems, scheduling, inventory, queueing, game theory and multi-criteria decisions.

Mathematics & Statistics Question Answering Sentence Similarity Feature Extraction

Hugging Face ↗GitHub ↗See it on the capability orb

72capabilities

16topics

72formulas typeset

8worked examples below

1.0.0version

About this model

What Optimization does

Optimization (optimization-ai999x) is an offline Python package for optimization. It covers linear and integer programming, convex and nonlinear optimisation, assignment, transportation and shortest-route problems, scheduling, inventory, queueing, game theory and multi-criteria decisions.

It has 72 capabilities — 72 computational procedures — in 16 topics, the largest being Network optimisation, Inventory management, Integer programming, Queueing theory, Multi-criteria decision analysis and Scheduling. Ask a question in words with ask(), or call a capability by name with typed inputs with solve(). Every answer carries its value and unit, the steps that produced it and the formula in LaTeX.

When a question is not determined — a value is missing, an input is out of range, or the request is outside the package — it says so and names what it needs, instead of guessing. It runs on an ordinary CPU without a network connection (Python >=3.10), and the same question always gets the same answer.

Install

pip install optimization-ai999x
hf download AI999X/optimization-ai999x --local-dir optimization-ai999x

What it covers

Calculus optimisation5Absolute extrema of a polynomial on a closed interval · Closed cylinder of least surface area for a given volume · Critical point of a two-variable quadratic and its classification …Cost-volume-profit analysis1Break-even quantity Dynamic programming2Discounted Markov decision process (optimal values and policy) · Dynamic lot sizing (Wagner-Whitin)Economic optimisation2Profit-maximising output with linear demand · Revenue-maximising price with linear demand Game theory42 x 2 zero-sum game (saddle point or mixed-strategy formula) · Mixed-strategy Nash equilibrium of a 2 x 2 game · Pure-strategy Nash equilibria of a bimatrix game …Integer programming80/1 knapsack problem · Bin packing (minimum number of bins) · Chromatic number (minimum graph colouring) …Inventory management9Economic order quantity (EOQ) · Economic production quantity (EPQ) · EOQ with planned backorders …Linear programming3Linear program (simplex method) · Shadow prices of a linear program · Two-variable linear program (graphical corner-point method)Multi-criteria decision analysis6AHP consistency ratio · AHP priority vector (principal eigenvector) · AHP weights by the geometric mean method …Network optimisation12All-pairs shortest distances (Floyd-Warshall) · Assignment problem (Hungarian method), maximum total value · Assignment problem (Hungarian method), minimum total cost …Nonlinear optimisation3Equality-constrained quadratic program (Lagrange multipliers / KKT) · Steepest descent step with exact line search (quadratic) · Unconstrained quadratic minimisation Project scheduling2Critical path method (project duration and slack) · PERT project duration and completion probability Queueing theory7Erlang B blocking probability (M/M/c/c loss system) · M/G/1 queue (Pollaczek-Khinchine formula) · M/M/1 queue …Revenue management1Littlewood's rule (two-fare protection level)Scheduling6Earliest due date rule (minimum maximum lateness) · Johnson's rule (two-machine flow shop) · Minimum makespan on identical parallel machines …Unconstrained optimisation1Optimum of a quadratic function

Try it

Worked examples

Each question below was put to optimization-ai999x and the answer shown is the one it returned, with the steps it took.

Network optimisationm.ask(…)

Solve the transportation problem with supply [20, 30], demand [10, 25, 15] and cost matrix [[2, 3, 1], [5, 4, 8]].

min_cost = 150

shipments = [[5, 0, 15], [5, 25, 0]]

plan_unique = yes

dual = [-3, 0, 5, 4, 4]

Show the steps

Transportation problem (minimum shipping cost)
\min \sum_{ij} c_{ij} x_{ij}\ \text{s.t.}\ \sum_j x_{ij} \le s_i,\ \sum_i x_{ij} = d_j,\ x \ge 0
with supply = [20, 30], demand = [10, 25, 15], cost = [2 3 1; 5 4 8]
→ min_cost = 150, shipments = [[5, 0, 15], [5, 25, 0]], plan_unique = yes, dual = [-3, 0, 5, 4, 4]

Capability: Transportation problem (minimum shipping cost)

Network optimisationm.ask(…)

Find the shortest path from A to D in the undirected graph with edges A-B 4, A-C 2, B-C 1, B-D 5, C-D 8.

distance = 8

path = [A, C, B, D]

path_unique = yes

Show the steps

Shortest path (Dijkstra's algorithm)
d(v) = \min_{(u,v)} \big(d(u) + w_{uv}\big)
with edges = A-B (4), A-C (2), B-C (1), B-D (5), C-D (8), source = A, target = D, directed = False
→ distance = 8, path = [A, C, B, D], path_unique = yes

Capability: Shortest path (Dijkstra's algorithm)

Inventory managementm.solve(…)

m.solve("eoq", D=1200, S=50, H=3)

Q = 200

total_cost = 600

orders_per_period = 6

cycle_time = 0.1666666667

Show the steps

Economic order quantity (EOQ)
Q^* = \sqrt{\frac{2 D S}{H}}, \quad TC^* = \sqrt{2 D S H}
with D = 1200, S = 50, H = 3
→ Q = 200, total_cost = 600, orders_per_period = 6, cycle_time = 0.1666666667

Capability: Economic order quantity (EOQ)

Multi-criteria decision analysism.ask(…)

Find the AHP consistency ratio for the pairwise judgments [3, 5, 2].

CR = 0.003184998331

CI = 0.001847299032

lambda_max = 3.003694598

weights = [0.6483290138, 0.2296507941, 0.1220201921]

acceptable = yes

Show the steps

AHP consistency ratio
CI = \frac{\lambda_{\max} - n}{n - 1},\quad CR = \frac{CI}{RI_n}
with judgments = [3, 5, 2]
→ CR = 0.003184998331, CI = 0.001847299032, lambda_max = 3.003694598, weights = [0.6483290138, 0.2296507941, 0.1220201921], acceptable = yes

Capability: AHP consistency ratio

Game theorym.ask(…)

Find the pure-strategy Nash equilibria of the bimatrix game with row payoffs [[3, 0], [5, 1]] and column payoffs [[3, 5], [0, 1]].

count = 1

equilibria = [[2, 2]]

Show the steps

Pure-strategy Nash equilibria of a bimatrix game
a_{rs} = \max_k a_{ks},\quad b_{rs} = \max_k b_{rk}
with A = [3 0; 5 1], B = [3 5; 0 1]
→ count = 1, equilibria = [[2, 2]]

Capability: Pure-strategy Nash equilibria of a bimatrix game

Calculus optimisationm.ask(…)

A closed cylindrical can must hold 500 cm^3. Find the dimensions that minimize the surface area.

radius = 4.301270069

height = 8.602540138

min_area = 348.7342055

Show the steps

Closed cylinder of least surface area for a given volume
r^* = \left(\frac{V}{2\pi}\right)^{1/3}, \quad h^* = 2r^*
with V = 500
→ radius = 4.301270069, height = 8.602540138, min_area = 348.7342055

Capability: Closed cylinder of least surface area for a given volume

Cost-volume-profit analysism.ask(…)

A firm has fixed costs of 5000, a selling price of 25 per unit and a variable cost of 15 per unit. Find the break-even quantity.

quantity = 500

revenue = 12500

contribution_margin = 10

Show the steps

Break-even quantity
Q_{BE} = \frac{F}{p - v}
with F_ = 5000, p = 25, v = 15
→ quantity = 500, revenue = 12500, contribution_margin = 10

Capability: Break-even quantity

Dynamic programmingm.ask(…)

Solve the discounted Markov decision process with rewards [[1, 0], [0, 2]], transitions [[1, 0], [0, 1], [0, 1], [1, 0]] and discount factor 0.9.

value_state_1 = 10

values = [10, 11]

policy = [1, 2]

Show the steps

Discounted Markov decision process (optimal values and policy)
V^*(s) = \max_a \Big( R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s') \Big)
with R = [1 0; 0 2], T = [1 0; 0 1; 0 1; 1 0], gamma = 0.9
→ value_state_1 = 10, values = [10, 11], policy = [1, 2]

Capability: Discounted Markov decision process (optimal values and policy)

Use it

From Python or the command line

Every snippet was run as shown; the output under it is what it printed.

import optimization_ai999x as m

a = m.ask("Solve the transportation problem with supply [20, 30], demand [10, 25, 15] and cost matrix [[2, 3, 1], [5, 4, 8]].")
print(a.outcome)
print(a.values)
for step in a.steps:
    print(step["name"])

Output

SOLVED
{'min_cost': 150.0, 'shipments': [[5.0, 0.0, 15.0], [5.0, 25.0, 0.0]], 'plan_unique': 'yes', 'dual': [-3.0, 0.0, 5.0, 4.0, 4.0]}
Transportation problem (minimum shipping cost)

import optimization_ai999x as m

a = m.solve("eoq", D=1200, S=50, H=3)
print(a.outcome)
print(a.values)

Output

SOLVED
{'Q': 200.0, 'total_cost': 600.0, 'orders_per_period': 6.0, 'cycle_time': 0.16666666666666666}

import optimization_ai999x as m

# an input is missing: the answer says what it needs instead of guessing
a = m.solve("eoq")
print(a.outcome)
print(a.message)

Output

NEEDS_INPUT
eoq needs D, S, H (demand per period (units, e.g. per year); fixed cost per order; holding cost per unit per period). Example: solve('eoq', D=1200, S=50, H=3).

optimization-ai999x "Solve the transportation problem with supply [20, 30], demand [10, 25, 15] and cost matrix [[2, 3, 1], [5, 4, 8]]."

Output

min_cost = 150, shipments = [[5.0, 0.0, 15.0], [5.0, 25.0, 0.0]], plan_unique = yes, dual = [-3.0, 0.0, 5.0, 4.0, 4.0]
1. Transportation problem (minimum shipping cost): the transportation LP solved exactly (rational simplex), certified by its dual (u_i + v_j <= c_ij)  with supply = [20, 30], demand = [10, 25, 15], cost = [2 3 1; 5 4 8]  ->  min_cost = 150, shipments = [[5.0, 0.0, 15.0], [5.0, 25.0, 0.0]], plan_unique = yes, dual = [-3.0, 0.0, 5.0, 4.0, 4.0]
Assumptions: total supply >= total demand (surplus stays at the sources at no cost); at most 60 routes
…

Figures

Computed, not drawn by hand

Every value in these figures was computed by the package, each point a run of solve(); in a notebook, plot() and plot_relation() draw a capability's curves the same way.

A linear programme: feasible region and optimal corner

z^* = \max_{v \in \text{corners}} c^\top v

Maximise 3x + 5y subject to x ≤ 4; 2y ≤ 12; 3x + 2y ≤ 18, x, y ≥ 0: the feasible region with the corner points the package returns ((0, 0), (0, 6), (2, 6), (4, 0), (4, 3)) and the objective line through the optimum; marked: x = 2, y = 6, objective 36.

Steepest descent zig-zagging to the minimum

\alpha = \frac{g^\top g}{g^\top Q g},\quad x_1 = x_0 - \alpha g

Steepest descent with exact line search on f(x) = ½ xᵀQx, Q = [[2, 0], [0, 8]], from x₀ = (4, 1): six steps computed by the package, each perpendicular to the level set through its start (f = 20, 7.2, 2.592, 0.93312, 0.335923, 0.120932, 0.0435356); marked: x₆ = (0.186624, 0.046656).

Shortest path and minimum spanning tree

d(v) = \min_{(u,v)} \big(d(u) + w_{uv}\big)

A weighted network (A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, A-E 7, E-D 3, C-E 6): the shortest path from A to D the package finds, A → C → B → D of length 8, and its minimum spanning tree (B-C, A-C, E-D, B-D, total weight 11).

An optimal transportation plan

\min \sum_{ij} c_{ij} x_{ij}\ \text{s.t.}\ \sum_j x_{ij} \le s_i,\ \sum_i x_{ij} = d_j,\ x \ge 0

The optimal transportation plan the package computes for supplies [20, 30], demands [10, 25, 15] and unit costs [[2, 3, 1], [5, 4, 8]] (rows: sources, columns: destinations; left the unit costs, right the quantities shipped): minimum total cost 150.

A two-machine schedule in Johnson's order

\min C_{\max} \text{ for } F2 \| C_{\max}

A two-machine flow shop: processing times [5, 2, 6, 7] on machine 1 and [3, 4, 8, 2] on machine 2. The package's Johnson order is job 2 → job 3 → job 1 → job 4, with makespan 22; each job starts on machine 2 as soon as it leaves machine 1 and machine 2 is free.

Formulas

The mathematics inside

12 of its 72 formulas; every one is in the capability browser below.

Transportation problem (minimum shipping cost)

\min \sum_{ij} c_{ij} x_{ij}\ \text{s.t.}\ \sum_j x_{ij} \le s_i,\ \sum_i x_{ij} = d_j,\ x \ge 0

Shortest path (Dijkstra's algorithm)

d(v) = \min_{(u,v)} \big(d(u) + w_{uv}\big)

Economic order quantity (EOQ)

Q^* = \sqrt{\frac{2 D S}{H}}, \quad TC^* = \sqrt{2 D S H}

AHP consistency ratio

CI = \frac{\lambda_{\max} - n}{n - 1},\quad CR = \frac{CI}{RI_n}

Pure-strategy Nash equilibria of a bimatrix game

a_{rs} = \max_k a_{ks},\quad b_{rs} = \max_k b_{rk}

Closed cylinder of least surface area for a given volume

r^* = \left(\frac{V}{2\pi}\right)^{1/3}, \quad h^* = 2r^*

Break-even quantity

Q_{BE} = \frac{F}{p - v}

Discounted Markov decision process (optimal values and policy)

V^*(s) = \max_a \Big( R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s') \Big)

Absolute extrema of a polynomial on a closed interval

\min_{[a,b]} f = \min\{f(a), f(b), f(c) : f'(c) = 0,\ a < c < b\}

Dynamic lot sizing (Wagner-Whitin)

C_t = \min_{1 \le s \le t} \Big( C_{s-1} + K + h \sum_{u=s}^{t} (u - s)\, d_u \Big)

Profit-maximising output with linear demand

q^* = \frac{a - c}{2b}, \quad p^* = \frac{a + c}{2}

2 x 2 zero-sum game (saddle point or mixed-strategy formula)

v = \frac{ad - bc}{a + d - b - c},\quad p = \frac{d - c}{a + d - b - c},\quad q = \frac{d - b}{a + d - b - c}

Capabilities

Every capability, with an example

Search by name, formula, input or topic. Each capability opens to show what it takes, what it returns, when it applies, and a question it answered.

72 capabilities

Calculus optimisation 5

Absolute extrema of a polynomial on a closed intervalpolynomial_extrema_interval

The absolute minimum and maximum of a polynomial on [lo, hi] (closed-interval method: endpoints and critical points), and where they are attained.

\min_{[a,b]} f = \min\{f(a), f(b), f(c) : f'(c) = 0,\ a < c < b\}

Inputs

coefficients polynomial coefficients, highest power first vector
lo left end of the interval
hi right end of the interval

Returns

min_value absolute minimum
max_value absolute maximum
argmin_example a point attaining the minimum (the smallest one on a tie)
argmax_example a point attaining the maximum (the smallest one on a tie)

Applies when

lo < hi
degree 1 to 5

Example

m.ask("Find the absolute minimum and maximum of the polynomial with coefficients [1, -3, 0, 2] on the interval [-1, 3].")

→ min_value = -2, max_value = 2, argmin_example = -1, argmax_example = 0

Closed cylinder of least surface area for a given volumecan_min_surface

The radius, height and surface area of the closed cylindrical can that holds a volume V with the least material.

r^* = \left(\frac{V}{2\pi}\right)^{1/3}, \quad h^* = 2r^*

Inputs

V volume (cube of the length unit)

Returns

radius optimal radius
height optimal height (equal to the diameter)
min_area least total surface area

Applies when

V > 0
closed top and bottom

Example

m.ask("A closed cylindrical can must hold 500 cm^3. Find the dimensions that minimize the surface area.")

→ radius = 4.30127, height = 8.60254, min_area = 348.734

Critical point of a two-variable quadratic and its classificationcritical_point_two_variables

For f(x, y) = a x^2 + b xy + c y^2 + d x + e y + f0: the critical point, its value and whether it is a local minimum, a local maximum or a saddle point (second-derivative test).

D = f_{xx} f_{yy} - f_{xy}^2 = 4ac - b^2

Inputs

a coefficient of x^2
b coefficient of xy
c coefficient of y^2
d coefficient of x optional
e coefficient of y optional
f0 constant term optional

Returns

f_value value of f at the critical point
x x of the critical point
y y of the critical point
type local minimum, local maximum or saddle point

Applies when

4ac - b^2 != 0 (an isolated critical point)

Example

m.ask("Find and classify the critical point of f(x, y) = 3x^2 + 2xy + y^2 - 4x + 6y + 1.")

→ f_value = -20.5, x = 2.5, y = -5.5, type = local minimum

Largest rectangle for a given length of fencingfence_max_area

The dimensions and maximum area of a rectangle enclosed by a fence of length L, on four sides or on three sides with a wall or river as the fourth.

A_{\max} = \frac{L^2}{16} \text{ (4 sides)}, \quad \frac{L^2}{8} \text{ (3 sides)}

Inputs

L total length of fencing (any length unit)
wall true when one side lies along a wall or river and needs no fence boolean optional

Returns

width side perpendicular to the wall (or one side of the square)
length side parallel to the wall
max_area maximum enclosed area (square of the length unit)

Applies when

L > 0

Example

m.ask("A farmer has 200 m of fencing to enclose a rectangular field. What is the maximum area?")

→ width = 50, length = 50, max_area = 2500

Open box of maximum volume from a rectangular sheetopen_box_max_volume

Squares of side x are cut from the corners of an L by W sheet and the sides folded up: the cut that maximises the volume, and that volume.

x^* = \frac{(L+W) - \sqrt{L^2 - LW + W^2}}{6}

Inputs

L sheet length
W sheet width

Returns

cut side of the corner squares at the maximum
max_volume maximum volume

Applies when

L > 0 and W > 0

Example

m.ask("An open box is made from a 12 by 12 sheet by cutting equal squares from the corners. Find the maximum volume.")

→ cut = 2, max_volume = 128

Cost-volume-profit analysis 1

Break-even quantitybreak_even_point

The number of units at which revenue equals total cost (fixed plus variable), and the revenue there.

Q_{BE} = \frac{F}{p - v}

Inputs

F_ fixed cost (currency)
p selling price per unit
v variable cost per unit

Returns

quantity break-even quantity (units)
revenue revenue at break-even
contribution_margin price minus variable cost per unit

Applies when

fixed cost >= 0
price > variable cost

Example

m.ask("A firm has fixed costs of 5000, a selling price of 25 per unit and a variable cost of 15 per unit. Find the break-even quantity.")

→ quantity = 500, revenue = 12500, contribution_margin = 10

Dynamic programming 2

Discounted Markov decision process (optimal values and policy)mdp_discounted

The optimal expected discounted reward from every state of a finite Markov decision process and an optimal stationary policy.

V^*(s) = \max_a \Big( R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s') \Big)

Inputs

R rewards, rows = states, columns = actions matrix
T transition probabilities: one row per (state, action) in the order s1a1, s1a2, ..., s2a1, ...; columns = next state matrix
gamma discount factor (0 < gamma < 1)

Returns

value_state_1 optimal value of state 1
values optimal value of every state
policy optimal action in each state, 1-based (the lowest-numbered one on a tie)

Applies when

0 < gamma < 1
rows of T sum to 1
at most 10 states and 5 actions

Example

m.ask("Solve the discounted Markov decision process with rewards [[1, 0], [0, 2]], transitions [[1, 0], [0, 1], [0, 1], [1, 0]] and discount factor 0.9.")

→ value_state_1 = 10, values = [10.0, 11.0], policy = [1.0, 2.0]

Dynamic lot sizing (Wagner-Whitin)wagner_whitin_lot_sizing

The cheapest ordering plan for known demands over several periods with a fixed cost per order and a holding cost per unit carried to the next period (no shortages).

C_t = \min_{1 \le s \le t} \Big( C_{s-1} + K + h \sum_{u=s}^{t} (u - s)\, d_u \Big)

Inputs

demand demand in each period vector
K setup (ordering) cost per order
h holding cost per unit per period

Returns

min_cost minimum total setup plus holding cost
order_quantities_example one optimal plan: quantity ordered in each period
orders number of orders in that plan

Applies when

demands, K, h >= 0
no initial stock, no shortages, holding charged on end-of-period stock

Example

m.ask("Wagner-Whitin lot sizing with demands [20, 50, 10, 50], setup cost 100 and holding cost 1 per unit per period.")

→ min_cost = 270, order_quantities_example = [80.0, 0.0, 0.0, 50.0], orders = 2

Economic optimisation 2

Profit-maximising output with linear demandprofit_max_linear_demand

With inverse demand p = a - b q and cost C = F + c q, the output, price and profit at the profit maximum.

q^* = \frac{a - c}{2b}, \quad p^* = \frac{a + c}{2}

Inputs

a demand intercept (price at zero quantity)
b demand slope (price drop per unit)
cv marginal (variable) cost per unit
F_ fixed cost (default 0) optional

Returns

quantity profit-maximising quantity
price price at that quantity
profit maximum profit

Applies when

b > 0
a > c

Example

m.ask("The demand is p = 100 - 2q and the cost is C = 300 + 20q. Find the profit-maximizing quantity.")

→ quantity = 20, price = 60, profit = 500

Revenue-maximising price with linear demandrevenue_max_linear_demand

With demand q = alpha - beta p, the price that maximises revenue p q, the quantity sold and the revenue.

p^* = \frac{\alpha}{2\beta}, \quad R^* = \frac{\alpha^2}{4\beta}

Inputs

alpha demand at a price of zero
beta drop in demand per unit increase in price

Returns

price revenue-maximising price
quantity quantity sold at that price
revenue maximum revenue

Applies when

alpha > 0
beta > 0

Example

m.ask("The demand is q = 1000 - 20p. Find the revenue-maximizing price.")

→ price = 25, quantity = 500, revenue = 12500

Game theory 4

2 x 2 zero-sum game (saddle point or mixed-strategy formula)zero_sum_2x2

The value of a 2 x 2 matrix game: the saddle-point value when one exists, otherwise the mixed-strategy solution (probability of each player's first strategy, unique in that case).

v = \frac{ad - bc}{a + d - b - c},\quad p = \frac{d - c}{a + d - b - c},\quad q = \frac{d - b}{a + d - b - c}

Inputs

A 2 x 2 payoff matrix to the row player [[a, b], [c, d]] matrix

Returns

value value of the game
saddle_point yes when a pure saddle point exists
p_row1 probability the row player plays row 1 (only without a saddle point)
q_col1 probability the column player plays column 1 (only without a saddle point)

Applies when

a 2 x 2 matrix

Example

m.ask("Solve the zero-sum game with payoff matrix [[3, -1], [-2, 4]].")

→ value = 1, p_row1 = 0.6, q_col1 = 0.5, saddle_point = no

Mixed-strategy Nash equilibrium of a 2 x 2 gamemixed_nash_2x2

The equilibrium of a 2 x 2 two-player game without a pure equilibrium: each player's probability of the first strategy (chosen to make the OTHER player indifferent) and the expected payoffs.

q = \frac{a_{22} - a_{12}}{a_{11} - a_{12} - a_{21} + a_{22}},\quad p = \frac{b_{22} - b_{21}}{b_{11} - b_{12} - b_{21} + b_{22}}

Inputs

A row player's 2 x 2 payoffs matrix
B column player's 2 x 2 payoffs matrix

Returns

p_row1 probability the row player plays row 1
q_col1 probability the column player plays column 1
row_payoff row player's expected payoff
col_payoff column player's expected payoff

Applies when

2 x 2 matrices
no pure-strategy equilibrium (then the mixed one is unique)

Example

m.ask("Find the mixed-strategy Nash equilibrium of the game with row payoffs [[3, -1], [-2, 1]] and column payoffs [[-1, 2], [1, -1]].")

→ p_row1 = 0.4, q_col1 = 0.285714, row_payoff = 0.142857, col_payoff = 0.2

Pure-strategy Nash equilibria of a bimatrix gamepure_nash_equilibria

Every pure-strategy Nash equilibrium (a cell where each player's strategy is a best reply to the other's) of a two-player game given by the two players' payoff matrices.

a_{rs} = \max_k a_{ks},\quad b_{rs} = \max_k b_{rk}

Inputs

A row player's payoffs (rows = row strategies) matrix
B column player's payoffs (same shape) matrix

Returns

count number of pure equilibria
equilibria all pure equilibria as [row, column], 1-based, in row-major order

Applies when

at most 8 strategies per player
weak best replies count (ties are equilibria)

Example

m.ask("Find the pure-strategy Nash equilibria of the bimatrix game with row payoffs [[3, 0], [5, 1]] and column payoffs [[3, 5], [0, 1]].")

→ count = 1, equilibria = [[2.0, 2.0]]

Two-person zero-sum game (value and optimal mixed strategies)zero_sum_game

The value of a matrix game (row player maximises the payoff in the matrix, column player minimises it) and one optimal mixed strategy for each player.

v = \max_{x \in \Delta_m} \min_{j} \sum_i x_i a_{ij} = \min_{y \in \Delta_n} \max_i \sum_j a_{ij} y_j

Inputs

A payoff matrix to the row player, rows = row strategies, columns = column strategies matrix

Returns

value value of the game
row_strategy_example one optimal mixed strategy of the row player
col_strategy_example one optimal mixed strategy of the column player

Applies when

at most 12 strategies per player

Example

m.ask("Solve the zero-sum game with payoff matrix [[3, -1, 2], [-2, 4, 1], [0, 1, -1]].")

→ value = 1, row_strategy_example = [0.6, 0.4, 0.0], col_strategy_example = [0.5, 0.5, 0.0]

Integer programming 8

0/1 knapsack problemknapsack_01

Choose items (each at most once) to maximise total value without exceeding the capacity: the maximum value, one optimal choice and its weight.

\max \sum_i v_i x_i \ \text{s.t.}\ \sum_i w_i x_i \le W,\ x_i \in \{0,1\}

Inputs

values value of each item vector
weights weight of each item vector
capacity knapsack capacity

Returns

max_value maximum total value
items_example one optimal set of items (1-based; ties to the lighter set)
total_weight weight of that set

Applies when

values, weights, capacity >= 0
at most 40 items

Example

m.ask("Solve the knapsack problem with values [60, 100, 120], weights [10, 20, 30] and capacity 50.")

→ max_value = 220, items_example = [2, 3], total_weight = 50

Bin packing (minimum number of bins)bin_packing

Pack items of given sizes into the fewest bins of a given capacity: the minimum number and one packing.

\min \#\text{bins} \ \ge\ \left\lceil \sum_j s_j / C \right\rceil

Inputs

sizes size of each item vector
capacity capacity of each bin

Returns

min_bins minimum number of bins
bin_of_item one optimal packing: bin number of each item
lower_bound ceil(total size / capacity)

Applies when

at most 14 items
every item fits in a bin

Example

m.ask("Bin packing: item sizes [4, 8, 1, 4, 2, 1] and bin capacity 10. Find the minimum number of bins.")

→ min_bins = 2, bin_of_item = [2, 1, 2, 2, 1, 2], lower_bound = 2

Chromatic number (minimum graph colouring)graph_coloring

The fewest colours needed so that adjacent nodes get different colours (scheduling exams, assigning frequencies), and one such colouring.

\chi(G) = \min\{k : \exists\, c: V \to \{1..k\},\ c(u) \neq c(v)\ \forall uv \in E\}

Inputs

edges edges 'A-B, B-C, ...' (undirected) edges

Returns

chromatic_number minimum number of colours
coloring_example one optimal colouring, in the order of 'nodes'
nodes node order (first appearance)

Applies when

at most 14 nodes
no self-loops

Example

m.ask("Find the chromatic number of the graph with edges A-B, B-C, C-A, C-D.")

→ chromatic_number = 3, coloring_example = [2.0, 3.0, 1.0, 2.0], nodes = ['A', 'B', 'C', 'D']

Integer linear program (branch and bound)integer_program

Optimise a linear objective over non-negative INTEGER points satisfying linear constraints: the optimal value and one optimal integer solution.

\max / \min \; c^\top x \quad \text{s.t. } A x \;(\le,\ge,=)\; b,\; x \in \mathbb{Z}_{\ge 0}^n

Inputs

sense maximize or minimize choice
c objective coefficients, one per variable vector
A constraint coefficients, one row per constraint matrix
b right-hand sides, one per constraint vector
relations relation of each constraint: <=, >= or = (default all <=) text optional

Returns

optimal_value optimal value over integer points
x_one_optimal one optimal integer solution (the first found: depth-first, lowest-index fractional variable, round-down branch first)
nodes branch-and-bound nodes explored

Applies when

all variables integer and >= 0
a bounded LP relaxation
at most 4000 branch-and-bound nodes

Example

m.ask("Maximize 5x + 4y subject to 6x + 4y <= 24, x + 2y <= 6, x, y >= 0 and integer.")

→ optimal_value = 20, x_one_optimal = [4.0, 0.0], nodes = 5

Minimum vertex cover (and maximum independent set)minimum_vertex_cover

The fewest nodes that touch every edge of a graph (placing guards or sensors), one such set, and the size of a largest set of pairwise non-adjacent nodes.

\tau(G) = \min\{|C| : C \cap \{u, v\} \neq \emptyset\ \forall uv \in E\},\quad \alpha(G) = |V| - \tau(G)

Inputs

edges edges 'A-B, B-C, ...' (undirected) edges

Returns

min_cover_size size of a minimum vertex cover
cover_example one minimum vertex cover
max_independent_set_size size of a maximum independent set (nodes minus cover)

Applies when

at most 30 nodes
no self-loops
only nodes that appear in an edge count

Example

m.ask("Find the minimum vertex cover of the graph with edges A-B, A-C, A-D, B-C, D-E.")

→ min_cover_size = 3, cover_example = ['A', 'C', 'E'], max_independent_set_size = 2

Minimum-cost set coverset_cover

Choose sets (each with a cost) that together contain every element, at least total cost.

\min \sum_i c_i x_i\ \text{s.t.}\ \sum_{i \ni e} x_i \ge 1\ \forall e,\ x \in \{0,1\}

Inputs

sets incidence matrix: row i lists with 0/1 which elements set i contains matrix
costs cost of each set vector

Returns

min_cost minimum total cost of a cover
sets_example one optimal choice of sets (1-based)

Applies when

at most 18 sets
every element in some set

Example

m.ask("Solve the set cover problem with incidence matrix [[1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 1, 1], [1, 0, 0, 1]] and costs [3, 2, 3, 2].")

→ min_cost = 4, sets_example = [2, 4]

Unbounded knapsack problemknapsack_unbounded

Choose any number of copies of each item type to maximise total value within the capacity.

V(c) = \max\big(V(c-1),\ \max_{i: w_i \le c} V(c - w_i) + v_i\big)

Inputs

values value of each item type vector
weights weight of each item type (whole numbers) vector
capacity capacity (a whole number)

Returns

max_value maximum total value
copies_example number of copies of each type in one optimal choice

Applies when

positive whole-number weights
capacity a whole number <= 100000

Example

m.ask("Solve the unbounded knapsack problem with values [10, 40, 50, 70], weights [1, 3, 4, 5] and capacity 8.")

→ max_value = 110, copies_example = [0.0, 1.0, 0.0, 1.0]

Uncapacitated facility locationfacility_location

Choose which facilities to open (each with a fixed cost) and serve every customer from its cheapest open facility, minimising fixed plus service cost.

\min_{S \neq \emptyset} \sum_{i \in S} f_i + \sum_j \min_{i \in S} c_{ij}

Inputs

fixed fixed opening cost of each facility vector
cost service cost matrix, rows = facilities, columns = customers matrix

Returns

min_cost minimum total cost
open_example one optimal set of facilities to open (1-based)

Applies when

at most 15 facilities
unlimited capacity

Example

m.ask("Facility location: fixed costs [10, 15, 12] and service cost matrix [[3, 8, 6, 9], [7, 2, 4, 3], [5, 6, 2, 8]]. Which facilities should open?")

→ min_cost = 31, open_example = [2]

Inventory management 9

Economic order quantity (EOQ)eoq

The order size that minimises ordering plus holding cost for a steady demand, the minimum cost, the number of orders per period and the time between orders.

Q^* = \sqrt{\frac{2 D S}{H}}, \quad TC^* = \sqrt{2 D S H}

Inputs

D demand per period (units, e.g. per year)
S fixed cost per order
H holding cost per unit per period

Returns

Q economic order quantity
total_cost minimum ordering + holding cost per period
orders_per_period number of orders per period
cycle_time time between orders (in periods)

Applies when

D, S, H > 0
constant demand, instant replenishment, no shortages

Example

m.ask("Find the EOQ for an annual demand of 1200 units, an ordering cost of 50 per order and a holding cost of 3 per unit per year.")

→ Q = 200, total_cost = 600, orders_per_period = 6, cycle_time = 0.166667

Economic production quantity (EPQ)epq_production_lot

The production lot size that minimises setup plus holding cost when stock builds up gradually at a finite production rate.

Q^* = \sqrt{\frac{2DS}{H(1 - D/P)}}

Inputs

D demand rate per period
P production rate per period (> D)
S setup cost per run
H holding cost per unit per period

Returns

Q economic production quantity
max_inventory maximum inventory Q (1 - D/P)
total_cost minimum setup + holding cost per period
runs_per_period production runs per period

Applies when

P > D > 0
S, H > 0

Example

m.ask("Find the EPQ for an annual demand of 1000 units, a production rate of 2000 units per year, a setup cost of 100 and a holding cost of 4 per unit per year.")

→ Q = 316.228, max_inventory = 158.114, total_cost = 632.456, runs_per_period = 3.16228

EOQ with planned backorderseoq_planned_shortages

The order quantity and the planned maximum backorder that minimise ordering, holding and shortage cost when unmet demand is backordered.

Q^* = \sqrt{\frac{2DS}{H}\cdot\frac{H+B}{B}}, \quad s^* = Q^* \frac{H}{H+B}

Inputs

D demand per period
S cost per order
H holding cost per unit per period
B backorder (shortage) cost per unit per period

Returns

Q optimal order quantity
max_backorder planned maximum backorder
max_inventory maximum inventory level
total_cost minimum total cost per period

Applies when

D, S, H, B > 0
backorders filled when the order arrives

Example

m.ask("Find the EOQ with backorders for an annual demand of 1200 units, an ordering cost of 50, a holding cost of 3 and a shortage cost of 6 per unit per year.")

→ Q = 244.949, max_backorder = 81.6497, max_inventory = 163.299, total_cost = 489.898

Newsvendor order quantity (discrete demand)newsvendor_discrete

For demand taking listed values with given probabilities, the order quantity that maximises expected profit (the smallest demand value whose cumulative probability reaches the critical ratio) and that profit.

Q^* = \min\{ d : F(d) \ge \tfrac{p - c}{p - s} \}

Inputs

p selling price per unit
c cost per unit
demands possible demand values, increasing vector
probs probability of each demand value (sum 1) vector
s salvage value per unsold unit (default 0) optional

Returns

critical_ratio critical ratio (p - c)/(p - s)
Q optimal order quantity (smallest optimal value)
expected_profit maximum expected profit

Applies when

salvage < cost < price
probabilities sum to 1
order quantities restricted to the listed demand values

Example

m.ask("Newsvendor: a cake sells for 10 and costs 4; demand values [10, 20, 30, 40] have probabilities [0.1, 0.3, 0.4, 0.2]. How many should be ordered?")

→ critical_ratio = 0.6, Q = 30, expected_profit = 130

Newsvendor order quantity (normal demand)newsvendor_normal

The single-period order quantity that maximises expected profit for normally distributed demand: the critical ratio, the optimal quantity and the expected profit.

F(Q^*) = \frac{p - c}{p - s}, \quad Q^* = \mu + z\,\sigma

Inputs

p selling price per unit
c cost per unit
mu mean demand
sigma standard deviation of demand
s salvage value per unsold unit (default 0) optional

Returns

critical_ratio critical ratio (p - c)/(p - s)
Q optimal order quantity
expected_profit expected profit at Q
expected_shortage expected unmet demand at Q

Applies when

salvage < cost < price
sigma > 0
continuous normal demand

Example

m.ask("Newsvendor problem: a paper sells for 2 and costs 0.5, leftovers are sold for salvage of 0.2, and demand is normal with mean 100 and standard deviation 20. Find the optimal order quantity.")

→ critical_ratio = 0.833333, Q = 119.348, expected_profit = 141.005, expected_shortage = 1.77228

Newsvendor order quantity (uniform demand)newsvendor_uniform

The single-period order quantity that maximises expected profit when demand is uniform on [a, b].

Q^* = a + \frac{p - c}{p - s}(b - a)

Inputs

p selling price per unit
c cost per unit
lo lowest possible demand a
hi highest possible demand b
s salvage value per unsold unit (default 0) optional

Returns

critical_ratio critical ratio (p - c)/(p - s)
Q optimal order quantity a + CR (b - a)
expected_profit expected profit at Q

Applies when

salvage < cost < price
0 <= a < b

Example

m.ask("Newsvendor: an item sells for 10 and costs 4, with uniform demand between 100 and 300. Find the optimal order quantity.")

→ critical_ratio = 0.6, Q = 220, expected_profit = 960

Order quantity with quantity discounts (all-units)eoq_quantity_discount

With all-units price breaks, the order quantity that minimises purchase + ordering + holding cost, the price paid and the minimum total cost per period.

TC(Q) = D p_k + \frac{D S}{Q} + \frac{i p_k Q}{2}

Inputs

D demand per period
S cost per order
i_rate holding cost as a fraction of the unit price per period (0.2 = 20%)
breaks minimum order quantity of each price tier, increasing, the first 0 vector
prices unit price of each tier vector

Returns

order_quantity optimal order quantity
total_cost minimum total cost per period (purchase + ordering + holding)
unit_price unit price paid

Applies when

D, S, i > 0
breaks increasing from 0
ties broken toward the lower-quantity tier

Example

m.ask("Quantity discounts: annual demand 5000, ordering cost 49, holding rate 20%, price breaks at [0, 1000, 2000] with prices [5, 4.8, 4.75]. Find the best order quantity.")

→ order_quantity = 1000, total_cost = 24725, unit_price = 4.8

Periodic-review order-up-to levelorder_up_to_level

The target inventory position S of a periodic-review system that covers demand over the review period plus the lead time with a given cycle service level.

S = \bar d (R + L) + z_{SL}\,\sigma_d\sqrt{R + L}

Inputs

d average demand per period
sigma standard deviation of demand per period
R review period (periods)
L lead time (periods)
SL cycle service level, e.g. 0.95

Returns

order_up_to_level order-up-to level S
safety_stock safety stock z sigma sqrt(R + L)
z standard normal quantile

Applies when

0.5 <= SL < 1
independent normal demand per period

Example

m.ask("In a periodic review system, demand averages 20 units per day with a standard deviation of 4, the review period is 7 days, the lead time is 2 days and the service level is 95%. Find the order-up-to level.")

→ order_up_to_level = 199.738, safety_stock = 19.7382, z = 1.64485

Reorder point with safety stockreorder_point

The stock level at which to reorder so that demand during the lead time is covered with a given cycle service level, for normally distributed demand per period.

ROP = \bar d L + z_{SL}\,\sigma_d \sqrt{L}

Inputs

d average demand per period
L lead time in periods
sigma standard deviation of demand per period
SL cycle service level (probability of no stockout per cycle, e.g. 0.95)

Returns

reorder_point reorder point
safety_stock safety stock z sigma sqrt(L)
z standard normal quantile of the service level
lead_time_demand expected demand during the lead time

Applies when

0.5 <= SL < 1
independent normal demand per period

Example

m.ask("Daily demand averages 40 units with a standard deviation of 8 units, the lead time is 9 days and the service level is 95%. Find the reorder point.")

→ reorder_point = 399.476, safety_stock = 39.4765, z = 1.64485, lead_time_demand = 360

Linear programming 3

Linear program (simplex method)linear_program

Optimise a linear objective subject to linear constraints with non-negative variables: the optimal value, an optimal solution (stated as unique only when it is) and the shadow prices.

\max / \min \; c^\top x \quad \text{s.t. } A x \;(\le, \ge, =)\; b,\; x \ge 0

Inputs

sense maximize or minimize choice
c objective coefficients, one per variable vector
A constraint coefficients, one row per constraint matrix
b right-hand sides, one per constraint vector
relations relation of each constraint: <=, >= or = (default all <=) text optional

Returns

optimal_value optimal value of the objective
x the optimal solution, variables in order of first appearance (only when unique; otherwise x_one_optimal)
solution_unique yes when the optimal solution is unique
shadow_prices change of the optimal value per unit increase of each right-hand side (only when unique; otherwise dual_one_optimal)

Applies when

all variables >= 0
the LP is feasible and bounded (otherwise INVALID_INPUT says which)
at most 12 variables and constraints

Example

m.ask("Maximize 3x + 5y subject to x <= 4, 2y <= 12, 3x + 2y <= 18, x, y >= 0.")

→ optimal_value = 36, x = [2.0, 6.0], solution_unique = yes, shadow_prices = [0.0, 1.5, 1.0]

Shadow prices of a linear programlp_shadow_prices

The shadow price (dual value) of each constraint: the change of the optimal value per unit increase of its right-hand side, when it is uniquely defined.

y^\top = c_B^\top B^{-1}, \qquad \frac{\partial z^*}{\partial b_i} = y_i

Inputs

sense maximize or minimize choice
c objective coefficients, one per variable vector
A constraint coefficients, one row per constraint matrix
b right-hand sides, one per constraint vector
relations relation of each constraint: <=, >= or = (default all <=) text optional

Returns

shadow_prices shadow price of each constraint, in order
optimal_value optimal value of the objective
x the optimal solution (only when unique; otherwise x_one_optimal)
solution_unique yes when the optimal solution is unique

Applies when

all variables >= 0
a finite optimum
unique dual solution (otherwise INVALID_INPUT)

Example

m.ask("Find the shadow prices: maximize 3x + 5y subject to x <= 4, 2y <= 12, 3x + 2y <= 18, x, y >= 0.")

→ optimal_value = 36, x = [2.0, 6.0], solution_unique = yes, shadow_prices = [0.0, 1.5, 1.0]

Two-variable linear program (graphical corner-point method)lp_two_variable_graphical

Solve a linear program in two variables by evaluating the objective at every corner point of the feasible region.

z^* = \max_{v \in \text{corners}} c^\top v

Inputs

sense maximize or minimize choice
c objective coefficients, one per variable vector
A constraint coefficients, one row per constraint matrix
b right-hand sides, one per constraint vector
relations relation of each constraint: <=, >= or = (default all <=) text optional

Returns

optimal_value optimal value of the objective
x first variable at the optimum (only when the optimum is unique)
y second variable at the optimum (only when the optimum is unique)
optimal_corners every corner point at which the optimum is attained
corner_points every corner point of the feasible region
solution_unique yes when exactly one point is optimal

Applies when

exactly two variables, both >= 0
a feasible region and a finite optimum

Example

m.ask("Use the graphical method to maximize 3x + 5y subject to x <= 4, 2y <= 12, 3x + 2y <= 18, x, y >= 0.")

→ optimal_value = 36, optimal_corners = [[2.0, 6.0]], corner_points = [[0.0, 0.0], [0.0, 6.0], [2.0, 6.0], [4.0, 0.0], [4.0, 3.0]], x = 2, y = 6, solution_unique = yes

Multi-criteria decision analysis 6

AHP consistency ratioahp_consistency_ratio

How consistent a set of pairwise comparisons is: CI = (lambda_max - n)/(n - 1) and CR = CI / RI (Saaty's random index); CR below 0.10 is conventionally acceptable.

CI = \frac{\lambda_{\max} - n}{n - 1},\quad CR = \frac{CI}{RI_n}

Inputs

judgments upper-triangle pairwise judgments a12, a13, ..., a23, ... (Saaty scale; a_ji = 1/a_ij) vector

Returns

CR consistency ratio
CI consistency index
lambda_max principal eigenvalue
weights priority weights
acceptable yes when CR < 0.10

Applies when

3 to 10 criteria
RI = 0.58, 0.90, 1.12, 1.24, 1.32, 1.41, 1.45, 1.49 for n = 3..10 (Saaty)

Example

m.ask("Find the AHP consistency ratio for the pairwise judgments [2, 4, 2].")

→ CR = 0, CI = 0, lambda_max = 3, weights = [0.5714285714285714, 0.2857142857142857, 0.14285714285714285], acceptable = yes

AHP priority vector (principal eigenvector)ahp_priority_vector

The priority weights of criteria compared in pairs (analytic hierarchy process): the normalised principal eigenvector of the reciprocal comparison matrix, and its eigenvalue lambda_max.

P w = \lambda_{\max} w,\quad \sum_i w_i = 1

Inputs

judgments upper-triangle pairwise judgments a12, a13, ..., a23, ... (Saaty scale; a_ji = 1/a_ij) vector

Returns

weights priority weights (sum 1)
lambda_max principal eigenvalue
best highest-priority criterion, 1-based

Applies when

judgments > 0
2 to 10 criteria

Example

m.ask("Find the AHP priority vector for the pairwise judgments [2, 4, 2].")

→ weights = [0.5714285714285714, 0.2857142857142857, 0.14285714285714285], lambda_max = 3, best = 1

AHP weights by the geometric mean methodahp_geometric_mean

Priority weights from pairwise comparisons as normalised row geometric means (the logarithmic least-squares solution).

w_i = \frac{(\prod_j a_{ij})^{1/n}}{\sum_k (\prod_j a_{kj})^{1/n}}

Inputs

judgments upper-triangle pairwise judgments a12, a13, ..., a23, ... (Saaty scale; a_ji = 1/a_ij) vector

Returns

weights priority weights (sum 1)
max_weight largest weight
best highest-priority criterion, 1-based

Applies when

judgments > 0
2 to 10 criteria

Example

m.ask("Find the AHP weights by the geometric mean method for the pairwise judgments [2, 4, 2].")

→ weights = [0.5714285714285714, 0.2857142857142857, 0.14285714285714285], max_weight = 0.571429, best = 1

TOPSIS ranking (closeness to the ideal solution)topsis

Rank alternatives scored on several criteria by their relative closeness to the ideal and distance from the anti-ideal solution (vector normalisation, weighted Euclidean distances).

C_i = \frac{D_i^-}{D_i^+ + D_i^-},\quad D_i^\pm = \Big\| w \odot r_i - v^\pm \Big\|_2

Inputs

X decision matrix, rows = alternatives, columns = criteria (all values > 0) matrix
w criterion weights (> 0; normalised to sum 1) vector
types criterion types: 1 = benefit (larger is better), -1 = cost (smaller is better) vector

Returns

scores score of each alternative
best_score the highest score
best best alternative, 1-based (on a tie the first listed)

Applies when

values > 0
weights > 0 (normalised to sum 1)
types 1 or -1

Example

m.ask("Rank with TOPSIS the alternatives with decision matrix [[1, 1], [2, 2]], weights [1, 1] and criteria types [1, 1].")

→ scores = [0.0, 1.0], best_score = 1, best = 2

Weighted product modelweighted_product_model

Score alternatives by the product of linearly normalised criterion values raised to the criterion weights.

P_i = \prod_j n_{ij}^{\,w_j}

Inputs

X decision matrix, rows = alternatives, columns = criteria (all values > 0) matrix
w criterion weights (> 0; normalised to sum 1) vector
types criterion types: 1 = benefit (larger is better), -1 = cost (smaller is better) vector

Returns

scores score of each alternative
best_score the highest score
best best alternative, 1-based (on a tie the first listed)

Applies when

values > 0
weights > 0 (normalised to sum 1)
types 1 or -1

Example

m.ask("Score with the weighted product model the alternatives with decision matrix [[4, 2], [2, 4]], weights [0.5, 0.5] and criteria types [1, 1].")

→ scores = [0.7071067811865476, 0.7071067811865476], best_score = 0.707107, best = 1

Weighted sum model (simple additive weighting)weighted_sum_model

Score alternatives by the weighted sum of linearly normalised criterion values (benefit x / max, cost min / x) and pick the best.

S_i = \sum_j w_j n_{ij},\quad n_{ij} = \frac{x_{ij}}{\max_i x_{ij}}\ \text{or}\ \frac{\min_i x_{ij}}{x_{ij}}

Inputs

X decision matrix, rows = alternatives, columns = criteria (all values > 0) matrix
w criterion weights (> 0; normalised to sum 1) vector
types criterion types: 1 = benefit (larger is better), -1 = cost (smaller is better) vector

Returns

scores score of each alternative
best_score the highest score
best best alternative, 1-based (on a tie the first listed)

Applies when

values > 0
weights > 0 (normalised to sum 1)
types 1 or -1

Example

m.ask("Score with the weighted sum model the alternatives with decision matrix [[250, 16, 12], [200, 16, 8], [300, 32, 16]], weights [0.4, 0.3, 0.3] and criteria types [-1, 1, 1].")

→ scores = [0.6950000000000001, 0.7, 0.8666666666666667], best_score = 0.866667, best = 3

Network optimisation 12

All-pairs shortest distances (Floyd-Warshall)all_pairs_shortest_paths

The table of shortest distances between every pair of nodes, and the graph's diameter.

d_{ij} \leftarrow \min(d_{ij},\, d_{ik} + d_{kj})

Inputs

edges weighted edges 'A-B 4, ...' edges
directed true for a directed graph, false for undirected boolean

Returns

distances shortest-distance matrix (rows and columns in the order of 'nodes')
nodes node order (first appearance)
diameter largest shortest distance

Applies when

every node reaches every other
no negative cycle
at most 40 nodes

Example

m.ask("Find the all-pairs shortest distances in the undirected graph with edges A-B 3, B-C 4, A-C 9, C-D 2.")

→ nodes = ['A', 'B', 'C', 'D'], distances = [[0.0, 3.0, 7.0, 9.0], [3.0, 0.0, 4.0, 6.0], [7.0, 4.0, 0.0, 2.0], [9.0, 6.0, 2.0, 0.0]], diameter = 9

Assignment problem (Hungarian method), maximum total valueassignment_max_profit

Assign each row (worker) to a different column (task) so that the total value is as large as possible: the optimum and an optimal assignment (stated as THE assignment only when unique).

\min_{\sigma} \sum_i c_{i\sigma(i)} = \max \Big\{ \sum_i u_i + \sum_j v_j : u_i + v_j \le c_{ij} \Big\}

Inputs

C value matrix, rows = workers, columns = tasks (square) matrix

Returns

max_value optimal total value
assignment column assigned to each row, 1-based (only when unique; otherwise assignment_example)
assignment_unique yes when the optimal assignment is unique
dual_u row potentials
dual_v column potentials (u_i + v_j bounds every cell: the optimality certificate)

Applies when

square matrix, at most 12 x 12 (pad with zeros for unbalanced problems)

Example

m.ask("Solve the assignment problem to maximize total profit with matrix [[9, 2, 7], [6, 4, 3], [5, 8, 1]].")

→ max_value = 21, assignment = [3, 1, 2], assignment_unique = yes, dual_u = [7.0, 4.0, 8.0], dual_v = [2.0, 0.0, 0.0]

Assignment problem (Hungarian method), minimum total costassignment_min_cost

Assign each row (worker) to a different column (task) so that the total cost is as small as possible: the optimum and an optimal assignment (stated as THE assignment only when unique).

\min_{\sigma} \sum_i c_{i\sigma(i)} = \max \Big\{ \sum_i u_i + \sum_j v_j : u_i + v_j \le c_{ij} \Big\}

Inputs

C cost matrix, rows = workers, columns = tasks (square) matrix

Returns

min_cost optimal total cost
assignment column assigned to each row, 1-based (only when unique; otherwise assignment_example)
assignment_unique yes when the optimal assignment is unique
dual_u row potentials
dual_v column potentials (u_i + v_j bounds every cell: the optimality certificate)

Applies when

square matrix, at most 12 x 12 (pad with zeros for unbalanced problems)

Example

m.ask("Solve the assignment problem with cost matrix [[9, 2, 7], [6, 4, 3], [5, 8, 1]].")

→ min_cost = 9, assignment = [2, 1, 3], assignment_unique = yes, dual_u = [4.0, 6.0, 4.0], dual_v = [0.0, -2.0, -3.0]

Maximum bipartite matchingbipartite_matching

The largest number of pairs that can be formed between two groups (workers and jobs, students and projects) using only allowed pairs, with one maximum matching and a vertex cover proving it maximum.

\nu(G) = \tau(G) \text{ for bipartite } G

Inputs

edges allowed pairs 'left-right', e.g. 'W1-J1, W1-J2, W2-J1' edges

Returns

max_matching size of a maximum matching
matching_example one maximum matching
vertex_cover a minimum vertex cover of the same size (Konig's theorem: the certificate)

Applies when

bipartite: the first node of each pair is on the left, the second on the right

Example

m.ask("Find the maximum bipartite matching with edges W1-J1, W1-J2, W2-J1, W3-J2, W3-J3.")

→ max_matching = 3, matching_example = ['W1-J2', 'W2-J1', 'W3-J3'], vertex_cover = ['W1', 'W2', 'W3']

Maximum flow and minimum cut (Edmonds-Karp)max_flow

The largest flow that can be sent from a source to a sink through a network of capacitated arcs, a flow achieving it and the minimum cut that proves it optimal.

\max |f| = \min_{(S, \bar S)} c(S, \bar S)

Inputs

edges directed arcs with capacities 'S-A 10, A-T 5, ...' edges
source source node text
target sink node text

Returns

max_flow maximum flow value
min_cut_source_side nodes on the source side of a minimum cut (those reachable in the final residual network)
edge_flows flow on each arc, in input order (one maximum flow)

Applies when

directed arcs
capacities >= 0

Example

m.ask("Find the maximum flow from S to T in the network with edges S-A 10, S-B 5, A-B 15, A-T 5, B-T 10.")

→ max_flow = 15, min_cut_source_side = ['S'], edge_flows = [10.0, 5.0, 5.0, 5.0, 10.0]

Maximum-weight matching (general graph)max_weight_matching

Pair up nodes of a graph (each node at most once) so that the total weight of the chosen edges is as large as possible: the maximum weight and one optimal matching.

\max_{M \text{ matching}} \sum_{e \in M} w_e

Inputs

edges undirected weighted edges 'A-B 4, ...' edges

Returns

max_weight maximum total weight of a matching
matching_example one maximum-weight matching

Applies when

at most 16 nodes
edges of weight <= 0 are never worth choosing

Example

m.ask("Find the maximum weight matching of the graph with edges A-B 6, B-C 5, C-D 6, A-D 2, A-C 4.")

→ max_weight = 12, matching_example = ['A-B', 'C-D']

Minimum spanning tree (Kruskal's algorithm)minimum_spanning_tree

The least total weight of edges connecting all nodes of an undirected graph, and the tree (stated as THE tree only when the minimum spanning tree is unique).

\min_{T \text{ spanning tree}} \sum_{e \in T} w_e

Inputs

edges undirected weighted edges 'A-B 4, ...' edges

Returns

total_weight weight of a minimum spanning tree
tree_edges the minimum spanning tree (only when unique; otherwise tree_edges_example)
tree_unique yes when the minimum spanning tree is unique

Applies when

connected undirected graph

Example

m.ask("Find the minimum spanning tree of the graph with edges A-B 4, A-C 1, B-C 2, B-D 5, C-D 8.")

→ total_weight = 8, tree_unique = yes, tree_edges = ['A-C', 'B-C', 'B-D']

Minimum-cost flow (transshipment)min_cost_flow

Send flow from supply nodes to demand nodes through capacitated arcs at least total cost (transshipment allowed): the minimum cost and a flow achieving it.

\min \sum c_{ij} x_{ij}\ \text{s.t.}\ \sum_j x_{vj} - \sum_i x_{iv} = b_v,\ 0 \le x_{ij} \le u_{ij}

Inputs

capacity arc capacities, n x n (row = from node, column = to node, 0 = no arc) matrix
cost unit cost of each arc, n x n matrix
supply net supply of each node (positive = supply, negative = demand), summing to 0 vector

Returns

min_cost minimum total cost
flows optimal flow matrix (only when unique; otherwise flows_example)
flow_unique yes when the optimal flow is unique
dual dual values: node potentials then arc-capacity prices

Applies when

supplies sum to 0
a feasible flow exists
at most 60 arcs

Example

m.ask("Find the minimum cost flow with capacity [[0, 10, 5], [0, 0, 10], [0, 0, 0]], cost [[0, 1, 4], [0, 0, 2], [0, 0, 0]] and supply [8, 0, -8].")

→ min_cost = 24, flows = [[0.0, 8.0, 0.0], [0.0, 0.0, 8.0], [0.0, 0.0, 0.0]], flow_unique = yes, dual = [3.0, 2.0, 0.0, 0.0, 0.0, 0.0]

Shortest path (Dijkstra's algorithm)shortest_path

The length of the shortest route between two nodes of a graph with non-negative edge weights, and the route itself (stated as the route only when it is the only shortest one).

d(v) = \min_{(u,v)} \big(d(u) + w_{uv}\big)

Inputs

edges weighted edges 'A-B 4, B-C 1, ...' edges
source start node text
target end node text
directed true for a directed graph (edge u-v goes from u to v), false for undirected boolean

Returns

distance shortest distance
path the shortest path (only when unique; otherwise path_example)
path_unique yes when exactly one shortest path exists

Applies when

weights >= 0
a path from source to target exists
parallel edges: the lightest counts

Example

m.ask("Find the shortest path from A to D in the undirected graph with edges A-B 4, A-C 2, B-C 1, B-D 5, C-D 8.")

→ distance = 8, path = ['A', 'C', 'B', 'D'], path_unique = yes

Shortest path with negative weights (Bellman-Ford)bellman_ford_shortest_path

Shortest distance in a directed graph whose edge weights may be negative, with all distances from the source; a negative cycle reachable from the source is reported instead of a number.

d(v) \le d(u) + w_{uv} \ \forall (u,v)

Inputs

edges directed weighted edges 'A-B 4, B-C -2, ...' edges
source start node text
target end node text

Returns

distance shortest distance from source to target
distances_from_source shortest distance to every reachable node

Applies when

directed graph
no negative cycle reachable from the source (otherwise INVALID_INPUT)

Example

m.ask("With negative weights allowed, find the shortest path from S to T in the directed graph with edges S-A 4, S-B 5, A-T 3, B-A -3, B-T 6.")

→ distance = 5, distances_from_source = {'S': 0.0, 'A': 2.0, 'B': 5.0, 'T': 5.0}

Transportation problem (minimum shipping cost)transportation_problem

Ship from sources with given supplies to destinations with given demands at least total cost: the minimum cost and a shipping plan (stated as THE plan only when it is unique).

\min \sum_{ij} c_{ij} x_{ij}\ \text{s.t.}\ \sum_j x_{ij} \le s_i,\ \sum_i x_{ij} = d_j,\ x \ge 0

Inputs

supply supply of each source vector
demand demand of each destination vector
cost unit shipping cost, rows = sources, columns = destinations matrix

Returns

min_cost minimum total shipping cost
shipments optimal plan, rows = sources (only when unique; otherwise shipments_example)
plan_unique yes when the optimal plan is unique
dual dual values (u for sources, v for destinations): the optimality certificate

Applies when

total supply >= total demand (surplus stays at the sources at no cost)
at most 60 routes

Example

m.ask("Solve the transportation problem with supply [20, 30], demand [10, 25, 15] and cost matrix [[2, 3, 1], [5, 4, 8]].")

→ min_cost = 150, shipments = [[5.0, 0.0, 15.0], [5.0, 25.0, 0.0]], plan_unique = yes, dual = [-3.0, 0.0, 5.0, 4.0, 4.0]

Travelling salesman tour (exact, Held-Karp)traveling_salesman

The shortest round trip visiting every city exactly once and returning to the start, for a distance matrix (symmetric or not): the minimum tour length and one optimal tour.

g(S, k) = \min_{m \in S \setminus \{k\}} \big(g(S \setminus \{k\}, m) + d_{mk}\big)

Inputs

D distance matrix, D[i][j] = distance from city i to city j matrix

Returns

min_tour_length length of a shortest tour
tour_example one optimal tour starting and ending at city 1

Applies when

2 to 11 cities

Example

m.ask("Solve the travelling salesman problem with distance matrix [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]].")

→ min_tour_length = 80, tour_example = [1, 3, 4, 2, 1]

Nonlinear optimisation 3

Equality-constrained quadratic program (Lagrange multipliers / KKT)equality_constrained_qp

Minimise 1/2 x^T Q x + c^T x subject to A x = b: the minimiser, the minimum and the Lagrange multipliers.

\begin{bmatrix} Q & A^\top \\ A & 0 \end{bmatrix}\begin{bmatrix} x \\ \lambda \end{bmatrix} = \begin{bmatrix} -c \\ b \end{bmatrix}

Inputs

Q symmetric positive definite Hessian Q matrix
c linear term c vector
A constraint matrix A (rows = constraints) matrix
b right-hand side b vector

Returns

f_min minimum value
x_star the minimiser (unique)
multipliers Lagrange multipliers lambda (convention Q x + c + A^T lambda = 0)

Applies when

Q symmetric positive definite
rows of A linearly independent

Example

m.ask("Minimise the equality-constrained quadratic with Hessian Q = [[2, 0], [0, 2]], linear term c = [0, 0], constraint matrix A = [[1, 1]] and right-hand side b = [2].")

→ f_min = 2, x_star = [1.0, 1.0], multipliers = [-2.0]

Steepest descent step with exact line search (quadratic)steepest_descent_step

One iteration of steepest descent on f(x) = 1/2 x^T Q x + c^T x from x0: the gradient, the exact step length, the new point and its function value.

\alpha = \frac{g^\top g}{g^\top Q g},\quad x_1 = x_0 - \alpha g

Inputs

Q symmetric positive definite Hessian Q matrix
c linear term c vector
x0 starting point x0 vector

Returns

alpha exact step length g^T g / g^T Q g
x1 new point x0 - alpha g
f1 f at the new point
gradient gradient at x0

Applies when

Q symmetric positive definite
x0 is not the minimiser

Example

m.ask("Take one steepest descent step with exact line search for Hessian Q = [[2, 0], [0, 8]] and linear term c = [0, 0] from x0 = [4, 1].")

→ alpha = 0.2, x1 = [2.4, -0.6], f1 = 7.2, gradient = [8.0, 8.0]

Unconstrained quadratic minimisationunconstrained_quadratic_min

Minimise f(x) = 1/2 x^T Q x + c^T x for a symmetric positive definite Q: the minimiser and the minimum.

x^* = -Q^{-1} c,\quad f^* = \tfrac12 c^\top x^*

Inputs

Q symmetric positive definite Hessian Q (n x n) matrix
c linear term c (n entries) vector

Returns

f_min minimum value
x_star the minimiser x* = -Q^{-1} c (unique)

Applies when

Q symmetric positive definite (convention: f = 1/2 x^T Q x + c^T x)
n <= 10

Example

m.ask("Minimise the unconstrained quadratic with Hessian Q = [[4, 1], [1, 3]] and linear term c = [-1, -2].")

→ f_min = -0.681818, x_star = [0.09090909090909091, 0.6363636363636364]

Project scheduling 2

Critical path method (project duration and slack)critical_path_method

For activities with durations and precedences, the minimum project duration, the critical activities and each activity's earliest start, latest start and slack (total float).

ES_k = \max_{j \to k}(ES_j + d_j),\quad LS_k = \min_{k \to s} LS_s - d_k,\quad \text{slack}_k = LS_k - ES_k

Inputs

durations duration of each activity; activities are named A, B, C, ... (or 1, 2, 3, ...) in this order vector
precedences precedence pairs 'A-B' meaning A must finish before B starts (none if omitted) edges optional

Returns

project_duration minimum project duration
critical_activities activities with zero slack
slack total slack of each activity
earliest_start earliest start of each activity
latest_start latest start of each activity

Applies when

finish-to-start precedences without cycles
deterministic durations

Example

m.ask("Activities A, B, C, D have durations [3, 4, 2, 5]; precedences: A-B, A-C, B-D, C-D. Find the critical path and the project duration.")

→ project_duration = 12, critical_activities = ['A', 'B', 'D'], slack = [0.0, 0.0, 2.0, 0.0], earliest_start = [0.0, 3.0, 3.0, 7.0], latest_start = [0.0, 3.0, 5.0, 7.0]

PERT project duration and completion probabilitypert_project

With optimistic, most likely and pessimistic times per activity, the expected project duration, its variance along the critical path and the probability of finishing by a deadline (normal approximation).

t_e = \frac{a + 4m + b}{6},\; \sigma^2 = \left(\frac{b - a}{6}\right)^2,\; P(T \le d) = \Phi\!\left(\frac{d - \mu}{\sigma}\right)

Inputs

times rows (optimistic, most likely, pessimistic), one per activity A, B, C, ... matrix
precedences precedence pairs 'A-B' (A before B) edges optional
deadline deadline for the completion probability (optional) optional

Returns

expected_duration expected project duration
variance variance of the critical path
std_dev standard deviation
critical_path the critical path (must be unique)
expected_times expected time of each activity (a + 4m + b)/6
probability probability of completion by the deadline

Applies when

a unique critical path (otherwise INVALID_INPUT)
independent activity times; normal approximation

Example

m.ask("PERT: activities A, B, C have times [[2, 4, 6], [3, 5, 13], [1, 2, 3]]; precedences: A-B, A-C. Find the expected project duration.")

→ expected_duration = 10, variance = 3.22222, std_dev = 1.79505, critical_path = ['A', 'B'], expected_times = [4.0, 6.0, 2.0]

Queueing theory 7

Erlang B blocking probability (M/M/c/c loss system)erlang_b

The probability that a call (customer) is blocked in a loss system with c servers and no waiting room, for an offered traffic of A erlangs, with the carried and lost traffic.

B(c, A) = \frac{A^c / c!}{\sum_{k=0}^{c} A^k / k!}

Inputs

A offered traffic in erlangs (arrival rate x mean holding time)
c number of servers (lines, trunks) integer

Returns

blocking_probability Erlang B blocking probability
carried_traffic carried traffic A (1 - B), erlangs
lost_traffic lost traffic A B, erlangs

Applies when

blocked customers are lost (no waiting)
A > 0

Example

m.ask("A trunk group of 5 lines is offered traffic of 3 erlangs. What is the Erlang B blocking probability?")

→ blocking_probability = 0.110054, carried_traffic = 2.66984, lost_traffic = 0.330163

M/G/1 queue (Pollaczek-Khinchine formula)mg1_pollaczek_khinchine

Mean queue length and waiting times of a single-server queue with Poisson arrivals and a GENERAL service time distribution given by its mean and standard deviation (M/D/1 when the standard deviation is 0).

L_q = \frac{\lambda^2 \sigma_S^2 + \rho^2}{2(1-\rho)}

Inputs

lam arrival rate
ES mean service time (time unit of 1/lambda)
sd standard deviation of the service time

Returns

rho utilisation lambda E[S]
Lq mean number waiting
L mean number in the system
Wq mean waiting time
W mean time in the system

Applies when

lambda E[S] < 1
Poisson arrivals, one server, first come first served

Example

m.ask("In an M/G/1 queue the arrival rate is 0.5 per minute, the mean service time is 1 minute and its standard deviation is 1 minute. Find Lq.")

→ rho = 0.5, Lq = 0.5, L = 1, Wq = 1, W = 2

M/M/1 queuemm1_queue

Steady-state measures of a single-server queue with Poisson arrivals and exponential service: utilisation, mean numbers in system and in queue, mean times in system and in queue, probability of an empty system.

L = \frac{\rho}{1-\rho},\; W = \frac{1}{\mu - \lambda},\; W_q = \frac{\rho}{\mu-\lambda}

Inputs

lam arrival rate (customers per unit time)
mu service rate (customers per unit time)

Returns

rho utilisation lambda/mu
L mean number in the system
Lq mean number waiting
W mean time in the system (time unit of the rates)
Wq mean waiting time in the queue
P0 probability the system is empty

Applies when

lambda < mu (stable)
Poisson arrivals, exponential service, one server, unlimited capacity

Example

m.ask("In an M/M/1 queue customers arrive at 8 per hour and are served at 10 per hour. Find L, Lq, W and Wq.")

→ rho = 0.8, L = 4, Lq = 3.2, W = 0.5, Wq = 0.4, P0 = 0.2

M/M/c queue (Erlang C)mmc_queue

Steady-state measures of a queue with c parallel identical servers, Poisson arrivals and exponential service: probability of waiting (Erlang C), mean queue length and waiting times.

C(c, a) = \frac{B(c,a)}{1 - \rho(1 - B(c,a))}, \quad L_q = C\,\frac{\rho}{1-\rho}

Inputs

lam arrival rate
mu service rate of each server
c number of servers integer

Returns

rho utilisation lambda/(c mu)
P_wait probability an arrival waits (Erlang C)
Lq mean number waiting
Wq mean waiting time
W mean time in the system
L mean number in the system
P0 probability the system is empty

Applies when

lambda < c mu (stable)
unlimited queue capacity

Example

m.ask("Customers arrive at 24 per hour at a bank with 3 tellers; each teller serves 10 per hour. Find the probability of waiting and Lq for this M/M/c queue.")

→ rho = 0.8, P_wait = 0.647191, Lq = 2.58876, Wq = 0.107865, W = 0.207865, L = 4.98876, P0 = 0.0561798

M/M/c/K queue (finite capacity)mmck_finite_queue

Steady-state measures of a queue with c servers and room for at most K customers in the system (arrivals finding it full are lost): blocking probability, effective arrival rate, mean numbers and times.

\pi_n \propto \frac{a^n}{n!}\ (n \le c),\quad \frac{a^c}{c!}\left(\frac{a}{c}\right)^{n-c}\ (c < n \le K)

Inputs

lam arrival rate
mu service rate of each server
c number of servers integer
K system capacity (customers in service plus waiting) integer

Returns

P_block probability an arrival is lost (system full)
lam_eff effective arrival rate
L mean number in the system
Lq mean number waiting
W mean time in the system
Wq mean waiting time
P0 probability the system is empty

Applies when

1 <= c <= K
any utilisation (finite capacity is always stable)

Example

m.ask("An M/M/1/3 queue has arrival rate 2 per hour and service rate 2 per hour. Find the blocking probability and L.")

→ P_block = 0.25, lam_eff = 1.5, L = 1.5, Lq = 0.75, W = 1, Wq = 0.5, P0 = 0.25

Machine-repair (finite-source) queuemachine_repair_queue

N machines each fail at rate lambda while running and c repairers fix them at rate mu each: mean number of machines down and waiting, failure rate, downtime and the mean number working.

\pi_n \propto \frac{N!}{(N-n)!}\,\frac{(\lambda/\mu)^n}{n!\ \text{or}\ c!\,c^{n-c}}

Inputs

N number of machines integer
lam failure rate of one running machine
mu repair rate of one repairer
c number of repairers (default 1) integer optional

Returns

L mean number of machines down
Lq mean number waiting for repair
lam_eff mean failure rate lambda (N - L)
W mean downtime per failure
Wq mean wait for a repairer
P0 probability all machines run
working mean number running

Applies when

1 <= c <= N
exponential failure and repair times

Example

m.ask("There are 5 machines; each machine breaks down at a rate of 0.2 per hour and one repairer repairs at a rate of 1 per hour. Find the mean number of machines down.")

→ L = 1.42434, Lq = 0.709207, lam_eff = 0.715132, W = 1.99171, Wq = 0.991714, P0 = 0.284868, working = 3.57566

Minimum number of servers for a service target (Erlang C)mmc_staffing

The smallest number of servers c of an M/M/c queue for which the probability of waiting, or the mean waiting time, meets a target.

c^* = \min\{c > \lambda/\mu : C(c, \lambda/\mu) \le \alpha\}

Inputs

lam arrival rate
mu service rate of each server
target target value (a probability, or a mean wait in the time unit of the rates)
criterion wait_probability (default) or mean_wait choice optional

Returns

servers minimum number of servers
P_wait probability of waiting with that many servers
Wq mean waiting time with that many servers
utilisation server utilisation

Applies when

Poisson arrivals, exponential service
target > 0

Example

m.ask("Calls arrive at 24 per hour and each agent serves 10 per hour. How many agents are needed so that the probability of waiting is at most 0.2?")

→ servers = 5, P_wait = 0.113504, Wq = 0.00436553, utilisation = 0.48

Revenue management 1

Littlewood's rule (two-fare protection level)littlewood_protection

How many seats (units) to protect for full-fare demand when a discount fare is also sold: the protection level and, with a capacity, the booking limit for the discount class.

P(D_1 > y^*) = \frac{p_2}{p_1}, \quad y^* = \mu + z\,\sigma

Inputs

p1 full fare
p2 discount fare
mu mean full-fare demand
sigma standard deviation of full-fare demand
capacity total capacity (optional) optional

Returns

protection_level units protected for full-fare demand
z standard normal quantile of 1 - p2/p1
booking_limit discount booking limit = capacity - protection (when a capacity is given)

Applies when

0 < p2 < p1
normally distributed full-fare demand
continuous approximation (no rounding)

Example

m.ask("Littlewood's rule: the full fare is 400 and the discount fare is 150; full-fare demand has mean 60 and standard deviation 20. Find the protection level.")

→ protection_level = 66.3728, z = 0.318639

Scheduling 6

Earliest due date rule (minimum maximum lateness)edd_max_lateness

The job order that minimises the maximum lateness (and so the maximum tardiness) on one machine.

\min L_{\max} = \min \max_j (C_j - d_j):\; d_{[1]} \le d_{[2]} \le \dots

Inputs

p processing time of each job vector
d due date of each job vector

Returns

max_lateness minimum possible maximum lateness
max_tardiness minimum possible maximum tardiness
sequence optimal order (earliest due date first; ties in job-number order)
tardy_jobs_in_sequence number of late jobs in this sequence (not minimised)

Applies when

all jobs available at time 0

Example

m.ask("Jobs have processing times [2, 4, 1, 3] and due dates [5, 6, 3, 9]. Find the sequence that minimizes the maximum lateness.")

→ sequence = [3, 1, 2, 4], max_lateness = 1, max_tardiness = 1, tardy_jobs_in_sequence = 2

Johnson's rule (two-machine flow shop)johnson_two_machine

The job order that minimises the makespan when every job is processed first on machine 1 and then on machine 2.

\min C_{\max} \text{ for } F2 \| C_{\max}

Inputs

a processing time of each job on machine 1 vector
b processing time of each job on machine 2 vector

Returns

makespan minimum makespan
sequence Johnson order (a < b by increasing a, then the rest by decreasing b; ties by job number)

Applies when

same job order on both machines
all jobs available at time 0

Example

m.ask("Use Johnson's rule: machine 1 times [5, 2, 6, 7] and machine 2 times [3, 4, 8, 2]. Find the minimum makespan.")

→ makespan = 22, sequence = [2, 3, 1, 4]

Minimum makespan on identical parallel machinesparallel_machine_makespan

Assign jobs to m identical machines so that the last machine finishes as early as possible (P||Cmax), exactly.

\min_{\text{assignment}} \max_k \sum_{j \to k} p_j

Inputs

p processing time of each job vector
m number of identical machines integer

Returns

makespan minimum makespan
machine_of_job one optimal assignment: machine number of each job
lower_bound the bound max(longest job, total / m)

Applies when

at most 12 jobs and 6 machines
jobs are not split

Example

m.ask("Jobs with processing times [7, 5, 4, 3, 3, 2] are scheduled on 2 identical machines. Find the minimum makespan.")

→ makespan = 12, machine_of_job = [1, 2, 2, 1, 2, 1], lower_bound = 12

Moore-Hodgson algorithm (minimum number of tardy jobs)moore_hodgson_tardy_jobs

The smallest possible number of late jobs on one machine, with an order of the on-time jobs and the set of late jobs.

\min \sum_j U_j

Inputs

p processing time of each job vector
d due date of each job vector

Returns

min_tardy_jobs minimum number of tardy jobs
on_time_sequence on-time jobs in due-date order
tardy_jobs jobs scheduled late (one optimal choice: the longest job removed, ties the higher job number)

Applies when

all jobs available at time 0

Example

m.ask("Jobs have processing times [4, 3, 2, 5, 6] and due dates [5, 6, 8, 12, 15]. Find the minimum number of tardy jobs.")

→ min_tardy_jobs = 2, on_time_sequence = [2, 3, 4], tardy_jobs = [1, 5]

Shortest processing time rule (minimum mean flow time)spt_mean_flow_time

The job order that minimises the mean flow (completion) time on one machine, and that minimum.

\min \tfrac{1}{n}\sum_j C_j:\; p_{[1]} \le p_{[2]} \le \dots

Inputs

p processing time of each job (jobs numbered 1, 2, ...) vector

Returns

mean_flow_time minimum mean completion time
total_completion_time minimum total completion time
sequence optimal job order (shortest first; equal times in job-number order)

Applies when

all jobs available at time 0
processing times >= 0

Example

m.ask("Jobs with processing times [4, 2, 6, 3] are done on one machine. Find the sequence that minimizes the mean flow time.")

→ sequence = [2, 4, 1, 3], total_completion_time = 31, mean_flow_time = 7.75

Weighted shortest processing time (Smith's rule)wspt_weighted_completion

The job order that minimises the total weighted completion time on one machine, and that minimum.

\min \sum_j w_j C_j:\; \frac{p_{[1]}}{w_{[1]}} \le \frac{p_{[2]}}{w_{[2]}} \le \dots

Inputs

p processing time of each job vector
w weight (importance) of each job vector

Returns

weighted_completion_time minimum total weighted completion time
sequence optimal order (ratio p/w ascending; ties in job-number order)

Applies when

weights > 0
all jobs available at time 0

Example

m.ask("Jobs have processing times [3, 1, 4] and weights [1, 2, 3]. Find the sequence minimizing the total weighted completion time.")

→ sequence = [2, 3, 1], weighted_completion_time = 25

Unconstrained optimisation 1

Optimum of a quadratic functionquadratic_optimum

The minimum or maximum of f(x) = a x^2 + b x + c: where it occurs and its value.

x^* = -\frac{b}{2a}, \quad f^* = c - \frac{b^2}{4a}

Inputs

a coefficient of x^2
b coefficient of x
c constant term
goal minimum, maximum or optimum (default optimum) choice optional

Returns

x_opt x at the optimum
f_opt optimal value f(x*)
type minimum (a > 0) or maximum (a < 0)

Applies when

a != 0
a minimum asked needs a > 0, a maximum a < 0

Example

m.ask("Find the minimum of f(x) = 2x^2 - 8x + 3.")

→ x_opt = 2, f_opt = -5, type = minimum

Versions & files

Releases and repository files

Files

15 files, 35.3 MB in total. The largest:

File	Size
model.safetensors	18.9 MB
dist/optimization_ai999x-1.0.0-py3-none-any.whl	8.2 MB
onnx/search/encoder.int8.onnx	4.9 MB
docs/optimization_ai999x_capabilities.pdf	2.4 MB
onnx/search/index.json	403.3 KB
docs/optimization_ai999x_capabilities.html	199.9 KB
onnx/search/tokenizer.json	176.4 KB
docs/optimization_ai999x_capabilities.md	148.9 KB
README.md	20.8 KB
LICENSE	11.4 KB
evaluation/release_gate.md	2.3 KB
evaluation/KNOWLEDGE_CARD.md	1.4 KB

Browse every file ↗

Questions

Frequently asked

What does optimization-ai999x do?

Optimization answers questions in optimization: linear and integer programming, convex and nonlinear optimisation, assignment, transportation and shortest-route problems, scheduling, inventory, queueing, game theory and multi-criteria decisions. Each answer gives the value with its unit, the steps and the formula in LaTeX.

How do I install optimization-ai999x?

With pip: pip install optimization-ai999x. The same files are on Hugging Face (hf download AI999X/optimization-ai999x --local-dir optimization-ai999x) and GitHub.

Does it run offline?

Yes. It is a Python package that runs on an ordinary CPU without a network connection (Python >=3.10); no GPU and no API key are needed.

How many capabilities does optimization-ai999x have?

72 capabilities in 16 topics, including Network optimisation, Inventory management, Integer programming, Queueing theory, Multi-criteria decision analysis.

Which field and tasks does it cover?

Field: Mathematics & Statistics. Tasks: Question Answering, Sentence Similarity, Feature Extraction.

What does an answer look like?

Asked "Solve the transportation problem with supply [20, 30], demand [10, 25, 15] and cost matrix [[2, 3, 1], [5, 4, 8]].", it answers: min_cost = 150, shipments = [[5.0, 0.0, 15.0], [5.0, 25.0, 0.0]], plan_unique = yes, dual = [-3.0, 0.0, 5.0, 4.0, 4.0].

What happens when a question cannot be answered?

It says so and names what is missing or out of range, instead of guessing a number.

Explore every model.

More in Mathematics & Statistics All models Capability orb