THE APPLICATION OF INTEGER LINEAR-PROGRAMMING TO THE IMPLEMENTATION OF A GRAPHICAL USER-INTERFACE - A NEW RECTANGULAR PACKING PROBLEM

This paper presents an instance of the rectangular packing problem whi ch arises in the implementation of a graphical user interface in a win dows environment. The problem consists of a single, containing rectang le of finite dimension and an ordered collection of rectangular object s to be packed in the rectangle. The size of the containing rectangle is dynamic, and restrictions are placed on the subset of the objects t hat can be packed in tire rectangle at any given instance. A detailed description of the general problem is provided and a mathematical form ulation is presented. A specific, real-world application is then intro duced and modeled as an integer linear programming problem. Finally, d ue to the intractability of a direct solution of the mathematical mode l, a network representation of the problem is derived from which an ef ficient branch-and-bound solution algorithm is developed. The performa nce with respect to execution time of the branch-and-bound algorithm i s analyzed for various instances of the problem and the quality of sol ution with respect to objective value is compared with that of an ad h oc method.