2-Approximation and Hybrid Genetic Algorithm for Long Chain Design Problem in Process Flexibility - Intelligent Computing for Sustainable Energy and Environment - page 233

The problem can be formulated as the following mixed 0-1 LP.
( P )min f ( x )=
i∈I

d i,j x i,j

j∈J

x i,j =2 j ∈ J (1)

i∈I

x i,j =2 i ∈ I (2)

j∈J

x i,j ≥ 1 U ⊂ I,V ⊂ J, 1 < | U | = | V | <n (3)

V

i∈U

j∈

x i,j ∈{ 0 , 1 } i ∈ I,j ∈ J (4)

Constraints (1) and (2) guarantee that each produce is satisfied exactly by two
plants and each plant produce two products. Constraints (3) eliminate short
chain solutions. This formulation contains 2 n variables and 2 n + n− 1

i =1 ( C n ) 2
constraints. Although, it can be transformed into a 2 n nodes symmetrical TSP,
the equivalent TSP formulation doesn't hold the triangle inequality property.

2.2 Problem Complexity
Proposition 1. Long chain design problem is NP-complete.
Proof. Let us first show that the long design problem is in NP, i.e., there is an
certificate-checking algorithm such that for any yes instance of its recognition
version problem, there exist a polynomial length certificate which can be checked
by the certificate-checking algorithm in polynomial time. Since its recognition
version problem is of the following form:
Given an instance with parameters

= n ,matrix [ d i,j ] n×n and an
number L , is there a feasible solution x such that f ( x )

| I | = | J |

L ?
Suppose we are given a yes instance ( n, [ d i,j ] n×n ,L ) of the long chain prob-
lem, then we can construct the polynomial length certificate x as a list of the
nodes which forms a long chain. This certificate can be checked eciently for
validity, because we only need to check whether n, [ d i,j ] n×n and L are appropri-
ate, whether x forms a long chain, and whether its total length f ( x )islessthan
or equal to L . The certificate-checking algorithm will reach the answer yes at
O ( n 2 ) steps. Hence, the long chain design problem is in NP.
Next we will show that any instance of Hamilton circuit problem can be
polynomially transformed to a instance of long design problem. Given any in-
stance of Hamilton circuit problem with graph G =( V,E )and

≤

| V | = n ,we

construct an instance of long chain design problem by letting | I | = | J | = n ,

E =( i,j ) , ∀ i,j ∈ V and

⎧
⎨

0if i = j,
1if( i,j ) d i,j = E,

M otherwise .

∈

⎩