METHOD AND APPARATUS FOR DISCRETE ACTIVITY RESOURCE ALLOCATION THROUGH CARDINALITY CONSTRAINT GENERATION

The required computational effort in the areas of production planning and logistics, scheduling, distribution and resource allocation is reduced by a procedure for solving a Discrete Activity Resource Allocation (DARA) problem. The procedure begins by reducing all activities and resources which do not contribute to maximizing benefit. Thus, all infeasible and non-profitable activities are discarded and all non-constraining resources are discarded, thereby considerably simplifying the solution to the problem. Next, an automatic mathematical model formulation of the DARA problem is performed. Based on this model, a list of cliques and covers are generated. The linear relaxation of the DARA problem using standard linear programming software is solved, and the generated list of clique and cover induced inequalities is scanned to select a set violated by the solution of the linear relaxation of the DARA problem. For those inequalities found, constraints are appended to the formulated DARA problem, forming another DARA problem with the same set of variables, but with additional constraints. The new DARA problem is then solved using the previous solution as the start of the solution. Based on this solution, the generated list of clique and cover induced inequalities is again scanned, and this process is continued until no violated inequalities are found. At this point in the procedure, conventional branch-and-bound or branch-and-cut routines are used to solve the enlarged DARA problem. The solution yields the optimal resource allocation producing the maximum benefit.