An enhanced bitstring encoding for exact maximum clique search in sparse graphs
This paper describes BBMCW, a new efficient exact maximum clique algorithm tailored for large sparse graphs which can be bit-encoded directly into memory without a heavy performance penalty. These graphs occur in real-life problems when some form of locality may be exploited to reduce their scale. One such example is correspondence graphs derived from data association problems. The new algorithm is based on the bit-parallel kernel used by the BBMC family of published exact algorithms. BBMCW employs a new bitstring encoding that we denote ‘watched’, because it is reminiscent of the ‘watched literal’ technique used in satisfiability and other constraint problems. The new encoding reduces the number of spurious operations computed by the BBMC bit-parallel kernel in large sparse graphs. Moreover, BBMCW also improves on bound computation proposed in the literature for bit-parallel solvers. Experimental results show that the new algorithm performs better than prior algorithms over data sets of both real and synthetic sparse graphs. In the real data sets, the improvement in performance averages more than two orders of magnitude with respect to the state-of-the-art exact solver IncMaxCLQ.
This paper describes our approach to document search based on the ontological resources and graph models. The approach is applicable in local networks and local computers. It can be useful for ontology engineering specialists or search specialists.
The article describes the original software tools for an experimental estimation of computational complexity of software solutions for problems on graph models of systems. The classes of the solved problems and the tools for analysis of results are listed. The method based on selection of graph models by their structural complexity is introduced.
This volume contains two types of papers—a selection of contributions from the “Second International Conference in Network Analysis” held in Nizhny Novgorod on May 7–9, 2012, and papers submitted to an "open call for papers" reflecting the activities of LATNA at the Higher School for Economics.
This volume contains many new results in modeling and powerful algorithmic solutions applied to problems in
- vehicle routing
- single machine scheduling
- modern financial markets
- cell formation in group technology
- brain activities of left- and right-handers
- speeding up algorithms for the maximum clique problem
- analysis and applications of different measures in clustering
The broad range of applications that can be described and analyzed by means of a network brings together researchers, practitioners, and other scientific communities from numerous fields such as Operations Research, Computer Science, Bioinformatics, Medicine, Transportation, Energy, Social Sciences, and more. The contributions not only come from different fields, but also cover a broad range of topics relevant to the theory and practice of network analysis. Researchers, students, and engineers from various disciplines will benefit from the state-of-the-art in models, algorithms, technologies, and techniques including new research directions and open questions.
In this paper, we consider the asymmetric capacitated vehicle routing problem (ACVRP). We compare the search tree size and computational time for the bottleneck tolerance-based and cost-based branching rules within a branch-and-bound algorithm on the FTV benchmark instances. Our computational experiments show that the tolerance-based branching rule reduces the search tree size by 45 times and the CPU time by 2.8 times in average.
Panos Pardalos was born to parents Calypso and Miltiades on June 17, 1954, in Mezilo (now Drossato), Greece. Ever since his grandmother Sophia taught him how to count in his early childhood, Panos has been fascinated with mathematics. The remote location of the mountain village and rather unfavorable economic conditions Panos grew up in would not stop him from pursuing knowledge. When he was 15, Panos wrote a letter to the Greek Ministry of Education describing his aspirations and the obstacles he faced in his quest for learning. The government responded by providing a scholarship to support his studies at the Athens University. After obtaining a bachelor’s degree in mathematics in 1977, Panos continued his education in the United States. In 1978, he earned a master’s degree in mathe- matics and computer science from Clarkson University (Potsdam, NY) and started Ph.D. studies in computer and information sciences at the University of Minnesota. In 1985, Panos successfully defended his dissertation, which served as the basis for his ﬁrst book Constrained Global Optimization: Algorithms and Applications (Springer-Verlag, 1987) co-authored with his Ph.D. advisor, Judah Ben Rosen. This book became a landmark publication in the emerging ﬁeld of global optimization and helped Dr. Pardalos to establish himself as one of the leading researchers in the ﬁeld. By the time of the book’s publication he already started his independent academic career as an assistant professor of computer science at the Pennsylvania State University. In 1991, Panos moved to the Department of Industrial and Systems Engineer- ing at the University of Florida (UF), where he currently holds a position of Dis- tinguished Professor and University of Florida Research Foundation Professor and also serves as the director of Center for Applied Optimization. At UF, he is also an afﬁliated faculty of Computer & Information Science & Engineering Department, Biomedical Engineering Department, McKnight Brain Institute, and the Genetics Institute. Dr. Pardalos compiled a very impressive record over the years of his (still very active) academic career, which includes nearly 20 co-authored books and over 300 journal articles. He is also an editor of numerous books, including 7-volume En- cyclopedia of Optimization (co-edited with Christodoulos Floudas) published by vvi Preface Springer. He served as the editor in chief and an editorial board member of many highly-respected journals and as the managing editor of several book series. He has organized conferences and gave plenary lectures in world leading institutions. Over 50 of his former Ph.D. students enjoy successful careers in academia and industry, making the impact of his mentoring felt all over the world. Professor Pardalos was honored with a number of awards for his scholastic achievements. His notable recognitions include the Constantin Carath´eodory Prize (2013) and EURO Gold Medal (2013); Honorary Doctorates from N.I. Lobachevski State University of Nizhni Novgorod, Russia (2005), V.M. Glushkov Institute of Cybernetics of The National Academy of Sciences of Ukraine (2008), and Wil- frid Laurier University, Canada (2012); Honorary Professorships from the Graduate School of Information Technology & Mathematical Sciences, University of Ballarat, Australia (2010) and from Anhui University of Sciences and Technology, China (2013). He was elected a Foreign Associate Member of Reial Acad´emia de Doctors, Spain (1998), a Foreign Member of Lithuanian Academy of Sciences (1999), Petro- vskaya Academy of Sciences and Arts, Russia (2000), and the National Academy of Sciences of Ukraine (2003), as well as an Honorary Member of the Mongolian Academy of Sciences (2005). He is also the recipient of a medal in recognition of broad contributions in science and engineering of the University of Catania, Italy (2013). Ivan V. Sergienko, Academician of the National Academy of Sciences of Ukraine (NASU), presents the diploma of a foreign member of NASU to Professor Panos M. Pardalos (2003). As impressive as his academic accomplishments are, it is safe to say that his personal qualities and friendship are the primary reasons Panos is so much lovedPreface vii and respected by his colleagues and students. As he likes to say, “Whatever it is that we do, we are humans ﬁrst.” His enthusiasm for science is just a reﬂection of his positive, energetic, and happy personality. He always remembers about his roots and knows how to enjoy simple things in life. Many of the readers might have heard the following story about Panos that is very characteristic of his caring nature. When he was a Ph.D. student at the University of Minnesota, Panos planted a grapefruit seed in a pot, and a tree started growing. When he moved to Penn State a few years later, he brought the plant with him. The next destination for Panos and the tree was Gainesville, Florida, where the climate was ﬁnally warm enough for planting a grapefruit tree outside. After some proﬁcient treatment from Panos’s father, the tree thrived as did Panos’s career at UF, bearing so much highest-quality fruit that it was plenty not only for the Pardalos family, but also for Panos’s colleagues and students in the department to enjoy. Panos with his son, Akis, and wife, Rosemary, next to the famous grapefruit tree, February 1, 2014. On behalf of all the authors of chapters, we are very pleased to dedicate this book to Panos Pardalos on occasion of his 60th birthday, and wish him many more happy, healthy, and productive years. We would like to thank all the contributors and Eliz- abeth Loew of Springer for making this publication possible. Xρ ´oνια Πoλλ ´α Π ´ανo! Athens, Greece Themistocles M. Rassias Princeton, New Jersey, USA Christodoulos Floudas College Station, Texas, USA Sergiy Butenko
Data Correcting Algorithms in Combinatorial Optimization focuses on algorithmic applications of the well known polynomially solvable special cases of computationally intractable problems. The purpose of this text is to design practically efficient algorithms for solving wide classes of combinatorial optimization problems. Researches, students and engineers will benefit from new bounds and branching rules in development efficient branch-and-bound type computational algorithms. This book examines applications for solving the Traveling Salesman Problem and its variations, Maximum Weight Independent Set Problem, Different Classes of Allocation and Cluster Analysis as well as some classes of Scheduling Problems. Data Correcting Algorithms in Combinatorial Optimization introduces the data correcting approach to algorithms which provide an answer to the following questions: how to construct a bound to the original intractable problem and find which element of the corrected instance one should branch such that the total size of search tree will be minimized. The PC time needed for solving intractable problems will be adjusted with the requirements for solving real world problems.
Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph.
Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even tighter bounds by reducing each colored subproblem to maximum satisfiability problem (MaxSAT). Moreover they show empirically that the new bounds obtained may be lower than the chromatic number.
Based on this idea this paper shows an efficient way to compute related “infra-chromatic” upper bounds without an explicit MaxSAT encoding. The reported results show some of the best times for a stand-alone computer over a number of instances from standard benchmarks.
We present an approach based on a two-stage ltration of the set of feasible solutions for the multiprocessor job-shop scheduling problem. On the rst stage we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can eciently be obtained and implemented.