HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML

Optimization And JAVA, by Irvin J. Lustig

As Java continues to be used in a wider range of applications, one measure of its progress is in its ability to take on more robust, high-performance computational applications. One of the most demanding areas within commercial software is optimization. Best known as the driving technology for planning and scheduling inside supply chain management applications, optimization involves computational engines fueled by specialized algorithms that crunch through complex business problems to find quick answers that can save businesses enormous amounts of time and money.

Optimization applications have lived in a universe far distant from Java. They've largely been C-, C, and FORTRAN-based - just what you would expect from such sophisticated, computationally demanding software. However, rapid evolutionary forces in both Java and the optimization sector, combined with the relentless need for higher levels of intelligence in commercial software applications, are converging to the point where Java and optimization are no longer mutually exclusive.

Until quite recently Java programmers who wanted to include optimization within their applications needed to write their own Java wrappers around optimization code. Another limiting factor has been the lack of hands-on knowledge of high-end optimization techniques among developers, who often aren't skilled in model development and selecting the best-solving strategy. However, commercial Java Native Interface (JNI) wrappers for optimization code are now emerging, with pure Java-based development solutions imminent. In addition, recent ease-of-use breakthroughs in the form of tools for modeling and embedding optimization software are bringing this technology closer to the mainstream.

For Java developers, having access to optimization technology offers the potential for smarter applications that deliver greater efficiencies, not just in planning and scheduling - the bedrock of optimization - but in emerging areas such as customer-facing software for solutions such as Web self-service. This article introduces optimization to the Java programming community: what it is, what it isn't, and how it can be an invaluable tool for creating a wide range of applications, particularly for the Web. Java developers should come away from this article with a better understanding of optimization and how they might leverage this powerful and flexible technology in their own applications.

Definition of Optimization
Modern-day optimization is defined by the application of mathematical and constraint programming. However, the ideas of optimization go back to Isaac Newton and calculus. Every calculus student learns how to find the minimum value of a function of variables by taking the derivative and solving a set of equations for the answer.

Today, optimization methods represent a set of techniques for finding the best usage of limited resources. The best usage could be minimum cost, maximum profit, highest level of service, or quickest delivery time. The types of resources that may be limited are people, vehicles, equipment, time, supplies, and money. Optimization is applied to manufacturing systems, telecommunication networks, asset allocation, and other business processes where it's possible to come up with a mathematical model for the underlying business processes. The successful application of optimization has the following features:

  1. Represents decisions by using a set of decision variables in which the possible values of the decision variables are known
  2. States a set of constraints that the decision variables must satisfy
  3. States an objective function of the decision variables
Given this broad description, a variety of powerful algorithms have been developed that are able to determine solutions to such problems. With the advent of improved computational hardware power combined with the improvements in the underlying algorithms for solving optimization problems, it's now possible to solve problems in seconds on desktop computers that only 10 years ago required weeks of computing time. Because of this, the range of possible applications of optimization has widened.

Optimization problems are inherently difficult to solve because the number of possible solutions to any particular problem is enormous. The most classic optimization problem is the traveling salesman problem: given a set of cities and starting at a home city, determine the shortest path that would enable the salesman to visit all the cities without visiting any city more than once, then returning home at the end of the tour. For a problem with 1,000 cities, there are over 102,567 possible solutions to consider! Sophisticated optimization algorithms are able to efficiently solve similar practical problems, despite the large number of potential solutions.

Optimization Examples
Some examples help illustrate the kinds of problems that can be solved with optimization technology. For each of these problems the concepts of "best usage," stated as an objective, and "limited resource," reflected in constraints, will be described.

  • An airline has a schedule of flights and a fleet of different aircraft types. The organization needs to determine the assignment of the aircraft to the different flights so as to maximize profit, while making sure that aircraft are scheduled for maintenance, have sufficient turnaround time between flights, and anticipated demand is met. Here, the "best usage" is the profit, as measured by the expected revenue obtained by assigning a particular aircraft type to a particular flight, less the cost of purchasing and operating enough aircraft to fly the entire schedule. The limited resources are the planes and the limits imposed by the airline's schedule. Optimization technology is used to determine the best assignment.

  • An automobile manufacturer needs to sequence cars through a paint shop. Each car is painted a certain color. Each time the paint color is changed, an expensive paint purging operation must occur. The goal is to reduce costs and increase throughput by reducing the number of purges. Here the limited resources are the paint shop and the space allocated for cars waiting to be painted, and the objective is to find the best usage of the shop. Optimization is applied to find a sequence of cars that minimizes the number of times the paint system must be purged by grouping cars of the same color together and respecting the availability of the limited size of the waiting area.

  • A consumer desires to obtain a home equity loan. Each consumer may have different objectives, such as minimizing payments, reducing overall debt, or maximizing the cash available from his or her home. At the same time, a bank has limits on the type of loan it's willing to approve. Optimization allows the bank to offer the loan best tailored for the consumer's needs by searching among all the possible loan configurations.

    Optimization Technologies
    While the foundations of mathematical optimization are found in calculus, the age of modern optimization began with the discovery of the simplex method for linear programming by George Dantzig in 1947, which led to the development of the fields of operations research and mathematical programming. Subsequently, developments in the artificial intelligence community led to the emergence of constraint programming as a technique that could be used to solve optimization problems. Today, numerous companies solve optimization problems using both techniques.

    Mathematical Programming
    Many optimization problems can be stated using decision variables that are real-valued, combined with objective functions that are linear and constraints that are linear inequalities. Such problems are known as linear programs. Here the word program refers to the original statement of the problem by Dantzig as a programming problem, where the problems Dantzig studied involved finding the best activities program for achieving a desired goal. If you restrict some or all of the decision variables to be integer valued, the problem is then an integer program.

    Linear and integer programming are the foundations of the field of mathematical programming and are taught in many universities in operations research and industrial engineering departments, as well as in quantitative courses in many MBA programs. A linear program can be represented using numerical matrices and vectors. Figure 1 illustrates the algebraic and matrix-vector forms of a linear program.

    Figure 1
    Figure 1:  A linear program

    In general, mathematical programming technologies are used for long-range planning applications. They're one of the keys behind the success and growth of supply chain management applications. Mathematical programming techniques are also used by all the major airlines for fleet assignment and crew scheduling. Telecommunication companies use mathematical programming techniques to optimally design their networks. The applications' growth has been driven by the improvement in algorithms and hardware so that linear and integer programs are solved by computationally intensive algorithms in a reasonable amount of time.

    The underlying algorithms used to solve linear and integer programs require a substantial amount of floating point computation. Efficient implementations take advantage of the underlying processor and cache architectures, as well as compilers that can produce code that's efficient for a particular class of hardware. Near term, pure Java implementations of these algorithms won't deliver the required performance for all kinds of optimization applications. As an initial remedy, it's now possible to obtain JNI wrappers around the implementations of these algorithms, which allows Java developers to develop in Java while achieving the performance delivered by the algorithms.

    Constraint Programming
    Constraint programming has its roots in the research of the artificial intelligence community. Here, the word programming refers to a particular methodology for doing computer programming. To apply constraint programming a specialized programming language is required, or special libraries built into a mainstream programming language can be used. Abstractly speaking, a programmer lists variables of a computer program along with their domains of allowable values. Then, constraints are listed that the variables must satisfy. As opposed to linear programming, they can be in any form that the underlying constraint programming language allows.

    The final step in applying constraint programming is to write a search strategy in the programming language indicating how the variables should be modified in order to find values of the variables that satisfy the constraints and, optionally, optimize an objective function.

    Sophisticated constraint propagation and domain reduction algorithms are used to process each constraint type so as to make the overall search strategy efficient. Listing 1 illustrates an example of a constraint program for coloring a map in the optimization programming language (OPL). The decision variables are represented by the array color, where for each country a specific color must be chosen. The constraints indicate which countries can't have the same color.

    Recently, constraint programming has been successfully applied to optimization problems that appear in more operational and tactical applications, where real-time answers to problems are required and mathematical programming techniques are insufficient. Typically, these problems involve logical constraints on integer variables, which can be processed efficiently by a constraint programming engine.

    Constraint programming has been successfully applied to scheduling, sequencing, and configuration problems. In supply chain management applications, it's used to determine the schedule of how products should be manufactured on a limited number of machines. The auto paint shop application mentioned earlier is solved using constraint programming techniques.

    Finally, the loan configuration problem represents another successful application of constraint programming due to its ability to efficiently process the complex underwriting constraints that describe the loans in order to search for the best loan configuration for a customer.

    Modeling Languages
    A model of the underlying processes must first be built to successfully apply optimization techniques to solving business problems. In mathematical programming this has typically been done by writing software to generate the matrices representing linear and integer programming. More recently, specialized mathematical programming modeling languages have been developed that provide the capability to succinctly represent a mathematical programming problem. The initial development of these languages created stand-alone tools that would allow users to enter problems in the modeling language, integrate external data, and then solve the resulting program. Today, these languages are now provided in the form of libraries that allow easy integration of mathematical programming models into large-scale applications.

    Constraint programming development has occurred in two directions. One was the development of special purpose languages for applying constraint programming techniques. Like mathematical programming languages, the specialized constraint programming languages were created as stand-alone tools and are now available as object libraries. The second direction is the creation of specialized constraint programming libraries on top of existing programming languages such as C and Java.

    Java-constraint programming tools are still in a state of development. The next year should see the introduction of pure Java constraint programming engines.

    The optimization programming language is unique in that it provides a language that enables the use of both mathematical and constraint programming techniques. An example of a linear program written in OPL is shown in Listing 2. The data is represented by the sets Products and Resources, and the arrays product and capacity. The decision variables are the arrays inside and outside. The modeling language representation directly maps to the matrix/vector notation discussed earlier.

    Java Tools for Optimization
    Optimization has been remote to the Java community mainly due to the lack of effective tools to utilize it. Affecting the technology's wider spread into the Java community has been the inherently slower performance of the Java platforms that made fully leveraging the technology difficult. But things are changing. New technology advances and new features in optimization software mean easier access for Java programmers and better performance. Complementing these advances and making it relevant are the performance improvements to the Java platforms that help minimize the performance hit for optimization applications.

    As mentioned above, traditional optimization as represented by mathematical programming applications have yet to be offered directly on the Java platform due to performance considerations. Today, Java interfaces to existing engines are now available, providing the benefits of a Java interface to a high-performance computational engine. If demand emerges for pure Java versions of mathematical programming tools, it's likely such solutions will be developed. Fortunately, the speed of the underlying engines has improved to a point where "Java" optimization can be used in real-time applications. In particular, marketplace auctions on the Web represent an excellent application of this technology.

    An interesting development for both mathematical and constraint programming is the introduction of ILOG OPL Studio 3.5, which allows models represented in OPL to be embedded inside Java programs. A Java developer assembles the required inputs for an OPL model and passes the data and the model description to the OPL component libraries, which are supplied with JNI wrappers. The libraries then interpret the model and the data and solve the resulting optimization problem. The optimal values of the decision variables can then be obtained by querying methods in the OPL component libraries.

    The advantage of using JNI in this case is that the underlying performance of the optimization engine on different hardware platforms is preserved. Furthermore, the process of developing an optimization model, which requires expertise in understanding the underlying business processes, is separated from the process of integrating the optimization model into a Java program.

    On the other hand, Java versions of constraint programming tools can be useful in a new class of Web-driven applications that are based on solving configuration problems, such as the loan configuration problem described earlier. In fact, the first versions of these tools will be available later this year. To illustrate, let's consider the problem of configuring an automobile that's subject to the requirements of a consumer and the constraints determined by the automobile manufacturer. The consumer may want the lowest-priced car with specific features. The manufacturer may have constraints that indicate the compatibility of certain options. For example, certain models may not be available with a sunroof or a particular engine. Constraint programming can be used to represent the possibility of different choices and the constraints on these choices.

    On the Web a form can be used to represent the different choices that are available to the consumer for configuring his or her automobile. After the consumer makes a choice, the constraint programming engine can then eliminate incompatible choices. Once a set of choices is made by the consumer, the choices left open by the user can then be considered for optimization by the constraint programming engine, and the lowest-priced car subject to the consumer's choices and the manufacturer's constraints can be determined.

    For this application a Java-based constraint engine is required, and it can be easily integrated within the J2EE framework. Figure 2 illustrates the design of such an application. To describe a configuration problem at design time, a business product model and configuration language are used with a builder, which generates an XML representation. This is then used at runtime.

    figure 2
    Figure 2:  Java-based configuration tool

    Constraint programming is used inside the configuration engine. Because the state of the current configuration must be represented and updated quickly, using a non-Java engine will be problematic. The performance improvements in the Java 2 framework should allow this kind of application to execute efficiently within a Web-based environment.

    Conclusion
    As more real-time decisions are required by businesses, optimization applications will appear on the Web and integration with Java will be a requirement. Java programmers are already creating JNI interfaces to existing optimization engines to allow access to Java programmers. Whether it's by using JNI interfaces to high-performance engines or by using pure Java applications, a growth of such applications should occur within the next couple of years. Fueling this growth will be the improvements in computer hardware and the underlying algorithms for optimization, allowing businesses to reduce costs and increase profits. The opportunities are unlimited.

    Author Bio
    Dr. Irvin Lustig is ILOG's optimization evangelist responsible for education and marketing initiatives around optimization. He received his PhD in operations research from Stanford University and a ScB in applied mathematics/computer science from Brown University. He's also the author of more than 30 scientific research papers. He was contacted at: [email protected]

    	
    
    
    Listing 1
    
    
    enum Country {Belgium,Denmark,France,
                  Germany,Netherlands,Luxembourg};
    enum Colors {blue,red,yellow,gray};
    var Colors color[Country];
    solve {
         color[France] <> color[Belgium];
         color[France] <> color[Luxembourg];
         color[France] <> color[Germany];
         color[Luxembourg] <> color[Germany];
         color[Luxembourg] <> color[Belgium];
         color[Belgium] <> color[Netherlands];
         color[Belgium] <> color[Germany];
         color[Germany] <> color[Netherlands];
         color[Germany] <> color[Denmark];
    
    
    
    Listing 2 enum Products ...; enum Resources ...;
    
    
    struct ProductData {
       float demand;
       float insideCost;
       float outsideCost;
       float consumption[Resources];
    };
    
    
    ProductData product[Products] = ...;
    float capacity[Resources] = ...;
    
    
    var float inside[Products];
    var float outside[Products];
    
    
    minimize
       sum(p in Products) (product[p].insideCost*inside[p] 
                           product[p].outsideCost*outside[p])
    subject to {
       forall(r in Resources)
          sum(p in Products) product[p].consumption[r] * inside[p]
                 <= capacity[r];
    
    
       forall(p in Products)
          inside[p] outside[p] >= product[p].demand;
    };
    
    
      
     
    

    All Rights Reserved
    Copyright ©  2004 SYS-CON Media, Inc.
      E-mail: [email protected]

    Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.