# Optimization Problems

Pascal Francq

January 23, 2012 (April 20, 2011)

## 1 Definition

*class*, e.g. “Bin Packing”, and an

*instance*representing a special type of a problem, e.g. “the Bin Packing problem involving size 5 boxes for 25 objects of different sizes”. Secondly, two categories of problem classes exist: the

*abstract problem classes*and the

*concrete problem classes*. As its name suggests, the second category refers to problems that have a “concrete existing”, i.e. problems for which instances can be created. The BPP corresponds to this category. Together, it is part also of a more abstract class: grouping problems. With abstract problem classes only, it is impossible to define instances. In fact, as shown in Figure 1↓, abstract and concrete problem classes form a hierarchy of optimizing problems.

## 2 Algorithms

*complexity*, , of an algorithm defines a relationship between the size of an instance, such as the number of objects in the Bin Packing Problem, and the necessary resources to solve it, i.e. the amount of memory and number of CPU cycles required. A complexity of for example signifies that the resources required evolute as the square of the size of the instance, i.e. an instance two times larger than another one needs four times more resources.

## 3 Heuristics

## 4 Meta-heuristics

*cost functions*which are, most of the time, a mathematical expression that represents the quality of a solution for a given problem. A brief introduction to simulated annealing and tabu search ends this section. Another meta-heuristic known as the genetic algorithms will be presented in the next sections.

## 5 Multiple Objective Problems

### 5.1 Definition

*multi-criteria decision problems*.

### 5.2 Exact and Approximate Problems

*exact*

*multi-criteria problem*as a problem where the aim is characterized by a set of well-defined criteria; each criterion can be accurately expressed by a function and each function must either be maximized or minimized.

*approximate*

*multi-criteria problem*as a problem where the aim cannot be accurately characterized in any way. A set of criteria is defined to approximate the characteristics of the target without guaranteeing an exact match between the criteria and the characteristics. Each criterion defines a function that must either be maximized or minimized.

### 5.3 Solve Multiple Objective Problems

*Pareto front*is illustrated in Figure 2↓, where five solutions , , , and are represented for a problem with two criteria, and . The solution, , is not dominated by any other solution, i.e. it is not possible to improve one criterion without downgrading another. This solution is called a

*Pareto optimal*. All the Pareto optimum form the so-called Pareto-optimal front.

## 6 Related

## References

[1] Christos H. Papadimitriou & Kenneth Steiglitz, *Combinatorial Optimization, Algorithms and Complexity*, Prentice-Hall, 1982.

[2] Michael Garey & David Johnson, *Computers and Intractability — A Guide to the Theory of NP-completeness*, W.H. Freeman Co., 1979.

[3] Alan Turing, “On Computable Numbers, With an Application to the Entscheidungsproblem”, In *Proceedings of the London Mathematical Society*, pp. 230—265, 1936.

[4] Jon Kleinberg, “Authoritative Sources in a Hyperlinked Environment”, *Journal of the ACM*, 46(5), pp. 604—632, 1998.

[5] Vilfredo Pareto, *Cours d’économie politique*, F. Rouge, 1988.

[6] Jean-Pierre Brans & Bertrand Mareschal, ”The PROMCALC & GAIA Decision Support System for Multicriteria Decision Aid”, *Decision Support Systems*, 12(4‑5), pp. 297—310, 1994.