Location Problems with Multiple Criteria - Location Science - page 228

methods to solve this family of problems using Barvinok's rational function of the
polytope defined by the feasible set of the given problem.
First of all, for the sake of readability, we recall some results on short rational
functions for polytopes that shall be later used in our presentation. For further details
the interested reader is referred to Barvinok ( 1994 ), Barvinok and Woods ( 2003 ).
Let P Df x 2

n . The main idea
of Barvinok's Theory was to encode the integer points inside a rational polytope in
a “long” sum of monomials:

n W Ax b;x 0 g be a rational polytope in

R R

f.P; z / D X
Ǜ2P\ Z

z Ǜ ;

n

where z Ǜ D z Ǜ 1 z Ǜ n , and then to re-encode, in polynomial-time for fixed
dimension, these integer points in a “short” sum of rational functions in the form

f.P I z / D X
i2I

z u i

" i ;

n

Y

.1 z v ij /

jD1

n for all i

where I is a polynomial-size indexing set, " i 2f 1; 1 g ,and u i ;v ij 2 Z

and j (Theorem 5.4 in Barvinok and Woods 2003 ).
It is well-known that enumerating the entire set of Pareto-optimal solutions of
general multiobjective integer linear problems is #P-hard even in fixed dimension
(see, e.g., Ehrgott and Gandibleux 2002 and Chinchuluun and Pardalos 2007 ).
Therefore listing these solutions, in general, is hopeless. Nevertheless, one can try to
represent these sets in polynomial time using a different strategy by simply encoding
their elements in an efficient way. This strategy has been recently applied by Blanco
andPuerto( 2012 ). In that paper, it is proved that using short generating functions
of rational polytopes, one can encode the whole set of Pareto-optimal solutions of
MOILP in polynomial time, fixing only the dimension of the space of variables. As
an application of this result we can state the following theorem.

Theorem 9.10 Assume that the number of facilities M and plants N is fixed. Then,
in polynomial time, we can encode the entire set of Pareto-optimal solutions for
( 9.6 ) - ( 9.10 ) in a short sum of rational functions.

Proof Apply Theorem 1 in Blanco and Puerto ( 2012 ) to the polytope of Problem
( 9.6 )-( 9.10 ).

The combination of Theorem 9.10 and Theorem 7 in De Loera et al. ( 2009 )
results in the following theorem.

Theorem 9.11 Assume M and N are constant. There exists a polynomial-delay
polynomial-space procedure to enumerate the entire set of Pareto-optimal solutions
of ( 9.6 ) - ( 9.10 ) .