### ?

## Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem

San Segundo P., Lopez A., Mikhail Batsyn et al., Applied Intelligence 2016 Vol. 45 No. 3 P. 868–880

This paper describes a new initial vertex ordering procedure NEW_SORT designed to enhance approximate-colour exact algorithms for the maximum clique problem (MCP). NEW_SORT considers two different vertex orderings: degree and colour-based. The degree-based vertex ordering describes an improvement over a well-known vertex ordering used by exact solvers. Moreover, colour-based vertex orderings for the MCP have ...

Added: May 27, 2016

Pablo San Segundo ., Jorge Artieda .., Mikhail Batsyn et al., Optimization Methods and Software 2017 Vol. 32 No. 2 P. 312–335

This paper describes BBMCW, a new efficient exact maximum clique algorithm tailored for large sparse graphs which can be bit-encoded directly into memory without a heavy performance penalty. These graphs occur in real-life problems when some form of locality may be exploited to reduce their scale. One such example is correspondence graphs derived from data association ...

Added: March 9, 2017

Zinder Y., Lazarev A. A., Musatova E. G. et al., Automation and Remote Control 2018 Vol. Vol. 79 No. 3 P. 506–523

The paper is concerned with scheduling the two-way traffic between two stations connected by a single-track railway with a siding. It is shown that if, for each station, the order in which trains leave this station is known or can be found, then for various objective functions an optimal schedule can be constructed in polynomial ...

Added: May 30, 2018

Bychkov A., Pogudin G., , in : International Workshop on Combinatorial Algorithms, 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021. Vol. 12757.: Springer, 2021. P. 122–136.

Added: September 8, 2021

Springer, 2018

This book constitutes the refereed post-conference proceedings of the 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, held in Singapore, Singapore, in July 2018. The 31 regular papers presented in this volume were carefully reviewed and selected from 69 submissions. They cover diverse areas of combinatorical algorithms, complexity theory, graph theory and combinatorics, combinatorial optimization, ...

Added: October 23, 2018

D. V. Gribanov, Shumilov I. A., D. S. Malyshev, Optimization Letters 2024 Vol. 18 P. 73–103

In this work we consider the problem of computing the (min,+)-convolution of two sequences a and b of lengths n and m, respectively, where n≥m. We assume that a is arbitrary, but b_i=f(i), where f(x):[0,m)→R is a function with one of the following properties: f is linear, f is monotone, f is convex, f is concave, f is piece-wise linear, f is a polynomial function of a fixed degree. To the best of our knowledge, the concave, piece-wise linear and polynomial ...

Added: May 28, 2023

Chistyakov V., Goldengorin B. I., Pardalos P. M., Journal of Global Optimization 2012 Vol. 53 No. 3 P. 475–495

The currently adopted notion of a tolerance in combinatorial optimization is defined referring to an arbitrarily chosen optimal solution, i.e., locally. In this paper we introduce global tolerances with respect to the set of all optimal solutions, and show that the assumption of nonembededdness of the set of feasible solutions in the provided relations between ...

Added: July 27, 2012

Dagaev D., Suzdaltsev A., Journal of Combinatorial Optimization 2018 Vol. 35 No. 1 P. 170–188

Before a knock-out tournament starts, the participants are assigned to positions in the tournament bracket through a process known as seeding. There are many ways to seed a tournament. In this paper, we solve a discrete optimization problem of finding a seeding that maximizes spectator interest in a tournament when spectators are interested in matches ...

Added: August 1, 2017

Молоствов В.С., Жаркынбаев С. Ж., Жуковский В. И., В кн. : Сборник научных трудов III Международной школы-симпозиума «Анализ, моделирование, управление, развитие экономических систем: АМУР-2009, Севастополь, 14 - 20 сентября 2009». : ТНУ им. В.И. Вернадского, 2009. С. 191–192.

На основе принципа минимаксного сожаления по Сэвиджу формализуется понятие функции риска в многошаговой позиционной задаче. Предлагаются достаточные условия существования максимума целевого функционала при учете неопределенности. ...

Added: July 11, 2014

NY: Springer, 2013

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 ...

Added: September 27, 2013

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 ...

Added: August 24, 2015

Springer, 2018

This book presents open optimization problems in graph theory and networks. Each chapter reflects developments in theory and applications based on Gregory Gutin’s fundamental contributions to advanced methods and techniques in combinatorial optimization.
Researchers, students, and engineers in computer science, big data, applied mathematics, operations research, algorithm design, artificial intelligence, software engineering, data analysis, industrial and ...

Added: October 10, 2018

Springer, 2014

This book constitutes the thoroughly refereed post-conference proceedings of the 8th International Conference on Learning and Optimization, LION 8, which was held in Gainesville, FL, USA, in February 2014. The 33 contributions presented were carefully reviewed and selected for inclusion in this book. A large variety of topics are covered, such as algorithm configuration; multiobjective ...

Added: August 13, 2014

Bronnikov S., Lazarev A. A., Petrov A. S. et al., , in : VI International Conference on Optimization Methods and Applications "Optimization and applications" (OPTIMA-2015), Petrovac, Montenegro, September 2015. : M.: -, 2015. P. 196–197.

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 ...

Added: October 20, 2015

Springer, 2014

This book constitutes the thoroughly refereed post-conference proceedings of the 8th International Conference on Learning and Optimization, LION 8, which was held in Gainesville, FL, USA, in February 2014. The 33 contributions presented were carefully reviewed and selected for inclusion in this book. A large variety of topics are covered, such as algorithm configuration; multiobjective ...

Added: September 15, 2014

Pardalos P. M., Ravetti M. G., Riveros C. et al., Annals of Operations Research 2012 Vol. 199 No. 1 P. 269–284

This paper addresses the Permutation Flowshop Problem with minimization of makespan, which is denoted by Fm{pipe}prmu{pipe}C max. In the permutational scenario, the sequence of jobs has to remain the same in all machines. The Flowshop Problem (FSP) is known to be NP-hard when more than three machines are considered. Thus, for medium and large scale ...

Added: February 5, 2013

Pham Cong T., Копылов А. В., Computer Optics 2018 P. 1–8

We consider here image denoising procedures, based on computationally effective tree-serial parametric dynamic programming procedures, different representations of an image lattice by the set of acyclic graphs and non-convex regularization of a new type which allows to flexibly set a priori preferences. Experimental results in image denoising, as well as comparison with related methods, are ...

Added: July 21, 2018

Andreev N. A., Mathematics 2019 Vol. 7 No. 12 P. 1147

We present a robust dynamic programming approach to the general portfolio selection problem in the presence of transaction costs and trading limits. We formulate the problem as a dynamic infinite game against nature and obtain the corresponding Bellman-Isaacs equation. Under~several additional assumptions, we get an alternative form of the equation, which is more feasible for ...

Added: October 30, 2019

Andreev N. A., Smirnov S. N., В кн. : "Тихоновские чтения": научная конференция: тезисы докладов: посвящается памяти академика Андрея Николаевича Тихонова: 29 октября-2 ноября 2018 г. : М.: МАКС Пресс, 2018. С. 11–11.

Управление портфелем ценных бумаг, для целей инвестирования или хеджирования, относится к классическим задачам финансовой математики, которые допускают различные постановки, обычно использующие стохастическое динамическое программирование, где управляемым объектом является структура портфеля, а рынок описывается некоторым стохастическим процессом.
Доклад посвящен альтернативе общепринятого стохастического подхода, - за основу берется неопределенность поведения рынка в будущем, а динамика рынка описывается одним ...

Added: October 30, 2018

Festa P., Pardalos P. M., Annals of Operations Research 2012 P. 663–682

Computational molecular biology has emerged as one of the most exciting interdisciplinary fields. It has currently benefited from concepts and theoretical results obtained by different scientific research communities, including genetics, biochemistry, and computer science. In the past few years it has been shown that a large number of molecular biology problems can be formulated as ...

Added: January 9, 2013

Lazarev A. A., Carballo L., Vakhania N. et al., , in : IFAC Proceedings Volumes 14th IFAC Symposium on Information Control Problems in Manufacturing, Bucharest, 23-25 May 2012. : Бухарест: IFAC Technical Committee, 2012. P. 381–386.

We present an approach based on a two-stage ltration of the set of feasible solutions for the multiprocessor job-shop scheduling problem. On the rst stage we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can eciently be obtained and implemented. ...

Added: February 12, 2013

Springer, 2022

The 21 full papers presented together with 6 invited abstracts lectures and 2 tutorial abstracts in this volume were carefully reviewed and selected from 88 submissions. The conference focuses on the following topics: Mathematical programming, bi-level and global optimization, integer programming and combinatorial optimization, approximation algorithms with theoretical guarantees and approximation schemes, heuristics and meta-heuristics, ...

Added: July 7, 2022

Irina Utkina, Mikhail Batsyn, , in : Models, Algorithms and Technologies for Network Analysis, Springer Proceedings in Mathematics & Statistics. Vol. 156.: Switzerland: Springer, 2016. P. 115–124.

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 ...

Added: October 23, 2018

Khodayifar S., Raayatpanah M. A., Pardalos P. M., Annals of Operations Research 2017 P. 1–11

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 ...

Added: April 10, 2017