• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
August 25, 2026
Scientists Develop Algorithm for More Reliable Processors in Data Centres
Researchers from HSE MIEM and Samara University have developed the LRF-3D algorithm to automatically bypass idle nodes in three-dimensional networks-on-chip. Thanks to its hierarchical architecture, the algorithm outperforms existing solutions in both speed and path accuracy, improving processor reliability for use in data centres, supercomputers, and AI computing. The source code and test results are publicly available.
August 24, 2026
Researchers Develop Method for Direct Generation of Regulatory DNA
Researchers at HSE University have developed a model for generating promoters and enhancers—DNA sequences that regulate gene activity. The model works directly with DNA nucleotides, without first transforming them into a continuous numerical representation. This solution could be useful for applications in synthetic biology and gene therapy. The study results were presented at the ICLR 2026 Workshop ‘Generative AI in Genomics (Gen^2): Barriers and Frontiers.’
August 21, 2026
Social Integration: At the Crossroads of Knowledge and Values
The International Laboratory for Social Integration Research (ILSIR) at HSE University studies the challenges faced by vulnerable groups and explores ways to help them participate fully in everyday life. To develop effective solutions, the laboratory’s researchers combine cutting-edge methods with practical fieldwork. In this interview with the HSE News Service, Laboratory Head Elena Iarskaia-Smirnova discusses the laboratory’s work.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem

P. 244–255.
Irina Utkina, Mikhail Batsyn, Ekaterina Batsyna
In press

We consider a fractional 0-1 programming problem arising in manufacturing. The problem consists in clustering of machines together with parts processed on these machines into manufacturing cells so that intra-cell processing of parts is maximized and inter-cell movement is minimized. This problem is called Cell Formation Problem (CFP) and it is an NP-hard optimization problem with Boolean variables and constraints and with a fractional objective function. Because of its high computational complexity there are a lot of heuristics developed for it. In this paper we suggest a branch and bound algorithm which provides exact solutions for the CFP with a variable number of cells and grouping efficacy objective function. This algorithm finds optimal solutions for 21 of the 35 popular benchmark instances from literature and for the remaining 14 instances it finds good solutions close to the best known.

Language: English
Full text
DOI
Text on another site
Keywords: бикластеризацияcell formationзадача о формировании производственных ячеекbiclusteringupper boundверхняя границаалгоритм ветвей и границточное решениеbranch and bound exact solution

In book

Discrete Optimization and Operations Research/9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings
Discrete Optimization and Operations Research/9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings
Springer, 2016.
Similar publications
MODEL OF DEEP BED FILTRATION IN A POROUS MEDIUM WITH HETEROGENEOUS POROSITY
Liudmila I. Kuzmina, Osipov, Y. V., International Journal for Computational Civil and Structural Engineering 2026 Vol. 22 No. 2 P. 138–148
Modeling the transport and sedimentation of small particles of suspensions and colloids in porous rocks is an important problem in subsurface hydromechanics. Particles entrained in fluid are transported and retained in the rock pores. The filtration process is determined by the number and size of pores and is characterized by porosity—the ratio of the void ...
Added: August 25, 2026
Exact Solutions to One-Dimensional Problem of Oil Displacement by Chemical
L.I.Kuzmina, Osipov Y. V., Mathematical notes, ISSN 0001-4346 2025 Vol. 116 No. 6 P. 1251–1261
We consider the displacement of oil by water with active chemical reagents in porous media. A one-dimensional model of reagent transport and deposition is defined by a hyperbolic system of first-order equations. The purpose of the article is to find the conditions for the existence of a continuous solution with discontinuous boundary and initial conditions. ...
Added: August 25, 2026
Advective Flow of a Rotating Fluid Layer in a Vibrational Field
Shvarts K.G., Russian Journal of Nonlinear Dynamics 2019 Vol. 15 No. 3 P. 261–270
This paper presents a derivation of new exact solutions to the Navier – Stokes equations in Boussinesq approximation describing two advective flows in a rotating thin horizontal fluid layer with no-slip or free boundaries in a vibrational field. The layer rotates at a constant angular velocity; the axis of rotation is aligned with the vertical axis of coordinates. ...
Added: November 24, 2024
Устойчивость адвективного течения в горизонтальном слое несжимаемой жидкости при наличии условия проскальзывания Навье
Шварц К. Г., Шварц Ю. А., Известия РАН. Механика жидкости и газа 2020 № 1 С. 33–44
Представлено точное решение уравнений Навье-Стокса в приближении Буссинеска, описывающее плоскопараллельное адвективное течение в плоском слое несжимающейся жидкости с горизонтальными границами, на которых задано условие проскальзывания Навье и линейное распределение температуры. Исследуется поведение скорости и температуры с ростом значения параметра проскальзывания. В рамках линейной теории исследуется устойчивость адвективного течения на плоские и спиральные возмущения. В рамках ...
Added: November 24, 2024
Устойчивость адвективного течения в горизонтальном теплоизолированном снизу слое жидкости с твердыми границами
Шварц К. Г., Шварц Ю. А., Прикладная математика и механика 2022 Т. 86 № 6 С. 926–937
Исследуется устойчивость адвективного течения в плоском горизонтальном слое несжимаемой жидкости с твердыми границами. На верхней границе слоя задано линейное распределение температуры, нижняя граница теплоизолированная. Плоскопараллельное течение, возникшее под действием горизонтальной конвекции, описывается аналитически в виде точного решения уравнений Навье-Стокса в приближении Буссинеска. В рамках линейной теории исследуется устойчивость адвективного течения на нормальные возмущения при различных ...
Added: November 21, 2024
Устойчивость адвективного течения во вращающемся горизонтальном теплоизолированном снизу слое несжимаемой жидкости с твердыми границами при малом числе Прандтля
Шварц К. Г., Известия РАН. Механика жидкости и газа 2022 № 2 С. 38–50
The stability of advective flow in a flat rotating horizontal layer of incompressible fluid with solid boundaries is studied. A linear temperature distribution is set on the upper boundary of the layer, the lower boundary is thermally insulated. The advective flow due to horizontal convection is described analytically in the form of a new exact ...
Added: November 18, 2024
Plane-Parallel Advective Flow in a Horizontal Layer of Incompressible Permeable Fluid
Shvarts K. G., Russian Journal of Nonlinear Dynamics 2023 Vol. 19 No. 2 P. 219–226
In this paper a new exact solution of the Navier – Stokes equations in the Boussinesq approximation describing advective flow in a horizontal liquid layer with free boundaries, where the vertical velocity component is a constant value, is obtained. The temperature is linear along the boundaries of the layer. Solutions of this kind are used ...
Added: November 16, 2024
ОСАЖДЕНИЕ РАЗНОРОДНЫХ ЧАСТИЦ В ПОРИСТОМ МАТЕРИАЛЕ
Л.И. Кузьмина, Осипов Ю. В., Строительные материалы 2024 № 8 С. 63–68
Фильтрация суспензий и коллоидов в пористых материалах встречается при строительстве и эксплуатации гидросооружений, туннелей и подземных хранилищ. Модели фильтрации используются при расчете проникновения укрепителя в рыхлый грунт, при очистке питьевой воды и промышленных стоков. В процессе фильтрации взвешенные частицы проходят через крупные поры и застревают на входе пор малого диаметра. Задержанные частицы образуют неподвижный осадок. ...
Added: October 31, 2024
Model Of Cake Filtration In Porous Medium
Liudmila I. Kuzmina, Osipov Y., International Journal for Computational Civil and Structural Engineering 2024 Vol. 20 No. 3 P. 116–124
Strengthening of loose soil and creation of water-resistant underground walls are associated with filtration of small particles in a porous medium. Liquid solution pumped into a well under pressure spreads through hollow channels and strengthens the soil upon hardening. Many porous filters retain particles near the entrance. The particles deposited on the filter surface form ...
Added: October 31, 2024
Long-term filtration of particles in a porous medium
Liudmila Kuzmina, Osipov Y., , in: BIO Web of Conferences: Volume 107:19th International Conference Water and Wastewater: Transportation, Treatment, Management “Yakovlev Readings” (YRC-2024)Vol. 107.: EDP Sciences, 2024. Ch. 03003.
The formation of grout sediment in the pores of loose rock increases the water resistance of the soil and strengthens the foundation. A one-dimensional model of filtration in a porous medium considers the particles transport by the flow of a carrier fluid and the deposition of particles on the framework of a porous medium. The ...
Added: June 27, 2024
Traveling Wave Solution to Filtration Model in Porous Medium
Kuzmina L., Osipov Y., , in: Proceedings of the 8th International Technical Conference on Frontiers of HCET 2023. Advances in Transdisciplinary Engineering, Volume 43.: IOS Press, 2023. P. 450–455.
Suspension and colloid filtration in porous rocks is encountered in problems of underground hydromechanics associated with construction. The formation of grout sediment in the pores of loose rock increases the water resistance of the soil and strengthens the foundation. A one-dimensional model of filtration in a porous medium considers the particles transport by the flow ...
Added: June 27, 2024
Фильтрация суспензии в пористом материале
Л. И. Кузьмина, Осипов Ю. В., Строительные материалы 2023 № 9 С. 89–93
Фильтрация взвешенных твердых частиц в пористом материале моделирует процессы укрепления фундаментов, создания водонепроницаемых стен в горной породе, строительстве и реконструкции дорог, кольматацию (осаждение частиц) в призабойной зоне скважины компонентами бурового раствора при нефтедобыче, работу фильтрующих элементов очистных сооружений и многое другое. Целью настоящей работы явилось исследование фильтрации монодисперсной суспензии высокой концентрации в однородной пористой среде, ...
Added: October 31, 2023
Dicke Model Semiclassical Dynamics in Superradiant Dipolar Phase in the “Bound Luminosity” State
Mukhin S., Mukherjee A., Seidov S., Journal of Experimental and Theoretical Physics 2021 Vol. 132
Added: September 17, 2023
Correspondence between Dicke-model semiclasscial dynamics in the superradiant dipolar phase and the Euler heavy top
Mukhin S., Mukherjee A., Seidov S., Physical Review A: Atomic, Molecular, and Optical physics 2023 Vol. 107
Added: September 17, 2023
“Bound luminosity” state in the extended Dicke model
Seidov S., Mukhin S., Annals of Physics 2023 Vol. 456
Added: September 17, 2023
Object-Attribute Biclustering for Elimination of Missing Genotypes in Ischemic Stroke Genome-Wide Data
Ignatov D. I., Khvorykh G., Khrunin A. et al., , in: Recent Trends in Analysis of Images, Social Networks and Texts. 9th International Conference, AIST 2020, Skolkovo, Moscow, Russia, October 15–16, 2020 Revised Supplementary ProceedingsVol. 12602.: Springer, 2021. P. 185–204.
© 2021, Springer Nature Switzerland AG.Missing genotypes can affect the efficacy of machine learning approaches to identify the risk genetic variants of common diseases and traits. The problem occurs when genotypic data are collected from different experiments with different DNA microarrays, each being characterised by its pattern of uncalled (missing) genotypes. This can prevent the ...
Added: November 1, 2022
Динамика частиц в пористой среде
Kuzmina L., Осипов Ю. В., Шайдуллина А. М., Промышленное и гражданское строительство 2021 № 10 С. 72–77
When designing tunnels and underground structures, filtration of particles in porous rock has to be considered. Long-term, deep bed filtration of suspensions and colloids in a porous medium leads to the formation of deposit in the pores and a change in the structure of the porous rock framework. The filtration model includes the equation for the balance of ...
Added: October 26, 2022
Unsteady edge waves generated by time-harmonic pressure: exact solutions
Abrashkin A. A., Journal of Physics A: Mathematical and Theoretical 2022 Vol. 55 No. 41 Article 415701
An analytical description of unsteady edge waves over a uniform slope is proposed. It is assumed that the waves are excited by time-harmonic external pressure with inhomogeneous spatial distribution. The problem is considered in Lagrangian variables. An exact solution of the hydrodynamic equations is obtained. It generalizes the stationary Gerstner–Constantin solution. The proposed model describes the dynamics of coastal splashes ...
Added: October 13, 2022
EXACT SOLUTION FOR DEEP BED FILTRATION WITH FINITE BLOCKING TIME
Nazaikinskii V., BEDRIKOVETSKY P., LIUDMILA I. KUZMINA et al., SIAM Journal on Applied Mathematics 2020 Vol. 80 No. 5 P. 2120–2143
An initial-boundary value problem for a quasilinear system describing deep bed ltration of a monodisperse suspension in a medium with pores of various sizes is investigated analytically. The ltration function is assumed to have power-law type while tending to zero with the power index lower than one. We found that this assumption has two consequences: (i) the ...
Added: January 7, 2021
Some parabolic equations for measures and Gaussian semigroups
Galkin O., Galkina S., / Series math "arxiv.org". 2020. No. arXiv:2012.07174.
This short communication (preprint) is devoted to mathematical study of evolution equations that are important for mathematical physics and quantum theory; we present new explicit formulas for solutions of these equations and discuss their properties. The results are given without proofs but the proofs will appear in the longer text which is now under preparation. In ...
Added: December 13, 2020
On the Dual and Inverse Problems of Scheduling Jobs to Minimize the Maximum Penalty
Alexander A. Lazarev, Nikolay Pravdivets, Werner F., Mathematics 2020 Vol. 8 No. 7 Article 1131
In this paper, we consider the single-machine scheduling problem with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both these problems can be solved in polynomial time. Since the dual problem ...
Added: September 2, 2020
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit