Optimization of large scale 0-1 integer linear programming problems with multiple-choice constraints

Abstract

In many capital budgeting decision making situations, the decision problem may be formulated as a 0-1 integer linear programming problem with multiple-choice constraints. An example of this formulation is a model of the rehabilitation and maintenance of the Texas State highway system. The realistic representation of a highway maintenance system involves a large number of 0-1 variables and many different constraints. For example, a formulation of the Texas State highway maintenance system may involve as many as 600 highway segments. There may be 10 strategies or maintenance alternatives for each highway segment. Hence, there would be 600 x 10 = 6000 variables. In addition, there may be several hundred constraints, including resource constraints, the generalized upper bound (GUB) constraints and technical feasibility constraints. Generalized upper bound constraints or miltiple-choice constraints imply that, at most one strategy may be selected from several possible strategies for each highway segment. Within the larger framework of optimal decision processes, similar large scale 0-1 integer programming problems with multiple-choice constraints are frequently encountered, particularly problems involving capital budgeting and resource allocation. ABSTRACT