Optimization Technology White Paper

OPTIMIZATION TECHNOLOGY WHITE PAPER
A comparative study of optimization techniques

ILOG, Inc. 1901 Landings Drive Mountain View, California 94043 1-800-FOR-ILOG www.ilog.com

© 1997, ILOG, Inc. All rights reserved. All trademarks and registered trademarks are the property of their respective holders.

2

Table of Contents

Introduction_______________________________________________4 Why optimize? ____________________________________________ 4 When to optimize? _________________________________________ 4 What optimization method to use? _____________________________ 5 Optimization ______________________________________________ 6 Problem formulation________________________________________ 6 Decision variables ________________________________________ 6 Objective function________________________________________ 7 Constraint functions ______________________________________ 7 Solution approaches ________________________________________ 8 Heuristics ________________________________________________ 8 Optimization techniques_____________________________________ 8 Rule based systems _______________________________________ 8 Linear and integer programming_____________________________ 9 Domain reduction and constraint propagation___________________ 9 Genetic algorithms_______________________________________ 10 Simulated annealing _____________________________________ 11 Examples ________________________________________________ 13 The mixing problem _______________________________________ 13 The scheduling problem ____________________________________ 15 Theresource allocation problem _____________________________ 16 The design problem _______________________________________ 20 Conclusion _______________________________________________ 21

3

Introduction
Why optimize?
The search for improved profits never ends. Many of the obvious areas for increased profit have been exhausted during the past decade. Both data gathering and management have beenautomated, even by smaller firms; optimization, however, can be used to extract detailed information from a system to yield new business opportunities. Optimization can fine tune operations to create further improvements in process efficiency. Systems based on optimization tools can promote flexibility so systems remain efficient under many scenarios. Many companies are now focusing on deliveringnew, custom designed services that rely on optimization. A delivery company may want to provide up to the minute information about the delivery times of customers’ packages. This information can be made available for individual packages by means of data from the delivery network and optimization tools. The existence of repetitive processes in many operations means improving the efficiency of asingle process, even by small amounts, can lead to substantial gains for the overall operation. Many production assembly lines have already been automated for improved efficiency, but further gains may be achieved by considering the order in which products are sent along the line. The gain for each product may be minuscule, but the overall gain for the assembly system increases with each product sentalong the line. When the magnitude of the operation is large, the overall gain can be very large. Systems that adapt quickly to changes in a process are of greater value than those that do not. Reacting to a change quickly allows a system to maintain efficiency. Airport gate allocation is dependent on flight arrival and departure times. If a flight is delayed, the most efficient gate allocationmay need to be changed. Finding efficient new allocations quickly lets gate allocations be implemented on the fly, which lets the allocation system run as efficiently as the information flow allows. Many companies are looking to the future with ideas that initially present complex problems. Optimization tools can transform many of these ideas into reality. New technology is opening up satellite...