A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems. (English) Zbl 1380.90261
Summary: We consider reformulations of fractional (hyperbolic) 0-1 programming problems as equivalent mixed-integer linear programs (MILP). The key idea of the proposed technique is to exploit binary representations of certain linear combinations of the 0-1 decision variables. Consequently, under some mild conditions, the number of product terms that need to be linearized can be greatly decreased. We perform numerical experiments comparing the proposed approach against the previous MILP reformulations used in the literature.
Keywords:
fractional 0-1 programming; hyperbolic 0-1 programming; linearization; binary representations; mixed integer linear programsReferences:
| [1] | Adams, W. P.; Forrester, R. J., A simple recipe for concise mixed 0-1 linearizations, Oper. Res. Lett., 33, 1, 55-61 (2005) · Zbl 1076.90030 |
| [2] | Adams, W. P.; Forrester, R. J., Linear forms of nonlinear expressions: New insights on old ideas, Oper. Res. Lett., 35, 4, 510-518 (2007) · Zbl 1149.90396 |
| [3] | Adams, W. P.; Henry, S. M., Base-2 expansions for linearizing products of functions of discrete variables, Oper. Res., 60, 6, 1477-1490 (2012) · Zbl 1287.90033 |
| [4] | Agrawal, S. C., An alternate method on integer solutions to linear fractional functionals by a branch and bound technique, ZAMM Z. Angew. Math. Mech., 57, 1, 52-53 (1977) · Zbl 0356.65063 |
| [5] | Amaldi, E.; Bosio, S.; Malucelli, F., Hyperbolic set covering problems with competing ground-set elements, Math. Program., 134, 2, 323-348 (2012) · Zbl 1254.90119 |
| [6] | Arora, S. R.; Puri, M. C.; Swarup, K., The set covering problem with linear fractional functional, Indian J. Pure Appl. Math., 8, 5, 578-588 (1977) · Zbl 0434.90093 |
| [7] | Boros, E.; Hammer, P. L., Pseudo-boolean optimization, Discrete Appl. Math., 123, 1, 155-225 (2002) · Zbl 1076.90032 |
| [8] | Busygin, S.; Prokopyev, O. A.; Pardalos, P. M., Feature selection for consistent biclustering via fractional 0-1 programming, J. Combin. Optim., 10, 1, 7-21 (2005) · Zbl 1123.90073 |
| [9] | Chaovalitwongse, W.; Pardalos, P. M.; Prokopyev, O. A., A new linearization technique for multi-quadratic 0-1 programming problems, Oper. Res. Lett., 32, 6, 517-522 (2004) · Zbl 1054.90047 |
| [10] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem-part ii, Oper. Res., 11, 6, 863-888 (1963) · Zbl 0124.36307 |
| [11] | Granot, D.; Granot, F., On solving fractional (0,1) programs by implicit enumeration, INFOR, Can. J. Oper. Res. Inf. Process., 14, 241-249 (1976) · Zbl 0344.90025 |
| [12] | Grunspan, M.; Thomas, M. E., Hyperbolic integer programming, Naval Res. Logist. Q., 20, 2, 341-356 (1973) · Zbl 0263.90019 |
| [13] | Hansen, P.; de Aragão, M. V.P.; Ribeiro, C. C., Boolean query optimization and the 0-1 hyperbolic sum problem, Ann. Math. Artif. Intell., 1, 1-4, 97-109 (1990) · Zbl 0870.68048 |
| [14] | Hansen, P.; de Aragão, M. V.P.; Ribeiro, C. C., Hyperbolic 0-1 programming and query optimization in information retrieval, Math. Program., 52, 1-3, 255-263 (1991) · Zbl 0737.90044 |
| [15] | Ibaraki, T., Integer programming formulation of combinatorial optimization problems, Discrete Math., 16, 1, 39-52 (1976) · Zbl 0357.90042 |
| [16] | Li, H.-L., A global approach for general 0-1 fractional programming, European J. Oper. Res., 73, 3, 590-596 (1994) · Zbl 0806.90119 |
| [17] | Méndez-Díaz, I.; Miranda-Bront, J. J.; Vulcano, G.; Zabala, P., A branch-and-cut algorithm for the latent-class logit assortment problem, Discrete Appl. Math., 164, 246-263 (2014) · Zbl 1326.90041 |
| [18] | Prokopyev, O. A., Fractional zero-one programming, (Encyclopedia of Optimization (2009)), 1091-1094 |
| [19] | Prokopyev, O. A.; Huang, H.-X.; Pardalos, P. M., On complexity of unconstrained hyperbolic 0-1 programming problems, Oper. Res. Lett., 33, 3, 312-318 (2005) · Zbl 1140.90469 |
| [20] | Prokopyev, O. A.; Meneses, C.; Oliveira, C. A.S.; Pardalos, P. M., On multiple-ratio hyperbolic 0-1 programming problems, Pac. J. Optim., 1, 2, 327-345 (2005) · Zbl 1105.90094 |
| [21] | Saipe, A. L., Solving a (0,1) hyperbolic program by branch and bound, Naval Res. Logist. Q., 22, 3, 497-515 (1975) · Zbl 0335.90042 |
| [22] | Sherali, H. D.; Smith, J. C., An improved linearization strategy for zero-one quadratic programming problems, Optim. Lett., 1, 1, 33-47 (2007) · Zbl 1149.90115 |
| [23] | Subramanian, S.; Sherali, H. D., A fractional programming approach for retail category price optimization, J. Global Optim., 48, 2, 263-277 (2010) · Zbl 1198.90370 |
| [24] | Tawarmalani, M.; Ahmed, S.; Sahinidis, N. V., Global optimization of 0-1 hyperbolic programs, J. Global Optim., 24, 4, 385-416 (2002) · Zbl 1046.90054 |
| [25] | Trapp, A.; Prokopyev, O. A.; Busygin, S., Finding checkerboard patterns via fractional 0-1 programming, J. Combin. Optim., 20, 1, 1-26 (2010) · Zbl 1198.90292 |
| [26] | Vielma, J. P.; Nemhauser, G. L., Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Math. Program., 128, 1-2, 49-72 (2011) · Zbl 1218.90137 |
| [27] | Watters, L. J., Reduction of integer polynomial programming problems to zero-one linear programming problems, Oper. Res., 15, 6, 1171-1174 (1967) |
| [28] | Williams, H. P., Experiments in the formulation of integer programming problems, (Approaches to Integer Programming (1974), Springer), 180-197 · Zbl 0353.90062 |
| [29] | Wu, T.-H., A note on a global approach for general 0-1 fractional programming, European J. Oper. Res., 101, 1, 220-223 (1997) · Zbl 0916.90252 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
