You are here

Variations in the efficiency of a mathematical programming solver according to the order of the constraints in the model

Journal Name:

Publication Year:

DOI: 
doi:10.3926/jiem.2008.v1n2.p4-15
Abstract (2. Language): 
Abstract: It is well-known that the efficiency of mixed integer linear mathematical programming depends on the model (formulation) used. With the same mathematical programming solver, a given problem can be solved in a brief calculation time using one model but requires a long calculation time using another. In this paper a new, unexpected feature to be taken into account is presented: the order of the constraints in the model can change the calculation time of the solver considerably. For a test problem, the Response Time Variability Problem (RTVP), it is shown that the ILOG CPLEX 9.0 optimizer returns a ratio of 17.47 between the maximum and the minimum calculations time necessary to solve optimally 20 instances of the RTVP, according to the order of the constraints in the model. It is shown that the efficiency of the mixed integer linear mathematical programming depends not only on the model (formulation) used, but also on how the information is introduced into the solver.
4-15

REFERENCES

References: 

Bar-Noy, A., Bhatia, R., Naor, J., & Schieber, B. (2002). Minimizing service and
operation costs of periodic scheduling. Mathematics of Operations Research, 27,
518-544.
Billionnet, A. (1999). Integer programming to schedule a hierarchical workforce
with variable demands. European Journal of Operational Research, 114, 105–114.
Bollapragada, S., Bussieck, M.R., Mallik, S. (2004). Scheduling commercial
videotapes in broadcast television. Operations Research, 52(5), 679-689.
Brusco, M.J. (2008). Scheduling advertising slots for television. Journal of the
Operational Research Society, 59, 1363-1372.
Corominas, A., Kubiak, W., Pastor, R. (2006). Solving the Response Time Variability
Problem (RTVP) by means of mathematical programming. Working paper IOC-DT,
Universistat Politècnica de Catalunya, Spain.
doi:10.3926/jiem.2008.v1n2.p4-15 ©© JIEM, 2008 – 01(02): 4-15 - ISSN: 2013-0953
Variations in the efficiency of a mathematical programming solver according to the order of
the constraints in the model
14
R. Pastor
Corominas, A., Pasto,r R., & Plans, J. (2008). Balancing assembly line with skilled
and unskilled workers. OMEGA The International Journal of Management Sciences,
36, 1126–1132.
Corominas, A., Kubiak, W., & Moreno, N. (2007). Response time variability. Journal
of Scheduling, 10, 97–110.
García, A., Pastor, R., & Corominas, A. (2006). Solving the Response Time
Variability Problem by means of metaheuristics. Frontiers in Artificial Intelligence
and Applications, 146, 187–194.
García-Villoria, A., Pastor, R., & Corominas, A. (2007). Solving the Response Time
Variability Problem by means of the Cross-Entropy Method. International Journal
of Manufacturing Technology and Management (to be published).
García-Villoria, A., & Pastor, R. (2008ª). Solving the Response Time Variability
Problem by means of the Electromagnetism-like Mechanism. Working paper IOCDT-
P-2008-03, Universitat Politècnica de Catalunya, Spain (available at
http://hdl.handle.net/2117/2013).
García-Villoria, A., & Pastor, R. (2008b). Solving the Response Time Variability
Problem by means of a Psychoclonal Approach. Journal of Heuristics.
doi:10.1007/s10732-008-9082-2.
García-Villoria, A., & Pastor, R. (2009). Introducing dynamic diversity into a
discrete Particle Swarm Optimization. Computers & Operations Research, 36(3),
951-966.
Herrmann, J.W. (2007). Generating Cyclic Fair Sequences using Aggregation and
Stride Scheduling. Technical Report, University of Maryland, USA.
Monden, Y. (1983). Toyota Production Systems. Industrial Engineering and
Management Press: Norcross, GA.
Pastor, R., Altimiras, J., & Mateo, M. (2008). Planning production using
mathematical programming: The case of a woodturning company. Computers &
Operations Research. doi: 10.1016/j.cor.2008.08.005
doi:10.3926/jiem.2008.v1n2.p4-15 ©© JIEM, 2008 – 01(02): 4-15 - ISSN: 2013-0953
Variations in the efficiency of a mathematical programming solver according to the order of
the constraints in the model
15
R. Pastor
Margot, F. (2007). Symmetric ILP: Coloring and small integers. Discrete
Optimization, 4, 40–62.
Salkin, H.M., & Mathur, K. 1989. Foundations of integer programming, North-
Holland, Amsterdam.
Waldspurger, C.A., & Weihl, W.E. (1995). Stride scheduling: deterministic
proportional-share resource management. Technical Memorandum MIT/LCS/TM-
528. MIT, Laboratory for Computer Science, Cambridge.

Thank you for copying data from http://www.arastirmax.com