1 of 45

Algebra of equivalent instances in the p-median problem and its applications

Boris Goldengorin

MIPT

Voronovo June 2021

1

2 of 45

Outline

  • Introduction
  • The origins of equivalence
  • Algebra of equivalent instances
  • Equivalence polyhedra
  • Complex instances

Voronovo June 2021

2

3 of 45

The PMP

Voronovo June 2021

3

minimize cost of black edges

Combinatorial Formulation

Pseudo-Boolean Formulation

4 of 45

The pseudo-Boolean polynomial

Voronovo June 2021

4

monomial

term

 

5 of 45

The pseudo-Boolean polynomial

  • Unique (even though the permutation matrix is not)
  • Compact
    • zero differences
    • p-truncation
    • summation of similar terms

Voronovo June 2021

5

6 of 45

Some tricks with numbers

Voronovo June 2021

6

exactly the same

 

 

7 of 45

Some tricks with numbers

Voronovo June 2021

7

any similarity ?

8 of 45

Some tricks with numbers

Voronovo June 2021

 

exactly the same

any similarity ?

 

9 of 45

Equivalence ?

Voronovo June 2021

9

10 of 45

Equivalence

Basic properties:

  • Reflexivity
  • Symmetry
  • Transitivity

Voronovo June 2021

10

Let us call two PMP instances defined on cost matrices C and D equivalent if and only if they are of the same size and:

11 of 45

Equivalence classes

  • Equivalence relation induces a partition of the space of matrices into equivalence classes

​

​

​

​

  • An equivalence class is closed under a certain finite set of operations

​

​

Voronovo June 2021

11

12 of 45

Operations preserving equivalence

Voronovo June 2021

12

  • Matrix representation of a pBp
    • every row i contains monomials of i-th degree (or 0);
    • monomials within each column have embedded terms.

13 of 45

Operations preserving equivalence

Voronovo June 2021

13

  • Matrix representation of a pBp
    • every row i contains monomials of i-th degree (or 0);
    • monomials within each column have embedded terms.

14 of 45

Operations preserving equivalence

Voronovo June 2021

14

  • Matrix representation of a pBp
    • every row i contains monomials of i-th degree (or 0);
    • monomials within each column have embedded terms.

ambiguous

uni que

uni que

uni que

15 of 45

Operations preserving equivalence

  1. permutation of columns

​

​

​

  • permutation of entries within one row preserving embedded structure of the columns

​

Voronovo June 2021

15

16 of 45

Operations preserving equivalence

  1. rearranging coefficients of similar monomials

​

​

​

  • insertion/deletion of a zero column

​

Voronovo June 2021

16

17 of 45

How to find the “smallest” matrix within an equivalence class

Voronovo June 2021

17

18 of 45

How to find the “smallest” instance within an equivalence class

Voronovo June 2021

18

Terms in the pBp can be considered as partially ordered subsets

Hasse diagram

19 of 45

How to find the “smallest” instance within an equivalence class

Voronovo June 2021

19

Terms in the pBp can be considered as partially ordered subsets

Definitions:

chain is a sequence of embedded terms, or a path in Hasse diagram, e.g.:

​

​

antichain is a set of terms, such that no two are embedded, e.g.:

​

20 of 45

How to find the “smallest” instance within an equivalence class

Voronovo June 2021

20

Hasse diagram

Each chain corresponds to a column of the costs matrix

21 of 45

How to find the “smallest” instance within an equivalence class

Voronovo June 2021

21

Decomposition into chains is not unique !

The problem of constructing the costs matrix with minimum number of columns

is equivalent to covering the Hasse diagram with minimum number of chains

22 of 45

How to find the “smallest” instance within an equivalence class

Voronovo June 2021

22

Terms in the pBp can be considered as partially ordered subsets

Dilworth theorem:

The minimum number of chains is equal to the size of a maximum antichain

Hasse diagram

a maximum antichain

23 of 45

How to find the “smallest” instance within an equivalence class

Voronovo June 2021

23

chains

polynomial in matrix form

costs matrix

24 of 45

Equivalence polyhedra

Voronovo June 2021

24

A set of all instances equivalent to the one defined by C:

25 of 45

Equivalence polyhedra

Voronovo June 2021

25

Take the pBp of an instance C in some matrix form:

A possible permutation matrix

Suppose, some instance defined by costs matrix D has the same permutation matrix and is equivalent to C (for any p)

must hold !

26 of 45

Equivalence polyhedra

Voronovo June 2021

26

equality of coefficients

27 of 45

Equivalence polyhedra

Voronovo June 2021

27

equality of coefficients

nonnegativity of differences

28 of 45

Equivalence polyhedra

Voronovo June 2021

28

equality of coefficients

nonnegativity of differences

nonnegativity of elements

29 of 45

Equivalence polyhedra

Voronovo June 2021

29

Equivalence polyhedron:

Set of all instances equivalent to the one defined by C:

30 of 45

Equivalence polyhedra

Voronovo June 2021

30

Theorem 1

31 of 45

Equivalence polyhedra

Voronovo June 2021

31

Theorem 1

Corollary

For any equivalence class there exist a natural equivalence relation that partitions this class into equivalence subclasses

32 of 45

Equivalence polyhedra

Voronovo June 2021

32

Properties of

Lemma 1

Lemma 2

Theorem 2

|B| - number of monomials in

|T| - number of nonzero elements in first m-p rows of the differences matrix

33 of 45

Complex instances

  • Definitions

Voronovo June 2021

33

Let us call instance D a reduced version of instance C ( D = red(C) ) if it satisfies the following conditions:

Complexity of instance data – minimum storage capacity needed to embed all data sufficient for solving the initial problem to optimality:

34 of 45

Complex instances

Voronovo June 2021

34

Possible reductions for PMP:

  • reduction of the number of rows (p-truncation)
  • reduction of the number of columns (covering Hasse diagram with fewer chains)
  • local aggregation of clients (adding similar terms)
  • local aggregation of locations (zero differences)

Goal: construct an instance of PMP for which all the above reductions are inapplicable

35 of 45

Complex instances

Voronovo June 2021

35

ensure that any (p-truncated) column contains no pair of equal entries

  1. reduction of the number of rows (p-truncation)
  2. reduction of the number of columns (covering Hasse diagram with fewer chains)
  3. local aggregation of clients (adding similar terms)
  4. local aggregation of locations (zero differences)

36 of 45

Complex instances

Voronovo June 2021

36

ensure that there is no pair of similar monomials in the pBp

for all k =1...m-p the sets of the first k entries in the columns of the permutation matrix are pairwise different

Hasse diagram is coverable with n internally vertex-disjoint chains (at least up to the level of m-p)

  1. reduction of the number of rows (p-truncation)
  2. reduction of the number of columns (covering Hasse diagram with fewer chains)
  3. local aggregation of clients (adding similar terms)
  4. local aggregation of locations (zero differences)

37 of 45

Complex instances

Voronovo June 2021

37

  1. reduction of the number of rows (p-truncation)
  2. reduction of the number of columns (covering Hasse diagram with fewer chains)
  3. local aggregation of clients (adding similar terms)
  4. local aggregation of locations (zero differences)

ensured by (3)

38 of 45

Complex instances

Voronovo June 2021

38

k

Optimal ratio: m=n

39 of 45

Complex instances

  • what if

Voronovo June 2021

39

these clients can be aggregated

40 of 45

Complex instances

  • Experimental results

Voronovo June 2021

40

41 of 45

Running times for OR-library and our instances of corresponding size

Voronovo June 2021

41

42 of 45

Complex instances

  • Experimental results

Voronovo June 2021

42

43 of 45

Conclusions

  • easy solvable cases in equiv. classes
  • data base of previously solved instances
  • generator of test instances
  • estimate complexity of existing benchmark instances

​

Voronovo June 2021

43

44 of 45

Literature

  • Bader F. AlBdaiwi, Boris Goldengorin, Gerard Sierksma. Equivalent instances of the simple plant location problem. Computers and Mathematics with Applications 57 (2009) 812–820.
  • Bader F. AlBdaiwi, Diptesh Ghosh, Boris Goldengorin. Data aggregation for p-median problems. Journal of Combinatorial Optimization (2011) 21: 348–363
  • Avella, P., Sforza, A.: Logical reduction tests for the p-median problem. Annals of Operations Research, 86, 105-115 (1999)
  • Avella, P., Sassano, A., Vasil'ev, I.: Computational study of large-scale p-median problems. Mathematical Programming, Ser. A, 109, 89-114 (2007)
  • Boros, E., Hammer, P.L.: Pseudo-Boolean optimization. Discrete Applied Mathematics, 123, 155-225 (2002)
  • Church, R.L.: BEAMR: An exact and approximate model for the p-median problem. Computers & Operations Research, 35, 417-426 (2008)
  • Cornuejols, G., Nemhauser, G., Wolsey, L.A.: A canonical representation of simple plant location problems and its applications. SIAM Journal on Matrix Analysis and Applications (SIMAX), 1(3), 261-272 (1980)
  • Elloumi, S.: A tighter formulation of the p-median problem. Journal of Combinatorial Optimization, 19, 69-83 (2010)

Voronovo June 2021

44

45 of 45

Literature (contd.)

  • Hammer, P.L.: Plant location -- a pseudo-Boolean approach. Israel Journal of Technology, 6, 330-332 (1968)
  • Mladenovic, N., Brimberg, J., Hansen, P., Moreno-Perez, J.A.: The p-median problem: A survey of metaheuristic approaches. European Journal of Operational Research, 179, 927-939 (2007)
  • Reese, J.: Solution Methods for the p-Median Problem: An Annotated Bibliography. Networks 48, 125-142 (2006)
  • ReVelle, C.S., Swain, R.: Central facilities location. Geographical Analysis, 2, 30-42 (1970)

Voronovo June 2021

45