Goal

most optimisation asks for the best; goal programming asks for good enough, several times over. 𐃏 you attach a numeric target to each of several objectives, measure how far the plan misses each target, and minimise the misses you dislike. the philosophy is herbert simon’s satisficing¹ — real decision makers do not maximise a grand utility function, they set aspiration levels and stop when they are met — and the machinery is pure linear programming: goal programming was invented by charnes and cooper as an LP device² and remains the most-used technique in practical multi-criteria decision making precisely because it never leaves LP territory.

the deviation-variable device#

hard constraints define a feasible set \(X\); goals are soft. for each goal \(i\) with criterion function \(g_i(x)\) and target \(t_i\), introduce two non-negative deviation variables and convert the aspiration into an equality:

\begin{equation} g_i(x) + d_i^{-} - d_i^{+} = t_i, \qquad d_i^{-},\, d_i^{+} \ge 0. \end{equation}

here \(d_i^{-}\) absorbs underachievement (the criterion falls short of the target) and \(d_i^{+}\) absorbs overachievement. which deviation is unwanted depends on the sense of the goal:

• at least \(t_i\) (a profit floor): penalise \(d_i^{-}\); overshooting is free or welcome.
• at most \(t_i\) (an overtime ceiling): penalise \(d_i^{+}\).
• exactly \(t_i\) (a staffing level): penalise both.

the generic goal program is then

\begin{align*} \text{minimise} \quad & h(d^{-}, d^{+}) \\ \text{subject to} \quad & g_i(x) + d_i^{-} - d_i^{+} = t_i \quad i = 1, \dots, m \\ & x \in X, \quad d^{-}, d^{+} \ge 0, \end{align*}

where the achievement function \(h\) is some non-decreasing combination of the unwanted deviations — a weighted sum, a lexicographic vector, or a max, giving the three classical variants below. when the \(g_i\) are linear and \(X\) is polyhedral, everything is an LP.

complementarity for free (and when it is not)#

the equality only pins the difference \(d_i^{+} - d_i^{-} = g_i(x) - t_i\), so the pair \((d_i^{-} + \delta,\, d_i^{+} + \delta)\) is feasible for any \(\delta \ge 0\). the deviations mean what you want them to mean — \(d_i^{-} = \max(0,\, t_i - g_i(x))\) — only when \(d_i^{-} d_i^{+} = 0\). nobody adds that (non-linear!) condition explicitly, for two reasons:

• both weights positive: if \(d_i^{-} > 0\) and \(d_i^{+} > 0\) at a claimed optimum, subtract \(\delta = \min(d_i^{-}, d_i^{+})\) from both. feasibility is untouched and the objective drops by \(\delta(w_i^{-} + w_i^{+}) > 0\) — contradiction. so any optimum is complementary.
• one weight zero (a one-sided goal): the argument fails and alternative optima with both deviations positive exist. but the two columns of \(d_i^{-}\) and \(d_i^{+}\) in the constraint matrix are negatives of each other, so no basis can contain both — every vertex solution is complementary anyway. a simplex solver (or barrier with crossover) is safe. 𐃏

the robust habit: report deviations recomputed from \(x\) as \(\max(0,\, t_i - g_i(x))\), never trust the raw solver values of unpenalised deviation variables. the same caution applies at intermediate stages of the lexicographic method, where lower-priority deviations are not yet in any objective.

weighted (archimedean) goal programming#

collapse everything into one LP:

\begin{equation} \text{minimise} \quad \sum_{i=1}^{m} \left( \frac{w_i^{-} d_i^{-} + w_i^{+} d_i^{+}}{k_i} \right) \end{equation}

with importance weights \(w_i^{\pm} \ge 0\) (zero on wanted deviations) and normalisation constants \(k_i\). called archimedean because every goal trades against every other at a finite rate — the axiom of archimedes, no quantity infinitely larger than another.

the normalisation trap#

the \(k_i\) are not optional decoration. raw deviations are incommensurable: \(d_1\) is in dollars, \(d_2\) in labour-hours, and a unit-weighted sum silently asserts one dollar = one hour. worse, the assertion changes if you re-express a goal in cents. standard normalisations:

• percentage: \(k_i = t_i\), so each term is a fractional miss. intuitive, dimensionless, but undefined for \(t_i = 0\) and misleading for targets near zero.
• euclidean: for a linear goal \(a_i^{\top} x\), take \(k_i = \lVert a_i \rVert_2\). geometrically honest — deviations become distances in decision space — but the numbers no longer mean anything to the decision maker.
• range (zero-one): \(k_i =\) the spread of \(g_i\) between its best and worst values over \(X\). robust, at the cost of \(2m\) auxiliary optimisations to find the ranges.

the worked example below shows the trap numerically: the same problem under raw and percentage weights picks different vertices. the weights are part of the model, not a tuning afterthought.

a third variant worth knowing: chebyshev (minmax) goal programming minimises the largest normalised deviation, \(\min D\) subject to \(w_i d_i / k_i \le D\) — it seeks balance between goals rather than the best total, and unlike the weighted sum it can reach efficient points off the convex hull of the criteria space.

preemptive (lexicographic) goal programming#

often the decision maker refuses finite trade-offs: safety before profit before polish, and no amount of polish buys back a safety miss. assign goals to priority levels \(P_1 \gg P_2 \gg \cdots \gg P_L\) and minimise the achievement vector

\begin{equation} \operatorname{lexmin} \; \big( h_1(d),\; h_2(d),\; \dots,\; h_L(d) \big), \end{equation}

comparing vectors lexicographically: \(h_1\) decides; ties go to \(h_2\); and so on.³ textbooks write this as minimising \(P_1 h_1 + P_2 h_2 + \cdots\) with \(P_k \gg P_{k+1}\), but the \(P_k\) are ordering symbols, not numbers. for LPs a large-enough finite weight ratio does reproduce the lexicographic optimum — the threshold depends on the instance data — yet it is unknowable in advance and numerically brutal, so the honest implementation is sequential:

• stage 1: minimise \(h_1\) over the goal-augmented feasible set; record the optimum \(h_1^{*}\).
• stage k: minimise \(h_k\) subject to the original constraints plus \(h_j(d) \le h_j^{*}\) for all \(j < k\) — earlier achievements are locked in as constraints, never renegotiated.
• stop: after level \(L\), or early if a stage has a unique optimum (nothing left to decide).

each stage is a plain LP, one extra row per completed level. two behavioural notes: the stage-1 minimiser is generally not the final answer (any point meeting the top goal ties at that stage, and the solver returns an arbitrary one); and a goal that ends up unmet at level \(k\) does not make lower levels moot — they still choose among the level-\(k\)-optimal points.

goal programming as scalarisation#

against the general multi-objective problem, goal programming is one more scalarisation: a rule collapsing a vector of criteria into a single solvable objective. its distinguishing input is the target vector \(t\), and therein lies the classic critique: 𐃏

• if \(t\) is utopian (unreachable in every penalised direction), every unwanted deviation is strictly positive at the optimum, any dominating point would strictly lower the objective, and the GP solution is pareto-efficient.
• if \(t\) is pessimistic — set inside the region where all goals can be met — then every point of the zero-deviation set scores a perfect \(h = 0\). the solver returns an arbitrary one, which may be badly dominated: same zero misses, strictly worse criteria. satisficing taken too literally leaves money on the table.

the standard repair is a restoration (efficiency-recovery) pass: after solving, fix all unwanted deviations at their achieved values and maximise a combination of the wanted deviations. this slides the solution along the optimal set to a pareto-efficient point without disturbing the achieved goals. (rewarding wanted deviations with negative weights in the original objective also works, but it breaks the complementarity argument above and risks unboundedness — the two-phase version is safer.) the worked example demonstrates the trap and the repair with real numbers.

a workshop example#

a workshop assembles two products. per unit, product a needs 2 labour-hours, 1 machine-hour and 1 kg of stock, clearing $6; product b needs 1 labour-hour, 3 machine-hours and 1 kg, clearing $4. exactly 12 kg of stock arrives per day — a hard constraint. management states three goals in strict priority order:

• P1 (profit): clear at least $48 a day — minimise the shortfall \(d_1^{-}\).
• P2 (labour): stay within the 14 rostered labour-hours — minimise overtime \(d_2^{+}\).
• P3 (machine): finish within the 20 machine-hours before the nightly maintenance window — minimise the overrun \(d_3^{+}\).

with \(x, y \ge 0\) the daily production of a and b, the goal-augmented system is

\begin{align*} 6x + 4y + d_1^{-} - d_1^{+} &= 48 \\ 2x + \phantom{4}y + d_2^{-} - d_2^{+} &= 14 \\ \phantom{6}x + 3y + d_3^{-} - d_3^{+} &= 20 \\ x + y &\le 12, \qquad x,\, y,\, d^{\pm} \ge 0. \end{align*}

the lexicographic solve#

the sequential method, honestly, as three scipy.optimize.linprog stages — each stage appends the previous level’s achievement as a new constraint row:

import numpy as np
from scipy.optimize import linprog

# variables: z = [x, y, d1m, d1p, d2m, d2p, d3m, d3p]
A_eq = [[6, 4, 1, -1, 0, 0, 0, 0],   # profit:  6x + 4y + d1m - d1p = 48
        [2, 1, 0, 0, 1, -1, 0, 0],   # labour:  2x +  y + d2m - d2p = 14
        [1, 3, 0, 0, 0, 0, 1, -1]]   # machine:  x + 3y + d3m - d3p = 20
b_eq = [48, 14, 20]
A_ub = [[1, 1, 0, 0, 0, 0, 0, 0]]    # material: x + y <= 12 (hard)
b_ub = [12]
bounds = [(0, None)] * 8

# priority levels: P1 min d1m, P2 min d2p, P3 min d3p
levels = [("P1: profit shortfall d1-", [0, 0, 1, 0, 0, 0, 0, 0]),
          ("P2: labour overtime d2+", [0, 0, 0, 0, 0, 1, 0, 0]),
          ("P3: machine overrun d3+", [0, 0, 0, 0, 0, 0, 0, 1])]

extra_A, extra_b = [], []
for name, c in levels:
    res = linprog(c, A_ub=A_ub + extra_A, b_ub=b_ub + extra_b,
                  A_eq=A_eq, b_eq=b_eq, bounds=bounds, method="highs")
    print(f"{name}: attained {res.fun:.4f} at (x, y) = "
          f"({res.x[0]:.4f}, {res.x[1]:.4f})")
    extra_A.append(c)                 # lock this level's achievement in
    extra_b.append(res.fun + 1e-9)    # as a constraint for later stages

x, y = res.x[:2]
print(f"\nfinal plan: x = {x:.4f}, y = {y:.4f}")
print(f"profit  6x+4y = {6*x+4*y:.2f}  (target 48)")
print(f"labour  2x+ y = {2*x+y:.2f}  (target 14)")
print(f"machine  x+3y = {x+3*y:.2f}  (target 20)")
print(f"material x+ y = {x+y:.2f}  (limit 12)")

P1: profit shortfall d1-: attained 0.0000 at (x, y) = (0.0000, 12.0000)
P2: labour overtime d2+: attained 0.0000 at (x, y) = (4.0000, 6.0000)
P3: machine overrun d3+: attained 2.0000 at (x, y) = (4.0000, 6.0000)

final plan: x = 4.0000, y = 6.0000
profit  6x+4y = 48.00  (target 48)
labour  2x+ y = 14.00  (target 14)
machine  x+3y = 22.00  (target 20)
material x+ y = 10.00  (limit 12)

reading the stages:

• stage 1 attains zero shortfall — the profit goal is reachable — but at \((0, 12)\), an arbitrary member of the zero-shortfall set (make only product b, flood the machine). intermediate stage answers are ties, not decisions.
• stage 2, with \(d_1^{-} \le 0\) locked in, also attains zero: the shaded sliver of the figure, with corners \((4,6)\), \((2,10)\), \((0,12)\), meets the profit floor without overtime.
• stage 3 cannot reach zero. minimising machine use \(x + 3y\) over the sliver gives 22 at the corner \((4,6)\) — an irreducible overrun of \(d_3^{+} = 2\) hours, since the corner values are 22, 26 and 36.

the plan: 4 units of a, 6 of b. profit lands exactly on $48, labour exactly on 14 hours, the machine runs 2 hours into the maintenance window, and 2 kg of stock is left over — the hard constraint is slack, which is fine; hard constraints bound, goals aspire. note what preemption means here: no finite amount of machine relief could have bought even a cent of profit shortfall.

the weighted solve, three ways#

same system, archimedean objective, three weightings — plus the pessimistic-target trap and its restoration repair:

import numpy as np
from scipy.optimize import linprog

# A_eq, b_eq, A_ub, b_ub, bounds as above

def solve(c, b_eq=b_eq, tag=""):
    r = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq,
                bounds=bounds, method="highs")
    x, y = r.x[:2]
    print(f"{tag}: obj = {r.fun:.6f}, (x, y) = ({x:.4f}, {y:.4f})")
    print(f"   profit {6*x+4*y:.2f} | labour {2*x+y:.2f} | machine {x+3*y:.2f}")
    return r

# raw weights: one dollar of shortfall trades 1:1 against one hour
solve([0, 0, 1, 0, 0, 1, 0, 1], tag="raw  w = (1, 1, 1)")

# percentage-normalised weights: deviations as fractions of target
solve([0, 0, 1/48, 0, 0, 1/14, 0, 1/20], tag="norm w = (1/48, 1/14, 1/20)")

# pessimistic profit target (36 instead of 48): pareto trap
b_lo = [36, 14, 20]
r = solve([0, 0, 1/36, 0, 0, 1/14, 0, 1/20], b_eq=b_lo,
          tag="lazy profit target t1 = 36")

# restoration pass: keep unwanted deviations at their optima (all zero),
# maximise the wanted deviation d1+ (profit above target)
A_lock = A_ub + [[0, 0, 1, 0, 0, 0, 0, 0],
                 [0, 0, 0, 0, 0, 1, 0, 0],
                 [0, 0, 0, 0, 0, 0, 0, 1]]
b_lock = b_ub + [r.x[2] + 1e-9, r.x[5] + 1e-9, r.x[7] + 1e-9]
r2 = linprog([0, 0, 0, -1, 0, 0, 0, 0], A_ub=A_lock, b_ub=b_lock,
             A_eq=A_eq, b_eq=b_lo, bounds=bounds, method="highs")
x, y = r2.x[:2]
print(f"restored: d1+ = {r2.x[3]:.2f}, (x, y) = ({x:.4f}, {y:.4f})")
print(f"   profit {6*x+4*y:.2f} | labour {2*x+y:.2f} | machine {x+3*y:.2f}")

raw  w = (1, 1, 1): obj = 0.285714, (x, y) = (4.5714, 5.1429)
   profit 48.00 | labour 14.29 | machine 20.00
norm w = (1/48, 1/14, 1/20): obj = 0.016667, (x, y) = (4.4000, 5.2000)
   profit 47.20 | labour 14.00 | machine 20.00
lazy profit target t1 = 36: obj = 0.000000, (x, y) = (2.0000, 6.0000)
   profit 36.00 | labour 10.00 | machine 20.00
restored: d1+ = 11.20, (x, y) = (4.4000, 5.2000)
   profit 47.20 | labour 14.00 | machine 20.00

four lessons, one per solve:

• raw weights pick \((32/7,\, 36/7)\): profit and machine hit exactly, and the whole miss is dumped on labour as \(d_2^{+} = 2/7\) of an hour. why labour? at a 1:1 exchange rate, \(2/7 \approx 0.29\) “units” of overtime is cheaper than $0.80 of profit shortfall or 2 machine-hours. the model just asserted that an hour and a dollar are the same thing.
• percentage weights pick \((4.4,\, 5.2)\): sacrifice $0.80 of profit — a \(1.7\%\) miss against its target — to hit labour and machine exactly, since \(0.8/48 \approx 0.017\) beats \((2/7)/14 \approx 0.020\) beats \(2/20 = 0.1\). different normalisation, different vertex.
• compare both with the lexicographic answer \((4, 6)\), which refused to trade any profit at all and ate the 2-hour machine overrun. three achievement functions, three plans, one feasible set: the weights are the model.
• the pessimistic-target trap: with the profit target slackened to $36, every goal is comfortably attainable, the objective bottoms out at zero, and the solver returns \((2, 6)\) — profit $36, zero overtime, machine exactly at target. nothing in the model objects, yet \((4.4,\, 5.2)\) earns $47.20 with the same zero unwanted deviations: the returned point is dominated in everything the decision maker actually cares about. the restoration pass — lock the unwanted deviations at zero, maximise the wanted \(d_1^{+}\) — recovers it, banking \(d_1^{+} = 11.2\) of free profit.

see also#

• linear programming — the solver technology underneath every variant here
• multi-objective — the general vector-optimisation problem goal programming scalarises
• integer programming — goal programs over discrete decisions; same deviation device, harder solves
• constraint — when every requirement really is hard
• robust — a different response to not trusting a single objective