1 of 78

Open Questions in Job Sequencing and Tool Switching Problem�(potential topics for grants, research, dissertations and just fun)�Introduction to Data Correcting Algorithms

Boris Goldengorin

MIPT

​

E-mail: goldengorin@gmail.com�

​

2 of 78

Outline of Lecture 3

  • Job Sequencing and Tool Switching Problem (SSP): Example and Research Projects
  • Three Problems and Dilworth Theorem in SSP
  • Link to the course on Applied Combinatorial Optimization
  • References to tolerance based algorithms for the Asymmetric Traveling Salesman Problem (ATSP)
  • Data Correcting Algorithms for the ATSP and Simple Plant Location Problem (SPLP): the idea and two examples

​

​

​

​

Lecture 3 Voronovo 2021

2

3 of 78

Job Sequencing and Tool Switching Problem (SSP)

Задача оптимизации управлением конвейерного производтсва и алгоритмы поиска оптимальной последовательности выполнения заранее заданного множества работ, минимизирующей количество замен приспособлений.

​

Ошибочность подавляющего большинства публикаций состоит в сведении SSP к обычной задаче коммивояжера, в которой расстояние между двумя городами (работами между приспособлениями) зависит только от предшествующего города (работы).

​

В общем случае это расстояние зависит от разного количества городов.

Максимальное такое расстояние будем называть пороговым.

​

Lecture 3 Voronovo 2021

3

4 of 78

Example of SSP

Lecture 3 Voronovo 2021

4

5 of 78

Задачи по лекциям Вороново 2021

  • Задача 1. Используя теорему Дилуорса разработать и протестировать программу сборки минимального количества столбцов в агрегированной матрице.
  • Шаг 1. Привести пример размером 6 х 8 исходной числовой матрицы и построить для него псевдо-Булевский полином (пБп).
  • Шаг 2. Разработать и протестировать программу сборки минимального количества столбцов в агрегированную матрицу.
  • Шаг 3. Оценить трудоемкость Вашего алгоритма.
  • Шаг 4. Используя современные алгоритмы сортировки и структуры данных построить почти линейный алгоритм агрегирования столбцов матрицы для матриц размером до 104 строк х 106 столбцов.

​

Lecture 3 Voronovo 2021

5

6 of 78

Литература к Задаче 1

M. Raghavachari and V. L. Mote. Generalization of Dilworth's Theorem on Minimal Chain Decomposition. Management Science, Vol. 16, No. 7, Theory Series (Mar., 1970), pp. 508-511.

​

Anne Kaldewaij. Some algorithms based on the dual of Dilworth's theorem. Science of Computer Programming, Volume 9, Issue 1, August 1987, Pages 85-89

​

Selma Ikiz, Vijay K. Garg. Efficient Incremental Optimal Chain Partition of Distributed Program Traces. 26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006, 4-7 July 2006, Lisboa, Portugal, 12 pages

http://www.it.uom.gr/teaching/distrubutedSite/eceutexas/dist2/termPapers/Selma.pdf

​

András A. Benczúr, Jörg Förster, Zoltán Király: Dilworth's Theorem and Its Application for Path Systems of a Cycle - Implementation and Analysis. ESA 1999, Lecture Notes in Computer Science, volume 164, 498-509

Henry Shum, L.E.Trotter Jr. Cardinality-restricted chains and antichains in partially ordered sets. Discrete Applied Mathematics, 65(1-3): 421-439 (1996)

​

János Balogh, Cosmin Bonchis, Diana Dinis, Gabriel Istrate, Ioan Todinca: On the heapability of finite partial orders. Discret. Math. Theor. Comput. Sci. 22(1) (2020)

​

Lecture 3 Voronovo 2021

6

7 of 78

Dilworth theorem (1950) Application to Job Sequencing and Tool Switching Problem.

Применение теоремы Дилуорса (1950) к Задаче Упорядочивания Работ и Перезагрузке Приспособлений

​

Задача 2. Как вычислить истинное (пороговое) расстояние между следующей работой (или следующей последовательностью работ) в зависимости от предыдущей последовательности работ, которые в тривиaльном случае могут состоять только из одной работы.

​

Lecture 3 Voronovo 2021

7

8 of 78

Проекты по Задаче 2

  1. Какова математическая модель вычисления порогового расстояния для заданных множества работ и их приспособлений?
  2. Какова вычислительная сложность поиска порогового расстояния?
  3. Как построить точный и/или приближенный алгоритм поиска порогового расстояния?
  4. Для тестовых наборов задач из открытых источников вычислить их пороговые значения.
  5. Используя теорему Dilworth (1950) построить алгоритм вычисления максимального количества работ с невложенными друг в друга множествами приспособлений.
  6. Используя алгоритмы построения экстремальных ДНФ, например, кратчайших, найти минимальное количество классов работ с невложенными друг в друга приспособлениями. Здесь минимизация суммарного перехода по импликантам и соответствующим им интервалам (подпространствам) приспособлений могут служить оценками снизу как для порога, так и для оптимального количества переключений.

​

Lecture 3 Voronovo 2021

8

9 of 78

Dilworth Theorem

Dilworth, Robert P. (1950), "A Decomposition Theorem for Partially Ordered Sets", Annals of Mathematics, 51 (1): 161–166, doi:10.2307/1969503

​

Lecture 1 Voronovo 2021

9

The minimum number of chains necessary and sufficient to cover all subsets is equal to the size of a maximum antichain

10 of 78

Задача 3

Задача 3. Зная истинное расстояние между парами последовательностей работ, найти адекватную математическую модель для задачи оптимизации управлением конвейерного производтсва и соответствующий алгоритм поиска оптимальной последовательности выполнения заранее заданного множества работ, минимизирующей количество замен приспособлений.

​

Lecture 3 Voronovo 2021

10

11 of 78

Проекты по Задаче 3

  1. Какова математическая модель вычисления порогового расстояния для заданных множества работ и их приспособлений?
  2. Какова вычислительная сложность поиска порогового расстояния?
  3. Как построить точный и/или приближенный алгоритм поиска порогового расстояния?
  4. Для тестовых наборов задач из открытых источников вычислить их пороговые значения.
  5. Используя теорему Dilworth (1950), построить алгоритм вычисления максимального количества работ с невложенными друг в друга множествами приспособлений.
  6. Используя алгоритмы построения экстремальных ДНФ, например, кратчайших, найти минимальное количество классов работ с невложенными друг в друга приспособлениями. Здесь минимизация суммарного перехода по импликантам и соответствующим им интервалам (подпространствам) приспособлений могут служить оценками снизу как для порога, так и для оптимального количества переключений.

​

Lecture 3 Voronovo 2021

11

12 of 78

Литература, 1�

  1. D. Calmels. The job sequencing and tool switching problem: state-of-the-art literature review, classification, and trends. International Journal of Production Research, 2019, 57(15-16): 5005-5025.
  2. G. Jäger, P. Molitor, Algorithms and experimental study for the traveling alesman problem of second order, in: Comb. Optim. Appl, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 211–224.
  3. E. Ahmadi, B. Goldengorin, G. A. Süer, and H. Mosadegh. A Hybrid Method of 2-TSP and Novel Learning-Based GA for Job Sequencing and Tool Switching Problem. Applied Soft Computing, 2018, 65: 214–229.
  4. B. Goldengorin, D. Krushinsky, P. M. Pardalos. Cell Formation in Industrial Engineering: Theory, Algorithms and Experiments. Springer, New-York, 2013, 218 pp. ISBN: ISBN 978-1-4614-8001-3
  5. G. Laporte, J.J. Salazar-Gonzáles, F. Semet, Exact algorithms for the job sequencing and tool switching problem, IIE Trans. 36 (2004) 37–45, http://dx.doi.org/10.1080/07408170490257871.

​

Lecture 3 Voronovo 2021

12

13 of 78

Литература, 2�

  1. Tiago Tiburcio da Silva, Antônio Augusto Chaves & Horacio Hideki Yanasse (2020) A new multicommodity flow model for the job sequencing and tool switching problem, International Journal of Production Research, DOI: 10.1080/00207543.2020.1748906
  2. G. Ghiani, A. Grieco, E. Guerriero, Solving the job sequencing and tool switching problem as a nonlinear least cost Hamiltonian cycle problem, Networks 55 (2010) 379–385, http://dx.doi.org/10.1002/net.20341.
  3. Chaves, A. A., L. A. N. Lorena, E. L. F. Senne, and M. G. C. Resende. 2016. “Hybrid Method with CS and BRKGA Applied to the Minimization of Tool Switches Problem.” Computers & Operations Research 67: 174–183.
  4. Senne, E. L. F., and H. H. Yanasse. 2009. “Beam Search Algorithms for Minimizing Tool Switches on a Flexible Manufacturing System.” In Proceedings of the XI WSEAS International Conference on Mathematical and Computational Methods in Science and Engineering. Vol. 1, 68–72, Baltimore, USA. WSEAS Press.
  5. Crama, Y., A. W. Kolen, A. G. Oerlemans, and F. C. R. Spiesksma. 1994. Minimizing the Number of Tool Switches on a Flexible Machine. The International Journal of Flexible Manufacturing System 6: 33–54. 

​

Lecture 3 Voronovo 2021

13

14 of 78

Ссылка на курс Прикладная Комбинаторная Оптимизация

https://drive.google.com/drive/u/0/folders/14K1sn4zTcpM3qyZm06EK-1YG3lV-TUE8

  1. Видео лекции
  2. Литература
  3. Описание исследовательских проектов
  4. Инструкция по подготвке отчета для выбранной Вами задачи

Lecture 3 Voronovo 2021

14

15 of 78

Литература по допускам: References on Tolerances

References on Tolerances: Theory and Applications

​

Turkensteen, Marcel; Ghosh, Diptesh; Goldengorin, Boris; Sierksma, Gerard. Tolerance based branch and bound algorithms for the ATSP. Euro-pean J. Oper. Res. 189 (2008), no. 3, 775–788.

​

R. Germs, B. Goldengorin, M. Turkensteen. Lower tolerance-based Branch and Bound algorithms for the ATSP. Computers & Operations Research, 2012, 39(2), 291-298.

​

Гольденгорин Б. И., Пардалос П. О., Чистяков В. В. Глобальные допуски в задачах комбинаторной оптимизации с аддитивной целевой функцией

Доклады Академии наук. 2012. Т. 446. № 1. С. 21-24.

​

G. Jager, C. Dong, B. Goldengorin, P. Molitor, D. Richter. Backbone Based TSP Heuristics for Large Instances. Journal of Heuristics, 2014, 20(1):107–124.

Lecture 3 Voronovo 2021

15

16 of 78

Data Correcting Approaches in Combinatorial Optimization

17 of 78

Lecture 3 Voronovo 2021

17

18 of 78

“A Data Correcting (DC) algorithm (typically applied to NP-hard optimization problems) is a branch-and-bound type algorithm, in which the input data are “heuristically corrected” at the various stages whereby two goals are pursued simultaneously. First, the modified input instance should belong to a (more) tractable (polynomially solvable) subproblem. Second, the solution that is optimal for the corrected data should be within a prespecified (additive!) deviation from the solution that is optimal for the original data.

…

The DC approach seems to come very close to a mature technology for (heuristically) solving a reasonably wide range of NP-hard combinato- rial optimization problems.”

Hans-Ulrich Simon, Ruhr University Bochum, Germany

Lecture 3 Voronovo 2021

18

19 of 78

Data Correcting Approach in Optimization. 1

We propose a data correcting (DC) algorithm - an approximation algorithm that makes use of poly-nomially solvable special cases to arrive at high-quality solutions.

The basic insight that leads to this algorithm is the fact that it is often easy to compute an upper bound on the difference in cost between an optimal solution of a problem instance and any feasible solution to the instance.

Lecture 3 Voronovo 2021

19

20 of 78

Data Correcting Approach in Optimization. 2

The approximation in the DC algorithm is in terms of an accuracy parameter, which is an upper bound on the difference between the objective value of an optimal solution to the instance and that of a solution returned by the DC algorithm.

​

Note that this is not expressed as a fraction of the optimal objective value for this instance. In this respect, the algorithm is different from common ε -optimal algorithms, in which ε is defined as a fraction of the optimal objective function value.

Lecture 3 Voronovo 2021

20

21 of 78

Our Objective

Given a function f, to be minimized over a domain D, and an accuracy parameter α, find xα ∈ D such that

​

f(xα) ≤ min{f(x): x ∈ D}+α

​

Lecture 3 Voronovo 2021

21

22 of 78

α and ε Approximation

α-approx: find xα s.t. f(xα) ≤ min{f(x): x ∈ D}+α

ε-approx: find xε s.t. f(xε) ≤ (1+ε).min{f(x): x ∈ D}

Optimal solution value

Allowed

suboptimality

α approx

ε approx

Lecture 3 Voronovo 2021

22

23 of 78

A Real Valued Function

D

f(x)

x

f(x*)

x*

Lecture 3 Voronovo 2021

23

24 of 78

α-Optimal Solutions

D

f(x)

x

x*

α

Acceptable solutions

or α-minima

Lecture 3 Voronovo 2021

24

25 of 78

Assertion

The minimum point of any function g(x) lying within the two

dashed lines is an α-minimum for the original function.

D

α/2

α/2

g(x)

Lecture 3 Voronovo 2021

25

26 of 78

Assertion

The minimum point of any function g(x) lying within the two

dashed lines is an α-minimum for the original function.

D

α/2

α/2

g(x)

xα

x*

g(xα) ≤ g(x*)

f(xα) - α/2 ≤

≤ f(x*) + α/2

Lecture 3 Voronovo 2021

26

27 of 78

Finding the α-Minimum

D

Lecture 3 Voronovo 2021

27

28 of 78

Finding the α-Minimum

D

D1

xα1

Lecture 3 Voronovo 2021

28

29 of 78

Finding the α-Minimum

D

D1

xα1

xα2

xα3

xα4

D2

D4

D3

α-minimum ∈ arg min{ f(xα1), f(xα2), f(xα3), f(xα4) }

Lecture 3 Voronovo 2021

29

30 of 78

Finding the α-Minimum

D

D1

xα1

xα2

xα3

xα4

D2

D4

D3

α-minimum ∈ arg min{ f(xα1), f(xα2), f(xα3), f(xα4) }

Lecture 3 Voronovo 2021

30

31 of 78

Points to Note

  • All sub-domains need to be considered before the algorithm returns an α-optimal solution.
  • The solution returned by the algorithm may not be close to the optimal solution in the domain of the function.
  • The approximation of the function in a given domain can be of any form, as long as it fits in the ‘corridor’ along the function.

Lecture 3 Voronovo 2021

31

32 of 78

To Combinatorial Optimization…

Continuous Optimization

  • Partition the domain of the function;
  • Approximate the function with a “nice” function in each domain;
  • Compute the optima of the “nice” functions in the partition and choose the best.

Combinatorial Optimization

  • Use an enumeration (branching) procedure;
  • Use polynomially solvable special cases for approximation;
  • Compute the optima of the polynomially solvable special cases and choose the best.

Lecture 3 Voronovo 2021

32

33 of 78

Data Correcting versus Branch and Bound

Data Correcting

Branch and Bound

Lecture 3 Voronovo 2021

33

34 of 78

Asymmetric

TSP

Example

Lecture 3 Voronovo 2021

34

35 of 78

An Asymmetric TSP Example

A B C D E F

A -- 10 16 19 25 22

B 19 -- 10 13 13 10

C 10 28 -- 22 16 13

D 19 25 13 -- 10 19

E 16 22 19 13 -- 11

F 13 22 15 13 10 --

A

B

D

E

C

F

Solution to the

Assignment Problem

on the same matrix

Lecture 3 Voronovo 2021

35

36 of 78

An Asymmetric TSP Example

A B C D E F

A -- 10 16 19 25 22

B 19 -- 10 13 13 10

C 10 28 -- 22 16 13

D 19 25 13 -- 10 19

E 16 22 19 13 -- 11

F 13 22 15 13 10 --

A

B

D

E

C

F

Lecture 3 Voronovo 2021

36

37 of 78

An Asymmetric TSP Example

A B C D E F

A -- 10 16 19 25 22

B 19 -- 10 13 13 10

C 10 28 -- 22 16 13

D 19 25 13 -- 10 19

E 16 22 19 13 -- 11

F 13 22 15 13 10 --

A

B

D

E

C

F

13

15

10

13

Lecture 3 Voronovo 2021

37

38 of 78

An Asymmetric TSP Example

A B C D E F

A -- 10 16 19 25 22

B 19 -- 10 12 13 10

C 10 28 -- 22 16 13

D 19 25 13 -- 10 19

E 16 22 19 13 -- 11

F 13 22 11 13 10 --

A

B

D

E

C

F

Lecture 3 Voronovo 2021

38

39 of 78

An Asymmetric TSP Example

A B C D E F

A -- 10 16 19 25 22

B 19 -- 10 13 13 10

C 10 28 -- 22 16 13

D 19 25 13 -- 10 19

E 16 22 19 13 -- 11

F 13 22 15 13 10 --

A B C D E F

A -- 10 16 19 25 22

B 19 -- 10 12 13 10

C 10 28 -- 22 16 13

D 19 25 13 -- 10 19

E 16 22 19 13 -- 11

F 13 22 11 13 10 --

Original Instance (O)

Optimal Tour : To

(unknown)

Corrected Instance (C)

Optimal Tour: Tc

(A-B-D-E-F-C-A)

cost(Tc) - cost(To) ≤ |13-12| + |15-11| = 5

Lecture 3 Voronovo 2021

39

40 of 78

An Asymmetric TSP Example

If you are satisfied with an accuracy (α) of 5, you

have an α-optimal solution already!

f(x)

x

nice function

Lecture 3 Voronovo 2021

40

41 of 78

An Asymmetric TSP Example

But if you need an accuracy of less than 5,

f(x)

x

you need to partition the problem domain!

nice function

Lecture 3 Voronovo 2021

41

42 of 78

An Asymmetric TSP Example

But if you need an accuracy of less than 5,

f(x)

x

you need to partition the problem domain!

Lecture 3 Voronovo 2021

42

43 of 78

An Asymmetric TSP Example

All Tours

Tours incl.

B→D

Tours excl.

B→D

A B C D E F

A -- 10 16 19 25 22

B 19 -- 10 ∞ 13 10

C 10 28 -- 22 16 13

D 19 25 13 -- 10 19

E 16 22 19 13 -- 11

F 13 22 15 13 10 --

A B C E F

A -- 10 16 25 22

C 10 28 -- 16 13

D 19 25 13 10 19

E 16 22 19 -- 11

F 13 22 15 10 --

Lecture 3 Voronovo 2021

43

44 of 78

An Asymmetric TSP Example

  • For an asymmetric TSP, instance data is corrected only at the leaf nodes of the branch and bound tree.
  • The size of the branch and bound tree is monotonically non-increasing in α. This means that increasing the value of α does not guarantee a decrease in the size of the branch and bound tree.

Lecture 3 Voronovo 2021

44

45 of 78

Uncapacitated

Facility Location

Problem

Lecture 3 Voronovo 2021

45

46 of 78

An Example of the UFLP

Four sites, four customers

Sites

A

B

C

D

Fixed

costs

9

4

3

6

Customers I II III IV

Transportation

costs

7 12 22 13

8 9 18 17

16 17 10 27

9 13 10 11

Lecture 3 Voronovo 2021

46

47 of 78

Pseudo-Boolean Representation

Our formulation is a PENALTY based approach

​

Variables

yj = 0 if a facility is located at site j;

= 1 if a facility is not located at site j.

Lecture 3 Voronovo 2021

47

48 of 78

Pseudo-Boolean Representation

9 | 7 12 22 13

4 | 8 9 18 17

3 | 16 17 10 27

6 | 9 13 10 11

Total Cost

Setting up

cost

Transportation

cost

9(1-y1) + 4(1-y2) +

3(1-y3) + 6(1-y4)

Cost for customer 1 +

Cost for customer 2 +

Cost for customer 4.

Cost for customer 3 +

+

Lecture 3 Voronovo 2021

48

49 of 78

Pseudo-Boolean Representation

Total Cost

Setting up

cost

Transportation

cost

9(1-y1) + 4(1-y2) +

3(1-y3) + 6(1-y4)

7 + 1y1 + 1y1y2+ 7y1y2y4 +

Cost for customer 2 +

Cost for customer 4.

Cost for customer 3 +

+

9 | 7 12 22 13

4 | 8 9 18 17

3 | 16 17 10 27

6 | 9 13 10 11

Lecture 3 Voronovo 2021

49

50 of 78

Pseudo-Boolean Representation

Total Cost

Setting up

cost

Transportation

cost

9(1-y1) + 4(1-y2) +

3(1-y3) + 6(1-y4)

7 + 1y1 + 1y1y2+ 7y1y2y4 +

9 + 3y2 + 1y1y2+ 4y1y2y4 +

11 + 2y4 + 4y1y4+ 10y1y2y4.

10 + 0y3 + 8y3y4+ 4y2y3y4 +

+

= 59 - 8y1 - y2 - 3y3 - 4y4 + 2y1y2 + 4y1y4 + 8y3y4 + 21y1y2y4 + 4y2y3y4

Hammer Function

9 | 7 12 22 13

4 | 8 9 18 17

3 | 16 17 10 27

6 | 9 13 10 11

Lecture 3 Voronovo 2021

50

51 of 78

Conventional Preprocessing�(based on Khumawala 1972)

Consider a site j:

Rule 1: If the coefficient of yj in the linear term of the Hammer function is non-negative, then locate a facility at site j.

Rule 2: If the coefficient of yj in the linear term is negative, and the sum of this coefficient and those of all non-linear terms containing yj is negative, then do not locate a facility at site j.

Lecture 3 Voronovo 2021

51

52 of 78

New Preprocessing

H(y) = 59-8y1-y2-3y3-4y4+2y1y2+4y1y4+8y3y4+21y1y2y4+4y2y3y4

Increasing cost

Optimal Solution

Lower Bound (Relaxation)

Upper Bound (Heuristic solution)

Lecture 3 Voronovo 2021

52

53 of 78

New Preprocessing

H(y) = 59-8y1-y2-3y3-4y4+2y1y2+4y1y4+8y3y4+21y1y2y4+4y2y3y4

Upper bound for optimal solution = 50 (say)

Lower bound for solutions with no facility

at 1, 2, or 4 (i.e. y1 = y2 = y4 = 1) = 70

What if 21y1y2y4 is changed to 20y1y2y4 in H(y)?

We can reduce the coefficient of 21y1y2y4 to anything more

than 1 without affecting the optimality of the

optimal solution to H(y).

Lecture 3 Voronovo 2021

53

54 of 78

New Preprocessing

So we can change

to

without changing the optimal solution!

H1(y) = 59-8y1-y2-3y3-4y4+2y1y2+4y1y4+8y3y4+1y1y2y4+4y2y3y4

H(y) = 59-8y1-y2-3y3-4y4+2y1y2+4y1y4+8y3y4+21y1y2y4+4y2y3y4

Khumawala’s rules reduce this to optimality

(locate plants at sites 2 and 4)

Lecture 3 Voronovo 2021

54

55 of 78

OR-Lib Instances

Problem Number Preprocessing� of sites Conv. New

cap071 16 4 0

cap072 16 6 0

cap073 16 6 3

cap074 16 2 0

cap101 25 9 0

cap102 25 13 0

cap103 25 14 0

cap104 25 12 0

cap131 50 34 8

cap132 50 27 5

cap133 50 25 10

cap134 50 19 0

Lecture 3 Voronovo 2021

55

56 of 78

OR-Lib Instances

Problem Non-linear Preprocessing� terms Conv. New

cap071 699 6 0

cap072 699 12 0

cap073 699 13 2

cap074 699 1 0

cap101 1147 24 0

cap102 1147 33 0

cap103 1147 38 0

cap104 1147 29 0

cap131 2389 163 8

cap132 2389 112 3

cap133 2389 101 11

cap134 2389 62 0

Lecture 3 Voronovo 2021

56

57 of 78

Other Standard Problem Sets

  • Bilde and Krarup (1977)

DC took 7% of the time to solve problems

93% CPU time reduction�

  • Galvao and Raggi (1989)

DC took <1% of the time to solve the problems

More than 99% CPU time reduction

Lecture 3 Voronovo 2021

57

58 of 78

Another New Preprocessing Rule: Introducing Suboptimality

H1(y) = 54 - 2y1 - 3y2 - 3y3 - 4y4 + 2y1y2 + 10y3y4 +

4y1y4 + 11y1y2y4 + 10y1y3y4 + 2y2y3y4

The optimal solution for H1(y) and H2(y) differ

by at most 2 units.

H2(y) = 54 - 0y1 - 3y2 - 3y3 - 4y4 + 2y1y2 + 10y3y4 +

4y1y4 + 11y1y2y4 + 10y1y3y4 + 2y2y3y4

Lecture 3 Voronovo 2021

58

59 of 78

Another New Preprocessing Rule: Introducing Suboptimality

H1(y) = 54 - 2y1 - 3y2 - 3y3 - 4y4 + 2y1y2 + 10y3y4 +

4y1y4 + 11y1y2y4 + 10y1y3y4 + 2y2y3y4

No preprocessing possible

Lecture 3 Voronovo 2021

59

60 of 78

Another New Preprocessing Rule: Introducing Suboptimality

H2(y) = 54 - 0y1 - 3y2 - 3y3 - 4y4 + 2y1y2 + 10y3y4 +

4y1y4 + 11y1y2y4 + 10y1y3y4 + 2y2y3y4

H2(y) = 54 - 3y2 - 3y3 - 4y4 + 10y3y4 + 2y2y3y4

y1 = 0

H2(y) = 51 - 3y3 - 4y4 + 12y3y4

y2 = 1

Lecture 3 Voronovo 2021

60

61 of 78

Summary of the Rule

H1(y) : 11 non-trivial terms, no preprocessing possible

(data correcting, with accuracy ≥ 2 units)

H2(y) : 10 non-trivial terms

(conventional preprocessing, two sites preprocessed)

H2(y) : 4 non-trivial terms, no preprocessing possible

Lecture 3 Voronovo 2021

61

62 of 78

Data Structures

Sites

A

B

C

D

Fixed

Costs

9

4

3

6

Customers I II III IV

​

Transportation costs

7 12 22 13

8 9 18 17

16 17 10 27

9 13 10 11

Permutation Matrix

Π

1 2 3 4

2 1 4 1

4 4 2 2

3 3 1 3

Skip Data Structure Details

Lecture 3 Voronovo 2021

62

63 of 78

Data Structures

Client k

Fk = 10

Tk = 5

3

7

8

4

2

9

Hammer function for this client:

​

10 + 2 + y6 + y2y6 + y2y5y6

+ 2y1y2y5y6 + y1y2y3y5y6

+ y1y2y3y4y5y6

Lecture 3 Voronovo 2021

63

64 of 78

Data Structures: Computing Linear Terms

Client k

Fk = 10

Tk = 5

3

7

8

4

2

9

​

Δk

1

1

1

2

1

1

0

​

Πk

6

2

5

1

3

4

7

L

NL

Linear term:

Look at the position of pointer L;

If that position is p, then coefficient

of linear term is Δ(p-1),k

Hammer function for this client:

​

10 + 2 + y6 + y2y6 + y2y5y6

+ 2y1y2y5y6 + y1y2y3y5y6

+ y1y2y3y4y5y6

Lecture 3 Voronovo 2021

64

65 of 78

Data Structures: Computing Non-linear Terms

Client k

Fk = 10

Tk = 5

3

7

8

4

2

9

​

Δk

1

1

1

2

1

1

0

​

Πk

6

2

5

1

3

4

7

L

NL

Non-Linear Term involving y1:

Locate the position p of 1 in Πk;

p

Add Δk values from the position

of NL to p (i.e. 0+1+1+2 = 6)

Hammer function for this client:

​

10 + 2 + y6 + y2y6 + y2y5y6

+ 2y1y2y5y6 + y1y2y3y5y6

+ y1y2y3y4y5y6

Lecture 3 Voronovo 2021

65

66 of 78

Data Structures: Updating the �L-pointer

Client k

Fk = 10

Tk = 5

3

7

8

4

2

9

​

Δk

1

1

1

2

1

1

0

​

Πk

6

2

5

1

3

4

7

L

NL

If y6 is set to 1 then

L points to the next position in

Πk.

L

Hammer function for this client:

​

10 + 2 + y6 + y2y6 + y2y5y6

+ 2y1y2y5y6 + y1y2y3y5y6

+ y1y2y3y4y5y6

Lecture 3 Voronovo 2021

66

67 of 78

Data Structures: Updating the�NL-pointer

Client k

Fk = 10

Tk = 5

3

7

8

4

2

9

​

Δk

1

1

1

2

1

1

0

​

Πk

6

2

5

1

3

4

7

L

NL

If (say) y3 is set to 0 then

NL points to the position

before that of 3 in Πk.

NL

Hammer function for this client:

​

10 + 2 + y6 + y2y6 + y2y5y6

+ 2y1y2y5y6 + y1y2y3y5y6

+ y1y2y3y4y5y6

Lecture 3 Voronovo 2021

67

68 of 78

The Data Correcting Algorithm

procedure data_correcting(H(.), y, α)

begin

do conventional preprocessing;

do new preprocessing with an accuracy α0 ≤ α;

partition the solution space by choosing a

branching variable yj;

/* New Hammer function is H’(.) */

set yj = 1;

sol1 = data_correcting(H’(.), y, α−α0);

set yj = 0;

sol0 = data_correcting(H’(.), y, α−α0);

return the better of sol1 and sol0;

end;

We do this step

only at the root

Lecture 3 Voronovo 2021

68

69 of 78

Körkel-Ghosh Instances (size 65)

Lecture 3 Voronovo 2021

69

70 of 78

Körkel-Ghosh Instances (size 65)

Lecture 3 Voronovo 2021

70

71 of 78

Körkel-Ghosh Instances (size 100)

Lecture 3 Voronovo 2021

71

72 of 78

Körkel-Ghosh Instances (size 100)

Lecture 3 Voronovo 2021

72

73 of 78

Summary

  • Data Correcting is a method for obtaining approximate solutions.
  • The method is not generally polynomial.
  • The method relies on polynomially solvable special cases of the base problem.
  • There are fundamental differences between this method and branch and bound.

Lecture 3 Voronovo 2021

73

74 of 78

Research Directions

  • Which polynomially solvable special cases are good for data correcting?
  • Can we have special branching rules that favor data correcting?
  • Can we generate hybrid algorithms by combining data correcting with dynamic programming, metaheuristics, etc.?

Lecture 3 Voronovo 2021

74

75 of 78

Literature 1

  • B.I. Goldengorin. Correcting algorirthm for the solution of some discrete optimization problems. Soviet Math. Doklady 270 (3), 1983, 525-528.
  • B.Goldengorin, G.Sierksma, G.A.Tijssen, M.Tso. The data correcting algorithm for minimization of supermodular functions. Management Science 45(11), 1999, 1539-1551.
  • B.Goldengorin, D.Ghosh, G.Sierksma. Solving the simple plant location problem using a data correct-ing approach. Journal of Global Optimization 25 (4), 2003, 377-406.

Lecture 3 Voronovo 2021

75

76 of 78

Literature 2

  • B.Goldengorin, D.Ghosh. The multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. Journal of Global Optimization 32 (1), 2005, 65 - 82 .
  • D. Ghosh, B. Goldengorin, and G. Sierksma. Data correcting algorithms in combinatorial optimiza-tion.  Handbook of Combinatorial Oprimization. Volume 5, Supplement Volume B. D.-Z. Du and P.M. Pardalos (Eds.). Springer, 2005, 1-53. 

Lecture 3 Voronovo 2021

76

77 of 78

Literature 3

  • B. Goldengorin, P.M. Pardalos. Data correcting approaches in combinatorial optimization. Springer, 2012, 124 pp.

​

  • B. Goldengorin. Data correcting approaches to routing and location problems. Handbook of Combinatorial Oprimization. D.-Z. Du P.M. Pardalos, R. L. Graham. (Eds.). Springer, 2013, 929-993 pp.

Lecture 3 Voronovo 2021

77

78 of 78

Thank you!