Optimization involves the use of techniques or tools to improve performance, enhance scalability, and increase the efficiency of data structures.
Examples:
Indexing techniques and sorting are the most commonly used optimization techniques in data structures.
Optimization Problems:
An optimization problem in data structures is one in which, by imposing certain constraints or conditions, we must either maximize or minimize the input dataset.
In such types of problems, the goal is to find the best solution among all possible feasible solutions.
An optimization problem consists of three components:
- An objective function
- Constraints
- Decision variables.
The representation of any real-world problem in terms of mathematical equations, variables, along with an objective function, decision variables, and constraints, formulates the optimization problem.
These varying elements divide the optimization problem into different categories.
Based on the nature of the variable (continuous or discrete):
- Continuous variable optimization problem
- Discrete variable optimization problem
Discrete variable optimization problems are more complex compared to continuous variable optimization problems. The objective of a discrete variable optimization problem is to find an object from a defined set, which could be an integer, a graph, or even a permutation. Most discrete optimization problems produce a sequence of continuous problems, which is why continuous optimization problems are a part of discrete optimization.
Based on the constraints on variables:
- Constrained optimization problem
- Unconstrained optimization problem
In an unconstrained optimization problem, there are no restrictions on variables; they can take any value. In contrast, variables in constrained optimization problems have restrictions, and they can only assume particular values from the set of available values.
Number of objective functions used in the problem:
- Single objective function optimization problem
- Multi-objective function optimization problem
Optimization problems that involve multiple objective functions are mostly encountered in the fields of economics, engineering, and logistics. Multi-objective optimization problems are reframed into a single objective optimization problem.
Type of the input dataset:
- Deterministic optimization
- Stochastic optimization
In deterministic optimization problems, the input data is known precisely, whereas stochastic optimization problems involve uncertain data. Uncertainty in the dataset arises from errors in measurement or from data that describes future events.
Classification of Optimization Problems:
- Linear programming
- Quadratic programming
In linear programming, the objective function and all constraints are linear in nature. On the other hand, quadratic programming uses a quadratic objective function and one or more linear constraints. Linear programming is employed to model complex real-life problems in various research fields.
Quadratic programming is used to either minimize or maximize a quadratic objective function. It finds applications in image processing, financial portfolio optimization, chemical plant scheduling, and statistics.
Dr. D.Y. Patil School of Science and Technology, Tathewade campus, Pune, offers a B.Tech. program in "Artificial Intelligence and Data Science" and "Computer Science and Design," which includes in-depth study of optimization techniques.