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

DOI10.1007/978-3-319-44914-2_20zbMATH Open1391.90417arXiv1603.04597OpenAlexW2299898751MaRDI QIDQ3133219FDOQ3133219

Authors: Irina Utkina, Mikhail Batsyn, Ekaterina Batsyna 

Publication date: 13 February 2018

Published in: Discrete Optimization and Operations Research (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1603.04597

Recommendations

• scientific article; zbMATH DE number 66872
• Fractional 0-1 programming: applications and algorithms
• scientific article; zbMATH DE number 6907481
• An effective branch and bound algorithm for minimax linear fractional programming
• A branch and bound algorithm for solving low rank linear multiplicative and fractional programming problems
• Branch-reduction-bound algorithm for linear sum-of-ratios fractional programs
• An efficient algorithm for solving a class of fractional programming problems
• A combined algorithm for fractional programming
• Branch-and-bound outer approximation algorithm for sum-of-ratios fractional programs
• A deterministic algorithm for solving a series of fractional programming problems

zbMATH Keywords

biclusteringbranch and boundexact solutionupper boundcell formation

Mathematics Subject Classification ID

Fractional programming (90C32) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Boolean programming (90C09)

Cited In (2)

• Title not available (Why is that?)
• A new branch and bound algorithm for cell formation problem

This page was built for publication: A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133219)