Fact-checked by Grok 2 weeks ago

Optimization problem

An optimization problem, also referred to as a mathematical programming problem, is the task of selecting the best solution from a finite or infinite set of feasible alternatives, typically by minimizing or maximizing a specified objective function subject to given constraints.^[1] This process involves decision variables that represent the choices to be made, an objective function that quantifies the performance or cost of those choices, and constraints that define the allowable region for the variables, ensuring the solution remains practical and feasible.^[1] Optimization problems arise across diverse fields, from engineering and economics to machine learning, where they enable efficient resource allocation, design improvement, and decision-making under limitations.^[1] The core components of an optimization problem include the objective function, which is a mathematical expression (often linear or nonlinear) to be optimized; the decision variables, which are the unknowns adjusted to achieve optimality; and the constraints, which can be equality or inequality conditions bounding the variables.^[1] Problems are classified as constrained if restrictions apply or unconstrained if variables can take any value in their domain, with the latter often focusing on continuous real-valued functions.^[1] Maximization tasks can be reformulated as minimization by negating the objective function, a standard technique that unifies the framework.^[2] Optimization problems encompass several major types, including linear programming, where both the objective and constraints are linear, solvable via methods like the simplex algorithm developed by George Dantzig in 1947; nonlinear programming, addressing curved relationships; integer programming, restricting variables to whole numbers for discrete scenarios like scheduling; and convex optimization, which guarantees global optima for convex functions and includes applications in least-squares fitting.^[1] Discrete or combinatorial optimization deals with finite, often computationally challenging sets of options.^[1] These categories highlight the field's breadth, with convex problems being particularly tractable and widely used in engineering design and data analysis.^[2] Historically, systematic optimization emerged in the mid-20th century with linear programming's resolution in the late 1940s, but roots trace to earlier calculus-based methods for unconstrained problems.^[1] Today, optimization drives advancements in fields like network design, resource allocation, and artificial intelligence, where algorithms minimize errors in models or maximize efficiency in systems.^[1] Despite its power, many problems—especially nonconvex or large-scale ones—remain computationally intensive, spurring ongoing research into approximation techniques and specialized solvers.^[2]

Definition and Formulation

Basic Definition

In mathematics and engineering, an optimization problem is fundamentally a decision-making process that involves selecting inputs, known as decision variables, from a predefined set to extremize—either minimize or maximize—an objective function that quantifies the performance or desirability of those inputs.^[3]^[4] The objective function can be scalar, providing a single measure of outcome, or vector-valued in cases involving multiple conflicting goals.^[5] This formal approach contrasts with everyday usage of "optimization," where the term often describes informal efforts to improve efficiency in personal routines, business operations, or resource allocation without the structured analysis of mathematical models.^[6]^[7] Central to any optimization problem are the concepts of feasible solutions and optimal solutions. A feasible solution consists of values for the decision variables that satisfy all specified conditions, such as resource limits or operational requirements, forming the allowable domain from which selections are made.^[8]^[9] An optimal solution, in turn, is the feasible solution that yields the best possible value of the objective function, representing the "extremum" sought in the problem.^[5]^[8] The search space outlines the overall domain for these variables, while constraints delineate the subset of feasible options within it. The roots of optimization problems as a formal field trace back to the 1940s in operations research, emerging from efforts to solve logistical challenges during and after World War II, with George Dantzig's 1947 invention of the simplex method for linear programming marking a pivotal advancement in systematizing such problems.^[10]^[11] This conceptual framework establishes the abstract structure essential for exploring specific instances, such as those in various domains or under particular constraints, without delving into algorithmic resolutions.^[12]^[13]

Standard Formulation

An optimization problem is generally formulated as the task of finding a point x in a set X that minimizes (or maximizes) an objective function f: X \to \mathbb{R}.^[14] This standard structure encompasses both minimization and maximization problems, where maximization of f is equivalent to minimization of -f.^[15] The objective function f maps elements from the domain X (often \mathbb{R}^n) to the real numbers, representing the quantity to be optimized.^[14] In the multi-objective case, the objective is a vector-valued function F: X \to \mathbb{R}^k, where trade-offs between objectives are analyzed via the Pareto front—the set of nondominated points where no feasible point improves all components of F without worsening at least one.^[15] Constraints define the feasible set within X and are classified as equality constraints h_j(x) = 0 for j = 1, \dots, p, inequality constraints g_i(x) \leq 0 for i = 1, \dots, m, or simple bounds l \leq x \leq u.^[14] The full standard formulation for a constrained minimization problem is thus

\begin{align*} \min_{x \in X} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \leq 0, \quad i = 1, \dots, m, \\ & h_j(x) = 0, \quad j = 1, \dots, p. \end{align*}

^[15]^[14] Unconstrained problems arise as a special case when m = p = 0, reducing to \min_{x \in X} f(x).^[14] Solutions are denoted using \arg\min or \arg\max for the optimizing point(s), which may not exist if the infimum (or supremum) is not attained; in such cases, the optimal value is the infimum \inf_{x \in X} f(x) (or supremum \sup_{x \in X} f(x)).^[15]^[14]

Search Space

General Search Space

In an optimization problem, the search space, also referred to as the domain, is defined as the set X comprising all possible values that the decision variables x can assume.^[16] This set X serves as the universal collection of candidate solutions over which the objective function is evaluated, independent of any specific constraints that might further restrict feasible choices.^[15] For instance, in continuous optimization, X = \mathbb{R}^n represents the n-dimensional real vector space, allowing decision variables to take any real-valued coordinates.^[15] In discrete settings, X might be the integer lattice \mathbb{Z}^n or the binary hypercube \{0,1\}^n, where variables are restricted to integer or binary values, respectively.^[16] The properties of the search space significantly influence the nature of optimization. It can be bounded, such as when confined to a compact subset like a box [x_{\min}, x_{\max}] \subset \mathbb{R}^n, or unbounded, as in the full \mathbb{R}^n or \mathbb{Z}^n.^[16] Connectivity varies: continuous spaces like \mathbb{R}^n are path-connected, enabling smooth traversals, while discrete spaces like \mathbb{Z}^n are disconnected, consisting of isolated points.^[15] Many search spaces possess a metric structure to quantify distances between points; for example, the Euclidean metric d(x, y) = \|x - y\|_2 applies naturally in \mathbb{R}^n, facilitating measures of proximity during exploration.^[15] The search space provides the foundational "universe" for optimization algorithms to explore potential solutions. Its size and complexity directly impact solvability: in high-dimensional settings, the exponential growth of the space leads to the curse of dimensionality, where the volume increases dramatically with dimension n, making exhaustive search computationally infeasible even for simple uniform sampling.^[16] This phenomenon, first articulated by Bellman, arises because the number of points needed to cover the space adequately scales exponentially, complicating convergence and increasing sensitivity to initial conditions. Examples of search spaces abound across problem types. Real vector spaces \mathbb{R}^n are common in engineering design, where variables represent continuous parameters like material densities.^[15] Integer lattices \mathbb{Z}^n appear in scheduling tasks with whole-number allocations.^[16] More abstract sets include the space of all permutations of n elements for problems like the traveling salesman, where solutions are orderings of cities, or the set of all subgraphs of a given graph for spanning tree optimization, encompassing all connected acyclic subsets of edges.^[17] Distinguishing between infinite and finite search spaces has profound implications for solution methods. Finite spaces, such as the n! permutations in combinatorial problems, allow in principle for complete enumeration, though this is impractical for large n due to exponential growth.^[17] Infinite spaces, like \mathbb{R}^n, preclude enumeration entirely, necessitating approximation techniques or convergence guarantees based on the space's topology and metric properties.^[15]

Feasible Search Space

In optimization problems, the feasible set, also referred to as the feasible region, is the subset of the overall search space that consists of all points satisfying the given constraints. It is formally defined as the set \{ x \in X \mid g_i(x) \leq 0 \ \forall i = 1, \dots, m, \ h_j(x) = 0 \ \forall j = 1, \dots, p \}, where X is the search space, g_i represent inequality constraint functions, and h_j represent equality constraint functions. This set delineates the valid solutions, excluding any points that violate the problem's restrictions. The properties of the feasible set depend on the form of the constraints. If the inequality constraints g_i are convex functions and the equality constraints h_j are affine, the feasible set is convex, meaning the line segment between any two feasible points lies entirely within the set. Convexity ensures desirable geometric properties, such as the absence of local optima distinct from global ones in convex problems. The feasible set is compact if it is closed and bounded, guaranteeing the existence of optimal solutions for continuous objective functions over it, as per the extreme value theorem.^[18] If the feasible set is empty, the problem is deemed infeasible, indicating no valid solution exists that meets all constraints simultaneously.^[19] Constraints shaping the feasible set are categorized as hard or soft. Hard constraints must be strictly satisfied, directly defining the boundaries of the feasible set, while soft constraints allow violations but incorporate penalties into the objective function to encourage compliance.^[20] They further divide into simple bounds, such as l \leq x \leq u on individual variables, and general constraints involving nonlinear or multivariable relations. The feasible set plays a central role in optimization, as candidate solutions are evaluated for optimality solely within its confines; optima can arise at interior points or on the boundary.^[19] Detecting whether the feasible set is nonempty is a preliminary step in solving constrained problems; for instance, in linear programming, a conceptual Phase I approach introduces auxiliary variables to ascertain feasibility without optimizing the original objective.^[21] In settings with uncertainty, such as parameter variations, robust feasibility extends the concept by requiring solutions to satisfy constraints across an entire uncertainty set, often via worst-case formulations to ensure reliability.^[22] This approach, prominent in robust optimization, addresses real-world variability absent in deterministic models.^[23]

Continuous Optimization Problem

Definition and Features

Continuous optimization involves finding values for real-valued decision variables that minimize or maximize a continuous objective function, subject to constraints defining a feasible region, typically over real numbers in \mathbb{R}^n.^[24] Unlike discrete optimization, the search space is infinite and continuous, allowing variables to take any value within their domain, often enabling the use of derivative-based methods for solution.^[24] Key features include the objective function f(x), which is often smooth (differentiable) and may be linear, quadratic, or nonlinear; equality or inequality constraints like c_i(x) = 0 or c_i(x) \geq 0; and bounds on variables.^[24] Problems can be unconstrained (no restrictions beyond the domain) or constrained, with convex formulations—where the objective is convex and the feasible set is convex—guaranteeing global optima via local searches.^[25] Algorithms exploit gradients or Hessians for efficiency, contrasting with enumeration in discrete cases, and include interior-point methods for large-scale problems.^[24] Common subtypes are linear programming (linear functions), quadratic programming (quadratic objectives with linear constraints), and nonlinear programming (general smooth functions).^[24] Challenges arise in nonconvex problems, where multiple local optima exist, requiring global optimization techniques like branch-and-bound or heuristics.^[24] The field emphasizes scalability for high-dimensional applications, with regularization terms often added to prevent overfitting in data-driven contexts.^[25]

Common Examples

Continuous optimization problems often model real-world scenarios with smooth relationships, such as resource allocation or parameter estimation.^[24] Least squares regression minimizes the sum of squared residuals \min_x \frac{1}{2m} \|Ax - y\|_2^2 to fit a linear model to data points (a_j, y_j), widely used in statistics and engineering for curve fitting.^[25] Ridge regression extends least squares by adding a penalty \min_x \frac{1}{2m} \|Ax - y\|_2^2 + \lambda \|x\|_2^2, where \lambda > 0 regularizes to handle multicollinearity in machine learning applications like predictive modeling.^[25] Portfolio optimization, as in Markowitz's mean-variance model, minimizes risk \min_w w^T \Sigma w subject to expected return constraints and w^T 1 = 1, balancing return and volatility in finance.^[24] Support vector machines (SVM) solve \min_{x, \beta} \frac{1}{m} \sum_j \max(1 - y_j (a_j^T x - \beta), 0) + \frac{\lambda}{2} \|x\|_2^2 for classification, maximizing margins in pattern recognition tasks.^[25] Nonlinear examples include minimizing drag coefficient in vehicle design via aerodynamic simulations or optimizing control systems in engineering, where objectives involve nonlinear dynamics.^[24]

Combinatorial Optimization Problem

Definition and Features

Combinatorial optimization constitutes a subfield of discrete optimization focused on selecting the best element from a finite set of discrete objects, where the feasible solutions correspond to structures such as subsets, permutations, or graphs.^[26] The search space X is inherently finite and discrete, often comprising configurations that grow exponentially in cardinality with the problem size n, such as |X| = n! for permutations or $2^n for subsets.^[26] Many canonical problems in this domain, including the traveling salesman problem and graph coloring, are NP-hard, implying that exact solutions cannot be guaranteed in polynomial time unless P=NP.^[26]^[27] Key features of combinatorial optimization include the absence of differentiability in the objective function, necessitating algorithms that avoid gradient-based methods and instead employ exact techniques like enumeration for small instances or branch-and-bound for structured problems.^[28] Approximations and heuristics, such as metaheuristics or linear programming relaxations, are commonly used for scalability, with integrality constraints implicitly enforced by the discrete domain rather than explicit continuous bounds.^[29] The field draws from combinatorics, algorithms, and integer programming to navigate these challenges.^[29] Prominent subtypes encompass integer programming, where decision variables are constrained to integers x \in \mathbb{Z}^n to model discrete choices; the set covering problem, which minimizes the number of selected sets to cover a universal set; and the matching problem, which maximizes pairings in a graph while avoiding shared vertices.^[30]^[31]^[32] These formulations highlight the reliance on finite enumerative structures, with the feasible set often representing discrete polyhedra that admit continuous relaxations for bounding purposes. Central challenges arise from the exponential growth of |X|, rendering exact solutions intractable for large n, a difficulty underscored by the P versus NP implications for decision versions of these problems.^[33]^[27] Solution concepts center on identifying an optimal subset, permutation, or graph configuration that extremizes the objective, while for NP-hard cases, approximation algorithms guarantee solutions within a bounded ratio of optimality, such as the 2-approximation for vertex cover, a covering problem.^[34]^[35] Emerging quantum-inspired approaches, like the Quantum Approximate Optimization Algorithm (QAOA), leverage variational quantum circuits to approximate solutions for combinatorial instances on near-term quantum devices.^[36] Understanding these requires familiarity with basic combinatorics, including measures like binomial coefficients \binom{n}{k} to quantify search space scales.

Common Examples

Combinatorial optimization problems frequently arise in discrete settings where decisions involve selecting or arranging finite sets of elements. Classic examples illustrate the challenge of optimizing over combinatorial structures, such as permutations, subsets, or assignments, within finite search spaces. These problems are typically NP-hard, highlighting their computational complexity.^[37] The Traveling Salesman Problem (TSP) requires finding a minimum-cost Hamiltonian cycle in a complete graph, where the vertices represent cities and the edge weights denote travel distances or costs, such that each city is visited exactly once before returning to the starting point. The decision variables correspond to permutations of the cities, emphasizing the discrete nature of sequencing in a finite set of possible tours. This problem exemplifies routing challenges in logistics and manufacturing.^[38] The 0-1 Knapsack Problem involves selecting a subset of items, each with a value v_i and weight w_i, to maximize the total value \sum v_i x_i subject to the capacity constraint \sum w_i x_i \leq W, where x_i \in \{0,1\} indicates whether item i is included. The binary decisions reflect the combinatorial choice of packing resources without fractions, common in applications like resource allocation and budgeting.^[39] Graph Coloring seeks the minimum number of colors needed to assign to the vertices of a graph such that no two adjacent vertices share the same color, with the decision space consisting of color assignments to vertices under adjacency constraints. This discrete assignment problem captures scheduling and resource partitioning tasks, where the finite palette of colors limits feasible configurations.^[40] The Maximum Matching Problem in a bipartite graph aims to select the largest possible set of edges with no two edges sharing a vertex, often applied to assignment scenarios like pairing workers to tasks. The objective is to maximize the cardinality of the edge set, with the search space exploring subsets of edges that respect vertex disjointness in the discrete graph structure.^[32] The Vehicle Routing Problem (VRP) generalizes TSP to multiple vehicles serving a set of customers from a depot, minimizing total travel cost while satisfying capacity and time constraints; variants include the capacitated VRP where vehicle loads are limited. In e-commerce logistics, post-2020 demand surges have amplified VRP's relevance for last-mile delivery, involving discrete route assignments across customer locations and vehicle fleets.^[41]^[42]

References

[1]
Mathematical Optimization - an overview | ScienceDirect Topics
Mathematical optimization is defined as the process of selecting the "best" solution from a set of alternatives based on a specified criterion, involving an ...Introduction to Mathematical... · Types and Categories of...
[2]
Introduction | SpringerLink
Jan 11, 2024 · Optimization is the way of achieving the best possible outcome given the degrees of freedom and the constraints. By degrees of freedom we mean ...Missing: sources | Show results with:sources
[3]
[PDF] Introduction to Mathematical Optimization
Mathematical optimization is making something 'best', which can involve maximizing or minimizing, and is a branch of applied mathematics.
[4]
Optimization - Calculus I - Pauls Online Math Notes
Nov 16, 2022 · Optimization problems seek the largest or smallest value of a function, often subject to a constraint, which is a condition that must be true.
[5]
Linear Programming Basics
... optimal solution and its objective function ... (For a maximization problem, it is unbounded if one can find feasible solutions who objective function value is ...
[6]
Optimization
Mar 5, 2011 · "In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize ...<|separator|>
[7]
[PDF] 1. WHAT IS OPTIMIZATION?
Optimization is maximizing or minimizing a function, often comparing choices to determine the 'best' option, such as minimal cost or maximal profit.
[8]
[PDF] Linear Programming
an optimal solution is the feasible solution that produces the best objective function ... components: decision variables, objective function, and constraints.
[9]
Optimization Characteristics - Analytica Docs
An optimization problem is defined by four parts: a set of decision variables, an objective function, bounds on the decision variables, and constraints.<|control11|><|separator|>
[10]
George Dantzig: Operations research phenom - Berkeley Engineering
George Dantzig, one of the founding fathers of industrial engineering and operations research, developed the simplex algorithm and was the first person to ...
[11]
George Dantzig (1914 - 2005) - Biography - MacTutor
George Dantzig was an American mathematical scientist who worked in operations research, computer science, economics and statistics. He is best known for ...
[12]
The Do's and Don'ts of choosing an Optimization Problem – OMSCS ...
Feb 19, 2024 · The fundamental components of an optimization problem include the objective function, decision variables, and constraints. The challenge in ...
[13]
Optimization | Department of Mathematics - UCSD Math
An optimization problem begins with a set of independent variables, and often includes conditions or restrictions that define acceptable values of the variables ...
[14]
[PDF] Numerical Optimization
Page 1. Numerical Optimization. Jorge Nocedal. Stephen J. Wright. Springer. Page 2. Springer Series in Operations Research. Editors: Peter Glynn Stephen M ...
[15]
None
Below is a merged summary of the standard formulation of convex optimization problems based on the provided segments from "Convex Optimization" by Boyd & Vandenberghe and related sections from https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. To retain all information in a dense and organized manner, I will use a combination of narrative text and a table in CSV format for detailed comparisons across the segments. The narrative will provide an overview, while the table will capture specific details such as general form, objective function, constraints, and other aspects for each segment.
[16]
[PDF] Multicriteria Optimization and Decision Making - LIACS
Here the search space is defined by a set of intervals, that restrict the range of variables, so called bounds or box constraints. Besides this, variables can ...
[17]
None
Below is a merged response that consolidates all the information from the provided summaries into a single, comprehensive summary. To maximize detail and clarity, I will use a table in CSV format to organize the key elements (Definition, Examples, Relevant Sections, and Useful URLs) while retaining all unique details from each segment. Following the table, I will provide a narrative summary that integrates the information cohesively.
[18]
[PDF] The generic optimization problem • Properties of functions and sets
Typically the constraint set is defined by in- equality and equality constraints, as well as the domain of the values of the decision variables, for e.g..
[19]
[PDF] Numerical Optimization - UCI Mathematics
This is a book for people interested in solving optimization problems. Because of the wide. (and growing) use of optimization in science, engineering ...<|control11|><|separator|>
[20]
[PDF] Solving Problems with Hard and Soft Constraints Using a Stochastic ...
In the language of operations research, the hard constraints specify the set of feasible solutions, and the soft constraints specify a function to be optimized ...
[21]
[PDF] Solving Linear Programs - MIT
All decision variables are constrained to be nonnegative. 2. All ... optimal solution; or shows that the objective function is unbounded over the ...
[22]
[PDF] A Practical Guide to Robust Optimization - arXiv
Jan 12, 2015 · There are two approaches to deal with data uncertainty in optimization, namely robust and stochastic optimization. Stochastic optimization (SO) ...
[23]
Robust and Data-Driven Optimization: Modern Decision Making U
[20] and Bertsimas and Sim [14, 15] have proposed a robust optimization approach based on polyhedral uncertainty sets, which preserves the class of problems ...
[24]
[PDF] Introduction to Combinatorial Optimization
Combinatorial optimization aims to find an optimal object from a finite set of objects, where feasible solutions are candidate objects.
[25]
What is Combinatorial Optimization?
Combinatorial optimization is the process of searching for maxima (or minima) of an objective function F whose domain is a discrete but large configuration ...
[26]
[PDF] COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP ...
The book should be suitable for use as a supplementary text in courses on algorithm design, computational complexity, operations research, or combinatorial ...
[27]
18.433 Combinatorial Optimization
This subject covers combinatorial optimization which deals with optimization problems defined on discrete structures.
[28]
[PDF] Combinatorial Optimization - University of Waterloo
Sep 18, 1997 · Combinatorial optimization is a lively field of applied mathematics, combining techniques from combinatorics, linear programming, and the ...
[29]
Integer Programming and Combinatorial Optimization
The course is a comprehensive introduction to the theory, algorithms and applications of integer optimization and is organized in four parts.
[30]
Set covering problem - Optimization Wiki
Dec 21, 2020 · The set covering problem, which aims to find the least number of subsets that cover some universal set, is a widely known NP-hard combinatorial ...Problem formulation · Integer linear program... · Approximation via LP...
[31]
[PDF] 1. Lecture notes on bipartite matching
Feb 2, 2013 · Matching problems are among the fundamental problems in combinatorial optimization. In this set of notes, we focus on the case when the ...
[32]
Design, Evaluation and Analysis of Combinatorial Optimization ...
Jul 7, 2012 · Unfortunately, many combinatorial optimization problems are NP-hard which usually means that they are unsolvable in practice. However, it is ...
[33]
Approximation algorithms for combinatorial problems - ScienceDirect
Simple, polynomial-time, heuristic algorithms for finding approximate solutions to various polynomial complete optimization problems are analyzed with respect ...
[34]
[1411.4028] A Quantum Approximate Optimization Algorithm - arXiv
Nov 14, 2014 · We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems.
[35]
Beyond fifty years of vehicle routing: Insights into the history and the ...
Jun 26, 2025 · Vehicle routing problems (VRPs) are a large class of well-studied and computationally hard combinatorial optimization problems.
[36]
[PDF] The Traveling Salesman Problem: An overview of exact and ...
The Traveling Salesman Problem (TSP) is one of the most widely studied combinatorial opti- mization problems. Its statement is deceptively.
[37]
(PDF) Knapsack Problems - ResearchGate
The multiple-choice knapsack problem (MCKP) is a generalization of the ordinary knapsack problem, where the set of items is partitioned into classes. The binary ...
[38]
Graph Coloring Problems | Wiley Online Books
Dec 3, 1994 · Graph Coloring Problems cover image. Graph Coloring Problems. Author(s):. Tommy R. Jensen, Bjarne Toft, ... PDF · References · Request permissions.
[39]
The Truck Dispatching Problem | Management Science - PubsOnLine
The paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations ...
[40]
(PDF) Optimized Vehicle Routing Problem for The Last Mile E ...
Feb 22, 2025 · This research addresses the Optimized Vehicle Routing Problem (VRP) for last-mile e-commerce parcel delivery using e-cargo bikes in a Central London case study ...