1 Foundations

Discrete optimization studies how to choose the best option from a finite or countably infinite collection of feasible alternatives. The “best” choice is defined by an objective, such as minimizing cost, time, distance, or resource use, or maximizing profit, reliability, or utility. The subject brings together mathematical modeling, algorithm design, and computational analysis.

Unlike continuous optimization, discrete optimization works with variables that must take separate, indivisible values. This makes it especially suitable for problems where decisions are naturally all-or-nothing, ordered in steps, or based on combinatorial structures. Many practical planning tasks fit this description, including routing vehicles, assigning workers, packing items, and designing networks.

1.1 Definition and scope

Discrete optimization refers to optimization problems in which the set of admissible solutions is discrete rather than continuous. The feasible set may be finite, as in selecting a subset of items, or countably infinite, as in some integer-valued models. The field includes both exact methods that guarantee optimality and approximate methods that seek near-optimal solutions when exact computation is impractical.

Its scope extends across mathematics, operations research, computer science, engineering, and economics. The central goal is to model a decision problem in a way that captures the available choices and then determine the most effective one under given constraints.

1.2 Discrete decision variables

Discrete decision variables take values from separated sets such as integers, binary values, categories, or permutations. A binary variable may represent whether a project is selected, while an integer variable may indicate the number of units produced. In other settings, the variable may encode an ordering, a route, or a matching between objects.

These variables are often used because the underlying decision is inherently discrete. A machine is either assigned to a task or not, a path either includes an edge or excludes it, and a schedule usually assigns whole jobs rather than fractions of jobs.

1.3 Feasible solutions and objective functions

A feasible solution satisfies all specified constraints of the problem. Constraints may limit capacity, enforce precedence, require balance, or preserve structural rules such as connectivity. Among the feasible solutions, the objective function ranks alternatives by their quality.

The objective can be linear or nonlinear, deterministic or uncertain, and may involve a single criterion or multiple competing criteria. In practice, modelers often seek formulations that are both accurate and computationally manageable.

1.4 Relation to continuous optimization

Discrete optimization and continuous optimization share many tools, such as duality, convex analysis, and decomposition. However, discrete problems are often more difficult because rounding or splitting decisions is not allowed. This restriction can make standard calculus-based methods inapplicable or only indirectly useful.

A common strategy is to relax discrete variables into continuous ones, solve the easier problem, and then recover a discrete solution through additional reasoning. In this way, continuous optimization often serves as a foundation for stronger discrete methods.

2 Problem classes

Discrete optimization includes a wide range of problem families defined by the structure of their variables and constraints. Some classes are distinguished by the form of the mathematical model, while others are classified by the objects being optimized, such as graphs or networks. Despite their diversity, these problems often share common algorithmic ideas.

2.1 Integer programming

Integer programming is a broad class in which some or all variables are required to be integers. The model may include linear or nonlinear relationships, though linear integer programming is especially prominent. Because integrality creates combinatorial complexity, integer programming is a central topic in the field.

2.1.1 Pure integer programming

In pure integer programming, every decision variable must take an integer value. Such models arise in selection, allocation, and counting problems. They are often used when all decisions are fundamentally discrete and no continuous quantities are involved.

2.1.2 Mixed-integer programming

Mixed-integer programming allows some variables to be continuous while others are integer-constrained. This flexibility makes it useful for models combining discrete choices with quantities that vary smoothly, such as production levels, flows, or temperatures subject to on/off decisions.

2.2 Combinatorial optimization

Combinatorial optimization concerns finding an optimal object from a finite collection of combinatorial structures. Examples include subsets, sequences, partitions, matchings, and spanning structures. The emphasis is on the arrangement or selection of discrete objects rather than on numerical magnitudes alone.

This class includes many well-known problems with elegant formulations and significant computational challenges. It is closely tied to graph theory, algorithm design, and complexity theory.

2.3 Graph optimization

Graph optimization deals with problems defined on graphs, where vertices and edges represent entities and relationships. Many real-world systems, from transportation networks to communication systems, are naturally modeled in this way. Graph problems are often among the most studied and best understood in discrete optimization.

2.3.1 Shortest path problems

Shortest path problems seek a path between two vertices with minimum total length, cost, or time. Variants may require one source, one destination, multiple destinations, or constraints on intermediate nodes. These problems are fundamental in routing and network analysis.

2.3.2 Minimum spanning tree problems

Minimum spanning tree problems ask for a connected subgraph linking all vertices with minimum total edge weight. The result is a tree, meaning it contains no cycles. Such models are important in network design, clustering, and infrastructure planning.

2.3.3 Matching problems

Matching problems involve pairing vertices or objects under given constraints. A matching selects edges so that no vertex is used more than allowed, often aiming to maximize total weight or cardinality. Applications include assignment, scheduling, and resource pairing.

2.4 Network optimization

Network optimization studies flows, capacities, costs, and connectivity in interconnected systems. Typical examples include transportation, distribution, and communication networks. Problems in this class often model how to move goods, information, or energy efficiently through a network.

Because network structure can be exploited algorithmically, many network optimization problems admit specialized and efficient methods. This makes the area especially important in practice.

2.5 Constraint satisfaction and optimization

Constraint satisfaction problems ask whether a set of conditions can be met, while constraint optimization problems seek the best feasible assignment. The constraints may be logical, arithmetic, temporal, or structural. These formulations are useful when the main difficulty lies in consistency rather than in numerical comparison alone.

In many applications, the boundary between satisfaction and optimization is fluid. A problem may first require finding any valid solution and then improving it according to a preference criterion.

3 Mathematical formulations

Discrete optimization problems are expressed through mathematical models that define variables, objectives, and constraints. The formulation chosen can strongly influence the ease of analysis and computation. A good model often reveals structural properties that can be turned into algorithmic advantages.

3.1 Linear objective models

Linear objective models use an objective function that is linear in the decision variables. They are common because they are easy to interpret and can often be combined with linear constraints. Even when the underlying problem is complex, a linear objective frequently provides a useful approximation or exact representation.

3.2 Nonlinear discrete models

Nonlinear discrete models involve objectives or constraints that are not linear. These may include products of variables, ratios, piecewise terms, or nonlinear penalty functions. Such models can better reflect real systems but are often harder to solve.

3.3 Binary variables and logical constraints

Binary variables encode yes-or-no decisions and are widely used in discrete optimization. Logical constraints connect these variables to express implications, exclusions, and dependencies. For example, one choice may require another, or two options may be incompatible.

These formulations are especially useful for modeling complex decision rules in a precise algebraic form. They also allow many practical problems to be translated into mixed-integer models.

3.4 Set-based formulations

Set-based formulations describe solutions as subsets of a ground set or collections of compatible subsets. This viewpoint is natural in problems such as knapsack selection, set covering, facility placement, and partitioning. It highlights the combinatorial nature of the decision and often leads to compact or insightful representations.

3.5 Polyhedral formulations

Polyhedral formulations study the geometric shape formed by feasible integer solutions and their convex hulls. By analyzing facets, bounds, and faces of these polyhedra, researchers can derive stronger models and more effective cutting planes. This geometric approach is central to modern integer programming.

4 Complexity theory

Complexity theory explains why some discrete optimization problems are easy to solve while others are not. It classifies problems according to the resources needed by an algorithm, typically time and memory. The field provides a framework for understanding both exact solvability and the limits of computation.

4.1 Polynomial-time solvability

A problem is polynomial-time solvable if an algorithm can solve it in time bounded by a polynomial in the input size. Such problems are generally considered tractable. Many classic network problems fall into this category, especially when their structure can be exploited.

4.2 NP-completeness and NP-hardness

NP-complete problems are decision problems that are both in NP and as hard as any problem in that class. NP-hard problems are at least as difficult as NP-complete ones and may not even be decision problems. Many discrete optimization problems are NP-hard, which explains the need for approximation, heuristics, and specialized algorithms.

4.3 Decision versus optimization versions

Decision versions ask whether a feasible solution exists that meets a threshold, while optimization versions ask for the best possible value. These two forms are closely related, and understanding one often helps with the other. In complexity theory, decision formulations are often easier to classify precisely.

4.4 Approximation limits

Approximation limits describe how well polynomial-time algorithms can perform relative to the optimum. Some problems admit strong approximation guarantees, while others are known to resist efficient approximation beyond certain bounds. These results help identify which problems can be handled effectively at scale and which require alternative methods.

5 Exact methods

Exact methods aim to prove optimality, not merely good performance. They are essential when reliability is critical or when solutions must be certified. Because discrete problems can grow rapidly in difficulty, exact methods often combine multiple strategies to narrow the search.

5.1 Branch and bound

Branch and bound systematically divides the problem into subproblems and computes bounds on their best possible solutions. Subproblems that cannot improve on the current best solution are discarded. This pruning can greatly reduce the search space in practice.

5.2 Branch and cut

Branch and cut augments branch and bound with valid inequalities called cuts. These cuts strengthen the relaxation of the problem and eliminate fractional or otherwise nonintegral solutions. The method is especially effective for integer and mixed-integer programming.

5.3 Dynamic programming

Dynamic programming solves problems by breaking them into overlapping subproblems and combining their solutions. It is particularly useful when the problem has optimal substructure and a manageable state description. Although sometimes exponential in worst-case size, it can be highly effective for structured instances.

5.3.1 State-space representation

State-space representation defines the information needed to describe each subproblem. A good state captures all relevant history while remaining compact enough for computation. The choice of state often determines whether a dynamic program is practical.

5.3.2 Bellman recursion

Bellman recursion expresses the optimal value of a state in terms of optimal values of smaller states. This recursive relationship provides the foundation of dynamic programming. It transforms a large decision problem into a sequence of smaller evaluations.

5.4 Cutting-plane methods

Cutting-plane methods solve relaxations of the original problem and then add constraints that remove infeasible or fractional solutions. Repeating this process gradually tightens the model. These methods are widely used in integer programming because they can improve bounds without exhaustively searching all possibilities.

Enumeration methods list candidate solutions, either systematically or with pruning. Search procedures may use depth-first, breadth-first, or best-first strategies depending on the structure of the problem. While brute-force enumeration is often impractical, informed search can still be effective for smaller or highly structured instances.

6 Relaxation techniques

Relaxation techniques simplify a difficult discrete model by replacing it with an easier one. The relaxed problem usually provides a bound on the original optimum. These methods are important both as stand-alone tools and as components of exact algorithms.

6.1 Linear relaxation

Linear relaxation replaces integrality requirements with continuous ones, producing a linear program when the remaining model is linear. The solution gives a bound and may also suggest promising integer decisions. Because linear programs can often be solved efficiently, they are a basic tool in discrete optimization.

6.2 Lagrangian relaxation

Lagrangian relaxation moves selected constraints into the objective function with penalty multipliers. This can decompose a hard problem into simpler parts while preserving useful bounds. The method is often combined with subgradient procedures or other techniques for adjusting multipliers.

6.3 Convex relaxation

Convex relaxation replaces a difficult feasible region with a convex superset. The relaxed problem is then easier to analyze and optimize. Convex relaxations are especially valuable when strong bounds are needed for nonlinear or nonconvex discrete models.

6.4 Surrogate relaxation

Surrogate relaxation combines multiple constraints into a smaller number of aggregated constraints. The resulting model may be simpler while still retaining much of the original structure. It is often used to obtain bounds or to guide search procedures.

7 Approximation and heuristic methods

Approximation and heuristic methods seek good solutions efficiently when exact optimization is too costly. Approximation algorithms provide performance guarantees, while heuristics and metaheuristics focus on practical effectiveness. These methods are widely used in large-scale applications.

7.1 Greedy algorithms

Greedy algorithms build a solution step by step, making the locally best choice at each stage. They are simple and often fast, though not always optimal. For some problems, however, greedy strategies are provably effective and yield strong guarantees.

Local search begins with an initial feasible solution and repeatedly improves it by making small changes. The method stops when no nearby move offers improvement, or when a stopping rule is met. Its success often depends on neighborhood design and initialization.

7.3 Metaheuristics

Metaheuristics are high-level strategies that guide heuristic search toward promising regions of the solution space. They are designed to balance exploration and exploitation, helping avoid poor local optima. Common examples include methods inspired by physical annealing, memory structures, and biological evolution.

7.3.1 Simulated annealing

Simulated annealing allows occasional worsening moves, especially early in the search, to escape local minima. A cooling schedule gradually reduces this randomness. The method is known for its simplicity and broad applicability.

Tabu search uses memory to prevent cycling and encourage exploration of new regions. Recently visited moves or solutions are temporarily forbidden, or tabu, unless special conditions apply. This helps the algorithm avoid repeatedly returning to the same local optimum.

7.3.3 Genetic algorithms

Genetic algorithms maintain a population of candidate solutions and combine them through selection, crossover, and mutation. They are inspired by evolutionary principles and are suited to large, complex search spaces. Their performance depends heavily on representation and operator design.

7.4 Randomized algorithms

Randomized algorithms use random choices to guide search or construct solutions. Randomness can improve robustness, help escape poor patterns, and provide probabilistic guarantees in some settings. These methods are often integrated with deterministic components.

7.5 Heuristic design principles

Effective heuristics usually reflect problem structure, exploit good initial solutions, and balance speed with solution quality. They may include preprocessing, decomposition, adaptive neighborhoods, and restart strategies. Careful experimental testing is often essential because performance can vary widely across instance types.

8 Major application areas

Discrete optimization is used wherever decisions are structured, limited, and interdependent. Its applications span industry, infrastructure, computing, and scientific planning. Many of these problems involve trade-offs among cost, time, capacity, and reliability.

8.1 Scheduling

Scheduling allocates tasks to time periods, machines, people, or other resources. The goal is often to reduce delay, idle time, or total completion time while respecting constraints. Scheduling problems are common in manufacturing, services, and project management.

8.1.1 Job shop scheduling

Job shop scheduling assigns jobs with multiple operations to machines in a specified order. The challenge is to coordinate sequences so that resource conflicts are avoided and overall performance is improved. This class is known for its combinatorial complexity.

8.1.2 Resource allocation

Resource allocation distributes limited resources among competing activities. Examples include machine time, labor, memory, or budget. The problem typically involves balancing priorities and respecting capacity limits.

8.2 Routing and transportation

Routing and transportation problems determine how to move goods, people, or information through a network. They often combine cost minimization with feasibility conditions such as vehicle capacity, time windows, or delivery requirements. These problems are central in logistics and operations planning.

8.2.1 Vehicle routing

Vehicle routing asks how to design efficient routes for one or more vehicles serving a set of locations. Variants may include capacity limits, service times, and depot constraints. The problem has wide practical importance in distribution and delivery systems.

8.2.2 Traveling salesperson problem

The traveling salesperson problem seeks the shortest tour that visits a set of locations exactly once and returns to the start. It is one of the best-known problems in discrete optimization and a standard benchmark for exact and heuristic methods. Its structure has inspired many theoretical and computational advances.

8.3 Facility location

Facility location determines where to place warehouses, plants, service centers, or other facilities. The objective is often to minimize total opening and transportation costs while providing adequate service coverage. These models are widely used in supply chain design and public service planning.

8.4 Production planning

Production planning chooses what to produce, when to produce it, and in what quantities. Discrete models may account for setup decisions, inventory levels, and capacity constraints. The aim is to coordinate production efficiently over time.

8.5 Telecommunications and network design

Telecommunications and network design problems involve building or improving communication infrastructure. Typical decisions include which links to install, how to route traffic, and how to provide redundancy. Discrete optimization helps manage cost while maintaining performance and resilience.

8.6 Energy systems

Energy systems use discrete optimization for unit commitment, transmission planning, storage coordination, and maintenance scheduling. Many such problems involve on/off decisions and network constraints. The models help operators manage reliability and cost in complex systems.

8.7 Computer science and machine learning

In computer science, discrete optimization appears in data clustering, compiler design, VLSI layout, and algorithmic resource management. In machine learning, it can support feature selection, structured prediction, and certain combinatorial learning tasks. These applications often require scalable methods due to large data sets and model sizes.

9 Software and computational tools

Discrete optimization relies heavily on software that can represent models, solve them, and analyze their performance. Modern tools combine mathematical programming engines with user-friendly modeling environments. Benchmarking and testing are also important for comparing methods.

9.1 Optimization solvers

Optimization solvers are programs that compute solutions to linear, integer, mixed-integer, and nonlinear models. They may use branch-and-bound, cutting planes, interior-point techniques, or specialized network algorithms. Commercial and open-source solvers are widely used in both research and industry.

9.2 Modeling languages

Modeling languages allow users to describe optimization problems in a high-level notation rather than coding algorithms from scratch. They separate the mathematical formulation from the solution process, making models easier to maintain and modify. This abstraction is especially helpful for large-scale applications.

9.3 Branch-and-cut implementations

Branch-and-cut implementations integrate search, relaxation, and cut generation into a unified framework. They are often highly engineered, with sophisticated preprocessing, heuristics, and parallel features. Such systems are among the most powerful tools for exact discrete optimization.

9.4 Benchmark instances

Benchmark instances are standard test problems used to evaluate algorithms. They help researchers compare performance, identify strengths and weaknesses, and track progress over time. Well-curated benchmarks are essential for reproducible computational research.

10 History and development

Discrete optimization developed from early work in mathematics, economics, and operations research. Its growth was shaped by advances in algorithm design, complexity theory, and computing power. Over time, the field evolved from manual reasoning and small-scale methods to highly sophisticated computational frameworks.

10.1 Early combinatorial methods

Early combinatorial methods focused on enumeration, graph reasoning, and ad hoc procedures for planning and allocation. Many of these ideas arose in transportation, military logistics, and scheduling. They laid the groundwork for later formal theories.

10.2 Rise of integer programming

Integer programming became a major discipline with the development of linear programming and the recognition that many practical decisions require integrality. As theory advanced, researchers introduced branching, cutting, and polyhedral methods. These ideas transformed discrete optimization into a systematic mathematical field.

10.3 Modern computational optimization

Modern computational optimization combines mathematical modeling with powerful solvers and extensive computational testing. Improvements in hardware, software engineering, and algorithmic techniques have made it possible to solve larger and more realistic instances than before. Hybrid methods that mix exact and heuristic components are now common.

10.4 Current research directions

Current research explores stronger formulations, faster exact algorithms, improved approximation methods, and scalable heuristics. Other active areas include robust optimization, stochastic variants, learning-enhanced optimization, and parallel computation. The field continues to expand as applications become larger and more interconnected.