### ?

## A Branch and Bound Algorithm for the Cell Formation Problem

P. 115-124.

Irina Utkina, Mikhail Batsyn

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 of the 35 popular benchmark instances from the literature.

### In book

Vol. 156. , Switzerland : Springer, 2016

Utkina I. E., Batsyn M. V., Программные продукты, системы и алгоритмы 2017 № 4 С. 1-10

The Cell Formation Problem (CFP) is an NP-hard optimization problem considered for cellular man- ufacturing systems. Because of its high computational complexity there have been developed a lot of heuristics and almost no exact algorithms for solving this problem. In this paper we suggest a branch- and-bound algorithm which provides exact solutions for the CFP ...

Added: October 18, 2017

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

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

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

Mikhail Batsyn, Ilya Bychkov, Boris Goldengorin et al., Springer Proceedings in Mathematics & Statistics 2012 Vol. 32 P. 11-50

In this paper we introduce a new pattern-based approach within the Linear Assignment Model with the purpose to design heuristics for a combinatorial optimization problem (COP). We assume that the COP has an additive (separable) objective function and the structure of a feasible (optimal) solution to the COP is predefined by a collection of cells ...

Added: October 9, 2012

Irina E. Utkina, Mikhail V. Batsyn, Ekaterina K. Batsyna, International Journal of Production Research 2018 Vol. 56 No. 9 P. 3262-3273

The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its ...

Added: March 11, 2018

Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos, Journal of Global Optimization 2014 Vol. 59 No. 1 P. 1-21

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed ...

Added: May 24, 2013

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

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

Pardalos P. M., Pappalardo E., Stracquadanio G., Dordrecht, L., Heidelberg, NY : Springer, 2013

Optimization Approaches for Solving String Selection Problems provides an overview of optimization methods for a wide class of genomics-related problems in relation to the string selection problems. This class of problems addresses the recognition of similar characteristics or differences within biological sequences. Specifically, this book considers a large class of problems, ranging from the closest ...

Added: November 8, 2013

Mikhail V. Batsyn, Ekaterina K. Batsyna, Ilya S. Bychkov, International Journal of Production Research 2020 Vol. 58 No. 20 P. 6159-6169

In the current paper we provide a proof of NP-completeness for the Cell Formation Problem (CFP) with the fractional grouping efficacy objective function. First the CFP with a linear objective function is considered. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is ...

Added: November 10, 2019

Chistyakov V., Goldengorin B. I., Pardalos P. M., Доклады Академии наук 2012 Vol. 86 No. 2 P. 707-710

It is known that by means of minimal values of tolerances one can obtain necessary and sufficient conditions for the uniqueness of the optimal solution of a combinatorial optimization problem (COP) with an additive objective function and the set of nonembedded feasible solutions. Moreover, the notion of a tolerance is defined locally, i.e., with respect ...

Added: February 4, 2013

Kuzmina L., Osipov, Y. V., Astakhov, M. D., Annali di Matematica Pura ed Applicata 2022 Vol. 201 No. 6 P. 2943-2964

During deep bed filtration of suspensions and colloids in a porous medium, some particles are retained in the pores and form a fixed deposit. A one-dimensional mathematical model of filtration with particles of two types is considered. Exact solution is derived. The existence and the uniqueness of the solution are proved by the method of ...

Added: October 26, 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

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

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

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

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

Burkov A. A., Shneer S., Turlikov A. M., , in : WAVE ELECTRONICS AND ITS APPLICATION IN INFORMATION AND TELECOMMUNICATION SYSTEMS. 2021. (WECONF 2021) St. Petersburg, Russia, 31 May - 4 June 2021. : IEEE, 2021. Ch. 9470700. P. 1-8.

The development of the Internet of Things technology in cellular networks is considered within the framework of massive machine-type communications with the use of random multiple access algorithms such as ALOHA and its modifications. Despite the fact that this class of algorithms has been studied for a long time, there are no numerical methods for ...

Added: October 28, 2022

Abrashkin A. A., Yakubovich E. I., Radiophysics and Quantum Electronics 2016 Vol. 58 No. 11 P. 852-857

We show that the discrete frequency spectrum of a plane hydrodynamic flow of ideal incompressible liquid with localized trajectories of the liquid particles can contain only one, two, or an infinite number of harmonics. ...

Added: November 17, 2016

Liudmila I. Kuzmina, Osipov Y., Astakhov M., International Journal for Computational Civil and Structural Engineering 2022 Vol. 18 No. 3 P. 86-94

During the construction of ground and underground structures, filtration of a liquid grout in loose soil makes it possible to strengthen the foundation and create underground waterproof partitions. A one-dimensional problem of filtering a bidisperse suspension in a homogeneous porous medium with size-exclusion particle capture mechanism is considered. The article is devoted to the calculation ...

Added: October 26, 2022

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

Ilya Bychkov, Mikhail Batsyn, Computers & Operations Research 2018 No. 91 P. 112-120

The Cell Formation Problem has been studied as an optimization problem in manufacturing for more than 90 years. It consists of grouping machines and parts into manufacturing cells in order to maximize loading of cells and minimize movement of parts from one cell to another. Many heuristic algorithms have been proposed which are doing well ...

Added: December 6, 2017