Infra-chromatic bound for exact maximum clique search
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 consider the problem of planning the ISS cosmonaut training with different objectives. A pre-defined set of minimum qualification levels should be distributed between the crew members with minimum training time differences, training expenses or a maximum of the training level with a limitation of the budget. First, a description of the cosmonaut training process is given. The model are considered for the volume planning problem. The objective of the model is to minimize the differences between the total time of the preparation of all crew members. Then two models are considered for the timetabling planning problem. For the volume planning problem, two algorithms are presented. The first one is aheuristic with a complexity of O(n) operations. The second one consists of a heuristic and exact parts, and it is based on the npartition problem approach.
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.
A simple measure of similarity for the construction of the market graph is proposed. The measure is based on the probability of the coincidence of the signs of the stock returns. This measure is robust, has a simple interpretation, is easy to calculate and can be used as measure of similarity between any number of random variables. For the case of pairwise similarity the connection of this measure with the sign correlation of Fechner is noted. The properties of the proposed measure of pairwise similarity in comparison with the classic Pearson correlation are studied. The simple measure of pairwise similarity is applied (in parallel with the classic correlation) for the study of Russian and Swedish market graphs. The new measure of similarity for more than two random variables is introduced and applied to the additional deeper analysis of Russian and Swedish markets. Some interesting phenomena for the cliques and independent sets of the obtained market graphs are observed.
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.
In this chapter, we present our enhancements of one of the most efficient exact algorithms for the maximum clique problem—MCS algorithm by Tomita, Sutani, Higashi, Takahashi and Wakatsuki (in Proceedings of WALCOM’10, 2010, pp. 191–203). Our enhancements include: applying ILS heuristic by Andrade, Resende and Werneck (in Heuristics 18:525–547, 2012) to find a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial coloring, and avoiding dynamic memory allocation. A good initial solution considerably reduces the search tree size due to early pruning of branches related to small cliques. Fast detecting of clique vertices is based on coloring. Whenever a set of candidates contains a vertex adjacent to all candidates, we detect it immediately by its color and add it to the current clique avoiding unnecessary branching. Though dynamic memory allocation allows to minimize memory consumption of the program, it increases the total running time. Our computational experiments show that for dense graphs with a moderate number of vertices (like the majority of DIMACS graphs) it is more efficient to store vertices of a set of candidates and their colors on stack rather than in dynamic memory on all levels of recursion. Our algorithm solves p_hat1000-3 benchmark instance which cannot be solved by the original MCS algorithm. We got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances, correspondingly.
The cell formation problem (CFP) is an NP-hard optimization problem considered for cell manufacturing systems. Because of its high computational complexity several heuristics have been developed for solving this problem. In this paper we present a branch and bound algorithm which provides exact solutions of the CFP. This algorithm finds optimal solutions for 13 problems of the 35 popular benchmark instances from the literature.
A model for organizing cargo transportation between two node stations connected by a railway line which contains a certain number of intermediate stations is considered. The movement of cargo is in one direction. Such a situation may occur, for example, if one of the node stations is located in a region which produce raw material for manufacturing industry located in another region, and there is another node station. The organization of freight traﬃc is performed by means of a number of technologies. These technologies determine the rules for taking on cargo at the initial node station, the rules of interaction between neighboring stations, as well as the rule of distribution of cargo to the ﬁnal node stations. The process of cargo transportation is followed by the set rule of control. For such a model, one must determine possible modes of cargo transportation and describe their properties. This model is described by a ﬁnite-dimensional system of diﬀerential equations with nonlocal linear restrictions. The class of the solution satisfying nonlocal linear restrictions is extremely narrow. It results in the need for the “correct” extension of solutions of a system of diﬀerential equations to a class of quasi-solutions having the distinctive feature of gaps in a countable number of points. It was possible numerically using the Runge–Kutta method of the fourth order to build these quasi-solutions and determine their rate of growth. Let us note that in the technical plan the main complexity consisted in obtaining quasi-solutions satisfying the nonlocal linear restrictions. Furthermore, we investigated the dependence of quasi-solutions and, in particular, sizes of gaps (jumps) of solutions on a number of parameters of the model characterizing a rule of control, technologies for transportation of cargo and intensity of giving of cargo on a node station.
Event logs collected by modern information and technical systems usually contain enough data for automated process models discovery. A variety of algorithms was developed for process models discovery, conformance checking, log to model alignment, comparison of process models, etc., nevertheless a quick analysis of ad-hoc selected parts of a journal still have not get a full-fledged implementation. This paper describes an ROLAP-based method of multidimensional event logs storage for process mining. The result of the analysis of the journal is visualized as directed graph representing the union of all possible event sequences, ranked by their occurrence probability. Our implementation allows the analyst to discover process models for sublogs defined by ad-hoc selection of criteria and value of occurrence probability
The geographic information system (GIS) is based on the first and only Russian Imperial Census of 1897 and the First All-Union Census of the Soviet Union of 1926. The GIS features vector data (shapefiles) of allprovinces of the two states. For the 1897 census, there is information about linguistic, religious, and social estate groups. The part based on the 1926 census features nationality. Both shapefiles include information on gender, rural and urban population. The GIS allows for producing any necessary maps for individual studies of the period which require the administrative boundaries and demographic information.
It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in EXPNP, or even in EXP that are not computable by polynomial size circuits and hence are not reducible to a sparse set. In this paper we study this question in a more restricted setting: what is the computational complexity of sparse sets that are selfreducible? It follows from earlier work of Lozano and Torán (in: Mathematical systems theory, 1991) that EXPNP does not have sparse selfreducible hard sets. We define a natural version of selfreduction, tree-selfreducibility, and show that NEXP does not have sparse tree-selfreducible hard sets. We also construct an oracle relative to which all of EXP is reducible to a sparse tree-selfreducible set. These lower bounds are corollaries of more general results about the computational complexity of sparse sets that are selfreducible, and can be interpreted as super-polynomial circuit lower bounds for NEXP.