Desktop version

Home arrow Engineering

  • Increase font
  • Decrease font


<<   CONTENTS   >>

: Mathematical Modeling for Problems in Elastic Optical Networks

An optimization problem is used to find the best solution from all feasible solutions. The best solution can be the minimum or maximum solution. An example of the former is finding the route from point A to point В that takes the minimum time. An example of the latter is determining how a production factory can maximize its profit by using limited materials. Both problems are optimization problems. An optimization problem can be solved by mathematical programming, a technique that expresses and solves problems as mathematical models. This chapter starts with a general description of optimization problems, and then presents different integer linear programming formulation for problems in elastic optical networks (EONs).

Basics of Linear Programming

Optimization Problem

A person wants to travel from city A to city B. He can travel either by airplane or train. How can he travel with the minimum cost given the following conditions? The conditions are (i) condition 1: The price for a one-way ticket should not exceed 150$, (ii) condition 2: He should arrive at city В by 11:10 am, and (iii) condition 3: He should depart city A after 8:00 am. He checks the airplane and train schedules, which are mentioned in Table 11.1. The person can choose

Table 11.1: Transportation details.

Choice

Transportation

Departure time

Arrival time

Price ($)

1

Airplane

7:25 am

8:40 am

134.70

2

Airplane

9:50 am

11:05 am

136.70

3

Airplane

10:45 am

12:00 am

136.70

4

Train

7:56 am

10:36 am

138.50

5

Train

8:03 am

11:03 am

135.50

6

Train

8:20 am

10:56 am

138.50

7

Train

8:30 am

11:06 am

138.50

8

Train

8:33 am

11:30 am

135.50

one choice from eight choices by satisfying all conditions while maintaining the minimum cost. As all the prices in Table 11.1 are less than 150$, they satisfy condition 1. As for condition 2, choices 3 and 8 are not considered since they arrive after 11:10 am. For condition 3, choices 1 and 4 are not considered since their departure times are before 8:00 am, and arriving at city В at 11:03 am, and spending 135.50$.

An optimization problem consists of three components, namely decision variables, objective function, and constraints. In case of the above example, the decision variables are type of transportation, departure time, arrival time, and price. The objective function is the price. The constraints are conditions 1, 2, and 3. In the following, a mathematical model can be established that considers all three components.

Decision variables are the variables within a model that can be controlled. If there are n decision variables, they are represented as .V| ,x2, ■ ■ ■ ,xn. Objective function is the function that we want to maximize or minimize. An objective function is written as f{x,x2, ■ ■ ■ ,x„). If we want to maximize this function, we write as maxXhX2t...tXiif(x,X2,--- ,x„). If we want to minimize this function, we write as minXljX2!... iXiif(xi ,x2,■■■ ,x„). Constraints are conditions or limitations of the problem.

 
<<   CONTENTS   >>

Related topics