The Central Idea
Continuous optimization allows variables to move through continuous ranges.
Discrete optimization restricts variables to separated choices.
For example,
\[ x\in[0,10] \]is continuous, while
\[ x\in\{0,1,2,\ldots,10\} \]is discrete.
The numerical bounds are similar, but the decision spaces are fundamentally different.
Continuous Decision Variables
A continuous variable can take any real value in an allowed interval or region.
Examples include:
- temperature;
- pressure;
- flow rate;
- time;
- distance;
- percentage allocation;
- physical dimensions;
- continuous financial allocations.
Discrete Decision Variables
A discrete variable can take only specified separated values.
Common examples include:
- number of vehicles;
- number of workers;
- number of machines;
- which route is selected;
- which facility is opened;
- which project is funded;
- which schedule is chosen;
- which items are included in a design.
Integer Variables
An integer decision variable satisfies
\[ \boxed{ x\in\mathbb{Z} }. \]If the variable must also be nonnegative,
\[ x\in\mathbb{Z}_{\ge0}. \]Integer variables are appropriate when fractional decisions would be meaningless.
Binary Variables
A binary variable takes only two values:
\[ \boxed{ x\in\{0,1\} }. \]It can represent a yes-or-no decision.
For example,
\[ x= \begin{cases} 1, & \text{open the facility},\\ 0, & \text{do not open the facility}. \end{cases} \]Categorical Decisions
Some decisions choose one option from several categories.
Such choices can often be encoded using several binary variables.
If exactly one of \(m\) alternatives must be selected, we may write
\[ x_1+\cdots+x_m=1 \]with
\[ x_i\in\{0,1\}. \]Continuous Feasible Sets
A continuous feasible set may contain entire intervals, curves, surfaces, or regions.
For example,
\[ x^2+y^2\le1 \]contains every point in the unit disk.
Small movements are possible in many directions.
Discrete Feasible Sets
A discrete feasible set consists of isolated possibilities.
If
\[ x,y\in\mathbb{Z}_{\ge0} \]and
\[ x+y\le5, \]only finitely many lattice points are feasible.
The line segments between feasible points are generally not themselves feasible.
Geometry Changes with Integrality
Suppose the continuous feasible region is
\[ x\ge0, \qquad y\ge0, \qquad x+y\le5. \]Continuously, this is a filled triangle.
If \(x\) and \(y\) must be integers, only the lattice points inside that triangle remain feasible.
This change can alter the optimizer.
Example: Continuous Versus Integer Solution
Minimize
\[ f(x)=(x-2.4)^2. \]Over
\[ x\in\mathbb{R}, \]the unique minimizer is
\[ \boxed{x=2.4}. \]If instead
\[ x\in\mathbb{Z}, \]the nearest feasible integers are \(2\) and \(3\).
Compare:
\[ f(2)=0.16, \] \[ f(3)=0.36. \]Therefore, the integer minimizer is
\[ \boxed{x=2}. \]Why Rounding Is Not a General Solution
It may be tempting to solve a continuous problem and round the answer.
This can fail because rounding may:
- violate constraints;
- produce a nonoptimal discrete point;
- change several interacting variables badly;
- destroy logical relationships among binary decisions.
Discrete optimization usually requires explicit discrete reasoning.
Example: Rounding Can Break Feasibility
Suppose
\[ x+y=5 \]and a continuous optimizer is
\[ (2.6,2.4). \]Rounding both coordinates independently gives
\[ (3,2), \]which happens to remain feasible.
But with different equality or inequality structures, independent rounding can easily violate the model.
Mixed-Integer Optimization
Many real models contain both continuous and discrete variables.
For example:
\[ x\in\mathbb{R}_{\ge0}, \qquad y\in\mathbb{Z}_{\ge0}, \qquad z\in\{0,1\}. \]Such problems are called mixed-integer optimization problems.
Mixed-Integer Linear Programming
If the objective and algebraic constraints are linear but some variables are integer or binary, the problem is a mixed-integer linear program, often abbreviated MILP.
A typical form is
\[ \boxed{ \begin{aligned} \text{maximize}\quad &\mathbf{c}^T\mathbf{x}\\ \text{subject to}\quad &A\mathbf{x}\le\mathbf{b},\\ &x_i\in\mathbb{Z} \text{ for selected }i. \end{aligned} } \]Continuous Relaxation
A common strategy temporarily removes integer restrictions.
For example,
\[ x\in\mathbb{Z}_{\ge0} \]may be relaxed to
\[ x\ge0. \]The resulting problem is called the continuous relaxation.
Why Relaxations Are Useful
A continuous relaxation is usually easier to solve.
Its optimal value can provide a bound on the discrete optimum.
These bounds are fundamental in systematic discrete-search algorithms.
Example: Relaxation Bound
Suppose a maximization problem requires
\[ x\in\mathbb{Z}_{\ge0}. \]If its continuous relaxation has maximum value
\[ 125.7, \]then no feasible integer solution can have a larger objective value than \(125.7\).
This gives an upper bound for the integer maximization problem.
Enumeration
If a discrete feasible set is very small, every feasible possibility can be tested directly.
This is called enumeration.
Enumeration is exact but can become impractical when the number of possibilities grows rapidly.
Combinatorial Explosion
Suppose there are \(n\) independent yes-or-no decisions.
The number of possible binary assignments is
\[ \boxed{2^n}. \]Even moderate values of \(n\) can produce enormous search spaces.
Example: Binary Search Space
With
\[ n=10, \]there are
\[ 2^{10}=1024 \]possible assignments.
With
\[ n=50, \]the number becomes
\[ 2^{50}, \]which is far too large for naive enumeration in most settings.
Branch and Bound
Branch and bound is a central method for discrete and mixed-integer optimization.
The basic idea is to:
- divide the decision space into smaller cases;
- compute bounds using easier relaxations;
- discard branches that cannot beat the best known feasible solution;
- continue only where improvement remains possible.
Branching
Suppose a relaxed solution gives
\[ x=4.6 \]but \(x\) must be an integer.
We can divide the problem into two branches:
\[ x\le4 \]and
\[ x\ge5. \]Each branch defines a smaller feasible set.
Bounding
Each branch can be relaxed and solved.
If its best possible relaxed value cannot improve on the best known discrete solution, that branch can be discarded.
This is the bounding step.
Pruning
Discarding a branch from further consideration is called pruning.
Pruning is what allows branch-and-bound algorithms to avoid testing every discrete possibility.
Cutting Planes
Another strategy adds valid constraints that remove fractional solutions without removing any feasible integer solutions.
These additional inequalities are called cutting planes.
Branch and Cut
Modern mixed-integer solvers often combine branch and bound with cutting planes.
This combined framework is called branch and cut.
Dynamic Programming
Dynamic programming solves certain discrete optimization problems by breaking them into overlapping subproblems and reusing previously computed results.
It is especially effective when the problem has a clear sequential or recursive structure.
Bellman's Principle
Dynamic programming relies on the idea that an optimal solution contains optimal solutions to appropriate subproblems.
This is often called the principle of optimality.
Shortest-Path Problems
A shortest-path problem chooses a route through a network that minimizes total distance, cost, or time.
The decisions are discrete because the route consists of selected edges.
Specialized graph algorithms can solve many such problems efficiently.
Assignment Problems
An assignment problem may decide which worker receives which task.
Binary variables can represent the decision:
\[ x_{ij} = \begin{cases} 1, & \text{worker }i\text{ assigned to task }j,\\ 0, & \text{otherwise}. \end{cases} \]Constraints enforce one-to-one or capacity relationships.
Scheduling Problems
Scheduling chooses:
- which job occurs first;
- which resource handles each job;
- when activities begin;
- whether two activities may overlap.
These decisions often combine discrete ordering choices with continuous time variables.
Facility-Location Problems
A facility-location model may decide which possible sites to open.
Binary variables represent opening decisions, while continuous variables may represent shipment quantities.
This naturally creates a mixed-integer model.
Knapsack Problems
In a basic knapsack problem, items have values and weights.
We choose which items to include:
\[ x_i\in\{0,1\}. \]The model may be written
\[ \text{maximize } \sum_i v_i x_i \]subject to
\[ \sum_i w_i x_i\le W. \]Continuous Optimization Methods
Continuous optimization can use tools such as:
- derivatives;
- gradients;
- Hessian matrices;
- Newton methods;
- gradient descent;
- convexity;
- Lagrange multipliers;
- interior-point methods.
Why Derivatives Are Less Direct in Discrete Problems
A derivative describes the effect of an infinitesimal change.
But if
\[ x\in\{0,1\}, \]there is no admissible infinitesimal change between \(0\) and \(1\).
Discrete optimization therefore requires different notions of neighboring decisions and search directions.
Neighborhoods in Discrete Optimization
A discrete search method may define neighboring solutions as those reached by a small combinatorial change.
Examples include:
- flipping one binary decision;
- swapping two assignments;
- reversing part of a route;
- moving one job to another machine.
Local Search
A discrete local-search method repeatedly moves from the current solution to a better neighboring solution.
It stops when no allowed local move improves the objective.
As in continuous nonconvex optimization, a local optimum need not be globally optimal.
Heuristics
A heuristic is a practical method designed to find good solutions quickly without necessarily proving global optimality.
Heuristics are often valuable when exact optimization is too expensive.
Metaheuristics
More general search frameworks include methods such as:
- simulated annealing;
- tabu search;
- genetic algorithms;
- ant-colony methods;
- variable-neighborhood search.
These methods are useful in some difficult combinatorial settings but generally do not provide the same optimality guarantees as exact methods.
Exact Versus Approximate Optimization
An exact method aims to prove that the returned solution is globally optimal.
An approximate method aims to find a high-quality solution without necessarily proving optimality.
The appropriate choice depends on problem size, available time, and the value of certification.
Optimality Gap
In discrete optimization, algorithms often maintain:
- a best known feasible solution;
- a bound on how good any unseen solution could still be.
The difference between these quantities is an optimality gap.
A small gap provides evidence that the current solution is near optimal.
Continuous Relaxation as a Bound
For an integer minimization problem, the relaxed minimum is no larger than the integer minimum.
Symbolically,
\[ \boxed{ f_{\text{relax}} \le f_{\text{integer}} }. \]For maximization, the inequality reverses.
Integrality Gap
The difference between the optimal value of a discrete problem and its continuous relaxation is called an integrality gap.
A small gap means the relaxation closely approximates the discrete model.
Continuous Models Can Approximate Discrete Systems
Sometimes a large discrete system is approximated continuously.
For example, a model might treat population, traffic flow, or production as continuous even though the underlying units are discrete.
This can simplify analysis when the scale is large enough that fractional approximations are acceptable.
Discrete Models Can Capture Logical Structure
Binary and integer variables can express logical conditions that are difficult to represent with smooth continuous equations.
Examples include:
- if one project is selected, another must also be selected;
- at most three facilities may open;
- exactly one route must be chosen;
- a machine is either active or inactive.
Example: At Most Three Selections
If
\[ x_i\in\{0,1\}, \]then the requirement that at most three alternatives be selected can be written
\[ \boxed{ \sum_i x_i\le3 }. \]Example: Exactly One Selection
If exactly one option must be chosen,
\[ \boxed{ \sum_i x_i=1 }. \]Example: Logical Implication
Suppose binary variable \(x\) represents selecting project A and \(y\) represents selecting project B.
If selecting A requires selecting B, then
\[ \boxed{ x\le y }. \]Continuous and Discrete Models Can Interact
A facility-location problem may contain:
- binary variables deciding which facilities open;
- continuous variables deciding shipment amounts;
- capacity constraints linking the two.
This illustrates why mixed-integer models are so common in practice.
Computational Difficulty
Many continuous convex optimization problems can be solved efficiently even at large scale.
Many discrete optimization problems become much harder as problem size grows.
The difficulty comes from the explosion of possible combinations and the loss of smooth geometric structure.
Problem Structure Still Matters
Not every discrete problem is computationally difficult.
Some special structures admit very efficient algorithms.
Shortest paths, minimum spanning trees, and certain network-flow problems are important examples.
Choosing the Right Model Type
Before selecting an optimization algorithm, ask:
- Can the decision vary fractionally?
- Must the decision be a whole number?
- Is the decision yes-or-no?
- Is there a mixture of continuous and discrete choices?
- Does rounding preserve meaning and feasibility?
These questions determine the correct mathematical model.
Common Error: Using Continuous Variables for Indivisible Decisions
A model that recommends
\[ 3.6 \]airplanes or
\[ 2.4 \]factories is usually not directly meaningful.
Integrality must be included when the decision is indivisible.
Common Error: Rounding Without Rechecking Constraints
A rounded solution may no longer satisfy resource, equality, or logical constraints.
Every rounded candidate must be rechecked for feasibility.
Common Error: Assuming the Relaxed Optimum Is Feasible
A continuous relaxation provides information and bounds.
Its solution may violate the original integer restrictions and therefore may not be an admissible solution.
Common Error: Assuming Discrete Means Finite
A discrete feasible set can still be infinite.
For example,
\[ x\in\mathbb{Z}_{\ge0} \]contains infinitely many values.
Common Error: Assuming Continuous Means Easy
Nonconvex continuous optimization can be extremely difficult.
Continuity alone does not guarantee easy computation or global optimality.
Common Error: Ignoring Problem Structure
General-purpose search may be much slower than a specialized method that exploits network, assignment, convexity, or dynamic-programming structure.
A Reliable Modeling Workflow
- Define the decision variables.
- Identify which variables are continuous.
- Identify which variables must be integer.
- Identify binary or categorical decisions.
- Write the objective function.
- Write all physical, resource, logical, and domain constraints.
- Determine whether the model is continuous, integer, or mixed-integer.
- Check whether the objective and constraints are linear or nonlinear.
- Choose methods that match the resulting structure.
- Use relaxations and bounds when helpful.
- Verify the feasibility of every candidate solution.
- Distinguish exact optimality from approximate quality.
- Interpret the solution in the original context.
Practice 1: Continuous or Discrete?
Classify each decision:
- amount of water pumped per hour;
- number of trucks purchased;
- whether a facility is opened;
- percentage of a budget invested in an asset.
Practice 2: Integer Feasible Set
List all feasible values if
\[ 0\le x\le5 \]and
\[ x\in\mathbb{Z}. \]Practice 3: Binary Constraint
Three binary variables \(x_1,x_2,x_3\) represent three projects.
Write a constraint requiring exactly one project to be selected.
Practice 4: At Most Two Selections
Four binary variables
\[ x_1,x_2,x_3,x_4 \]represent four alternatives.
Write a constraint allowing at most two selections.
Practice 5: Continuous Versus Integer Minimum
Minimize
\[ f(x)=(x-3.7)^2. \]Find the minimizer over
\[ x\in\mathbb{R} \]and over
\[ x\in\mathbb{Z}. \]Practice 6: Relaxation
A model requires
\[ x\in\mathbb{Z}_{\ge0}. \]Write the corresponding continuous relaxation of this restriction.
Practice 7: Binary Search Space
How many possible assignments exist for \(8\) independent binary variables?
Practice 8: Logical Implication
Binary variable \(x\) represents choosing option A and binary variable \(y\) represents choosing option B.
Write a linear constraint expressing:
If A is chosen, B must also be chosen.
Practice 9: Mixed-Integer Classification
A model contains
\[ x\in\mathbb{R}_{\ge0}, \qquad y\in\mathbb{Z}_{\ge0}, \qquad z\in\{0,1\}. \]Is the model continuous, purely integer, or mixed-integer?
Practice 10: Identify the Error
A continuous optimization model recommends opening
\[ 2.6 \]warehouses.
The analyst rounds the answer to \(3\) and accepts it without further analysis.
Explain the modeling error.
Practice Answers
Practice 1
- continuous;
- discrete integer;
- binary discrete;
- continuous.
Practice 2
\[ \boxed{ \{0,1,2,3,4,5\} }. \]Practice 3
\[ \boxed{ x_1+x_2+x_3=1 }. \]Practice 4
\[ \boxed{ x_1+x_2+x_3+x_4\le2 }. \]Practice 5
Over the real numbers,
\[ \boxed{x=3.7}. \]Over the integers, compare the nearby values \(3\) and \(4\):
\[ f(3)=0.49, \] \[ f(4)=0.09. \]Therefore,
\[ \boxed{x=4} \]is the integer minimizer.
Practice 6
\[ \boxed{ x\ge0, \qquad x\in\mathbb{R} }. \]Practice 7
\[ 2^8=\boxed{256}. \]Practice 8
\[ \boxed{x\le y}. \]Practice 9
Because the model contains both continuous and discrete variables, it is
\[ \boxed{\text{mixed-integer}}. \]Practice 10
The number of warehouses is indivisible, so the variable should have been modeled as integer from the beginning.
Rounding the continuous answer may violate constraints or fail to produce the best integer solution.
The rounded point must not be accepted without solving or checking the discrete problem.
What to Remember
The nature of the decision variables determines the structure of the optimization problem.
- continuous variables can take real values across intervals or regions;
- integer variables represent whole-number decisions;
- binary variables represent yes-or-no choices;
- mixed-integer models combine continuous and discrete decisions;
- continuous relaxations provide useful bounds;
- rounding a continuous solution is not a general discrete optimization method;
- branch and bound systematically searches large discrete spaces;
- dynamic programming exploits recursive structure;
- heuristics trade optimality guarantees for speed;
- problem structure determines which optimization method is appropriate.
The central modeling principle is
\[ \boxed{ \text{choose the mathematics to match the actual kind of decision} }. \]Where We Go Next
So far, each optimization model has generally treated one numerical objective as the quantity to make best. Real decisions often involve several competing goals at the same time: lower cost, higher performance, lower risk, greater speed, improved reliability, and other priorities may conflict.
The next lesson, Multiobjective Tradeoffs, develops the mathematics of competing objectives, weighted combinations, Pareto optimality, and the tradeoffs that arise when no single decision is best in every dimension.