A polynomial time algorithm for the minimum flow problem in time-varying networks
Flow variations over time generalize standard network flows by introducing an element of time. In contrast to the classical case of static flows, a flow over time in such a network specifies a flow rate entering an arc for each point in time. In this setting, the capacity of an arc limits the rate of flow into the arc at each point in time. Traditionally, flows over time are computed in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static network flows, its drawback is the enormous size of the time-expanded network. In this paper, we extend the results about the minimum flow problem to network flows (with n nodes and m arcs) in which the time-varying lower bounds can involve both the source and the sink nodes (as in Fathabadi et al.) and also one additional node other than the source and the sink nodes. It is shown that this problem for the set (Formula presented.) of time points can be solved by at most n minimum flow computations, by suitably extending the dynamic minimum flow algorithm and reoptimization techniques. The running time of the presented algorithm is (Formula presented.).
Рассматривается проблема планирования подготовки экипажей Международной космической станции (МКС). Разработаны математические модели, описывающие подготовку космонавтов для работы на МКС. Также предлагаются эвристические алгоритмы для решения этой задачи, и приводятся результаты экспериментов на различных исходных данных.
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
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.
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.