CLICK HERE TO GO TO THE DIGITAL VERSION OF THIS ARTICLE

No Such Thing As a Free Lunch?

Think again. Combinatorial auctions help feed two million public school children from low-income families in Chile.

JUNAEB provides meals for 2 million children in primary and secondary public schools.

By Jaime Catalán, Rafael Epstein, Mario Guajardo, Daniel Yung, Lysette Henriquez, Cristain Martinez and Gabriel Weintraub

Economists love to say that there is no such thing as a free lunch. But the Chilean government agency responsible for school grants, Junta Nacional de Auxilio Escolar y Becas (JUNAEB), is an exception to the rule. During the school year, JUNAEB provides breakfast and lunch for 2 million children in primary and secondary public schools. In a developing country where about 14 percent of children under the age of 18 live below the poverty line, many students depend on these free meals as a key source of nutrition.

In 1980, JUNAEB began assigning catering contracts to companies through competitive auctions. At first, only three companies submitted bids, but this number rose to 30 during the 1990s and remains close to that level today.

Given the volume of meals it procures, JUNAEB has always had significant bargaining power over vendors. However, until the late 1990s, JUNAEB awarded contracts based on subjective, and quite rudimentary, criteria, making it easier for bidders to exert inappropriate pressures on JUNAEB officials. Vendors lacked incentives to reduce costs and inefficiencies, and JUNAEB wound up paying a high price for low-quality products.

In 1997, JUNAEB’s board asked a team of academics from the University of Chile’s Department of Industrial Engineering to design and implement a new mechanism for auctioning its school meals service. The new model was implemented for the first time that year and has been used ever since. (We have updated and enhanced the model during this period.) In this article, we present the development and application of this new mechanism, which assigns bids in a single-round, sealed-bid combinatorial auction and is based on an integer linear programming model.

The use of an optimization model in the bidding process to award school meal contracts in Chile has yielded significant social benefits.

The New Auction Process

FOR THE PURPOSES OF the auction, Chile is divided into approximately 120 school districts or territorial units (TUs). JUNAEB holds auctions for school catering services in one-third of these districts every year, awarding three-year contracts. The auction process begins when JUNAEB contacts and registers potential vendors. The agency then evaluates the companies from a managerial, technical and financial point of view, and eliminates those that don’t meet minimum reliability standards. Qualifying vendors are classified according to two characteristics: their financial and operating capacity, and their technical and managerial competence.

After the companies are classified, JUNAEB publishes a call to tender with the rules for bidding. Potential vendors submit their bids through an online system. Each bid includes a technical project for meal service and its price. The technical project must meet regulations established by JUNAEB, such as nutritional and hygiene requirements. In this way, meal plans are standardized.

Vendors that satisfy these conditions remain in the bidding process and compete on price, through their respective bids. A bid can cover anywhere from one to 12 TUs, depending on the vendor’s classification. Vendors can submit as many bids as they want; each bid is accepted or rejected in its entirety. When JUNAEB accepts a company’s bid, the company must provide all meal services in the corresponding TUs.

Because JUNAEB allows companies to submit bids that cover multiple TUs, vendors can take advantage of economies of scale. The shared use of infrastructure in neighboring regions, volume discounts and efficiencies in transportation and staffing all contribute to the economies of scale. Firms generally submit many bids, ranging from bids that cover just one TU to those that cover a package of TUs. The ability to submit bids on various groupings of TUs defines the combinatorial character of this auction — and makes identifying the optimal solution much more difficult.

Each bid includes prices for the various catering services that JUNAEB provides in the corresponding TUs. Furthermore, JUNAEB asks companies to quote alternatives to these services, such as improvements to the nutritional quality of the meals. Vendors also quote prices for different levels of demand, thereby reducing the risk the vendors would face if they provide fewer meals because of unforeseen events, such as teacher strikes. Firms can also offer discounts if the

real demand turns out to be higher than anticipated.

In recent years, combinatorial auctions have received a lot of attention from both the academic and industrial worlds. Combinatorial auctions have clear advantages when the auctioned items have a higher value as a set than as separate parts. Other successful applications of these auction applications have been documented [1, 2, 3, 4].

The Assignment Model and Its Solution

The new model’s objective is to select a combination of bids that supply all of the TUs at a minimum cost. The performance of vendors based on JUNAEB’s evaluations, or their quality index, is also a factor in awarding contracts. Other constraints include:

• Limits on the number of vendors supplying a region. Having too few vendors increases the risk of supply interruptions, while having too many can make management more difficult.
• A maximum award per vendor, calculated as a function of other contracts held by the vendor, its quality index and its financial and operating capacity.
• Minimum prices. A phenomenon known as “winner’s curse” occurs when the firm that bid the lowest price is found to have underestimated its costs, raising the possibility of losses or even financial ruin [5]. To avoid this, unrealistically low bids are eliminated.

Furthermore, we consider various scenarios such as different food structures and demand levels. By combining all of the possible variations, we generated more than 700 scenarios for analysis. In practice, the decision-maker will be interested in evaluating no more than 200 of them.

To find the optimal assignment for each scenario, we formulated the problem as an integer linear programming model. We defined a binary decision variable for each bid, where the decision is either to accept the bid or reject it. We also defined auxiliary binary variables that correspond to the restrictions limiting the number of firms in each region and the number of firms in the winning assignment.

Not surprisingly, the difficulty of solving combinatorial bidding models is one of the main impediments to their broader use. Solving our model can be a challenging task, indeed, since it contains three classical combinatorial structures, each NP-hard: a set-covering problem, a multiknapsack problem and uncapacitated facility location problem. A real instance of the problem contains about 90,000 binary variables. In addition, considering the high number of scenarios to be evaluated, we had to design an efficient solving strategy. (Additional technical details can be found in [6, 7].)

We found optimal solutions by solving the different scenarios of the model, and the JUNAEB Contract Award Commission was able to evaluate these scenarios along with the quality and robustness of their solutions. For example, the model allows JUNAEB to analyze the performance of the optimal solution when the demand level is at 100 percent, and compare this to the performance when demand is at 80 percent.

It is important to note that the commission selects the scenario to be considered for the award, but the optimization model provides the specific solution. The entire process ¬ including data processing, administrative tasks, legal procedures and analysis of scenarios ¬ is usually completed in no more than 10 days.

In developing countries, state-run social programs like school meals often account for the bulk of the national budget.

Results and Conclusions

The use of an optimization model in the bidding process to award school meal contracts in Chile, along with other managerial advances at JUNAEB, has yielded significant social benefits. For example, we compared the 1999 auction (which used the new model) and the 1995 auction (carried out under the old process) and found substantial improvements in the nutritional quality of the meals, the infrastructure of the meals service and the labor conditions of the food handlers. Although these improvements increased total costs by 24 percent (in real terms), the average price of a meal rose by only 0.76 percent. In all, the new model saved the government about $40 million a year, or the cost of feeding 300,000 children.

Using mathematical modeling to assign contracts allowed JUNAEB to reap significant savings for the following reasons:

1. The new process is objective and transparent, providing few opportunities for vendors to pressure on decision makers.
2. The process is impartial and reliable. It forces companies to compete and to increase productivity. Participating vendors have improved their management, enhanced the quality of their service and cut their prices, and they still manage to make profits. In fact, a survey by JUNAEB compared the companies’ average profit on sales before and after the model was introduced. The results showed profits increased from 3.2 percent to 4.9 percent. Average return on equity also rose, climbing from 28 percent to 38 percent, reflecting the vendors’ higher rate of investment.
3. By allowing companies to make bids that cover multiple TUs, vendors can take advantage of economies of scale.
4. In every scenario, JUNAEB is able to get the lowest-cost bid combination that meets all of its restrictions. This would be nearly impossible to accomplish manually. Would the agency attempt to do so, and make an assignment that is just 2 percent more costly than the optimal solution, it would overspend by $10 million, — the equivalent of providing food to 40,000 children.

The clearest evidence of the model’s success is its continued use. JUNAEB introduced the model in 1997 and has applied it ever since. To date, the Chilean government has awarded more than $2 billion of contracts using the combinatorial auction methodology. Over the years, we have enhanced the model’s outputs and improved the comparison among different scenarios. In 2002, this work received the IFORS Prize for Operational Research in Development, awarded by the International Federation of Operational Research Societies to the best application of O.R. in developing countries.

Recently, we developed new procedures to solve the multiple auction scenarios, reducing solution times significantly [7]. We are currently studying the empirical behavior of bidders, so that we can better understand their cost structures and economies of scale, and thereby improve the auction design. Overall, the project has generated a stimulating and challenging research agenda on both algorithmical issues and auction design.

In developing countries, state-run social programs often account for the bulk of the national budget. The success of this case shows that sophisticated decision-making tools can help. Small changes in these programs can lead to enormous savings, and these savings can lead to tangible improvements in quality of life, such as meals for school children. Perhaps operational research tools can continue to uncover free lunches where they are needed the most.

Rafael Epstein ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ) is an associate professor in the Department of Industrial Engineering, University of Chile, where Jaime Catalán ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ), Mario Guajardo ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ) and Daniel Yung ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ) are research assistants. Gabriel Weintraub ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ) is an assistant professor of decision, risk and operations at Columbia Business School. Lysette Henriquez ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ) is former Director of JUNAEB. Cristian Martínez ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ) is Vice-Minister of Education, Chile.

References

1. Hohner G., Rich, J., Ng, E., Reid, G., Davenport, A.J., Kalagnanam, J.R., Lee, H.S., An, C., 2003, “Combinatorial and Quantity-Discount Procurement Auctions Benefit Mars, Incorporated and Its Suppliers,” Interfaces, Vol. 33, Vol. 1, pp. 23-35.

2. Sheffi, Y., 2004, “Combinatorial Auctions in the Procurement of Transportation Services,” Interfaces, Vol. 34, No. 4, pp. 245-252.

3. Metty, T., Harlan, R., Samelson, Q., Moore, T., Morris, T., Sorensen, R., Schneur A., Raskina O., Schneur R., Kanner, J., Potts K., Robbins, J., 2005, “Reinventing the Supplier Negotiation Process at Motorola,” Interfaces, Vol. 35, No. 1, pp. 7-23.

4. Sandholm, T., Levine, D., Concordia, M., Martyn, P., Hughes, R., Jacobs, J., Begg, D., 2006, “Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization,” Interfaces, Vol. 36, No. 1, pp. 55-68.

5. Milgrom, P., 1989, “Auctions and Bidding: A Primer,” The Journal of Economic Perspectives, Vol. 3, No. 3, pp. 3-22.

6. Epstein, R., Henríquez, L., Catalan, J., Weintraub, G., Martínez, C. A., 2002, “Combinatorial Auction Improves School Meals in Chile,” Interfaces, Vol. 32, No. 6, pp. 1-14.

7. Catalan, J., Epstein, R., Guajardo, M., Yung, D., Martínez, C., 2006, “Solving multiple scenarios in a combinatorial auction,” accepted for publication in Computers and Operations Research.

CLICK HERE TO GO TO THE DIGITAL VERSION OF THIS ARTICLE