Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP
It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the sample. Borders of the interval, which contains 90% of the sample of the logarithm of the complexity, are also given.
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 cousmonaut's time in ISS with given set of tasks, time planning horizon and load constraints. Shown that the problem is NP-hard in a strong sense. The heuristic algorithm was proposed. Proved that proposed algorithm is exact for problem with requirement of performing all tasks. Program C++ was written and algorithm's work was qualitatively analyzed.
The possibility of using approximate approaches for solving supply chain optimization problem with continuously accrued fines is discussed. The problem was investigated by numerical simulation for the case of exponentially growing fines, when a logistic operator must deliver the cargo to several points. The vehicle was allowed to move from any point to any other point. To solve the problem we used a so-called “Monte-Carlo” method. Numerical simulations showed that the variation of the parameters of the optimization model leads to a change in the optimal order of visiting points. It is shown that it is possible to find a solution that ensures the order close to the optimal. The proposed method, in contrast to the other known approaches, can be easily generalized for the case when functions determining fines in each point are different for different delivery points.
Author describes quantitative methods of optimization in management of different kinds of resources, which can be used within investment projects buildup on the stage of feasibility studies. Particulary, the issue of optimization of re-adjustment time duration is investigated (on the example of cases, when different goods are produced by one tool, but in each discrete time moment only one item can be produced by this tool). The determined model of optimization of re-adjustment time duration is proposed. Also the article contains discription of re-adjustment process optimization under uncertainty and risk.
The given analytical report was prepared on the commision and by request of the European Enviromemnt Agency (EEA) and is a part of the common EEA project on the implementation of the assessment of assessments of the state of the environment in the pan-European region for presentation at the VII Ministerial "Environment for Europe" conference, Astana, Kazakhstan, 2011. The report was published within the series of reports by the EEA (Copenhagen, Denmark). It contains the assessment of environmental assessments in the Russian Federation and the country environmental profile of Russia. Special attention in the report is paid to such topics as water resources abd related ecosystems, as well as to the issues of green economy and resource efficiency in Russia.