In
mathematics,
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
and
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analyzes ...
, an optimization problem is the
problem of finding the ''best'' solution from all
feasible solutions.
Optimization problems can be divided into two categories, depending on whether the
variables are
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
or
discrete
Discrete may refer to:
*Discrete particle or quantum in physics, for example in quantum theory
*Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit
*Discrete group, a g ...
:
* An optimization problem with discrete variables is known as a ''
discrete optimization
Discrete optimization is a branch of optimization in applied mathematics and computer science.
Scope
As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete varia ...
'', in which an
object
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ...
such as an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
,
permutation or
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
must be found from a
countable set.
* A problem with continuous variables is known as a ''
continuous optimization
Continuous optimization is a branch of optimization in applied mathematics.
As opposed to discrete optimization, the variables used in the objective function are required to be continuous variables—that is, to be chosen from a set of rea ...
'', in which an optimal value from a
continuous function must be found. They can include
constrained problems and multimodal problems.
Continuous optimization problem
The ''
standard form'' of a
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
optimization problem is
where
* is the
objective function
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
to be minimized over the -variable vector ,
* are called inequality
constraints
* are called equality constraints, and
* and .
If , the problem is an unconstrained optimization problem. By convention, the standard form defines a minimization problem. A maximization problem can be treated by
negating the objective function.
Combinatorial optimization problem
Formally, a
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
problem is a quadruple , where
* is a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of instances;
* given an instance , is the set of feasible solutions;
* given an instance and a feasible solution of , denotes the
measure
Measure may refer to:
* Measurement, the assignment of a number to a characteristic of an object or event
Law
* Ballot measure, proposed legislation in the United States
* Church of England Measure, legislation of the Church of England
* Mea ...
of , which is usually a
positive
Positive is a property of positivity and may refer to:
Mathematics and science
* Positive formula, a logical formula not containing negation
* Positive number, a number that is greater than 0
* Plus sign, the sign "+" used to indicate a posi ...
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010) ...
.
* is the goal function, and is either or .
The goal is then to find for some instance an ''optimal solution'', that is, a feasible solution with
For each combinatorial optimization problem, there is a corresponding
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
that asks whether there is a feasible solution for some particular measure . For example, if there is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
which contains vertices and , an optimization problem might be "find a path from to that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from to that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.
In the field of
approximation algorithms, algorithms are designed to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is more naturally characterized as an optimization problem.
See also
*
*
*
*
*
*
* − the optimum need not be found, just a "good enough" solution.
*
*
References
External links
*
{{Authority control
Computational problems