Mikhail Batsyn
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Mikhail Batsyn has a total of 31 co-authors. Here are the top co-authors by number of shared publications:
Panos M. Pardalos
National Research University Higher School of Economics
11 shared publications- Boris Goldengorin
University of Florida
5 shared publications Pavel Sukhov
4 shared publications- Alexander Ponomarenko
Center for Hydroacoustics and Geophysical Research Division, Institute of Applied Physics of the Russian Academy of Sciences, 603950 Nizhny Novgorod, Russia
3 shared publications - Alexey Nikolaev
National Research University Higher School of Economics
3 shared publications Ekaterina K. Batsyna
National Research University Higher School of Economics
3 shared publications
Latest Publications
- 14 September 2020
- Published by Springer Nature
- p. 379-386
Fast Heuristic for Vehicle Routing Problem on Trees
- 14 September 2020
- Published by Springer Nature
- p. 379-386
Fast Heuristic for Vehicle Routing Problem on Trees
- 26 September 2019
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 58 (20) , 6159-6169
NP-completeness of cell formation problem with grouping efficacy objective
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 known to be NP-complete due to the reduction from the 3-Exact 3-Cover Problem – 3E3CP (Amit, 2004). Then we suggest a polynomial reduction of the CFP with the linear objective to the CFP with the grouping efficacy objective. It proves the NP-completeness of this fractional CFP formulation. Along with the NP-status our paper presents important connections of the CFP with the BGEP and 3E3CP. Such connections could be used for ”transferring” of known theoretical properties, efficient algorithms, polynomial cases, and other features of well-studied graph editing and exact covering problems to the CFP.
- 26 September 2019
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 58 (20) , 6159-6169
NP-completeness of cell formation problem with grouping efficacy objective
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 known to be NP-complete due to the reduction from the 3-Exact 3-Cover Problem – 3E3CP (Amit, 2004). Then we suggest a polynomial reduction of the CFP with the linear objective to the CFP with the grouping efficacy objective. It proves the NP-completeness of this fractional CFP formulation. Along with the NP-status our paper presents important connections of the CFP with the BGEP and 3E3CP. Such connections could be used for ”transferring” of known theoretical properties, efficient algorithms, polynomial cases, and other features of well-studied graph editing and exact covering problems to the CFP.
- 4 March 2019
- Published by Springer Nature in Operational Research
- Vol. 21 (1) , 399-423
Vehicle assignment in site-dependent vehicle routing problems with split deliveries
- 4 March 2019
- Published by Springer Nature in Operational Research
- Vol. 21 (1) , 399-423
Vehicle assignment in site-dependent vehicle routing problems with split deliveries
- Open Access
On NP-completeness of the cell formation problem
In the current paper we provide a proof of NP-completeness for the CFP problem with the fractional grouping efficacy objective. For this purpose we first consider the CFP with the linear objective minimizing the total number of exceptions and voids. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is known to be NP-complete (Amit, 2004). Then we suggest a reduction of the CFP problem with the linear objective function to the CFP with the grouping efficacy objective.
Open AccessOn NP-completeness of the cell formation problem
In the current paper we provide a proof of NP-completeness for the CFP problem with the fractional grouping efficacy objective. For this purpose we first consider the CFP with the linear objective minimizing the total number of exceptions and voids. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is known to be NP-complete (Amit, 2004). Then we suggest a reduction of the CFP problem with the linear objective function to the CFP with the grouping efficacy objective.
- 25 August 2018
- Published by Springer Nature
- p. 3-18
Tabu Search for Fleet Size and Mix Vehicle Routing Problem with Hard and Soft Time Windows
- 25 August 2018
- Published by Springer Nature
- p. 3-18
Tabu Search for Fleet Size and Mix Vehicle Routing Problem with Hard and Soft Time Windows
- 4 July 2018
- Published by Springer Nature
- p. 311-322
Branch-and-Bound Algorithm for Symmetric Travelling Salesman Problem
- 4 July 2018
- Published by Springer Nature
- p. 311-322
Branch-and-Bound Algorithm for Symmetric Travelling Salesman Problem
- 7 March 2018
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 56 (9) , 3262-3273
A branch-and-bound algorithm for the cell formation problem
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 machines with operations on its parts. We consider one of the computationally hardest formulations of this problem – the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%.
- 7 March 2018
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 56 (9) , 3262-3273
A branch-and-bound algorithm for the cell formation problem
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 machines with operations on its parts. We consider one of the computationally hardest formulations of this problem – the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%.
- Open Access
A Model of Optimal Network Structure for Decentralized Nearest Neighbor Search
One of the approaches for the nearest neighbor search problem is to build a network which nodes correspond to the given set of indexed objects. In this case the search of the closest object can be thought as a search of a node in a network. A procedure in a network is called decentralized if it uses only local information about visited nodes and its neighbors. Networks, which structure allows efficient performing the nearest neighbour search by a decentralised search procedure started from any node, are of particular interest especially for pure distributed systems. Several algorithms that construct such networks have been proposed in literature. However, the following questions arise: "Are there network models in which decentralised search can be performed faster?"; "What are the optimal networks for the decentralised search?"; "What are their properties?". In this paper we partially give answers to these questions. We propose a mathematical programming model for the problem of determining an optimal network structure for decentralized nearest neighbor search. We have found an exact solution for a regular lattice of size 4x4 and heuristic solutions for sizes from 5x5 to 7x7. As a distance function we use L1 , L2 and L_inf metrics. We hope that our results and the proposed model will initiate study of optimal network structures for decentralised nearest neighbour search.
Open AccessA Model of Optimal Network Structure for Decentralized Nearest Neighbor Search
One of the approaches for the nearest neighbor search problem is to build a network which nodes correspond to the given set of indexed objects. In this case the search of the closest object can be thought as a search of a node in a network. A procedure in a network is called decentralized if it uses only local information about visited nodes and its neighbors. Networks, which structure allows efficient performing the nearest neighbour search by a decentralised search procedure started from any node, are of particular interest especially for pure distributed systems. Several algorithms that construct such networks have been proposed in literature. However, the following questions arise: "Are there network models in which decentralised search can be performed faster?"; "What are the optimal networks for the decentralised search?"; "What are their properties?". In this paper we partially give answers to these questions. We propose a mathematical programming model for the problem of determining an optimal network structure for decentralized nearest neighbor search. We have found an exact solution for a regular lattice of size 4x4 and heuristic solutions for sizes from 5x5 to 7x7. As a distance function we use L1 , L2 and L_inf metrics. We hope that our results and the proposed model will initiate study of optimal network structures for decentralised nearest neighbour search.
- Open Access
An efficient exact model for the cell formation problem with a variable number of production cells
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 even for large-sized instances. However, only a few authors have aimed to develop exact methods and most of these methods have some major restrictions such as a fixed number of production cells for example. In this paper we suggest a new mixed-integer linear programming model for solving the cell formation problem with a variable number of manufacturing cells. The popular grouping efficacy measure is used as an objective function. To deal with its fractional nature we apply the Dinkelbach approach. Our computational experiments are performed on two testsets: the first consists of 35 well-known instances from the literature and the second contains 32 instances less popular. We solve these instances using CPLEX software. Optimal solutions have been found for 63 of the 67 considered problem instances and several new solutions unknown before have been obtained. The computational times are greatly decreased comparing to the state-of-art approaches.
Open AccessAn efficient exact model for the cell formation problem with a variable number of production cells
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 even for large-sized instances. However, only a few authors have aimed to develop exact methods and most of these methods have some major restrictions such as a fixed number of production cells for example. In this paper we suggest a new mixed-integer linear programming model for solving the cell formation problem with a variable number of manufacturing cells. The popular grouping efficacy measure is used as an objective function. To deal with its fractional nature we apply the Dinkelbach approach. Our computational experiments are performed on two testsets: the first consists of 35 well-known instances from the literature and the second contains 32 instances less popular. We solve these instances using CPLEX software. Optimal solutions have been found for 63 of the 67 considered problem instances and several new solutions unknown before have been obtained. The computational times are greatly decreased comparing to the state-of-art approaches.
- 24 June 2017
- Published by Springer Nature in Springer Proceedings in Mathematics & Statistics
- p. 11-26
Heuristic for Maximizing Grouping Efficiency in the Cell Formation Problem
- 24 June 2017
- Published by Springer Nature in Springer Proceedings in Mathematics & Statistics
- p. 11-26
Heuristic for Maximizing Grouping Efficiency in the Cell Formation Problem