» Download Article

Authors
Kochetov, Yuri; Plyasunov, Alexandr; Mikhailova, Anastasiya

Identifier
10.3182/20090603-3-RU-2001.00335

Index Terms
Heuristic and Metaheuristics; Integer Linear Programming; Discrete Applied Mathematics

Abstract
A new genetic local search algorithm is designed for the graph partitioning problem with cardinality constraint for each subset of the vertices. The family of local optima under the polynomial neighborhoods is used as a population in order to systematically produce better local optima. It is shown that the corresponding local search problems are tightly PLS-complete. So, any local improvement algorithm takes, in the worst case, an exponential number of iterations regardless of the tie--breaking and pivoting rules used. Nevertheless, the local search problems are polynomially solvable if all weights of the edges are identical. For this case, computational experiments are produced for the real--world and random test instances. We observe that this algorithm is efficient and effective. It allows to find the high quality local optima.

References

\begin{thebibliography}{15}

\bibitem[{Bertold (2008)}]{Ber:08}
Bertold T. (2008)
\newblock Automatic detection of orbitopal symmetries.
\newblock \emph{Abstracts of International Conference Operations Research 2008,
September 3--5, 2008}, Augsburg, Germany, 198--198.

\bibitem[{Chopra, Rao (1993)}]{CR:93}
Chopra S., Rao M. R. (1993)
\newblock The partition problem
\newblock \emph{Mathematical Programming}, 59, 87--115.

\bibitem[{Dreo et~al.(2006)}]{DrPet:06}
Dreo J., Petrowski A., Siarry P., Taillard E. (2006)
\newblock Metaheuristics for Hard Optimization,
\newblock Springer.

\bibitem[{Festa, Resende (2002)}]{Resen:02}
Festa~P., Resende~M.~G.~C. (2002)
\newblock GRASP: An annotated bibliography.
\newblock In:  C.~C.~Ribeiro, P.~Hansen (Eds.) \emph{Essays and
Surveys in Metaheuristics}. Kluwer Academic Publishers, 325--368.

\bibitem[{Fiduccia, Mattheyses (1982)}]{Fid:82}
Fiduccia~C.~M., Mattheyses~R.~M. (1982)
\newblock A linear-time heuristic for improving network partitions
\newblock \emph{Proc. of
the 19-th Design Automation Conference, Los Alamitos, CA} IEEE
Comput. Soc. Press, 175--181.

\bibitem [{Gary, Johnson (1979)}]{GJ:79}
Gary~M. R., Johnson~D. S. (1979)
\newblock Computers and Intractability: A Guide to the Theory of NP--Completeness.
\newblock New York: Freeman.

\bibitem [{Glover, Laguna (1997)}]{GL:97}
Glover~F., Laguna~M. (1997)
\newblock Tabu Search.
\newblock Boston: Kluwer Acad. Publ.

\bibitem[{Kernighan, Lin (1970)}]{KL}
Kernighan B. W., Lin S. (1970)
\newblock An effective heuristic procedure for partitioning graphs
\newblock \emph{Bell System Techn J.}, 49,  291--307.

\bibitem[{Kochetov et al. (2005)}]{Koch:05}
Kochetov~Yu., Alekseeva~E., Levanova~T., Loresh~M.(2005)
\newblock Large neighborhood local search for the $p$-median problem
\newblock \emph{Yugoslav Journal of Oper. Res.}, 15(1), 53--63.

\bibitem[{Kochetov et al. (2008)}]{Koch:08a}
Kochetov~Yu., Kononova~P., Paschenko~M. (2008)
\newblock Formulation space search
approach for the teacher/class timetabling problem
\newblock \emph{Yugoslav Journal of Oper. Res.}, 18(1), 1--11.

\bibitem[{Kochetov (2008)}]{Koch:08}
Kochetov Yu. (2008)
\newblock Computational capabilities of local search in combinatorial optimization.
\newblock \emph{Computational Mathematics and Mathematical Physics}, 48(5),
747--763.

\bibitem [{Laszewski (1991)}]{Las}
Laszewski G. (1991)
\newblock Intelligent structural operators for the
$k$-way graph partitioning problem.
\newblock \emph{Proceedings of Fourth International Conference on Genetic
Algorithms, San Diego, CA, USA}, 45--52.

\bibitem [{Moraglio et al. (2007)}]{Mor}
Moraglio~A., Kim~Y.-H., Yoon~Y., Moon~B.-R. (2007)
\newblock Geometric crossovers for multiway graph partitioning,
\newblock \emph{Evolutionary Computation}, 15(4), 445--474.


\bibitem[{Nurminski (2008)}]{Nurm:08}
Nurminski E.A. (2008)
\newblock Decomposition and parallel computations via Fejer
processes with small disturbances.
\newblock \emph{ Proceedings of XIV Baikal
International School--Seminar Optimization Methods and Their
Applications}, 1, 128--135.


\bibitem [{Peinhardt (2008)}]{Pein}
Peinhardt M. (2008)
\newblock Breaking model symmetry for graph partitioning.
\newblock \emph{Abstracts of International Conference Operations
Research 2008, September 3--5, 2008, Augsburg, Germany}, 198--198.

\bibitem [{Rendl, Wolkowicz (2005)}]{RW}
Rendl F., Wolkowicz H. (2005)
\newblock A projection technique for partitioning the nodes of a graph.
\newblock \emph{Annals of Operations Research}, 58(3),155--179.


\bibitem [{Yannakakis (1997)}]{Ya}
Yannakakis~M. (1997)
\newblock Computational complexity.
\newblock In: E.~Aarts, J.~K.~Lenstra (Eds.)  \emph{Local Search in Combinatorial
Optimization}, Chichester: Wiley, 19--55.


\end{thebibliography}