Abstract
This paper addresses alternative formulations and model enhancements for two combinatorial optimization problems that arise in subassembly matching problems. The first problem seeks to minimize the total deviation in certain quality characteristics for the resulting final products from a vector of target values, whereas the second aims at maximizing the throughput under specified tolerance restrictions. We propose set partitioning and packing models in concert with a specialized column generation (CG) procedure that significantly outperform alternative assignment-based formulations presented in the literature, even when the latter are enhanced via tailored symmetry-defeating strategies. In particular, we emphasize the critical importance of incorporating a complementary CG feature to consistently produce near-optimal solutions to the proposed set partitioning and packing models. Extensive computational results are presented to demonstrate the relative effectiveness of the different proposed modelling and algorithmic strategies.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barnhart C, Johnson EL, Nemhauser GL, Sigismondi G and Vance P (1993). Formulating a mixed integer programming problem to improve solvability. Opns Res 41 (6): 1013–1019.
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh M and Vance PH (1998). Branch-and-price: Column generation for solving huge integer programs. Opns Res 46: 316–329.
Coullard CR, Gamble AB and Jones PC (1998). Matching problems in selective assembly operations. Ann Opns Res 76: 95–107.
Gent IP, Petrie KE and Puget J-F (2006). Symmetry in constraint programming. In: Rossi F, van Beek P and Walsh T (eds). Handbook of Constraint Programming. Elsevier: Amsterdam, pp 329–376.
Ghoniem A and Sherali HD (2009). Complementary column generation and bounding approaches for set partitioning formulations. Optim Lett 3 (1): 123–136.
Glover F (1976). Maximum matching in a convex bipartite graph. Nav Res Logist Q 14: 313–316.
Iwata S, Matsui T and McCormick ST (1998). A fast bipartite network flow algorithm for selective assembly. Opns Res Lett 22: 137–143.
Jeroslow RG and Lowe JK (1985). Experimental results on the new techniques for integer programming formulation. J Opl Res Soc 36: 393–403.
Kannan SM and Jayabalan V (2001). A new grouping method for minimizing the surplus parts in selective assembly. Qual Eng 14 (1): 67–75.
Kannan SM, Jayabalan V and Jeevanantham K (2003). Genetic algorithm for minimizing assembly variation in selective assembly. Int J Prod Res 41 (14): 3301–3313.
Lübbecke ME and Desrosiers J (2005). Selected topics in column generation. Opns Res 53 (6): 1007–1023.
Mansoor EM (1961). Selective assembly—Its analysis and applications. Int J Prod Res 1: 13–24.
Margot F (2010). Symmetry in integer linear programming. In: Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G and Wolsey LA (eds). 50 Years of Integer Programming 1958–2008. Springer: Heidelberg, pp 647–686.
Musa R and Chen FF (2008). Simulated annealing and ant colony optimization algorithms for the dynamic throughput maximization problem. Int J Adv Manuf Tech 37 (7): 837–850.
Musa R, Chen FF and Ghoniem AS (2006). Dynamic variation reduction technique in assembly lines after batch inspection. IIE Annual Conference and Expo, Orlando, FL, May.
Sherali HD and Smith JC (2001). Improving discrete model representations via symmetry considerations. Mngt Sci 47: 1396–1407.
Williams HP (1974). Experiments in the formulation of integer programming problems. Math Program Stud 2: 180–197.
Williams HP (1978). The reformulation of two mixed integer programming problems. Math Program 14: 325–331.
Williams HP (1999). Model Building in Mathematical Programming. Wiley: New York.
Wolsey LA (1989). Strong formulations for mixed integer programming: A survey. Math Program 45: 173–191.
Wolsey LA (2003). Strong formulations for mixed integer programs: Valid inequalities and extended formulations. Math Program 97 (1–2): 423–447.
Acknowledgements
This work has been partially supported by the National Science Foundation under Grant CMMI-0552676. The authors also thank the Editor and two anonymous referees for their constructive comments that have helped improve the presentation in this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ghoniem, A., Sherali, H. Set partitioning and packing versus assignment formulations for subassembly matching problems. J Oper Res Soc 62, 2023–2033 (2011). https://doi.org/10.1057/jors.2010.165
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2010.165