Location Problems with Multiple Criteria - Location Science - page 227

X

N

y j D p; (9.9)

jD1

x ij 2f 0;1 g ;y j 2f 0;1 g ; i 2 I; j 2 J: (9.10)

As it is usual, v-min stands for vector minimum of the considered objective
functions. Here variable y j takes the value 1 if plant j is open and 0 otherwise. The
binary variable x ij is 1 if the demand point i is assigned to plant j and 0 otherwise.
Constraints ( 9.7 ), together with integrality conditions on the x variables, ensure
that each demand point is assigned to exactly one plant, while constraints ( 9.8 )
guarantee that no demand point is assigned to a non-open plant. Finally, constraint
( 9.9 ) ensures that exactly p plants are opened.
Recall that in the single criterion case the integrality conditions on the x variables
need not be explicitly stated. The reason is that when the x ij represent the proportion
of demand of client i satisfied by plant j (i.e. 0 x ij 1), there exists an optimal
solution with x ij D 0;1, i 2 I, j 2 J This property is not necessarily true when
multiple criteria are considered because, in general, there might be undominated
solutions with non-integer values and even non-supported undominated integer
solutions.

9.4.2 Determining the Entire Set of Pareto-Optimal Solutions

In order to characterize the set of Pareto locations of the p-MP we shall use
rational generating functions. Short rational generating functions were used by
Barvinok ( 1994 ) as a tool to develop an algorithm for counting the number of integer
points inside convex polytopes, based on the previous geometrical paper by Brion
( 1988 ). The main idea is to encode those integer points in a rational function of
as many variables as the dimension of the space where the polytope is defined.
Let P

n
C

R be a given convex bounded polyhedron. Its integer points may be

expressed in a formal sum f.P; z / D P Ǜ z Ǜ with Ǜ D .Ǜ 1 ;:::;Ǜ n / 2 P \

n ,where
z Ǜ D z Ǜ 1 z Ǜ n n Barvinok's goal was to represent that formal sum of monomials in
the multivariate polynomial ring

Z

Œ z 1 ;:::; z n , as a “short” sum of rational functions
with the same variables. Actually, Barvinok ( 1994 ) developed a polynomial-time
algorithm when the dimension, n, is fixed, to compute those functions. A clear
example is the polytope P D Œ0;T

Z

R with T 2 N : the long expression of

the generating function of the integer points inside P is f.P; z / D P iD0 z i ,andit
is easy to see that its representation as sum of rational functions is the well known
formula .1 z T C1 /=.1 z /.
The above approach, apart from counting lattice points, has been used to develop
some algorithms to solve integer programming problems exactly. Specifically,
De Loera et al. ( 2004 , 2005 ), and Woods and Yoshida ( 2005 ) presented different