Submitted for publication / in preparation


k-metric antidimension of some generalized Petersen graphs

Jozef Kratica, Vera Kovačević-Vujčić, Mirjana Čangalović

Submitted for publication

Abstract

The k-metric antidimension problem was recently introduced with the aim to evaluate the resistance of social graphs to active attacks. In this paper we study the k-metric antidimension of generalized Petersen graphs. We prove that $GP(n,2)$ is 3-metric antidimensional for $n \ne 8$, while $GP(n,1)$ is 3-metric antidimensional if $n$ is even, and 2-metric antidimensional if $n$ is odd.

Keywords

Keywords: Generalized Petersen graphs; $k$-metric antidimension



International journals, monographs and chapters in edited books

2017.

Kratica J., Kovačević-Vujčić V., Čangalović M., The strong metric dimension of some generalized Petersen graphs, Applicable Analysis and Discrete Mathematics, Vol 11., No. 1, pp. 1-10., 2017. doi:10.2298/AADM161110032K Journal site - full paper

Matić D., Kratica J., Maksimović Z., Solving the minimum edge-dilation k-center problem by genetic algorithms, Computers & Industrial Engineering, Vol. 113, pp. 282-293, November 2017. doi:10.1016/j.cie.2017.09.029 Journal site - full paper

Maksimović Z., Kratica J., Savić A., Two metaheuristics for solving the connected multidimensional maximum bisection problem, Soft Computing, Vol. 21, No. 21, pp. 6453-6469, November 2017. doi:10.1007/s00500-016-2203-1 Journal site - full paper

Variable neighborhood search for solving bandwidth coloring problem

Dragan Matić, Jozef Kratica, Vladimir Filipović

Computer Science and Information Systems, Vol. 14, No. 2, pp. 309-327, 2017. DOI: 10.2298/CSIS160320012M

Abstract

This paper presents a variable neighborhood search (VNS) algorithm for solving bandwidth coloring problem (BCP) and bandwidth multicoloring problem (BMCP). BCP and BMCP are generalizations of the well known vertex coloring problem and they are of a great interest from both theoretical and practical points of view. Presented VNS combines a shaking procedure which perturbs the colors for an increasing number of vertices and a specific variable neighborhood descent (VND) procedure, based on the specially designed arrangement of the vertices which are the subject of re-coloring. By this approach, local search is split in a series of disjoint procedures, enabling better choice of the vertices which are addressed to re-color. The experiments show that proposed method is highly competitive with the state-of-the-art algorithms and improves 2 out of 33 previous best known solutions for BMCP.

Keywords

Keywords: Bandwidth Coloring, Bandwidth MultiColoring, Frequency Assignment, Variable Neighborhood Search, Variable Neighborhood Descent

PDF arXiv

2014.

Two metaheuristic approaches for solving multidimensional two-way number partitioning problem

Jozef Kratica, Jelena Kojić, Aleksandar Savić

Computers & Operations Research, Vol. 46, pp. 59-68, 2014. DOI: 10.1016/j.cor.2014.01.003

Abstract

In this paper, we address two metaheuristic approaches, a Variable Neighborhood Search (VNS) and an Electromagnetism-like metaheuristic (EM), on an NP-hard optimization problem: Multi-dimensional Two-way Number Partitioning Problem (MDTWNPP). MDTWNPP is a generalization of a Two-way Number Partitioning Problem (TWNPP), where a set of vectors is partitioned rather than a set of numbers. The simple $k$-swap neighborhoods allow an effective shaking procedure in the VNS search. The attraction-repulsion mechanism of EM is extended with a scaling procedure, which additionally moves EM points closer to local optima. Both VNS and EM use the same local search procedure based on 1-swap improvements. Computational results were obtained on 210 standard instances. Direct comparison with results from the literature confirm the significance of applying these methods to MDTWNPP.

Keywords

Number partitioning, Metaheuristics, Combinatorial optimization.

Journal site - full paper

A new mixed integer linear programming model for the multi level uncapacitated facility location problem

Jozef Kratica, Djordje Dugošija, Aleksandar Savić

Applied Mathematical Modelling, Vol. 38, No. 7-8, pp. 2118-2129, 2014. DOI:10.1016/j.apm.2013.10.012

Abstract

This paper considers the Multi Level Uncapacitated Facility Location Problem (MLUFLP). A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on instances known from literature. The results achieved by CPLEX and Gurobi solvers, based on the proposed MILP formulation, are compared to the results obtained by the same solvers on the already known formulations. The results show that CPLEX and Gurobi can optimally solve all small and medium sized instances and even some large-scale instances using the new formulation.

Keywords

Multi level location problems, Integer linear programming, Mathematical modelling, Discrete location.

Journal site - full paper | MLUFLP instances (.7z, 11 MB) | MLUFLP optimal and best known results

Strong metric dimension: A survey

Jozef Kratica, Vera Kovačević-Vujčić, Mirjana Čangalović, Nenad Mladenović

Yugoslav Journal of Operations Research, in press, 2014. DOI: 10.2298/YJOR130520042K

Abstract

The strong metric dimension has been a subject of considerable amount of research in recent years. This survey describes the related development by bringing together theoretical results and computational approaches, and places the recent results within their historical and scientific framework.

Keywords

Strong metric dimension, graph problems, combinatorial optimization.

AMS 2010 Primary Class. 05-02 AMS 2010 Secondary Class. 05C12; 90C10; 68T20

DOI Serbia - full paper

2013.

An electromagnetism-like metaheuristic for the uncapacitated multiple allocation p-hub median problem

Jozef Kratica

Computers & Industrial Engineering, Vol. 66, No. 4, pp. 1015-1024, December 2013. DOI:10.1016/j.cie.2013.08.014

Abstract

This paper deals with the uncapacitated multiple allocation p-hub median problem (UMApHMP). An electromagnetism-like (EM) method is proposed for solving this NP-hard problem. The new scaling technique combined with movement based on the attraction-repulsion mechanism directs EM towards promising search regions. Numerical results on a battery of benchmark AP and TM instances known from the literature are reported. The computational results show that EM reaches all previously known optimal solutions, and gives excellent results on large-scale instances.

Keywords

Electromagnetism-like metaheuristic, hub location, combinatorial optimization

Journal site - full paper

An electromagnetism-like method for the maximum set splitting problem

Jozef Kratica

Yugoslav Journal of Operations Research, Vol. 23, No. 1, pp. 31-41, 2013.

Abstract

In this paper, an electromagnetism-like approach (EM) for solving the maximum set splitting problem (MSSP) is applied. Hybrid approach consisting of the movement based on the attraction-repulsion mechanisms combining with the proposed scaling technique directs EM to promising search regions. Fast implementation of the local search procedure additionally improves the efficiency of overall EM system. Afterward, the performance of the proposed EM approach is evaluated on two classes of instances from the literature: minimum hitting set and Steiner triple systems. The results show, except in one case, that EM reached optimal solutions up to 500 elements and 50000 subsets on minimum hitting set instances. EM reached all optimal/best-known solutions for Steiner triple systems.

Keywords

electromagnetism-like metaheuristic, combinatorial optimization, maximum set splitting problem, Steiner triple systems

Journal site - full paper

Minimal doubly resolving sets of prism graphs

Mirjana Čangalović, Jozef Kratica, Vera Kovačević-Vujčić, Milica Stojanović

Optimization, Vol. 62, No. 8, pp. 1037-1043, 2013.

Abstract

In this paper we consider the problem of determining the minimal cardinality of double resolving sets for prism graphs $Y_n$. It is proved that the minimal cardinality is equal to 4 if $n$ is even and equal to 3 if $n$ is odd.

Keywords

metric dimension; minimal doubly resolving set; prism graphs, generalized Petersen graphs

AMS 2010 Primary Class. 05C12 AMS 2010 Secondary Class. 68R10; 05C75

Journal site - full paper

A new non-linear model for the two-dimensional packing problem

Aleksandar Savić, Jozef Kratica, Vladimir Filipović

Publications de l'Institut Mathematique, Nouvelle serie, tome 93 (107), pp. 95-107, 2013.

Abstract

This paper is dealing with the rectangle packing problem where a big rectangle is filled with smaller rectangles, while the rectangle dimensions are real numbers. A new non-linear programming formulation is presented and validity of this formulation is being proven. In addition, two cases of the problem are presented in the paper - with and without rotation of smaller rectangles for $90^\circ$. The mixed integer piecewise linear formulation derived from the model is given, but with a simple form of the objective function.

Keywords

nonlinear programming, piecewise linear relaxation, rectangle packing problem.

AMS 2010 Mathematics Subject Classification: 90C30; 90C11.

Journal site - full paper

An improved genetic algorithm for the multi level uncapacitated facility location problem

Vanja Korać, Jozef Kratica, Aleksandar Savić

International Journal of Computers, Communications & Control, Vol. 8, No. 6, pp. 845-853, 2013.

Abstract

In this paper, an improved genetic algorithm (GA) for solving the multi-level uncapacitated facility location problem (MLUFLP) is presented. First improvement is achieved by better implementation of dynamic programming, which speeds up the running time of the overall GA implementation. Second improvement is hybridization of the genetic algorithm with the fast local search procedure designed specially for MLUFLP. The experiments were carried out on instances proposed in the literature which are modified standard single level facility location problem instances. Improved genetic algorithm reaches all known optimal and the best solutions from literature, but in much shorter time. Hybridization with local search improves several best-known solutions for large-scale MLUFLP instances, in cases when the optimal is not known. Overall running time of both proposed GA methods is significantly shorter compared to previous GA approach.

Keywords

evolutionary approach, metaheuristics, discrete location, combinatorial optimization.

MLUFLP instances (.7z, 11 MB) | MLUFLP optimal and best known results | Journal site - full paper

2012.

Minimal doubly resolving sets and the strong metric dimension of some convex polytopes

Jozef Kratica, Vera Kovačević-Vujčić, Mirajana Čangalović, Milica Stojanović

Applied Mathematics and Computation, Vol. 218, No. 19, pp. 9790-9801, 2012.

Abstract

In this paper we consider two similar optimization problems on graphs: the strong metric dimension problem and the problem of determining minimal doubly resolving sets. We prove some properties of strong resolving sets and give an integer linear programming formulation of the strong metric dimension problem. These results are used to derive explicit expressions in terms of the dimension $n$, for the strong metric dimension of two classes of convex polytopes $D_n$ and $T_n$. On the other hand, we prove that minimal doubly resolving sets of $D_n$ and $T_n$ have constant cardinality for $n>7$.

Keywords

Minimal doubly resolving set, Strong metric dimension, Convex polytopes

AMS 2010 Primary Class. 05C12, AMS 2010 Secondary Class. 90C10

Journal site - full paper

Variable neighborhood search for metric dimension and minimal doubly resolving set problems

Nenad Mladenović, Jozef Kratica, Vera Kovačević-Vujčić, Mirajana Čangalović

European Journal of Operational Research, Vol. 220, pp. 328-337, 2012.

Abstract

In this paper, two similar NP-hard optimization problems on graphs are considered: the metric dimension problem and the problem of determining a doubly resolving set with the minimum cardinality. Both are present in many diverse areas, including network discovery and verification, robot navigation, and chemistry. For each problem, a new mathematical programming formulation is proposed. For solving more realistic large-size instances, a variable neighborhood search based heuristic is designed. An extensive experimental comparison on five different types of instances indicates that the VNS approach consistently outperforms a genetic algorithm, the only existing heuristic in the literature designed for solving those problems.

Keywords

Metaheuristics, Combinatorial optimization, Variable neighborhood search, Metric dimension, Minimal doubly resolving set

Journal site - full paper | GERAD Preprint

Minimal doubly resolving sets and the strong metric dimension of Hamming graphs

Jozef Kratica, Vera Kovačević-Vujčić, Mirajana Čangalović, Milica Stojanović

Applicable Analysis and Discrete Mathematics, Vol. 6, No. 1, pp. 63-71, 2012.

Abstract

We consider the problem of determining the cardinality $\psi(H_{2,k})$ of minimal doubly resolving sets of Hamming graphs $H_{2,k}$. We prove that for $k \geq 6$ every minimal resolving set of $H_{2,k}$ is also a doubly resolving set, and, consequently, $\psi(H_{2,k})$ is equal to the metric dimension of $H_{2,k}$, which is known from the literature. Moreover, we find an explicit expression for the strong metric dimension of all Hamming graphs $H_{n,k}$.

Keywords

Hamming graphs, metric dimension, minimal doubly resolving set, strong metric dimension, graph theory.

Journal site - Full paper

An Electromagnetism-Like Approach for Solving the Low Autocorrelation Binary Sequence Problem

Jozef Kratica

International Journal of Computers, Communications & Control, Vol. 7, No. 4, pp. 687-694, 2012.
Abstract | Journal site - Full paper

A genetic algorithm for the routing and carrier selection problem

Jozef Kratica, Tijana Kostić, Dušan Tošić, Djordje Dugošija, Vladimir Filipović

Computer Science and Information Systems - COMSIS, Vol. 9, No. 1, pp. 49-62, January 2012.

Abstract

In this paper we present new evolutionary approach for solving the Routing and Carrier Selection Problem (RCSP). New encoding scheme is implemented with appropriate objective function. This approach in most cases keeps the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard data sets known from the literature and results were successful comparing to two other recent heuristic for solving RCSP.

Keywords

vehicle routing problems, genetic algorithm, evolutionary computation, combinatorial optimization.

Journal site - full paper

A mixed integer quadratic programming model for the low autocorrelation binary sequence problem

Jozef Kratica

Serdica Journal of Computing, Vol. 6, No. 4, pp. 49-62, pp. 385-400, 2012.

Abstract

In this paper the low autocorrelation binary sequence problem (LABSP) is modeled as a mixed integer quadratic programming (MIQP) problem and proof of the model's validity is given. Since the MIQP model is semidefinite, general optimization solvers can be used, and converge in a finite number of iterations. The experimental results show that IQP solvers, based on this MIQP formulation, are capable of optimally solving general/skew-symmetric LABSP instances up to 30/51 elements in a moderate time.

Keywords

Integer programming, Quadratic programming, low autocorrelation binary sequence problem

ACM Computing Classification System (1998): G.1.6, I.2.8



Variable neighborhood search for the strong metric dimension problem

Nenad Mladenović, Jozef Kratica, Vera Kovačević-Vujčić, Mirjana Čangalović

Electronic Notes in Discrete Mathematics, Vol. 39, pp. 51-57, 2012. DOI:10.1016/j.endm.2012.10.008

Abstract

We consider a variable neighborhood search (VNS) approach for solving the strong metric dimension problem. Computational experiments on ORLIB instances show that the VNS outperformes a genetic algorithm, the only existing heuristic in the literature for solving this problem.

Keywords

Strong metric dimension, metaheuristics, combinatorial optimization.

Journal site - full paper

Variable neighborhood search for solving the balanced location problem

Jozef Kratica, Markus Leitner, Ivana Ljubić

Electronic Notes in Discrete Mathematics, Vol. 39, pp. 21-28, 2012. DOI:10.1016/j.endm.2012.10.004

Abstract

In this paper we propose a general variable neighborhood search approach for the balanced location problem. Next to large shaking neighborhoods, the embedded variable neighborhood descent utilizes three neighborhood structures that focus on different solution aspects. By a computational study, we show that this VNS outperforms existing methods with respect to average solution quality and stability.

Keywords

discrete location, balanced allocation of clients, variable neighborhood search

Technical report | Journal site - full paper

Variable neighborhood search for multiple level warehouse layout problem

Dragan Matić, Jozef Kratica, Vladimir Filipović, Djordje Dugošija

Electronic Notes in Discrete Mathematics, Vol. 39, pp. 161-168, 2012. DOI:10.1016/j.endm.2012.10.022

Abstract

In this paper we present a variable neighborhood search algorithm (VNS) for solving Multiple Level Warehouse Layout Problem (MLWLP). The algorithm deals with a specific representation of the solution, enabling the effective application of the shaking and local search procedures. System of neighborhoods changes the assignment ordering for an increasing number of items, while local search procedure tries to locally improve the solution by swapping the assignment ordering for pairs of items. Numerical experiments are performed on instances known in the literature. Computational results show that the proposed VNS achieves all optimal solutions for smaller instances, while for larger instances it finds rather better solutions than previously known method.

Keywords

Warehouse Layout, Variable Neighborhood Search, Discrete Optimization

Journal site - full paper

2011.

An evolutionary based approach for solving a capacitated hub location problem

Jozef Kratica, Marija Milanović, Zorica Stanimirović, Dušan Tošić

Applied Soft Computing, Vol. 11, No. 2, pp. pp. 1858-1866, 2011.

Abstract

This paper addresses the Capacitated Hub Location Problem (CHLP), which is a variant of the classical capacitated hub problem. What is presented is a modified mixed integer linear programming (MILP) formulation for the CHLP. This modified formulation includes fewer variables and constraints compared to the existing problem formulations in the literature. We propose two evolutionary algorithms (EAs) that use binary encoding and standard genetic operators adapted to the problem. The overall performance of both EA implementations is improved by a caching technique. In order to solve large-scale instances within reasonable time, the second EA also uses a newly designed heuristic to approximate the objective function value. The presented computational study indicates that the first EA reaches optimal solutions for all smaller and medium-size problem instances. The second EA obtains high-quality solutions for larger problem dimensions and provides solutions for large-scale instances that have not been addressed in the literature so far.

Keywords

Genetic algorithms; Network design; Capacitated hub location problems; Transportation and telecommunication networks.

Journal site - full paper

Two metaheuristic approaches to solving the p-ary transitive reduction problem

Marija Milanović, Dragan Matić, Aleksandar Savić, Jozef Kratica

Applied and Computational Mathematics, Vol. 10, No. 2, pp. 294-308, 2011.

Abstract

Two metaheuristic methods for solving the $p$-ary transitive reduction (TR$_p$) problem are proposed: a genetic algorithm and a reduced variable neighborhood search method. Experiments were performed on a set of randomly generated instances. Presented results are the first experimental results in the literature so far for values $p>2$.

Keywords

evolutionary algorithm, variable neighborhood search, transitive reduction, signal transduction networks, systems biology.



A new genetic representation for quadratic assignment problem

Jozef Kratica, Dušan Tošić, Vladimir Filipović, Djordje Dugošija

Yugoslav Journal of Operations Research, Vol. 21, No. 2, pp. 225-238, 2011.

Abstract

In this paper, we propose a new genetic encoding for well known Quadratic Assignment Problem (QAP). The new encoding schemes are implemented with appropriate objective function and modified genetic operators. The numerical experiments were carried out on the standard QAPLIB data sets known from the literature. The presented results show that in all cases proposed genetic algorithm reached known optimal solutions in reasonable time.

Keywords

Genetic algorithm, evolutionary computation, combinatorial optimization, quadratic assignment problem.

Journal site - full paper

2010.

A mixed integer linear programming formulation of the maximum betweenness problem

Aleksandar Savić, Jozef Kratica, Marija Milanović, Djordje Dugošija

European Journal of Operational Research, Vol. 206, No. 3, pp. 522-527. 2010.

Abstract

This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time.

Keywords

Integer programming; Linear programming; Betweenness problem

Journal site - full paper

Solving the task assignment problem with a variable neighborhood search

Jozef Kratica, Aleksandar Savić, Vladimir Filipović, Marija Milanović

Serdica Journal of Computing, Vol. 4, No. 4, pp. 435-446, 2010.

Abstract

In this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. Appropriate neighborhood scheme along with shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by genetic algorithm. It can be seen that the proposed VNS approach reaches all optimal solutions in a quite short amount of computational time.

Keywords

Task assignment, multiprocessor systems, variable neighborhood search, assignment problems, combinatorial optimization.

Abstract on the publisher site



Mathematical optimization for the train timetabling problem

Predrag Stanojević, Miroslav Marić, Jozef Kratica, Nebojsa Bojović, Milos Milenković

Mathematica Balkanica, Vol. 24, No. 3-4, pp. 303-312, 2010.

Abstract

Rail transportation is very rich in terms of problems that can be modelled and solved using mathematical optimization techniques. Train scheduling problem as the most important part of a rail operating policy has a very significant impact on a rail company profit considering the fact that from the quality of a train timetable depends a flow of three most important resources on rail network: cars, locomotives and crews. The train timetabling problem aims at determining a periodic timetable for a set of trains that does not violate track capacities and satisfies some operational constraints. In this paper, we developed an integer programming approach for determining an optimal train schedule for a single, one-way track linking two major stations, with a number of intermediate stations between. The application has been tested on a realistic example suggested by the PE "Serbian Railways". Obtained results show a potential for a practical application of proposed approach.

Keywords

rail transportation, scheduling, timetabling, integer programming

Abstract on the publisher site



2009.

Computing minimal doubly resolving sets of graphs

Jozef Kratica, Mirjana Čangalović, Vera Kovačević-Vujčić

Computers & Operations Research, Vol. 36, No. 7, pp. 2149-2159, 2009.

Abstract

In this paper we consider the minimal doubly resolving sets problem (MDRSP) of graphs. We prove that the problem is NP-hard and give its integer linear programming formulation. The problem is solved by a genetic algorithm (GA) that uses binary encoding and standard genetic operators adapted to the problem. Experimental results include three sets of ORLIB test instances: crew scheduling, pseudo-boolean and graph coloring. GA is also tested on theoretically challenging large-scale instances of hypercubes and Hamming graphs. Optimality of GA solutions on smaller size instances has been verified by total enumeration. For several larger instances optimality follows from the existing theoretical results. The GA results for MDRSP of hypercubes are used by a dynamic programming approach to obtain upper bounds for the metric dimension of large hypercubes up to 2^90 nodes, that cannot be directly handled by the computer.

Keywords

Minimal doubly resolving sets; Metric dimension; Genetic algorithms; Evolutionary approach; Hypercubes

Full paper on the publisher site

Computing the metric dimension of graphs by genetic algorithms

Jozef Kratica, Vera Kovačević-Vujčić, Mirjana Čangalović

Computational Optimization and Applications, Vol. 44, No. 2, pp. 343-361, 2009.

Abstract

In this paper we consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes.

Keywords

Graph theory; Metric dimension; Evolutionary approach

Full paper on the publisher site

Two hybrid genetic algorithms for solving the super-peer selection problem

Jozef Kratica, Jelena Kojić, Dušan Tošić, Vladimir Filipović, Djordje Dugošija

Applications of Soft Computing: From theory to Praxis, Menhen J., Köppen M., Saad A., Tiwari A., edition: Advances in Intelligent and Soft Computing, Vol. 58, Springer-Verlag, Berlin Heidelberg, ISBN: 978-3-540-89618-0, ISSN: 1867-5662, pp. 337-346, 2009.

Abstract

The problem that we will address here is the Super-Peer Selection Problem (SPSP). Two hybrid genetic algorithm (HGA) approaches are proposed for solving this NP-hard problem. The new encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard data set known from the literature. The results of this test show that in 6 out of 12 cases HGAs outreached best known solutions so far, and that our methods are competitive with other heuristics.

Keywords

Genetic algorithms, Evolutionary computation, %Peer-to-peer network topology, Combinatorial optimization.

Full paper on the publisher site

GA inspired heuristic for uncapacitated single allocation hub location problem

Vladimir Filipović, Jozef Kratica, Dušan Tošić, Djordje Dugošija

Applications of Soft Computing: From theory to Praxis, Menhen J., Köppen M., Saad A., Tiwari A., edition: Advances in Intelligent and Soft Computing, Vol. 58, Springer-Verlag, Berlin Heidelberg, ISBN: 978-3-540-89618-0, ISSN: 1867-5662, pp. 149-158, 2009.

Abstract

In this article, the results achieved by applying GA-inspired heuristic on Uncapacitated Single Allocation Hub Location Problem (USAHLP) are discussed. Encoding scheme with two parts is implemented, with appropriate objective functions and modified genetic operators. The article presents several computational tests which have been conducted with ORLIB instances. Procedures described in related work round distance matrix elements to few digits, so rounding error is significant. Due to this fact, we developed exact total enumeration method for solving subproblem with fixed hubs, named Hub Median Single Allocation Problem (HMSAP). Computational tests demonstrate that GA-inspired heuristic reach all best solutions for USAHLP that are previously obtained and verified branch-and-bound method for HMSAP. Proposed heuristic successfully solved some instances that were unsolved before.

Keywords

Genetic algorithms, Evolutionary computations, Hub location, USAHLP, HMSAP.

Full paper on the publisher site

2008.

Solving the maximally balanced connected partition problem in graphs by using genetic algorithm

Brankica Djurić, Jozef Kratica, Dušan Tošić, Vladimir Filipović

Computing and Informatics, Vol. 27, No. 3, pp. 341-354, 2008.

Abstract

This paper exposes a research of the NP-hard Maximally Balanced Con- nected Partition problem (MBCP). The proposed solution comprises of a genetic algorithm (GA) that uses: binary representation, fine-grained tournament selection, one-point crossover, simple mutation with frozen genes and caching technique. In cases of unconnected partitions, penalty functions are successfully applied in or- der to obtain the feasible individuals. The effectiveness of presented approach is demonstrated on the grid graph instances and on random instances with up to 300 vertices and 2000 edges.

Keywords

Balanced partitions, evolutionary computation, metaheuristics, combinatorial optimization

Computing strong metric dimension of some special classes of graphs by genetic algorithms

Jozef Kratica, Vera Kovačević-Vujčić, Mirjana Čangalović

Yugoslav Journal of Operations Research, Vol 18, No 2., pp. 143-151, 2008.

Abstract

In this paper we consider the NP-hard problem of determining the strong metric dimension of graphs. The problem is solved by a genetic algorithm that uses binary encoding and standard genetic operators adapted to the problem. This represents the first attempt to solve this problem heuristically. We report experimental results for two special classes of ORLIB test instances: crew scheduling and graph coloring.

Keywords

Strong metric dimension, genetic algorithms, evolutionary approach

Full paper on the publisher site

Genetic algorithm approach for solving the task assignment problem

Aleksandar Savić, Dušan Tošić, Miroslav Marić, Jozef Kratica

Serdica Journal of Computing, Vol. 2, pp. 267-276, 2008.

Abstract

In this paper a genetic algorithm (GA) for the task assignment problem (TAP) is considered.An integer representation with standard ge- netic operators is used. Computational results are presented for instances from the literature, and compared to optimal solutions obtained by the CPLEX solver. It can be seen that the proposed GA approach reaches 17 of 20 optimal solutions. The GA solutions are obtained in a quite a short amount of computational time.

Keywords

evolutionary approach; genetic algorithms; assignment problems, multiprocessor systems, combinatorial optimization

Full paper on the publisher site

Parameter adjustment for genetic algorithm for two-level hierarchical covering location problem

Miroslav Marić, Milan Tuba, Jozef Kratica

WSEAS Transactions on Computers, Vol. 7, No. 6, pp. 746-755, 2008.

Abstract

In this paper the two-level Hierarchical Covering Location Problem - HCLP is considered. A new genetic algorithm for that problem is developed, including specific binary encoding with the new crossover and mutation operators that keep the feasibility of individuals. Modification that resolves the problem of frozen bits in genetic code is proposed and tested. Version of fine-grained tournament [5] was used as well as the caching GA technique [12] in order to improve computational performance. Genetic algorithm was tested and its parameters were adjusted on number of test examples and it performed well and proved robust in all cases. Results were verified by CPLEX.

Keywords

Genetic Algorithms, Evolutionary computing, Location problem, Hierarchical location, Covering models



2007.

Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem

Jozef Kratica, Zorica Stanimirović, Dušan Tošić, Vladimir Filipović

European Journal of Operational Research, Vol. 182, No. 1, pp. 15-28, 2007.

Abstract

This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.

Keywords

Genetic algorithms; Evolutionary computations; Location; p-Hub median problem; Single allocation

Full paper on the publisher site

Genetic algorithms for solving the discrete ordered median problem

Zorica Stanimirović, Jozef Kratica, Djordje Dugošija

European Journal of Operational Research, Vol. 182, No. 3, pp. 983-1001, 2007.

Abstract

In this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits.

Keywords

Genetic algorithms; Evolutionary computations; Discrete location

Full paper on the publisher site Additional computational results

2006. or earlier

Solving the uncapacitated multiple allocation p-hub center problem by genetic algorithm

Jozef Kratica, Zorica Stanimirović

Asia-Pacific Journal of Operational Research, Vol. 24, No. 4, pp. 425-437, 2006.

Abstract

In this paper we describe a genetic algorithm (GA) for the uncapacitated multiple allocation p-hub center problem (UMApHCP). Binary coding is used and genetic operators adapted to the problem are constructed and implemented in our GA. Computational results are presented for the standard hub instances from the literature. It can be seen that proposed GA approach reaches all solutions that are proved to be optimal so far. The solutions are obtained in a reasonable amount of computational time, even for problem instances of higher dimensions.

Keywords

p-hub center problem; genetic algorithms; discrete location problems.

Full paper on the publisher site

Genetic algorithm for solving uncapacitated multiple allocation hub location problem

Jozef Kratica, Zorica Stanimirović, Dušan Tošić, Vladimir Filipović

Computing and Informatics, Vol. 24, pp. 415-426, 2005.

Abstract

Hub location problems are widely used for network designing. Many variations of these problems can be found in the literature. In this paper we deal with the uncapacitated multiple allocation hub location problem (UMAHLP). We propose a genetic algorithm (GA) for solving UMAHLP that uses binary encoding and genetic operators adapted to the problem. Overall performance of GA implementation is improved by caching technique. We present the results of our computational experience on standard ORLIB instances with up to 200 nodes. The results show that GA approach quickly reaches all optimal solutions that are known so far and also gives results on some large-scale instances that were unsolved before.

Keywords

Hub location problem, genetic algorithms, evolutionary computation, discrete location and assignment, network design, combinatorial optimization

A genetic algorithm for probabilistic SAT problem

Zoran Ognjanović, Uroš Midić, Jozef Kratica

Lecture Notes in Artificial Intelligence - LNAI, Vol. 3070, pp. 462–467, 2004.

Abstract

We describe new results in developing of a satisfiability checker for probabilistic logic based on the genetic algorithm approach combined with a local search procedure. Computational experiences show that problems with 200 propositional letters can be solved. They are, to the best of our knowledge, the largest PSAT-problems reported in the literature.

Keywords

Full paper on the publisher site

A genetic algorithm for the index selection problem

Jozef Kratica, Ivana Ljubić, Dušan Tošić

Lecture Notes in Computer Science - LNCS, Vol. 2611, pp. 281-291, 2003.

Abstract

This paper considers the problem of minimizing the response time for a given database workload by a proper choice of indexes. This problem is NP-hard and known in the literature as the Index Selection Problem (ISP). We propose a genetic algorithm (GA) for solving the ISP. Computational results of the GA on standard ISP instances are compared to branch-and- cut method and its initialisation heuristics and two state of the art MIP solvers: CPLEX and OSL. These results indicate good performance, reliability and efficiency of the proposed approach.

Full paper (PDF 188 KB) | Full paper on the publisher site

| Class A instances (TGZ - 512 KB) | Class B instances (TGZ - 352 KB)

A genetic algorithm for the uncapacitated network design problem

Jozef Kratica, Dušan Tošić, Vladimir Filipović, Ivana Ljubić

Soft Computing in Industry - Recent Applications, R. Roy, M. Koppen, S. Ovaska, T. Furuhashi, F. Hoffmann, Springer Verlag, pp. 329-338., 2002.

Abstract

In this paper is presented genetic algorithm (GA) for solving the uncapacitated network design problem (UNDP) with single sources and destinations for each commodity. UNDP is base in class of the network design problems, but it is still NP-hard. Robust GA implementation is additionally improved by caching GA technique. Computational results on instances up to 50 commodities, 100 nodes and 700 edges are reported.



Solving a Semidefinite Relaxation of the Traveling Salesman Problem

Vera Kovačević-Vujčić, Mirjana Čangalović, Jozef Kratica

Central European Journal of Operations Research - CEJOR, Vol. 10, No. 4, pp. 277-296, 2002.

Abstract

This paper studies the behavior of the semidefinite programming method proposed by Helmberg, Rendl, Vanderbei and Wolkowicz on a special class of semidefmite programs obtained as relaxations of the symmetric traveling salesman problem (STSP. We propose modifications which reduce the computational time and improve numerical stability. Computational results for the STSP instances with dimensions up to 60 are reported.



A genetic algorithm for satisfiability problem in a probabilistic logic: A first report

Zoran Ognjanović, Jozef Kratica, Miloš Milovanović

Springer Lecture Notes in Artificial Intelligence - LNAI, Vol. 2143, pp. 805-816, 2002.

Abstract

This paper introduces a genetic algorithm for satisfiability problem in a probabilistic logic. A local search based improvement procedure is integrated in the algorithm. A test methodology is presented and some results are given. The results indicate that this approach could work well. Some directions for further research are described.

Full paper on the publisher site

Solving the simple plant location problem by genetic algorithms

Jozef Kratica,Dušan Tošić, Vladimir Filipović, Ivana Ljubić

RAIRO - Operations Research, Vol. 35, No. 1, pp. 127-142, 2001.

Abstract

The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.

Keywords

Simple plant location problem, genetic algorithms, combinatorial optimization. RAIRO RO Contents | Full paper | Go to RAIRO - Operations Research (RO) home page| SPLP - Original M instances win32 generator (ZIP - 33 KB) | SPLP - Original M instances win32 generator mirror (ZIP - 33 KB)



A hybrid GA for the edge-biconnectivity augmentation problem

Ivana Ljubić, Günther Raidl, Jozef Kratica

Lecture Notes in Computer Science, Vol. 1917, pp. 641-650, 2000.

Abstract

In the design of communication networks, robustness against failures in single links or nodes is an important issue. This paper proposes a new approach for the NP-complete edge-biconnectivity augmentation (E2AUG) problem, in which a given graph G (V;E) needs to be augmented by the cheapest possible set of edges AUG so that a single edge deletion does not disconnect G. The new approach is based on a preliminary reduction of the problem and a genetic algorithm (GA) using a binary vector to represent a set of augmenting edges and therefore a candidate solution. Two strategies are proposed to deal with infeasible solutions that do not lead to edge-biconnectivity. In the first, more traditional variant, infeasible solutions are detected and simply discarded. The second method is a hybrid approach that uses an effective heuristic to repair infeasible solutions by adding usually cheap edges to AUG until the graph augmented with AUG becomes edge-biconnected. The two GA-variants are empirically compared to each other and to another iterative heuristic for the E2AUG problem using instances involving up to 1270 edges.

Connectivity Augmentation Problems in Graphs | Full paper | Full paper on the publisher site

Solving inverse geophysical problem by genetic algorithm

Vesna šešum, Jozef Kratica, Dušan Tošić

Yugoslav Journal of Operational Research - YUJOR, Vol. 10, No. 2, pp. 283-292, 2000.

Abstract

Tomographic methods are often used to solve the geophysical inversion problem. This is the problem of determining the characteristics of an underground region by using measurement data. With a tomographic method, the pictures of the physical properties in the region between pairs of boreholes can be reconstructed. In this paper, we apply genetic algorithms to cross-hole seismic line-integral data. These data can be generated by the transmission problem through the cross-hole region using seismic energy. Some test-examples for measuring the performance of the applied genetic algorithms are presented. The obtained results are promising.

Keywords

Genetic algorithm, tomography, geophysical inversion problem.

Full paper - PDF (62 KB)

Improving performances of the genetic algorithm by caching

Jozef Kratica

Computers and Artificial Intelligence, Vol. 18, No. 3, pp. 271-283, 1999.

Abstract

In this paper we optimize run-time performance of the genetic algorithm by caching. We are caching the genetic algorithm procedure for evaluation of an objective function. Least Recently Used (LRU) caching strategy is used, that is simple but effective. This approach is good for problems that have a relatively small length of item string, and a large evaluation time of objective function. We present results of the caching to genetic algorithm for solving one such problem - the simple plant location problem (SPLP).

Keywords

Genetic algorithms, caching, simple plant location problem

Go to Journal home page | Vol. 18, No 3. Abstracts

Improvement of simple genetic algorithm for solving the uncapacitated warehouse location problem

Jozef Kratica

Advances in Soft Computing - Engineering Design and Manufacturing, R.Roy, T. Furuhashi and P.K. Chawdhry, Springer-Verlag London Limited, pp. 390-402, 1998., ISBN: 1-85233-062-7

Abstract

This paper investigates the applicability of the improvement of simple genetic algorithm (SGA) method for solving the uncapacitated warehouse location problem (UWLP). Function for computing the item’s objective value is improved depending upon the number of established warehouses. It is efficiently implemented, giving excellent results in specified environment. Mutation rate is also changed and now depends on test problem size. Duplicate item strings in population are discarded, which makes the population more diversified. Overall performance of implementation is finally tuned by caching SGA. Through caching technique relatively smaller profit in performance is obtained when compared to previous techniques, but it is a general technique, and can be directly applied to other problems, not only to UWLP. Computational experience with given problem examples indicates that, when compared to code in [1], the implementation of the modified algorithm is faster several times. For large size test problems the increase of computational speed may even exceed factor 10, and quality of obtained solutions is also significantly better.

Keywords

Genetic Algorithms, Uncapacitated Warehouse Location Problem.



One Method of Implementation of LISP Interpreter to Transputers

Jozef Kratica

FILOMAT, Vol. 9, No. 2, pp. 367-376, 1995.

Abstract

The paper describes one method of implementation of LISP interpreter to transputers. Developed interpreter contains standard functions common for almost all LISP versions. Architecture is binary tree message passing. Implementation was developed on transputer parallel C language (ANSI C with procedures for interprocess or communications and synchronization). Part intended for evaluation of functions (expressions) was parallelized, but I/O operation and parsing were sequential. This is caused by the technical limitations of transputer systems, because I/O operations can executed only by first transputer, and interprocess or communication is slow. Maxima increase in speed equals 6.5 times, on transputer system with 17 transputers T800, by as compared to single transputer T800. That increase in speed is obtained for recursive problems de­manding much computing. Small increase in speed is obtained for problems with more I/O operations.



Last update: 08. 05. 2012.