Polyhedral approach: the p median polytope

Mourad Baïou

Description

Polyhedral approach: the p-median polytope Mourad Baıou Laboratoire LIMOS, Universite Clermont II 31 janvier 2008

• minimum spanning


• xf ?


• ?tx ≤


• vector xf


• let ?tx


• maximum-weight matching

Informations

• Publié par: pefav
• Publié le: 01 janvier 2008
• Nombre de lectures: 18
• Langue: English

Extrait

Polyhedral approach: the p-median polytope
Mourad Ba¨ıou
Laboratoire LIMOS, Universit´e Clermont II
31 janvier 2008I. Polyhedral approach
Given a finite setE ={e ,e ,...,e }. LetF be a family of some particular
1 2 n
subsets of E (feasible solutions), and let c be a cost function, a mapping
c :E −→IR.
The problem
X
def
(P) : minimize {c(F) = c(e) :F ∈F},
e∈F
is called a combinatorial optimization problem.
Examples: Traveling Salesman problem, Maximum-Weight Matching
problem, Minimum Spanning Tree problem, ...
1Integer Polyhedra
F E
For every element F ∈F, associate a 0,1 vector x ∈{0,1} , defined as
follows:

1 if e∈F
F
x (e) =
0 otherwise,
F
x is called the incidence vector of F.
(P) may be rewritten as
T F F
(P) : minimize {c x :x ∈S},
where S is the set of incidence vectors of the elements of F.
2Convex hulls: The convex hull of a finite set S, denoted by conv(S), is the
set of all points that are a convex combination of points in S.
n n
Proposition 1. Let S ⊆IR be a finite set and let c∈IR . Then
T T
min{c x :x∈S} = min{c x :x∈ conv(S)}.
The set S
Conv(S)
3Polytopes:
n m
• P ={x ∈ IR : Ax≤ b} where A is an m×n matrix and b ∈ IR , is
called a polyhedron.
• A
polytope is a bounded polyhedron.
T T
• Aninequalityα x≤α isvalidforapolytopeP ifP ⊆{x : α x≤α }.
0 0
• The dimension of a polytope P, dim(P), is equal to the maximum
number of affinely independent points in P minus one.
T
• Let α x ≤ α be a valid inequality for the polytope P. F = {x ∈
0
T
P : α x = α } is called a face of P. F is a facet of P if dim(F) =
0
dim(P)−1.
4• x∈P is an extreme point of P if x is a face of P of dimension 0.
A valid inequality
extreme point
A valid inequality
that is a face
A facet
56
Two useful characterizations of extreme points are:
Characterization 1. x ∈ P is an extreme point of P if and only if there
1 1
1 2 1 2 1 2
do not exist x ,x ∈P, x =x , such that x = x + x .
2 2
Characterization 2. x ∈ P is an extreme point of P if x is the
unique solution of a subsystem of inequalities defining P when replaced
by equalities.
Theorem 1. A set P is a polytope if and only if there exists a finite set
S such that P is the convex hull of S.
By this theorem, the optimization over conv(S) is equivalent to the
optimization over a polytope.
6An example
Consider the following combinatorial optimization problem (P) formulated
as an integer linear program:
max x +x
1 2

subject to

−x +x ≤ 1

1 2
−13x +28x ≤ 72
 
1 2
−x +2x ≤ 4
 
1 2
−5x +4x ≤ 4
 
1 2
x −x ≤ 1

1 2
9x −4x ≤ 24 D =
1 2
x ≤ 4
P =

1
1
6x −5x ≤ 9
 
1 2
x ≥ 0


1
x ≥ 0
 
1
x ≥ 0

2
x ≥ 0
2
x and x integers
1 2
Theorem 1 says that the convex hull of the solutions of (P) is also a
polytope; in our example this polytope is denoted D.
724
24
*
,
=( )
x
5
5
P
1
A valid inequality of
D
*
violated by x
D
8The p-median problem
Given a direct graph G = (V,A) where each arc (u,v) is associated with
a cost c(u,v). The problem is to select p nodes, and assign to them the
non-selected one such that the assignment cost is minimized.
9