Abstract
The generalized independent set (GIS) problem was first introduced by Hochbaum and Pathria (Forest Sci 43(4), 544–554, 1997) and independently explored in greater detail by Hochbaum (Manage Sci 50(6), 709–123, 2004). This problem, with applications in forest management and a variety of related areas, is a generalization of the classical maximum independent set problem. In this paper we highlight a natural, nonlinear formulation for the problem that is an attractive alternative to the linear model found in the literature. The effectiveness of this alternative formulation is demonstrated by computational experience on test problems of varying size and density, disclosing a dramatic reduction in the time to obtain optimal and near optimal solutions and an ability to solve much larger problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alidaee B., Glover F., Kochenberger G., Rego C.(2005): A new modeling and solution approach for the number partitioning problem. J. of Appl. Math. Decis. Sci. 9(2): 113–121
Glover F., Kochenberger G., Alidaee B.(1998a): Adaptive memory tabu search for binary quadratic programming. Manage. Sci. 44(3): 336–345
Glover F., Kochenberger G., Alidaee B., Amini M.(1998b): Tabu search with critical event memory: an enhanced application for binary quadratic programming. In: Voss S., Martello S., Osman I., Roucairol C. (eds). Meta Heuristics: Theory and Applications. Kluwer, Dordrecht, pp. 93–109
Hochbaum D(2004): Selection, provisioning, shared fixed costs, maximum closure, and implications on algorithmic method today. Manage. Sci. 50(6): 709–723
Hochbaum D, Pathria A.(1997): Forest harvesting and minimum cuts. Forest Sci. 43(4): 544–554
Kochenberger G.A., Glover F., Alidaee B., Rego C.(2004): A unified modeling and solution framework for combinatorial optimization problems. OR Spectrum 26, 237–250
Kochenberger G., Glover F., Alidaee B., Rego C.(2005a): An unconstrained quadratic binary approach to the vertex coloring problem. Ann. OR 139, 229–241
Kochenberger G., Glover F., Alidaee B., Lewis K.(2005b): Using the unconstrained quadratic program to model and solve max 2-Sat problems. Int. J. Oper. Res. 1(1 & 2): 89–100
Kochenberger G., Glover F., Alidaee B., Wang H.(2005c): Clustering of microarray data via clique partitioning. J. Comb. Optim. 10, 77–92
Lewis M., Alidaee B., Kochenberger G.(2005): Using xQx to model and solve the uncapacitated task allocation problem. OR Lett. 33, 176–182
Pardalos P., Rodgers G.(1990): Computational aspects of a B&B algorithm for quadratic zero-one programming. Computing 45, 131–144
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kochenberger, G., Alidaee, B., Glover, F. et al. An effective modeling and solution approach for the generalized independent set problem. Optimization Letters 1, 111–117 (2007). https://doi.org/10.1007/s11590-006-0007-4
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-006-0007-4