?
Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem
Burashnikov E.
Publication based on the results of:
Pérez A. C., Sánchez-Ansola E., Rosete A. et al., Heliyon 2022 Vol. 8 No. 4 Article e09291
Added: September 18, 2026
Belomestny D., Gasnikov A., Gladin E. et al., Russian Mathematical Surveys 2026 Vol. 81 No. 4(490) P. 3–90
Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates ...
Added: August 3, 2026
Springer, 2025.
The second edition of this 5-volume handbook is intended to be a basic yet comprehensive reference work in combinatorial optimization that will benefit newcomers and researchers for years to come. This multi-volume work deals with several algorithmic approaches for discrete problems as well as with many combinatorial problems. The editors have brought together almost every aspect ...
Added: January 18, 2026
Ignatov A., , in: 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers. Communications in Computer and Information Science (CCIS, volume 1913)Vol. 1913.: Springer, 2023. P. 173–187.
Modeling protein folding, which is the process by which a protein obtains its spacial shape, still remains a challenging problem. Protein geometry might be simplified by using the coarse-grained models. The highest level of simplification is achieved in HP-models where only polarity of amino acid residues is considered, and the unified monomers are located in nodes ...
Added: January 18, 2024
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
Smirnov S., Voloshinov V., O.V. Sukhoroslov, , in: Proceedings of the 9th International Conference "Distributed Computing and Grid Technologies in Science and Education" (GRID'2021), Dubna, Russia, July 5-9, 2021.: CEUR Workshop Proceedings, 2021. P. 413–417.
ParaSCIP is rather advanced open-source solver for discrete and global optimization problems. This solver is distinguished by that it can run on distributed memory systems and use up to 80,000 cores, solving open problems from the MIPLIB test libraries. Earlier, using this solver, we confirmed the conjecture on optimal packing of nine congruent circles on ...
Added: October 30, 2022
Maron A., Maron M., Вестник Московского авиационного института 2022 Т. 29 № 2 С. 158–165
The relevance of this work is due to the fact, that reducing the time of searching and the time for eliminating defects in civil aviation passenger aircraft can significantly reduce departure delays and the associated losses of airlines. The analysis of statistical data shows that the searching and eliminating defects are the dominant causes of ...
Added: September 30, 2022
Afanasiev V., М.: Красанд/URSS, 2020.
This book has been prepared on the basis of lectures on control theory given by the author for a number of years to students of the Department of Applied Mathematics of the National Research University Higher School of Economics and the Faculty of Physics Moscow State University named after M. V. Lomonosov. The content of the ...
Added: August 27, 2022
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
Raayatpanah M. A., Khodayifar S., Weise T. et al., Journal of Combinatorial Optimization 2022 Vol. 44 No. 1 P. 242–268
In this paper, an extension of the minimum cost flow problem is considered in which multiple incommensurate weights are associated with each arc. In the minimum cost flow problem, flow is sent over the arcs of a graph from source nodes to sink nodes. The goal is to select a subgraph with minimum associated costs ...
Added: November 16, 2021
Switzerland: Springer, 2021.
This book constitutes the refereed proceedings of the 12th International Conference on Optimization and Applications, OPTIMA 2021, held in Petrovac, Montenegro, in September-October 2021.
The 22 full and 3 short papers presented were carefully reviewed and selected from 63 submissions. The papers are organized into the following topical sub-headings: mathematical programming, global optimization, discrete and combinatorial ...
Added: November 4, 2021
Andreev N. A., Smirnov S. N., Computational Mathematics and Modeling 2021 Vol. 32 P. 22–44
We consider a guaranteed deterministic approach to discrete-time super-replication for guaranteed coverage of contingent claims on options for all possible asset-price scenarios. Price increases during a period are assumed to be contained in a priori specified compacta dependent on price history. A game problem is stated and reduced to the solution of the corresponding Bellman–Isaacs ...
Added: September 30, 2021
Bychkov A., Pogudin G., , in: International Workshop on Combinatorial Algorithms, 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021Vol. 12757.: Springer, 2021. P. 122–136.
Added: September 8, 2021
Cham: Springer, 2021.
This book constitutes the proceedings of the 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021, held in Irkutsk, Russia, in July 2021.
The 29 full papers and 1 short paper presented in this volume were carefully reviewed and selected from 102 submissions. Additionally, 2 full invited papers are presented in the volume. ...
Added: July 8, 2021
Pospelov I. G., Zhukova A., , in: 2020 European Control Conference (ECC).: Institute of Electrical and Electronics Engineers Inc., 2020. P. 1129–1134.
This paper presents the approach to solving optimal control problems that appear in economic models using the Lagrange's multipliers method. This method is not as widely used as it might be, taking into accounts its benefits and convenience. The power of this method for intertemporal general equilibrium allows building complex structural models of the whole ...
Added: December 8, 2020
Andreev N. A., В кн.: "Тихоновские чтения": научная конференция: тезисы докладов: посвящается памяти академика Андрея Николаевича Тихонова: 29 октября-1 ноября 2019 г.: М.: ООО «Макс Пресс», 2019. С. 14–14.
Доклад посвящен приложению гарантированного подхода, предложенного Смирновым С.Н. [1],[2], к задаче управления портфелем финансовых инструментов на низколиквидном рынке с учетом модельной ошибки. Рассматривается игровая постановка в дискретном времени на конечном горизонте, в рамках которой инвестор максимизирует ожидаемое вознаграждение от портфеля (робастный эквивалент Сэвиджа) в конце стратегии. Оптимальная стратегия находится в неявном виде как решение соответствующего ...
Added: October 30, 2019
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
Smirnov Sergey, Voloshinov V., Procedia Computer Science 2018 Vol. 136 P. 128–135
Previous publications presented an implementation of coarse-grained parallel Branch-and-Bound (B&B) method. It supports two strategies: decomposition of feasible domain into a set of sub-problems; “multisearch” (or concurrent) solving the same problem with different settings of the BNB-method. In both cases several B&B-solver’s processes exchange best values of goal function on feasible solutions they found. Earlier, ...
Added: December 20, 2018
Maslov V. P., Mathematical notes 2018 Vol. 103 No. 4 P. 678–680
In the paper we consider the hidden parameter (measurement time t_meas) which combines quantum and classical theory. We show that the Bose–Einstein and Fermi–Dirac quantum distributions turn out to be the decisive factor in the construction of isotherms in classical thermodynamics and in the description of the phase transition “gas to liquid” and “liquid ...
Added: December 8, 2018
Andreev N. A., Smirnov S. N., В кн.: "Тихоновские чтения": научная конференция: тезисы докладов: посвящается памяти академика Андрея Николаевича Тихонова: 29 октября-2 ноября 2018 г.: М.: МАКС Пресс, 2018. С. 11–11.
Управление портфелем ценных бумаг, для целей инвестирования или хеджирования, относится к классическим задачам финансовой математики, которые допускают различные постановки, обычно использующие стохастическое динамическое программирование, где управляемым объектом является структура портфеля, а рынок описывается некоторым стохастическим процессом.
Доклад посвящен альтернативе общепринятого стохастического подхода, - за основу берется неопределенность поведения рынка в будущем, а динамика рынка описывается одним ...
Added: October 30, 2018
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
Irina Utkina, Mikhail Batsyn, , in: Models, Algorithms and Technologies for Network Analysis, Springer Proceedings in Mathematics & StatisticsVol. 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
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