Technical ArticlesNew Age of Optimization ApplicationsIncreased computing speed, advances in algorithms and emphasis on modeling boost production for O.R. professionals and business users alike. Carol Tretkoff, Principal Technical Account Manager, and Irvin Lustig, Director, ILOG Direct Channel, ILOG, Inc. We are moving to a day where managers want to do real-time adjustments to their plans and schedules, as well as interactively perform complex analysis in real-time on a desktop computer. In particular, these managers want to simulate different scenarios in order to understand how the solution to a problem is affected by varying the inputs. After all, we live in an uncertain world, where only change is given, and plans need to be robust. Due to the increase in computing speed, better algorithms and modeling tools that make application development possible in a short amount of time, this has become a reality and should help usher in a new age of optimization applications. Linear, integer and quadratic programming algorithms provide an excellent example of operations research developments that deliver value to businesses and government on a daily basis. As mentioned above, there are many applications of these optimization technologies across a wide variety of industries. Traditional applications using linear programming technology in the supply chain arena include supply chain planning, production planning and production scheduling. In the airline industry, integer programming applications include crew scheduling and fleet assignment, and in the financial industry, portfolio optimization has been a staple based on quadratic programming. What these applications have in common is that after the modeling work is complete and a user interface is created that allows a business user to benefit from optimization technology, the software application is run periodically and the results are used to run the business. The data and perhaps some parameter settings could be changed, but essentially, the application would be run whenever needed in a batch or production mode. Real-Time ApplicationsToday, real-time scheduling and real-time adjustments are very important in a number of industries. As an example, the arrival of concrete trucks at a construction site is very time sensitive due to the fact that the concrete dries rather quickly, and if the concrete dries in the truck before it can be poured, it becomes useless. If multiple trucks are being scheduled, they need to arrive at the appropriate intervals so that they can be unloaded and so that room is made for the next truck. Furthermore, orders at additional sites need to be taken into account in real time. This application was described by Karla Hoffman (2006) at the INFORMS Practice meeting. Semiconductor manufacturing is another instance where real-time, or near real-time scheduling is needed in order to take into account ideal production quantities, as well as operational constraints such as machine configurations, bottlenecks and business objectives. The goal is for the application to deliver a recommended sequence of lots for each machine for the current shift and reschedule as needed throughout the shift, based on incoming orders, as well as the unpredictable times required for each step in the fabrication process. It is the frequent rescheduling that allows an even greater improvement in overall productivity of the plant. This is particularly important due to the high cost and value associated with semiconductor wafers, as well as the high cost of building a fab for making the wafers. Getting more wafers produced in an existing fab through better scheduling thus becomes very important. This application of optimization is part of ILOG Fab PowerOps and has been deployed at a leading semiconductor manufacturer. In 2001, the team from the General Electric Research and Development Center (GE-RDC) were finalists in the Franz Edelman Competition for their work in applying optimization to increase advertising revenues and improve productivity at NBC. The group from GE-RDC developed a system that allowed NBC to more effectively sell advertising spots. An existing laborious manual process that was used to generate sales proposals was replaced with this optimization-based system, allowing plans to be generated in real time. These applications illustrate how optimization is applied to solve real-time decision problems. This is possible because of computational and algorithmic advances. Improvements over the Last 20 YearsIn the past 20 years, there have been significant advances in computational power, as well as algorithmic improvements for linear programming and mixed integer programming. Considering a 15-year time period, Robert Bixby in the article, "Solving Real-World Linear Programs: A Decade And More Of Progress," reported a speedup of a factor of 800 due to hardware improvements that can be extrapolated to a factor of 1,600 using today's hardware. He also reported a speedup of a factor of 2,400 over that same time period due to innovations in linear programming algorithm implementation. These improvements have made it possible for operations research professionals to rethink what can be accomplished not only in terms of the size and complexity of problems that can be solved, but also in terms of how the results can be effectively managed by the business user. Parallel to the improvements mentioned above in computer hardware and algorithmic implementations, there has been an increased use of algebraic modeling languages, such as AMPL, GAMS, MPL and OPL. These modeling languages are now in a position to be extended so that complete applications that meet the needs of the business user can be developed with very little effort on the part of the operations research professional. In the past the O.R. professional was responsible for designing the model and producing the results in a report. Thus, the O.R. person worked as business consultant, technical analyst and software developer. The next step was to take these systems and put them into the hands of the business users who ran them in batch mode, often overnight. Now, a new set of technologies has emerged that make it easy for the O.R. professional to create optimization applications that allow the business user to do the required analysis in complex planning and scheduling problems. This analysis can now be done in real time, meeting the critical needs of the business user. Applications for the Business UserYet, another class of applications is now possible because of these advances. These applications allow a deeper understanding of the optimization results, because the business user can now spend as much time as needed looking at multiple scenarios before committing the business to a specific path. In particular, the business user can use multiple scenarios to do what-if analysis. Some of the tradeoffs he can look at include seeing how placing different weights on various key performance indicators (KPIs) changes the solution. For example, one business user might be more concerned about customer satisfaction while another may be more concerned about the use of fuel. These may be competing objectives, and the business users may need to see the tradeoff between higher customer satisfaction and more fuel usage. The business user would also be interested in sensitivity analysis and how robust his solution might be under various changes in business conditions, such as fuel costs or increased demand. There may also be tradeoffs in terms of constraints. The constraint that workers never work overtime on Sunday may need to be relaxed if customer orders are going to be met in time for a major holiday. In the new age of optimization applications, all of this is possible for the business user, and an easy-to-use interface can be made that allows the business user to analyze these tradeoffs by comparing the results from optimizing multiple scenarios. In traditional applications, allowing business users to modify constraints, perform KPI tradeoff analysis and change other key parameters required a substantial development effort, typically customized for the specific application. Providing this capability required the O.R. modeler to design this capability into his optimization model. This is no longer necessary. New tools allow a modeler to simply develop the model and then easily create an application that will handle scenarios, constraint relaxation, the ability to change the weights on the KPIs and graphical displays of the input and the results with a few clicks of the mouse. The increased speed of computers, the advances in algorithms and the emphasis on modeling in the past several decades has resulted in the O.R. professional and the business user being able to accomplish much more in terms of problems that can be solved, ROI that can be generated and business analysis that can be done. New tools are available that make it easy to create powerful applications from a modeling language specification. These tools will lead us to the new age of optimization applications. An Application FrameworkAs an example of what can now be accomplished in terms of optimization given the recent advances in computing speed, algorithms and modeling languages, consider a new product from ILOG called Optimization Decision Manager (ODM) that can be used to develop an application directly from a model described by the modeling language OPL. ODM provides an application framework that puts the power of optimization into the hands of the business user by allowing this business user to change constraints, KPIs and other key parameters, as well as fix the values of some of the results and rerun a new scenario of the application to see how this affects the solution. A key aspect of the application framework is the integration with a modeling language. The O.R. developer can simply create an application directly from a model using a "wizard" that creates a default application. This application can then easily be customized in a point-and-click editor so that the application contains business-friendly labels for input values, objectives and constraints. To illustrate the power of creating an application using an application framework, we will use an example from supply chain planning, where an application is created that allows the business user to determine answers to the following questions:
In this case there are a number of competing objectives of interest to the business user. These are:
These can be seen in the "Goals" section part of the screen that is shown in Figure 1. 
Figure 1: Goals section of screen. Since the model has actually been solved, the values for each of the KPIs or goals has been filled in by the application. In the screen shot, all of the goals/KPIs are active. Should the business user decide that the fixed distribution center cost is not relevant since the company plans to keep all of the distribution centers open anyway, he can simply uncheck this goal. Also note that the importance factor in the example below is always 1. The user might choose to make all of the goals that relate to transportation have a higher priority or importance and then compare the results. This might be particularly interesting to the user when the price of fuel is rising. Figure 2 demonstrates the Scenario Explorer. For each scenario, one can view the goals (objectives), requirements (constraints), input data and solution. Note the list of tables in the Solution folder that can be viewed. These tables can be set up to view the answers in a way that is convenient for the business user. Similarly, charts and graphs can be set up to view the output with a few additional mouse clicks. 
Figure 2: Scenario Explorer. After the model has been solved, the map, displayed by clicking on the "Map" in the Scenario Explorer, and shown in Figure 3, displays the routing decisions of the optimal solution, as well as which distribution centers to open. 
Figure 3: Map for supply chain application. Continuing to describe what we could do in terms of analysis of the same example, let's assume that we wanted to constrain the DC Fixed Cost to $3,000,000 in a new scenario. This could be done by filling in 3000000 in the Constrain max field that you can see in Figure 4. After solving the new scenario, one could view the differences in the results as they would appear highlighted. 
Figure 3: Map for supply chain application. Note also in Figure 2 that there is a folder labeled Rules on the left side, and it has been opened to indicate that there are three types of rules associated with this application: Production Rules, Distribution Rules and Network Rules. One of the rules that could be set up by the model developer is a rule that allowed the user to force certain products to be produced by particular plants. Now, the modeler might be aware that if this rule is mandatory, then the problem might become infeasible. The modeler can specify that the constraint on satisfying all customer orders is not mandatory, and the system will then allow this constraint to be relaxed in order to satisfy the user's desire to force certain products to be produced by particular plants. Extrapolating to the general situation, the modeler is able to indicate which constraints are hard and which are soft so that the business user almost always gets a solution, albeit one with some of the constraints violated as in this case where all of the customer demand might not be satisfied. The ODM system automatically relaxes constraints according to their priority order. The power of this kind of application opens up many new opportunities for business users to understand the power of optimization. Carol Tretkoff is a principal technical account manager specializing in optimization at ILOG, Inc. Source: ORMS Today, December 2006 References1. Bixby, R.E, 2002, "Solving Real-World Linear Programs: A Decade And More Of Progress," Operations Research, Vol. 50, No. 1, pp. 3-15. 2. Hoffman, K., 2006, "The Dance of the Thirty-Ton Trucks: Demand Dispatching in a Dynamic Environment," presentation, INFORMS Practice Meeting, May 2006. Available at http://iris.gmu.edu/~khoffman/DAC_Stuff/Dance_of_the_30_ton_trucks_Practice2006.pdf |
|---|