Difficulty: Intermediate | Prerequisites: Doc 1 of these study notes (Statistical and ML Models as optimisation problems).
Not all optimisation problems are created equal. Some can be solved in seconds for millions of variables; others are computationally intractable even for modest sizes. This section introduces the classification hierarchy that tells you how hard your problem is before you try to solve it. It also covers network models, a special class of linear program that arises naturally in logistics, routing and resource allocation. Knowing where your problem sits in this hierarchy determines which solver to reach for and whether to expect an exact answer or settle for a heuristic.
Optimisation problems range from easy (linear programs) to very hard (general non-convex programs). Network models are a special, even-faster subclass of linear programs. When a problem is too hard to solve exactly, heuristics give feasible but not necessarily optimal solutions.
Linear program (LP)
An optimisation model where the objective function f(x) is linear and the constraint set X is defined by linear equations and inequalities. In simple terms, everything is straight lines and flat planes, which makes it fast to solve.
Convex quadratic program (QP)
An optimisation model where f(x) is a convex quadratic function and the constraints are still linear. Think of it as a linear program with one curved (bowl-shaped) surface in the objective. Nearly as fast as an LP.
Convex program
An optimisation model where f(x) is convex (if minimising) or concave (if maximising) and the constraint set X is convex. In simple terms, the feasible region has no dents or holes and the objective has no local minima to get trapped in. Solvable but can be slower than LPs.
Integer program (IP)
A linear program with the added restriction that some or all variables must take integer (whole number) values, including binary (0/1). Think of it as an LP where the answer has to be a whole number, which makes it much harder because you cannot smoothly walk to the solution.
General non-convex program
An optimisation model where convexity does not hold. The feasible region or objective may have multiple local optima. In simple terms, the landscape has hills and valleys, and the solver can get stuck in a valley that is not the deepest one.
Network model
A special type of linear program structured around nodes (locations) and arcs (connections). Variables represent flow on each arc. Constraints enforce flow conservation (what goes into a node must come out) and capacity limits. Even faster to solve than a general LP.
Shortest path model
A network model that finds the route with the lowest total cost from one node to another. This is what GPS navigation uses.
Assignment model
A network model that matches items in one set (e.g. workers) to items in another set (e.g. jobs) to optimise some criterion like total efficiency.
Maximum flow model
A network model that determines the greatest total flow that can pass through a network from a source to a sink, respecting capacity limits on each arc.
Heuristic
A method that finds feasible solutions quickly without guaranteeing optimality. Used when the exact problem is too complex or too slow to solve. Think of it as a practical shortcut that gets you a good answer, if not the best one.
All optimisation models can be described in a general form: minimise or maximise f(x), subject to x belonging to a set X. What makes some problems harder than others is the shape of f(x) and the nature of X.
The hierarchy, from easiest to hardest:
Linear programs – f(x) is linear, X is defined by linear equations and inequalities. Fast to solve even for very large instances (millions of variables). This is the gold standard of tractability.
Convex quadratic programs – f(x) is a convex quadratic, X is defined by linear equations and inequalities. Nearly as fast as LPs. Ridge regression falls into this category.
Convex programs – f(x) is convex (for minimisation) or concave (for maximisation), and X is a convex set. Still solvable with guarantees, but can take meaningfully longer than LPs or QPs.
Integer programs – structurally a linear program, but some or all variables must be integers. The integrality requirement makes these much harder. Solvers use techniques like branch-and-bound, which can be slow for large instances.
General non-convex programs – the problem is not convex. Multiple local optima exist, and finding the global optimum is not guaranteed. These are the hardest class.
When a problem is too hard to solve optimally (particularly integer and non-convex programs), a heuristic approach gives feasible solutions without guaranteeing they are optimal. The trade-off is speed for quality of solution.
A network model is a special type of linear program built on a graph structure: nodes (vertices) connected by arcs (edges).
Variables: x_ij represents the flow on the arc from node i to node j
Constraints:
Flow conservation: flow into each node equals flow out of that node
Capacity: flow on each arc must be between its minimum and maximum allowable values
Objective: a linear function of the flow variables (e.g. minimise total cost)
An important property: if all the data (costs, capacities, demands) are integers, then all optimal variable values will also be integers. This means you get integer solutions "for free" without needing to formulate an integer program.
Shortest path models: find the lowest-cost route from one node to another. GPS navigation is the everyday example.
Assignment models: optimally match items from one set to items in another (workers to jobs, students to projects). The objective typically maximises efficiency or minimises cost.
Maximum flow models: determine the greatest volume that can flow through a network from source to sink, respecting arc capacities. Think of oil flowing through a pipeline network, or data packets through a communication network.
Students often assume that "harder" optimisation problems always produce worse solutions. The difficulty ranking (LP to non-convex) refers to computational effort, not solution quality. A non-convex problem may have a perfectly good optimal solution; it is just harder for the solver to find it.
Students sometimes think integer programs are easy because linear programs are easy. Adding the integrality constraint transforms the problem dramatically. An LP with a million variables can be solved in seconds; the same problem with integer variables may take hours or be unsolvable in practice.
Students confuse network models with general graph algorithms. A network model is specifically a linear programming formulation on a graph, with flow conservation constraints and a linear objective. Algorithms like Dijkstra's are related but not the same formulation.
Students often forget the integer-data property of network models: if all data is integer, the optimal solution is automatically integer. This is a significant advantage that removes the need for an integer program formulation.
⚠️ Be able to rank the five optimisation model types from easiest to hardest: LP, convex QP, convex program, integer program, general non-convex program.
⚠️ Know the defining characteristics of each type (what makes f(x) and X different in each case).
⚠️ Expect a question asking you to classify a given model. You will need to inspect the objective function and constraints to determine the type.
⚠️ Understand why network models can be solved faster than general LPs and what the integer-data property means.
⚠️ Be able to identify the three common network model applications (shortest path, assignment, maximum flow) and describe the structure of each.
⚠️ Know when and why a heuristic approach is used instead of exact optimisation.
True or false: A convex quadratic program is harder to solve than an integer program. (False: integer programs are harder.)
Fill in the blank: In a network model, the constraint that flow into a node equals flow out is called ______ conservation. (flow)
True or false: If all data in a network model is integer, the optimal solution is guaranteed to be integer. (True.)
Fill in the blank: When an optimisation problem is too hard to solve exactly, a ______ approach gives feasible but not necessarily optimal solutions. (heuristic)
True or false: A convex program always has multiple local optima. (False: convexity guarantees a single global optimum.)
Q: List the five types of optimisation models in order from easiest to hardest to solve.
A: Linear programs, convex quadratic programs, convex programs, integer programs, general non-convex programs.
Q: What defines a convex program, and why does convexity matter for solving?
A: A convex program has a convex objective function (when minimising) or concave (when maximising), and a convex feasible set X. Convexity guarantees that any local optimum is also the global optimum, so the solver will not get stuck in a suboptimal solution.
Q: Describe the three components of a network model (variables, constraints, objective).
A: Variables are x_ij representing flow on the arc from node i to node j. Constraints include flow conservation (flow in equals flow out at each node) and capacity limits (flow on each arc between min and max). The objective is a linear function of the flow variables.
Q: Why are network models sometimes preferred over general linear programs?
A: Network models exploit the graph structure for faster solution algorithms, they automatically produce integer solutions when data is integer, and they naturally model real-world logistics, routing and allocation problems.
Q: Give an example of when you would use a heuristic instead of exact optimisation.
A: When the problem is an integer program or non-convex program that is too large or complex to solve optimally within a reasonable time frame. The heuristic produces a feasible solution quickly, trading optimality for speed.
The classification hierarchy connects to every optimisation topic in this course. When you formulate a model (regression, SVM, scheduling), the first question is: what type of program is this? That determines the solver you use and the results you can expect.
Network models connect to graph theory and algorithms (Dijkstra's algorithm for shortest paths, Ford-Fulkerson for maximum flow). If you are studying operations research or supply chain management, these models are foundational.
The heuristic concept connects to metaheuristics (simulated annealing, genetic algorithms) covered in more advanced courses, as well as to the stochastic optimisation material in the next set of notes.
Linear programs underpin airline crew scheduling, manufacturing planning and portfolio optimisation. Network models drive logistics at every major shipping company, power grid management and telecommunications routing. Integer programs are used for facility location decisions (where to build warehouses) and vehicle routing. Heuristics are standard in real-time systems where decisions must be made in milliseconds, such as ad bidding and ride-sharing dispatch.
Tags: linear program, LP, convex quadratic program, QP, convex program, integer program, non-convex program, network model, shortest path, assignment model, maximum flow, flow conservation, heuristic, branch and bound, graph structure, nodes, arcs, prescriptive analytics, computational complexity