Decisions & optimisation

Linear optimization and scheduling explained

Optimization finds the best of all feasible actions—provided the objective and constraints are described correctly. An introduction to linear programming, integer models and scheduling, with fully reproducible examples.

  • 12 min read
  • Updated on
  • smartlytics editorial team

At a glance

  1. An optimization model consists of decision variables, an objective function and constraints. Most errors arise in modeling, not in calculation.
  2. Linear programs can be solved very efficiently. An optimum lies at a vertex of the feasible region, and shadow prices show the value of one additional unit of a scarce resource.
  3. Integer requirements and sequences make problems much harder. Rounding is not enough; Branch-and-Bound, constraint programming and heuristics bridge the gap.

Decision theory compares a manageable number of options. In many business problems, however, the number of possibilities is enormous: how much of each product should we manufacture this week? In what order should jobs run on a machine? Which vehicles should serve which customers? Mathematical optimization systematically searches such spaces for the best feasible solution. It is at the heart of operations research, and its best-known form—linear programming—has been a standard planning tool since George B. Dantzig’s work in the late 1940s (Dantzig 1963).

An optimization model in three parts

Every optimization model consists of the same building blocks:

  1. Decision variables—the quantities we can choose, such as production volumes or start times.
  2. Objective function—the quantity to maximize or minimize, such as contribution margin, costs or lateness.
  3. Constraints—the limits every solution must respect: capacities, budgets, minimum quantities and rules.

If the objective and constraints are linear, the problem is called linear optimization or a linear program (LP). In matrix notation, the standard form is max⁡ c⊤x\max\ c^\top x subject to Ax≤bAx \le b and x≥0x \ge 0. Here, “program” means a plan in the older sense of the word, rather than computer code.

Example: production planning as a linear program

A business manufactures two products. One “Standard” unit contributes €30 and requires one hour in production and three hours in assembly. One “Premium” unit contributes €40 and requires two hours each in production and assembly. Each week, 40 production hours and 72 assembly hours are available, and at most 16 Premium units can be sold. The numbers are constructed to illustrate the principle.

With x1x_1 Standard units and x2x_2 Premium units per week, the model is:

max⁡30 x1+40 x2subject tox1+2 x2≤40(production)3 x1+2 x2≤72(assembly)x2≤16(Premium sales)x1, x2≥0\begin{aligned} \max\quad & 30\,x_1 + 40\,x_2 \\ \text{subject to}\quad & x_1 + 2\,x_2 \le 40 && \text{(production)}\\ & 3\,x_1 + 2\,x_2 \le 72 && \text{(assembly)}\\ & x_2 \le 16 && \text{(Premium sales)}\\ & x_1,\ x_2 \ge 0 \end{aligned}

All points satisfying every constraint form the feasible region—a pentagon in this case. The figure shows it together with two lines of equal contribution margin.

Feasible region of the production example, with vertices (0|0), (24|0), (16|12), (8|16) and (0|16). The dashed lines of equal contribution margin last touch the region at vertex (16|12), with 960 euros. 0 8 16 24 4 8 12 16 20 Standard x₁ (units per week) Premium x₂ Production Assembly Sales ≤ 16 480 € 960 € Optimum (16 | 12) €960 per week
Feasible region of the production example (green). The dashed lines connect production plans with equal contribution margin. Moving them up and to the right increases the value—until they touch the region only at vertex (16 | 12).

The pentagon’s vertices and their contribution margins:

Vertex (x1∣x2)(x_1 \mid x_2) Binding constraints Contribution margin
(0 | 0) Nonnegativity €0
(24 | 0) Assembly €720
(16 | 12) Production and assembly €960
(8 | 16) Production and sales €880
(0 | 16) Sales €640

The optimum is therefore 16 Standard units and 12 Premium units, with a weekly contribution margin of €960. Production and assembly are fully utilized; there is room to sell another 4 Premium units.

Why an optimum lies at a vertex

All plans with equal contribution margin 30 x1+40 x2=z30\,x_1 + 40\,x_2 = z lie on a straight line, and these lines are parallel for different values of zz. As you move them towards higher values, the last line leaves the feasible region at a vertex—or, if it happens to be parallel to an edge, along an entire edge of equally good solutions. This picture extends to any number of dimensions: if a linear program has an optimal solution and its feasible region has vertices at all, then a vertex is also optimal (Bertsimas & Tsitsiklis 1997). There is therefore no need to search infinitely many points, only finitely many vertices—although in large models their number can be astronomical.

How solvers solve linear programs

The simplex method directly exploits the vertex property: it starts at a feasible vertex and moves along edges to neighboring vertices as long as the objective value improves (Dantzig 1963). In the example, it can move from (0 | 0) through (24 | 0) to (16 | 12)—or, depending on its selection rule, via (0 | 16) and (8 | 16). In 1972, Victor Klee and George Minty constructed examples in which the method needs exponentially many steps; in practice, it is nevertheless usually very fast (Bertsimas & Tsitsiklis 1997).

Interior-point methods take a different route. They move towards the optimum through the interior of the feasible region. In 1984, Narendra Karmarkar presented such a method with polynomial running time that was also competitive in practice (Karmarkar 1984). Modern solvers combine both approaches. For example, the simplex component of the freely available HiGHS solver is based on a parallelized version of the dual simplex method (Huangfu & Hall 2018); other freely available tools include SCIP and Google OR-Tools, alongside commercial solvers.

Shadow prices: what an extra hour is worth

Every linear program has a corresponding second program, the dual. Its variables can be interpreted as prices for scarce resources—hence the concept of duality. For our example, it is:

min⁡40 y1+72 y2+16 y3subject toy1+3 y2≥302 y1+2 y2+y3≥40y1, y2, y3≥0\begin{aligned} \min\quad & 40\,y_1 + 72\,y_2 + 16\,y_3 \\ \text{subject to}\quad & y_1 + 3\,y_2 \ge 30\\ & 2\,y_1 + 2\,y_2 + y_3 \ge 40\\ & y_1,\ y_2,\ y_3 \ge 0 \end{aligned}

The optimal solution is y1=15y_1 = 15, y2=5y_2 = 5, y3=0y_3 = 0, with value 40⋅15+72⋅5=96040 \cdot 15 + 72 \cdot 5 = 960—exactly the optimal contribution margin of the original problem. This equality is called strong duality.

The dual values are the resources’ shadow prices:

  • An additional production hour increases the optimal contribution margin by €15, and an additional assembly hour by €5.
  • The sales limit has a shadow price of €0: it is not binding, so relaxing it brings no benefit.
  • These prices “explain” the solution: one Standard unit uses one production hour and three assembly hours, valued at 1⋅15+3⋅5=301 \cdot 15 + 3 \cdot 5 = 30 euros—exactly its contribution margin. For Premium, 2⋅15+2⋅5=402 \cdot 15 + 2 \cdot 5 = 40 euros. Both products therefore cover exactly the value of the resources they consume.

Integer optimization: when rounding is not an option

Many decisions are indivisible: you buy a whole machine or none, and a vehicle either drives a route or does not. If variables must take integer values, this is called integer optimization (MIP, mixed-integer programming). An obvious approach would be to solve the linear program and round the result. A small example shows why this fails:

Without integer constraints, the optimum is x1=2,25x_1 = 2{,}25 and x2=3,75x_2 = 3{,}75, with output 41.25. Rounding to (2 | 4) exceeds the budget because 5⋅2+9⋅4=465 \cdot 2 + 9 \cdot 4 = 46. Rounding down to (2 | 3) gives only 34, while the neighboring point (3 | 3) yields 39. The actual integer optimum, however, is (0 | 5), with output 40—only large machines, far from the rounded solution.

The standard method for such problems is Branch-and-Bound, introduced by Ailsa Land and Alison Doig in 1960 (Land & Doig 1960). It first solves the linear program without integer constraints. If a variable is fractional, it splits the problem into two subproblems (for example, x2≤3x_2 \le 3 and x2≥4x_2 \ge 4). Each LP solution provides an upper bound for its subtree; if that bound falls below the best known integer solution, the subtree is discarded. Seven nodes suffice for this example:

Node Additional constraints LP solution Value Result
1 – (2.25 | 3.75) 41.25 Branch on x2x_2
2 x2≤3x_2 \le 3 (3 | 3) 39 Integer: first solution
3 x2≥4x_2 \ge 4 (1.8 | 4) 41 Bound above 39: branch on x1x_1
4 x2≥4, x1≥2x_2 \ge 4,\ x_1 \ge 2 – – Infeasible
5 x2≥4, x1≤1x_2 \ge 4,\ x_1 \le 1 (1 | 4.44) 40.56 Branch on x2x_2
6 x2=4, x1≤1x_2 = 4,\ x_1 \le 1 (1 | 4) 37 Below 39: discard
7 x2≥5, x1≤1x_2 \ge 5,\ x_1 \le 1 (0 | 5) 40 Integer: new best solution

Modern solvers supplement the method with cutting planes, preprocessing and heuristics; integer models with yes-or-no decisions, fixed costs or logical conditions can often be solved effectively in practice (Wolsey 2020). In general, however, they are NP-hard: no known method solves every instance in polynomial time.

Scheduling: optimizing sequences

Scheduling assigns jobs to resources over time. Even the simplest case—one machine and four jobs—shows that “optimal” depends on the objective (Pinedo 2016):

Job Processing time (h) Due after (h)
A 7 9
B 3 14
C 5 11
D 2 17
Sequence Rule Sum of completion times Mean flow time Maximum lateness
A–B–C–D Arrival order 49 h 12.25 h 4 h ©
D–B–C–A SPT: shortest first 34 h 8.5 h 8 h (A)
A–C–B–D EDD: earliest due date first 51 h 12.75 h 1 h (C and B)

The SPT (shortest processing time) rule minimizes the sum of completion times—and thus the mean waiting time. The proof uses an interchange argument: if a longer job ii immediately precedes a shorter job jj, and the pair starts at time tt, swapping them reduces the sum of their completion times by

(t+pi)+(t+pi+pj)−[(t+pj)+(t+pj+pi)]=pi−pj>0,(t + p_i) + (t + p_i + p_j) - \big[(t + p_j) + (t + p_j + p_i)\big] = p_i - p_j > 0,

while leaving all other jobs unchanged. By contrast, the EDD (earliest due date) rule minimizes maximum lateness. In the example, it gives the best result for meeting deadlines, with one hour of lateness—and at the same time the worst sum of completion times among all 24 possible sequences.

Realistic problems are much harder. In the job-shop problem, jobs pass through several machines in different orders; it is NP-hard, and even medium-sized instances cannot be solved by trying every possibility (Pinedo 2016). Approaches include integer models, constraint programming—which directly expresses time windows, sequences and resources as logical conditions—and heuristics and metaheuristics such as local search or simulated annealing. Heuristics quickly produce good schedules but offer no guarantee of optimality; bounds from exact methods show how much improvement might still be possible in the worst case.

Optimization under uncertainty

The production example assumes that capacities, contribution margins and sales are known with certainty. They rarely are. A plan that is optimal for average demand can become costly or even infeasible under real variation. Two approaches account for this explicitly:

  • Stochastic optimization describes uncertainty using scenarios with probabilities. Two-stage models are common: today, you choose what must be fixed before the uncertainty is resolved; later, you respond with corrective actions. The expected value across all scenarios is optimized (Birge & Louveaux 2011). Scenarios often come from a Monte Carlo simulation.
  • Robust optimization requires a solution to remain feasible for all values in an uncertainty set and optimizes the worst case. It is more cautious, but does not require probabilities (Ben-Tal et al. 2009).

In practice, a third approach helps: re-optimize regularly as new data arrives—while making sure plans are not overturned with every small change.

Common mistakes in practice

  1. The wrong objective. Maximizing utilization alone often creates long queues. The objective must represent what actually matters to the business—including priorities between competing goals.
  2. Missing constraints. Setup times, shift rules or quality approvals omitted from the model make the optimal plan unusable.
  3. Infeasible or unbounded. If the solver reports “infeasible”, some constraints contradict each other; many solvers can identify a minimal conflicting subset. “Unbounded” almost always points to a forgotten limit.
  4. False precision. If input data is accurate to ten percent, seven decimal places in the result are meaningless. Sensitivity analysis shows which data really matters.
  5. Being unable to explain the solution. Shadow prices, binding constraints and comparisons with simple alternative plans make a recommendation understandable—and therefore suitable for approval.

Conclusion

Optimization translates a planning question into variables, an objective and constraints—and then reliably finds the best feasible solution to that model. Linear programs form the well-understood core: efficient to solve, geometrically intuitive, and accompanied by shadow prices that explain which resources are scarce. Integer requirements and sequences make problems harder, but Branch-and-Bound, constraint programming and heuristics make them manageable. To go further, Williams covers the art of modeling (Williams 2013), Bertsimas and Tsitsiklis cover the theory of linear optimization (Bertsimas & Tsitsiklis 1997), and Pinedo provides the tools for scheduling (Pinedo 2016).

Frequently asked questions

What is linear optimization?

Linear optimization, also called linear programming, finds values for decision variables that maximize or minimize a linear objective function while satisfying linear constraints. A typical example is choosing production quantities that maximize contribution margin without exceeding machine capacity.

What is a shadow price?

The shadow price of a constraint indicates how much the optimal objective value improves when the associated resource increases by one unit. In this article’s example, an additional production hour is worth €15 and an assembly hour €5. The value applies only within a range where the structure of the optimal solution stays the same.

Why can't you simply round the solution of a linear program?

Rounded values can be infeasible or much worse than the integer optimum. In this article’s example, the rounded solution exceeds the budget, and the integer optimum lies somewhere quite different. Integer problems are solved using methods such as Branch-and-Bound.

Which software solves optimization problems?

There are freely available solvers such as HiGHS and SCIP, toolkits such as Google OR-Tools and commercial solvers such as Gurobi or CPLEX. A well-formulated model with verified data usually matters more than the choice of solver.

Sources and further reading

  1. BookDantzig, G. B. (1963): Linear Programming and Extensions. Princeton University Press.
  2. BookBertsimas, D. and Tsitsiklis, J. N. (1997): Introduction to Linear Optimization. Athena Scientific.A thorough textbook on geometry, the simplex method, duality and interior-point methods.
  3. BookWilliams, H. P. (2013): Model Building in Mathematical Programming (5th edition). Wiley.A classic on translating real-world problems into linear and integer models.
  4. PaperKarmarkar, N. (1984): A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395.
  5. PaperLand, A. H. and Doig, A. G. (1960): An Automatic Method of Solving Discrete Programming Problems. Econometrica 28(3), 497–520.
  6. BookWolsey, L. A. (2020): Integer Programming (2nd edition). Wiley.
  7. BookPinedo, M. L. (2016): Scheduling: Theory, Algorithms, and Systems (5th edition). Springer.A standard reference on priority rules, complexity and algorithms for scheduling problems.
  8. PaperHuangfu, Q. and Hall, J. A. J. (2018): Parallelizing the dual revised simplex method. Mathematical Programming Computation 10(1), 119–142.The basis of the simplex solver in the freely available HiGHS solver.
  9. BookBirge, J. R. and Louveaux, F. (2011): Introduction to Stochastic Programming (2nd edition). Springer.
  10. BookBen-Tal, A., El Ghaoui, L. and Nemirovski, A. (2009): Robust Optimization. Princeton University Press.

Content last reviewed on 25 September 2026. Please let us know about any errors: impressum@nyxai.com.

From NyxAI

smartlytics is the learning hub of NyxAI GmbH.

Explore the methods we work with, explained openly, with sources and calculations you can reproduce.

Decision Core

NyxAI is developing a Decision Core for Decision Intelligence that combines optimisation, simulation, statistics and reinforcement learning: compare options, make uncertainty visible and learn from outcomes, with people in control.

DeepSquare

Explainable chess AI with human playing styles: NyxAI’s testing ground for understandable decisions under time pressure.