This post introduces basic linear optimizaiton through the example of TopBrass.

TopBrass #

Top Brass Trophy Company makes large championship trophies for youth athletic leagues. At the moment, they are planning production for fall sports: football and soccer. Each football trophy has a wood base, an engraved plaque, a large brass football on top, and returns 12 USD in profit.

Soccer trophies are similar except that a brass soccer ball is on top, and the unit profit is 9 USD.

Since the football has an asymmetric shape, its base requires 4 board feet of wood; the soccer base requires only 2 board feet.

There are 1000 brass footballs in stock, 1500 soccer balls, 1750 plaques, and 4800 board feet of wood. What trophies should be produced from these supplies to maximize total profit assuming that all that are made can be sold?

using HiGHS, JuMP

m = Model(HiGHS.Optimizer)

@variable(m, 0<= f <= 1000)
@variable(m, 0<= s <= 1500)
@objective(m, Max, 12*f + 9*s)
@constraint(m, 4*f + 2*s <= 4800) # board feet of wood
@constraint(m, f + s <= 1750)

$$ f + s \leq 1750.0 $$

print(m)

$$ \begin{aligned} \max\quad & 12 f + 9 s\\ \text{Subject to} \quad & 4 f + 2 s \leq 4800.0\\ & f + s \leq 1750.0\\ & f \geq 0.0\\ & s \geq 0.0\\ & f \leq 1000.0\\ & s \leq 1500.0\\ \end{aligned} $$

println(m)

Max 12 f + 9 s
Subject to
 4 f + 2 s ≤ 4800.0
 f + s ≤ 1750.0
 f ≥ 0.0
 s ≥ 0.0
 f ≤ 1000.0
 s ≤ 1500.0

optimize!(m)

Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
2 rows, 2 cols, 4 nonzeros
2 rows, 2 cols, 4 nonzeros
Presolve : Reductions: rows 2(-0); columns 2(-0); elements 4(-0) - Not reduced
Problem not reduced by presolve: solving the LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 0s
          2     1.7700000000e+04 Pr: 0(0) 0s
Model   status      : Optimal
Simplex   iterations: 2
Objective value     :  1.7700000000e+04
HiGHS run time      :          0.02

println("The total number of football trophies is ", value(f))
println("The total number of soccer trophies is ", value(s))
println("The highest possible profit is \`$", objective_value(m))

The total number of football trophies is 650.0
The total number of soccer trophies is 1100.0
The highest possible profit is $`17700.0

Geometry meaning #

Last modified on 2023-03-22