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: 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: 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;
};