1

Basic Concepts in Optimization and Graph Theory

1.1. Introduction

An optimization problem is a formal specification of a set of proposals related to a specific framework that includes one or numerous decision makers, one or several objectives to be achieved and a set of structural constraints. Optimization has been practiced in numerous fields of study as it provides a primary tool for modeling and solving complex and hard constrained problems. After the 1960s, integer programming formulations and approximate approaches have received considerable attention as useful tools for solving optimization problems. Depending on the problem structure and its complexity, appropriate solution approaches were proposed to generate appropriate solutions in a reasonable computation time. Several optimization studies are formulated as a problem whose goal is to find the best solution, which corresponds to the minimum or maximum value of a single-objective function. The challenge of solving combinatorial problems lies in their computational complexity since most of them are non-deterministic polynomial-time (NP)-hard [GAR 79]. This complexity can mainly be expressed in terms of the relationship between the search space and the difficulty of finding a solution. The search space in combinatorial optimization problems is discrete and multidimensional. The higher the dimensionality, the larger the search space, and the harder the problem. The remainder of this chapter is organized as follows. In section 1.2, we highlight the terminology adopted throughout this book. Section 1.3 deals with the mathematical structure of an optimization problem and enumerates its main variants. Section 1.4 illustrates the previously announced principles by a didactic example. Section 1.5 outlines the main features of an optimization problem.

1.2. Notation

We present in the following the major symbols used for defining an optimization problem:

Symbols Description n the number of decision variables k the number of objectives x = (x1,...,xn)T the vector of decision variables c(p,n) the cost matrix A the matrix of constraints B Resources limitations EO The set of efficient solutions in the objective space ED The set of efficient solutions in the decision space

1.3. Problem structure and variants

Assuming the linearity of an optimization problem, its mathematical modeling is outlined as follows:

[1.1]

[1.2]

[1.3]

where x = (x1,.,xn)T denotes the vector of decision variables, p, b and A are constant vectors and matrix of coefficients, respectively.

Many variants of this formulation can be pointed out:

- Continuous linear programming (CLP): The optimization model [1.1]-[1.3] is a CLP if the decision variables are continuous. For continuous linear optimization problems, efficient exact algorithms such as the simplex-type method [BUR 12] or interior point methods exist [ANS 12]. - Integer linear programming (ILP): The optimization model [1.1]-[1.3] is an ILP if ? is the set of feasible integer solutions (i.e. decision variables are discrete). This class of models is very important as many real-life applications are modeled with discrete variables since their handled resources are indivisible (as cars, machines and containers). A large number of combinatorial optimization problems can be formulated as ILPs (e.g. packing problems, scheduling problems and traveling salesman) in which the decision variables are discrete and the search space is finite. However, the objective function and constraints may take any form [PAP 82]. - Mixed integer programming (MIP): The optimization model [1.1]-[1.4] is called MIP, when the decision variables are both discrete and continuous. Consequently, MIP models generalize the CLP and ILP models. MIP problems have improved dramatically of late with the use of advanced optimization techniques such as relaxations and decomposition approaches, branch-and-bound, and cutting plane algorithms when the problem sizes are small [GAR 12, WAN 13, COO 11]. Metaheuristics are also a good candidate for larger instances. They can also be used to generate good lower or upper bounds for exact algorithms and improve their efficiency.

1.4. Features of an optimization problem

Optimization problems can be classified in terms of the nature of the objective function and the nature of the constraints. Special forms of the objective function and the constraints give rise to specialized models that can efficiently model the problem under study. From this point of view, various types of optimization models can be highlighted: linear and nonlinear, single and multiobjective optimization problems, and continuous and combinatorial programming models. Based on such features, we have to define the following points:

- The number of decision makers: if one decision maker (DM) is involved, the problem dealt with is an optimization problem; otherwise we are concerned with a game that can be cooperative or non-cooperative, depending on the DMs' standpoints. - The number of objectives: it determines the nature of the solution to be generated. If only one objective is addressed in the decision problem, the best solution corresponds to the optimal solution. However, if more than one objective is considered, we went to generate a set of efficient solutions that correspond to some trade-offs between the objectives under study. - The linearity: when both the objective(s) and the constraints are linear, the optimization problem is said to be linear. In that case, specific solution approaches can be adapted as the simplex method. Otherwise, the problem is nonlinear in which case the resolution becomes more complex and the decision space is not convex. - The nature of the decision variables: if the decision variables are integer, we deal with a combinatorial optimization problem.

1.5. A didactic example

Let us consider the following optimization problem involving two decision variables x1 and x2. We show in this illustrative example how the solution changes in terms of the nature of the decision variables that can be either continuous or binary and the number of objectives k = 1, 2. Hence, four optimization problems follow:

As previously mentioned, the resolution of the single-objective optimization problem yields to the finding of the optimal solution that varies depending on the nature of the decision variables. However, if a second objective is added, the resolution generates a set of Pareto-optimal solutions, as it is the case for k = 2.

1.6. Basic concepts in graph theory

A graph G is defined as a couple of sets G = (V, E): a vertex set V and an edge set E.

- The vertex set states all involved entities that model the original problem. - The edge set is an exhaustive enumeration of all possible connections between two vertices. If e = {x, y} is an edge, we say "x is adjacent to y". A graph can also contain a loop whose endpoints are equal. Based on such features, we can point out numerous types connections in a graph: - Simple edge: a connection between two vertices x and y such that x ? y. It is modeled as a set of two nodes {x, y}. - Oriented edge: an edge represented by a couple of vertices (x, y). - Multiple edges: numerous edges having the same pair of vertices. - Loop: an edge whose endpoints are equal.

Figure 1.1. An example of a graph with n = 4 and e = 5

A simple graph is a graph that contains neither loops nor multiple edges. Simple graphs can be directed as shown in Figure 1.2(a), undirected as is the case of Figure 1.2(b) or/and weighted as shown in Figure 1.2(c). A weighted graph can designate a road network where each edge is labeled by the distance between the corresponding vertices. Weights can also express the traveling cost between two adjacent vertices.

Figure 1.2. Types of simple graphs

1.6.1. Degree of a graph

The degree of a vertex x in a graph G, denoted by dG(x), is the number of edges where x is one of their endpoints. Note that .

1.6.2. Matrix representation of a graph

An alternative representation of a graph is the matrix representation A that designates the adjacency matrix. It is a symmetric square matrix of order n if the graph is undirected. If the graph is weighted, the matrix reports the distances' values if the corresponding vertices are adjacent and 0 elsewhere. Table 1.1 corresponds to the matrix...