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

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.

Keywords: mixed integer linear mathematical programming, response time variability problem, combinatorial optimization

Author: Rafael Pastor

Journal Code: jptindustrigg080010

Artikel Terkait :

Jp Teknik Industri gg 2008

• Adaptation of coordination mechanisms to network structures
• Empirical evaluation of the efficiency of the Iberian power futures market
• The employee satisfaction in metalworking manufacturing: How do organizational culture and organizational learning capacity jointly affect it?
• AHP approach for supplier evaluation and selection in a steel manufacturing company
• A collaborative knowledge management framework for supply chains: A UML-based model approach
• Profile and competences of Spanish industrial engineers in the European Higher Education Area (EHEA)
• Measuring the impact of HRM on organizational performance
• Relationship between the components of product/service quality and the customers’ emotions and satisfaction
• Which competitive advantages can firms really obtain from ISO14001 certification?
• Pragmatic evaluation of the Toyota Production System (TPS) analysis procedure for problem solving with entry-level nurses
• Application of root cause analysis in improvement of product quality and productivity
• THE QUALITY IMPROVEMENT OF PRIMER PACKAGING PROCESS USING SIX SIGMA METHODOLOGY
• EFFECT OF COST INCREMENT DISTRIBUTION PATTERNS ON THE PERFORMANCE OF JIT SUPPLY CHAIN
• A SMOOTH DIFFUSION RATE MODEL OF WOOD DRYING: A SIMULATION TOWARD MORE EFFICIENT PROCESS IN INDUSTRY
• Joint Economic Lot Sizing Optimization in a Supplier-Buyer Inventory System When the Supplier Offers Decremental Temporary Discounts
• MODELING BILL-OF-MATERIAL WITH TREE DATA STRUCTURE: CASE STUDY IN FURNITURE MANUFACTURER
• ANALYSIS ON THE INFLUENCE OF WOMEN FARMING WORKERS TO INCOME AND FAMILY CONSUMPTION PATTERN IN SURBAKTI VILLAGE, SIMPANG EMPAT SUB-DISTRICT, KARO REGENCY, NORTH SUMATERA PROVINCE, INDONESIA