The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
The tolerance of an element of a combinatorial optimization problem with respect to its optimal solution is the maximum change of the cost of the element while preserving the optimality of the given optimal solution and keeping all other input data unchanged. Tolerances play an important role in the design of exact and approximation algorithms, but the computation of tolerances requires additional computational time. In this paper, we concentrate on combinatorial optimization problems for which the computation of all tolerances and an optimal solution have almost the same computational complexity as of finding an optimal solution only. We summarize efficient computational methods for computing tolerances for these problems and determine their time complexity experimentally.
In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances.
This book constitutes the proceedings of the 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016, held in Vladivostok, Russia, in September 2016.
The 39 full papers presented in this volume were carefully reviewed and selected from 181 submissions. They were organized in topical sections named: discrete optimization; scheduling problems; facility location; mathematical programming; mathematical economics and games; applications of operational research; and short communications.
This paper represents our solution for the problem of movement organization based on timetable optimization on the problematic part of railway system, i.e. single-track line. The approximate solution of this problem was founded on the heuristic method. The method gives the exact results in the case of limited amount of parameters and also can be used in the case with huge number of parameters due to reasonable computational time.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.
The author argues on expediency and mutual conditionality of evolutionary changes in the nature and in society. In the article three major factors of the evolution are allocated, namely: the accident, the factor of coincidence of circumstances and the factor of acceleration of social evolution.
The phenomenon of communication as a manifestation of complexity of interacting creatures. Communication is considered not as a privilege of a human being; it is shown that it is rooted in the world of living nature, it has an evolutionary origins. Communicative complexity is exposed by such concepts as flexibility, constructing, intersubjectivity, participatory sense-making, empathy, synergy, mutual incorporation and co-emergence of creatures which enter the process of communication. Understanding of communication from the position of the conception of enactivism allows disclosing some substantial aspects of the constructivist character of communicative interaction.
Global Equilibrium Search (GES) is a meta-heuristic framework that shares similar ideas with the simulated annealing method. GES accumulates a compact set of information about the search space to generate promising initial solutions for the techniques that require a starting solution, such as the simple local search method. GES has been successful for many classic discrete optimization problems: the unconstrained quadratic programming problem, the maximum satisfiability problem, the max-cut problem, the multidimensional knapsack problem and the job-shop scheduling problem. GES provides state-of-the-art performance on all of these domains when compared to the current best known algorithms from the literature. GES algorithm can be naturally extended for parallel computing as it performs search simultaneously in distinct areas of the solution space. In this talk, we provide an overview of Global Equilibrium Search and discuss some successful applications.
The monograph is devoted to the consideration of complex systems from the position of the end the 21st century. The considerable breakthrough in the understanding of complex systems is comprehensively analyzed. Such a breakthrough is connected with the use of the newest methods of nonlinear dynamics, of organization of the modern computational experiments. The book is meant for specialists in different fields of natural sciences and the humanities as well as for all readers who are interested in the recent advancements in science.
A form for an unbiased estimate of the coefficient of determination of a linear regression model is obtained. It is calculated by using a sample from a multivariate normal distribution. This estimate is proposed as an alternative criterion for a choice of regression factors.