The method of constructing lexicographic equivalence for solving linear mixed combinatorial optimization problems on arrangements is considered. The software that implements algorithms of this method is described. The efficiency of algorithms is analyzed be means of computational experiment.
Actual trend of the modern theory of optimization is to study the problems of combinatorial nature. In particular, these problems are examined by [1–7]. Important results have been obtained as a result of immersion of combinatorial sets in Euclidean space and study the properties of such problems. Y.G.Stoyan started the theory of Euclidean combinatorial optimization, his disciples – O.O. Iemets, S.V. Yakovlev, I.V. Grebennik and numerous other representatives of this school carry out research in this sphere. They have studied in their works both and properties of Euclidean combinatorial sets immersed in the arithmetical space, and extreme properties of the objective functions, and methods of solving Euclidean combinatorial optimization problems.
This article considers such an important class of Euclidean combinatorial optimization problems as problems on arrangement. The properties of the convex hull of the set of arrangements are explored in [8, 9], in [10, 11] and others — properties of the solution of certain classes of problems on arrangements, a number of results on the solving methods and algorithms of the optimization problems on arrangements in a rather general statement are summarized in [12]. In particular, method of constructing lexicographic equivalence for solving completely linear combinatorial problems on arrangements is substantiated. In [13] this method was extended to mixed combinatorial problems.
The aim of the paper is to describe the software implementation of the algorithms of the method of constructing lexicographic equivalence for solving linear mixed combinatorial optimization problems on arrangements and to present results of computational experiments.
New scientific result obtained in the paper is investigation of an effectiveness of algorithms of method of constructing lexicographic equivalence. Since theoretical estimates are not obtained, then the effectiveness is analyzed by mean of computational experiments. 2
Let’s consider necessary definitions and facts. As multiset G we understand set of elements, which can include and similar ones. Any multiset G g1 , g2 , ..., g can be assigned by its base S G , i.e. the tuple of all its different elements, and by multiplicity – number of repetition of each element of the base. The tuple of multiplicities in the order that corresponds to the elements of the base is called primary specification and is defined by G . The set is called the Euclidian combinatorial set, the different elements of which are different ordered k -samples from the multiset G g1 , g2 , ..., g of the representation
gi1 , gi2 , ..., gik , gij G , i j i j i j , it Jn , j, t Jk (here and after Jk defines set of k first natural numbers). Examples of Euclidian combinatorial sets are [9] general set of arrangements Ek G — set of all k -samples of the representation from the multiset G , general multiset of permutations E G E G .
The introduction of the concept of Euclidean combinatorial sets allows highlighting from problems of combinatorial nature the class of problems where the feasible set is Euclidean combinatorial set. In particular, the linear Euclidean problem of combinatorial optimization on arrangements is to find a pair L x* , x* (consisting of maximum and maximal) such that
n n
L x* mxaRxn j1 c j x j , x* arg mxaRxn j1 c j x j ,
under the combinatorial condition
and additional linear constraints
x1 , x2 , ..., xk Ek G
n
aij x j bi , i J m ,
j1
(
n n L x* lexmax c j x j , x* arg lexmax c j x j
xRn j1 xRn j1
under conditions (
One of the approaches to solving problem (
Lexicographic equivalence of points of the space with respect to k -arrangements (the relation k ) is used as the equivalence relation in the method of constructing lexicographic equivalence. Elements of the quotient set with respect to the equivalence k are called k -classes. Each element of set Ek G defines separate k -class. Such classes are called combinatorial. Algorithms for constructing lexicographic equivalence involve directed search of k -classes. Let us describe these algorithms (validation of these algorithms for solving mixed combinatorial problems is presented in [13]).
The first algorithm is used to solve a problem of finding a pair (
According to the second algorithm, the direct search of combinatorial k -classes in lexicographically increasing order and lexicographically decreasing order is carried out. Classes whose representatives give the objective function a value smaller than result obtained at previous iterations, are excluded from the search.
The third algorithm is approximate and allows getting the objective function value that differs from the optimum by no more than a predetermined value. It involves search k -classes whose representatives satisfy
n
h c j x j h
j1
(
The proposed algorithms of the method of constructing lexicographic equivalence for
solving linear conditional problems of combinatorial optimization on arrangement
(
Software was developed in the Turbo Delphi environment. The program allows you to generate a series of problems with the given parameters, to solve problems by selected algorithms, to save the results of problem solving, etc.
Input data (multiset, coefficients of the objective function and additional constraints) are presented as text files. This allows you to access the same set of data more than once. Data is generated using standard Delphi language procedure.
Multiset was assigned by its base and primary specification. Elements of the base are generated in increasing order, maximum difference between adjacent elements is given. Multiplicities of elements of the base were specified less or equal to the number k of combinatorial variables because the choice of larger multiplicities does not affect the solving problem.
When creating data files, the following parameters were set: the number of elements of the multiset base; the maximum difference between adjacent elements; the dimension of space n ; the number k of combinatorial variables; the number m of constraints.
The main characteristics of the algorithms studied during computational experiments are the running time and the number of iterations in the process of approaching the solution. Time is defined as the difference between the system time before the start of the procedure that implements the corresponding algorithm and after its completion.
Before starting the test, the user must select the directory in which the problem files are placed. You can choose to test all the files contained in the selected directory, as well as individual files. You can also set the generation of files automatically before testing.
In the main window of the program (see Fig. 1), the user can select algorithms which will be used for solving problems. We assume that values of the objective function in the first algorithm of the method of constructing lexicographic equivalence should be integers (i. e. A Z ). If you choose the third algorithm you need to specify the exactness.
Since even with rather small dimensions there are problems whose solving requires a considerable amount of time, the program allows you to set the time limit for the execution of algorithms. In case the algorithm runs longer than the specified time, the execution is interrupted and the corresponding message is output to the result file. If necessary, you can try to solve such problems later.
During testing, the main window shows the percentage of problems that are completed, the name of the current problem file and the name of the algorithm. When the “Details” button is clicked, a table of results is displayed. This table contains the names of the tested files, the time of solving the corresponding problem by each of the algorithms and the number of iterations.
In addition to solving existing problems by selected algorithms, the software product allows automatically generate series of problems with given parameters (the dimension of space, the numbers of constraints and combinatorial variables, the number of elements of the multiset base, etc.). The maximum and minimum values of each parameter of the series are specified, as well as the number of problems with each set of parameters.
All algorithms of the method of constructing lexicographic equivalence involve
solving linear programming problem which is obtained by replacing the combinatorial
condition (
For the convenience of further analysis of the results of computational experiment, it is possible to create a summary file. This file contains for each problem information about the main parameters (the number of variables, the number of constraints, etc.) and the characteristics of the algorithms (the running time, the number of iterations). In the future, the data of such files can be systematized and grouped, for example, using a table processor. 5
Several series of computational experiment were conducted using the software product described above. Testing of programs was carried out on a computer with a dualcore AMD A4-3400 processor, clock speed of each core 2700 MHz.
The first series of tests consists of 480 tasks, the generation of which parameters are given as follows: the dimension of space n 30 ; number of combinatorial variables k accepts consecutive values from 15 to 30; number of constraints m accepts consecutive values from 5 to 10.
For each set of parameters, 5 problems were solved. Separate characteristics of the results of solving problems for which the running time does not exceed 30 min is given in the Table 1, Table 2, where such notation is used: qp is the percentage of problems solved in less than 30 minutes; st is the average running time; mt is the maximum running time.
Time is given in minutes:sec; time less than 1 second displayed as 0:01.
The results of the experiments presented in the Table 1, 2 show that the dependence of the running time of algorithms both on the number of combinatorial variables, and on the number of constraints, is characterized by a certain irregularity. In particular, all 30 problems with k=27 combinatorial variables were solved by the third algorithm in less than 10 minutes, whereas for two problems with k=26 the solution was not obtained in 30 minutes. The average running time of the second algorithm for problems with 22 combinatorial variables is greater than for problems with 23 combinatorial variables. Solutions 78 out of 80 problems with 9 constraints were obtained by the first algorithm in less than 30 minutes, while 79 out 80 problems with 10 constraints were solved in less than 30 minutes.
“Irregularity” confirmed Fig. 2, where each point corresponds to the results of the solving using the first algorithm for constructing lexicographic equivalence of one problem (the abscissa of the point is the number of combinatorial variables, and the ordinate is the corresponding time of solving the problem; if problem was not solved then time was equal to 30 min). For the second and third algorithms, similar images are obtained.
The second series of tests consists of 420 problems (see Table 3).
The number of combinatorial variables is equal to 25, dimension accepts consecutive values from 30 to 43 and the number of constraints accepts consecutive values from 5 to 10, 5 problems were solved for each set of parameters. The running time was less than 11 minutes. The results are presented in the Table 3, where, as in the previous tables, st is the average running time; mt is the maximum running time. In contrast to the first series of tests if the dimension of space increases (so the number of continuous variables increases) then the running time decreases.
Parameters of problems in the third series of tests were defined as follows: the number of continuous variables is equal to 7, the number of constraints is equal to 10, dimension accepts consecutive values from 25 to 48 (so the number of combinatorial variables changes from 18 to 40), the number of problems with identical parameters is equal to 10.
The analysis of Table 3 and Table 4 gives reason to assert that the dimension of space has less effect on the running time than the number of continuous variables, but the corresponding dependencies with an acceptable correlation coefficient can not be established. The paper considers the software implementation of the algorithms of the method of constructing lexicographic equivalence. This method is used for solving linear mixed combinatorial optimization problems on arrangements and involves partition the space into equivalence classes followed by their direct search. The offered software allows you to generate a series of problems with the given parameters, to solve problems by selected algorithms, to save the results of problem solving. The computational experiment showed that the developed algorithms are effective for most problems with dimensions up to 50.