Decomposition Method for Solving a Three-Index Planar Assignment Problem
- PDF / 184,642 Bytes
- 4 Pages / 612 x 792 pts (letter) Page_size
- 102 Downloads / 272 Views
UTER METHODS
Decomposition Method for Solving a Three-Index Planar Assignment Problem L. G. Dumbadzea, V. Yu. Leonovb, A. P. Tizika,*, and V. I. Tsurkovb,** a
b
Central Research Institute of Communications, Moscow, Russia Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, Moscow, Russia *e-mail: [email protected] **e-mail: [email protected] Received April 6, 2020; revised April 20, 2020; accepted May 25, 2020
Abstract—The classical assignment problem is considered. A third index is introduced, which can characterize, for example, the location of the work carried out. An iterative decomposition algorithm is proposed. At each step, a problem is solved with three constraints from different groups of conditions and with one connecting variable. The triples of problems are also solved with one restriction, and according to certain rules, the coefficients of the objective functions change. The iterative process that is monotonic in the objective function either arrives at the exact optimum solution of the original problem or indicates the nonuniqueness of the solution. In the latter case, a simple procedure finds the optima. DOI: 10.1134/S1064230720050056
INTRODUCTION The three-index planar assignment problem [1], as is well known, belongs to the class of NP-complete problems [2, 3]. To solve it, the branch and bound method [4], as well as the “greedy” and heuristic algorithms [5], are used. In [6], improvements to the approximate algorithms were proposed by moving to a probabilistic interpretation. In this paper, we apply the method of the sequential modification of the objective function [7–9] to solve the planar three-index assignment problem. The algorithm finds an exact solution, and the numerical experiments give a polynomial time estimate with respect to the dimension of the original problem. 1. FORMULATION OF THE PROBLEM The three-index planar assignment problem can be written as a linear integer programming problem: n
x i =1
ijk
= 1,
j = 1, n,
k = 1, n,
(1.1)
= 1,
i = 1, n,
k = 1, n,
(1.2)
= 1,
i = 1, n,
j = 1, n,
(1.3)
n
x j =1
ijk
n
x k =1
ijk
xijk ∈ {0, 1} , n
n
i, j, k = 1, n,
(1.4)
→ min .
(1.5)
n
c i =1 j =1 k =1
ijk xijk
695
696
DUMBADZE et al.
2. METHOD FOR SOLVING THE PROBLEM First we solve
3n2
problems with one restriction each. The first n2 problems n
cijk xijk → min i =1 3 under constraints (1.1) and (1.4). The second n2 problems
n
j =1
(2.1)
cijk xijk → min 3
(2.2)
under constraints (1.2) and (1.4). The third n2 problems n
cijk (2.3) xijk → min k =1 3 under constraints (1.3) and (1.4). All 3n2 problems of form (2.1)–(2.3) are easily solved by searching for the minimum coefficient for the variables in the corresponding objective functions. If as a result of the solution of the 3n2 problems given above, the values of the variables satisfy constraints (1.1)–(1.3), then the original problem (1.1)–(1.5) is solved. The sum of the values of the objective functions in the optimal solutions to problems (2.1)–(2.3) will b
Data Loading...
