Algorithm Design and Evaluation - 15

The branch-bound technique can be applied to solve the given problem if it is possible to find a function g defined on the set of all partial solutions of the problem that satisfies the following inequality:

g(a 1 , a 2 , ..., ak) min{f(x): x  D, x i =a i , i= 1,2, ..., k } (*)

for all partial solutions ( a 1, a 2 , ..., a k ) , and for all k = 1,2,...

The inequality (*) means that the value of the function g at the partial solution (a 1 , a 2 ,

..., a k ) is not greater than the minimum value of the problem's objective function on the subset of solutions

D(a 1 , a 2 , ..., a k ) = { x D :x i = a i , i = 1, 2, ..., k}

or in other words, g(a 1 , a 2 , ..., a k ) is the lower bound of the objective function value on the set D(a 1 , a 2 ,..., a k ). For that reason, the function g is called the lower bound function , and the value g(a 1 , a 2 , ..., a k ) is called the lower bound of the set D(a 1 , a 2 ,..., a k ) . Since we can identify the set D(a 1 , a 2 ,..., a k ) with the partial solution (a 1 , a 2 ,..., a k ) , we also call the value g(a 1 , a 2 , ..., a k ) the lower bound of the partial solution (a 1 , a 2 , ..., a k ).

Suppose we have a function g. We consider how to use this function to reduce the amount of searching in the process of searching all solutions according to the backtracking algorithm. In the process of listing the solutions, some solutions to the problem may have been obtained. Let x * be the solution with the smallest objective function value among the solutions found,

f

denoted by f * = f(x * ) . We will call x * the best available solution, and 

is a record. Suppose

we have f * . Then if

g(a 1 , a 2 , ..., a k ) > f *

then from inequality (*) we get

f * < g(a 1 , a 2 , ..., a k ) min {f(x): x  D, x i =a i , i= 1,2,..., k } ,

Therefore, the subset of solutions to the problem D(a 1 , a 2 ,...,a k ) certainly does not contain an optimal solution. In this case, we do not need to continue developing the partial solution (a 1 , a 2 ,...,a k ) , in other words, we can eliminate the solutions in the set D(a 1 , a 2 ,...,a k ) from the search process.

The backtracking algorithm lists the options that need to be revised as follows Try(k)

/* Develop partial solutions (a 1 , a 2 ,...,ak) using the backtracking algorithm with lower bound checking before continuing to develop the solution */

{

for a k A k do

if (<accept a k >)

{

x k = a k ;

if(k == n)

<update record>; else

if(g((a 1 , a 2 ,...,a k ) f * )

Try(k+1)

}

}

Then, the branch technique is performed as follows: Branch_near()

{

f * = ;

/* If we know a solution x * we can set f * = f(x * ) */ Try(1);

if (f * < )

< f * is the optimal value, x * is the optimal solution > else

<problem has no solution>;

}

Note that if in the Try function we replace the statement if(k == n)

<update record>; else

if(g((a 1 , a 2 ,...,a k ) f * )

Try(k+1)

by :

if(k == n)

<update record>; else

Try(k+1)

The Try function will list all the solutions of the problem, and we get the exhaustive search algorithm. The construction of the g function depends on each specific combinatorial optimization problem.

body. Usually we try to build it so that:

 Calculating the value of g must be simpler than solving the combinatorial optimization problem on the right side of (*).

 The value of g ( a 1 , a 2 ,..., a k ) must be close to the value of the right side of (*). However, these two requirements are often contradictory in practice.

5.2. Application examples

5.2.1. The tourist problem

1) Problem

A tourist wants to visit n cities numbered 1, 2, ...,

n. Starting from a certain city, the tourist wants to visit all the remaining cities, each city exactly once, and then return to the starting city. Knowing cij is the cost of going from city i to city j (i, j = 1, 2,…, n) , find the itinerary (a way of going that satisfies the given conditions) with the smallest total cost.

Problem analysis :

With such content of the problem, it is very difficult to visualize its model, we will analyze and bring it to a general form. There are two factors that need to be determined and pointed out: Set D and objective function F(x).

We can set up a 1-1 correspondence between the journeys.

 (1) ->  (2) ->…->  (n)->  (1)

with a permutation  = (  (1),  (2) ,…,  (n)) of n natural numbers 1, 2, …, n. Let F(  ) = c  (1,  (2) + ... + c  (n-1),  (n) + c  (n),  (1)

and denote D by the set of all permutations  = (  (1),  (2),…,  (n)) of n natural numbers 1, 2,

…, n. Then the problem is reduced to the following general form:

min { F(  ) :   D }.

2) Algorithm design

The tourist problem leads to the problem: Find the minimum of the function:

f(x 1, x 2 , x 3 ,...,x n ) = c[x 1 , x 2 ] + c[ x 2 , x 3 ] +...+ c[ x n-1 + x n ] + c[ x n , x 1 ]

Given that (x 1 , x 2 , x 3 ,...,x n ) is a permutation of the numbers 1, 2, 3,..., n.

input: cost matrix C = (c ij )

output: optimal solution x * and f * =f(x * ) The try() function can be sketched as follows: Try (i)

{

for (j = 1 -> n)

if( Accept J )

{

Determine xi according to j; Record state; if(i == n)

Update optimal solution;

else

{

}

Determine the limit g(x 1 ,..., xi );

if( g(x 1 ,..., xi ) ≤ f* ) Try (i+1);

Return status;

}

}

- Determine the limit g( x1 ,..., xi )

The notation Cmin = min{c[ i, j ], i, j = 1,2,...,n, i  j } is the minimum travel cost between cities.

Suppose we have a partial plan (u 1 , u 2 ,...,u i ). This plan corresponds to a partial trip through i cities:

u 1 u 2 ... u i-1 u i

So the cost to pay for this part of the journey will be

= c[u 1 ,u 2 ] + c[u 2 ,u 3 ] + ...+ c[u i-1 ,u i ].

To develop this partial journey into a complete journey, we still have to go through nk remaining cities and then return to city u1 , which means we still have to go through n-i+1 more roads.

Since the cost of going through each of the remaining n-i+1 segments is not less than cmin, the lower bound for the partial solution (u 1 ,u 2 ,..,ui) can be calculated by the formula

g(u 1 , u 2 ,..., ui) =  + (n-i+1).cmin

- The acceptable condition of j is that city j has not been through. We use an array Daxet[] to represent this state with the convention:

+ Daxet[j] = 0 : city j has not been visited

+ Daxet[j] = 1: city j has been passed through

The Daxet[] array is initialized to 0 (all elements are 0)

- Determine xi according to j using the command: xi = j

- Record status: Daxet[j] = 1.

- Update the cost when xi is determined: S = S+ C xi −1,xi

- Update optimal solution:

Calculate the cost of the trip just found: Tong = S + C xn, 1 ;

If (Tong < f*) then

x * = x;

f* = Total;

- Restore status:

Daxet[j] = 0.

Return old cost: S = S- C xi −1,xi

- We fix the starting city as city 1.

Functions : Init()

/* Function to calculate cmin, Initially all cities are unvisited; Initialize optimal values, starting from city 1*/

{

Cmin = maxint;//Minimum cost between 2 cities for(i = 1; i <= n; i++)

Daxet[i] = 0; for(i = 1; i <= n; i++)