• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 7 публикаций
Сортировка:
по названию
по году
Статья
Syed M., Georgiev P. G., Pardalos P. M. Computers & Operations Research. 2014. Vol. 41. P. 386-398.

В данной статье описывается задача слепого разделения сигналов (BSS): дано  X∈Rm×N, задача BSS используется, чтобы найти A∈Rm×n и S∈Rn×N, где матрицы связаны как X=AS. Мы рассмотрели достаточные условия для структуры X, A и S с точки зрения редкости условий S, таких, что уравнение может быть решено однозначно (с точностью до перестановки и масштабируемости).  Предлагается хиерархический 0-1 MIP для решения данной задачи. Вероятно, мы показали, что каждый последующий уровень иерархической MIP будет легче решить, чем предшествующий  уровень MIP. Более того, мы представили тематические исследования, которые поясняют эффективность предложенного подхода решения для коррелированных редких источников.

Добавлено: 31 декабря 2012
Статья
Cheng T., Lazarev A. A., Gafarov E. Computers & Operations Research. 2012. Vol. 36. No. 2. P. 308-315.
Добавлено: 23 ноября 2012
Статья
Ilya Bychkov, Mikhail Batsyn. Computers & Operations Research. 2018. No. 91. P. 112-120.
Добавлено: 6 декабря 2017
Статья
Goldengorin B. I., Ghosh D., Sierksma G. Computers & Operations Research. 2003. Vol. 30. No. 7. P. 967-981.
Добавлено: 31 июля 2012
Статья
Goldengorin B. I., Ghosh D., Sierksma G. Computers & Operations Research. 2003. Vol. 30. No. 7. P. 967-981.
Добавлено: 22 сентября 2010
Статья
San Segundo P., Nikolaev A., Batsyn M. Computers & Operations Research. 2015. Vol. 64. P. 293-303.

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.

Добавлено: 24 августа 2015
Статья
Germs R., Goldengorin B. I., Turkensteen M. Computers & Operations Research. 2012. No. 2 (39). P. 291-298.

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.

Добавлено: 30 июля 2012