Reprinted (with additional material) from Compass News, number 5, fall 1997 Over the past four years, I have been using AMPL to solve an unusual kind of assignment problem for a well-known firm (to remain nameless). Here I'll first describe the problem as it originally came to my attention, and then the way that I originally solved it. At the end I'll briefly note some of the variations that have arisen, and some current research toward making AMPL even more useful for this kind of application.
The eminent company official in charge of this event was concerned that participants might only use it to socialize with the most familiar of their co-workers -- that is, with the ones most like themselves. Hence it was decreed that the dinner groups be "as diverse as possible" with respect to employees of different kinds. Dinner assignments satisfying this goal would be made in advance, so that they could be given to the participants when they arrived for the meeting.
This certainly sounded like a variant of the "assignment problem" that has been a staple of linear programming and management science textbooks for decades. Nevertheless, there were a number of ways in which the situation differed from the applications of optimization techniques most familiar to me.
First, the employees charged with making the dinner assignments could not be expected to have a background in linear programming or in any operations research techniques. The person who first brought the problem to my attention was a database specialist; it had landed on his desk for the seemingly logical reason that the names of the participants were in a database file, and the dinner assignments were to be added as a record in that file. He had no training of the sort that would have helped him to attack the problem systematically, nor did any of the others involved with planning and executing the meeting.
Second, the problem's objective function did not correspond to any measurable sort of cost or profit. Indeed, although there did appear to be an objective -- namely, maximizing "diversity" -- there was no specific measure of diversity by which the results would be measured. So long as every group seemed to contain a representative mix of participant characteristics, the assignment would be considered acceptably diverse. As it developed, there were four characteristics of interest, which could be summarized as rank, department, location, and sex. The difficulty of the problem lay in making each group simultaneously representative in all four characteristics.
Third, the definition of an acceptable solution was not fundamentally physical or economic in origin. Of course, a person could only be assigned to one group, and group size was limited by room size, but other restrictions could be added or changed at the whim of the person in charge. An illustration of this principle was soon forthcoming, as it was decided that too much diversity might not be such a good thing. Thus I was informed that a group should not contain just one person from any location, or even a few people from a location unless they were of "adjacent" ranks.
Finally, there were no obstacles to implementation. The company would send me a table of people and their characteristics, and a few days later I would send back the same table with an extra column headed "restaurant". We faced none of the usual problems of integrating an optimization model within a complex production or logistical system.
The linear objective function of the textbook assignment problem could not be made to represent "diversity" in the desired sense, so it was fortunate that the problem gave me plenty of leeway in choosing an objective. Rather than trying to maximize diversity directly, I considered minimizing the simpler concept of "sameness" to achieve an equivalent result. At first I experimented with summing terms of the form same[i1,i2] * Assign[i1,j] * Assign[i2,j], where same[i1,i2] was the number of characteristics in which persons i1 and i2 were the same. There are several clever ways in which this quadratic objective can be transformed to an equivalent linear one. Unfortunately, experiments with small subsets of the data indicated that the resulting integer programs could not be solved with reasonable effort using the computers and solvers then available.
In the end, I turned to a more straightforward approach for the objective. For each value of each characteristic at each restaurant, I determined a target number of people in the group. If 24% of the meeting participants were from the Chicago office, for example, and some restaurant had a capacity of 30, then the ideal number of people from Chicago assigned to that restaurant would be 24% x 30 = 7.2, and my target would be 7 or 8. The idea was then to minimize the total deviation of the solution from the targets, summed over all four characteristics, all possible values of these characteristics, and all restaurants. This could be written as a linear function of some new deviation variables, which were tied to the assignment variables by some auxiliary constraints.
When I proceeded from small experimental datasets to the full 1000-person problem, additional refinements were necessary in order to make the computations practical. To reduce the size and symmetry of the problem, I lumped together people who had the same values for all four characteristics; such people were indistinguishable from the standpoint of the assignment. I then broke the problem in two, solving first to distribute just the two characteristics that figured in the "not too much diversity" constraints, and then refining that assignment to include the other two characteristics. I stopped the solution process for the first part as soon as a feasible solution was found, as that solution was already very close to my targets. Here again, I took advantage of the fact that the objective was merely a heuristic device, rather than a direct measure of cost or profit; there was little to be gained by insisting on an exact, provable optimum.
The final runs took 4-5 hours for each part, on a Unix workstation that was moderately fast by then-current standards. The results were returned to the company with time to spare. In fact there was time to re-run the models closer to the deadline, to take account of last-minute changes.
The advantages of AMPL for this project were evident. Without so flexible a tool, I could not have experimented with so many formulations in the time available. AMPL's powerful and general set expressions were put to good use in transforming the raw data to the target values and other information required by the model. The communication from the first to the second part of the optimization was easily specified by a small program written in AMPL's procedural command language.
A more complicated recent application involved seating students in lecture rooms for a multi-week training session, with the different characteristics spread more-or-less evenly through the room. In another project we assigned people to different series of 3 presentations, taking their preferences into account; the integer programs were easy in this case, but only once some difficult data manipulations were worked out. Neither of these projects could have been completed at reasonable cost without a prototyping tool like AMPL.
Fees for these projects have been based on a formula that takes account of the number of people, the number of characteristics, and the number of different assignments required. Proceeds go into an account to support additional research. Plans are underway to seek out other companies that may have similar needs.
The use of zero-one assignment variables is not necessarily the best way to formulate these problems, but currently it is the only approach that can take full advantage of the AMPL language. One current focus of my research is to determine how AMPL can be enhanced to support other formulation and solution approaches, such as those associated with constraint logic programming.
Further information on balanced assignment services and research is to be made available through a new web site. Look for links from the AMPL in Action page, http://www.ampl.com/ampl/CASES/.
Robert Fourer, one of the designers of AMPL, is Professor of Industrial Engineering and Management Sciences at Northwestern University. More information on balanced assignment models and services can be obtained by contacting him at +1 847-491-3151 or 4er@iems.nwu.edu.
Return to the AMPL cases index.