A mathematical programming problem is one in which there is a particular function to be maximized or minimized subject to several constraints. For instance, a typical mathematical programming problem, (P), can be formulated as Minimize (Maximize) subject to for . If the functions f and are linear for , then (P) is called a linear programming (LP) problem. If, in addition, the variables x, are integer valued, then (P) is called an integer linear programming (ILP) problem. (For more references on (LP) and (ILP) see Chvatal [3] and Schrijver [8]).
Here are two typical real-world applications that can be modeled as a pure integer programming problem.
Consider the problem of scheduling court hearings over a planning horizon consisting of n periods and also m different classes of hearings. Let be the available judge-hours at period j, be the number of hearings of class i arriving at period j, and be the number of judge-hours required to process a hearing of class i. It is desired to determine the number of hearings of class i processed at period j, so that the total number of hearings of all classes over all periods of time is maximized.
First of all, we can model the problem as an (LP) in the following manner.
where the variables is the number of hearings of cases of class i processed at period j, for and .
Inequalities (
) describe the constraints that
the total number of judge hours used cannot exceed what is available
at any time period, while inequalities () say that
the cumulative number of hearings (of each class) up to any
time period cannot exceed the cumulative number of arrivals
(of court cases of the same class) up to that time period.
Constraints () restrict the variables to be non-negative.
Now, it is conceivable that an optimal solution to the (LP) model could contain fractional components. Now, the number of hearings of court cases is generally integer valued. Thus, a better and more accurate model would be an (ILP), as given below.
The only difference is the extra constraints numbered ()
that forces the variables to take integer values.
In general, an (ILP) is more difficult to solve, computationally, than an (LP). The former is an NP-Hard problem (see Garey and Johnson[3]), while for the latter (LP), there is an efficient way of solving it called the Karmarkar's algorithm (See Karmarkar [5]).
An approach to solving (ILP), computationally, is to to apply various heuristics to either the Branch-and-Bound or the Cutting-plane algorithms (see Schrijver [8]).
South Georgia Regional University (a.k.a. SGR-U)'s Vice-president for Planning has compiled a list of badly needed construction projects . For each, she has an estimate of the cost of the project in its 1st (y=1), 2nd(y=2),year, once it has begun. Some projects are also interrelated. Project pairs are mutually exclusive, i.e. at most one of them can ever be undertaken. Project pairs are dependent, i.e. p can be undertaken only if q was started in a prior year. Naturally, there is a limited budget, , in each fiscal year f's budget improvement, for . Like all university administrators, the VP sees her role as making life as easy as possible for SGR-U's administrators. She has estimated for each project, p, a convenience (or sucking-up) value , measuring how much the project will be appreciated by her administrative colleagues.
Her task is to decide on which particular projects to choose, and the start time to implement the chosen projects. She has to do this in such a way that it conforms to budgets, M and D, while maximizing total convenience value.
In a similar way, we can model this problem as an (ILP) except that we restrict the variables to be bounded between 0 and 1, thus making them binary.
The (ILP) model is as follows.
Define decision variables:
For every , and for every ,
Inequalities () describes the budget constraints for each
year, meaning the total amount incurred by all projects during
any fiscal year cannot exceed what is allocated during that year.
Constraints () and () take care of
the mutually exclusive and dependent pairs of projects in the
sets M and D, respectively.
Since each project, if chosen, can start in only one of the fiscal years,
we need inequalities ().
Finally, the constraints () forces the
variables to take on binary values only.
