Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink

DDJ: Joining us today is Jean Francois Abramatic, ILOG's chief product officer. Jean Francois is responsible for the company's product vision and strategy, product design and development, and product marketing and management.

Jean Francois, when we usually think about "optimization," it is in terms of making applications run more efficently by tweaking algorithms or even resorting to, say, assembler to optimize program hotspots. However, ILOG seems to have a different spin on the term "optimization." Can you briefly explain your take?

JFA: "Optimization" is used in a broad range of software activities, and to confine it to a narrow definition is not possible. Your use of the word relates to one such use. Our use of the same word relates to the use of mathematics to find the best possible decision in a very complex business situation.

Optimization is often associated with enhancing efficiency, when one needs to pick the best among an exponenetial number of choices. When profitability rides on picking the best among an exponential number of choices, optimization is the only technology that can reliably identify the best possible business action.

To illustrate how far we've come in applying optimization, consider manufacturing. Back in the '80s ILOG CPLEX -- that's our optimization engine -- earned its spurs in the petroleum industry, helping plan and schedule refinery operations. Over time, optimization became essential technology for running other heavy manufacturing operations such as steel, automobiles, and paper.

Today, Fab PowerOps (FPO) from ILOG uses the same technology to schedule key processes in IBM's 300mm fab in East Fishkill, New York, arguably among the most advanced manufacturing environments in the world. I could tell you similar stories of pervasiveness in transportation, logistics, hospitality, and finance.

DDJ: But you also get right down into issues involved in optimizing the likes of Linear Programs, Quadratic Programs, and Mixed Integer Programs. Why do you tackle specific topics such as these?

JFA: Optimization problems come in many forms but there are two distinct ways to approach solving them. Our portfolio spans Math Programming and Constraint Programming, both complimentary technologies allowing us to cover a broad range of applications.

Since we started shipping our first software components -- written in Lisp, by the way -- we have focused on technology leadership. In 1992 we brought to market the first Constraint Programming (CP) engine written entirely in C++. In 1997 SAP began to embed our CP technology and we created a joint development partnership. Around that time we also noticed many of our customers also using Linear and Mixed Integer Programming (LP-MIP) to solve really tough, really large problems in supply chain management and logistics. The following year, we acquired the CPLEX LP-MIP business. By 2000 most major supply chain vendors sourced ILOG for optimization. When we noticed that the leaders in financial engineering, companies such as Financial Engines and Ameriprise, began designing customer-facing apps using ILOG CPLEX, we extended it to include Quadratic Programming (QP). Today, we continue to use feedback from our 2500+ customers to map our technology agenda.

DDJ: By "Mathematical Programming", what do you mean?

JFA: "Mathematical Programming" is a branch of Applied Mathematics. It finds mathematical optimality by applying equations to a large search space of potential solutions. Algebra and analytical geometry form the core, but they are assisted by a large number of algorithms and heuristics (rules of thumb) that take advantage of concepts and methods developed in both mathematics and computer science over the past 20 years.

Linear equations are the dominant language of optimization, which is why the term "Linear Programming" (LP) is used interchangeably when talking about MP; however, some models also require the use of quadratic equations (ax2 + bx + c = 0) which are not linear. More importantly, most business problems can only be solved if you can adjust all or some of the solution recommendations to whole numbers -- because in the real world, most machines, people and activities come in wholenumbers. These two extensions may sound like simple adjustments, but it has actually taken over 50 years of continuous effort for LP to fully support Quadratic Programming (QP) and Mixed Integer Programming (MIP or MIQP). Given the number of constraints that need to be satisfied, the decisions that need to be made, and the goals that need to be balanced, optimization as we know it today would not be possible without modern computing power. With today's computing power, it is now possible to execute millions of calculations and generate thousands of trial solutions on the road to finding the optimal solution.

DDJ: And "Constraint Programming"?

JFA: Okay, the second major technology for optimization is Constraint Programming, which is a branch of computer science (also known as "Logic Programming") with roots in the Artificial Intelligence (AI) and Expert System efforts of the 1980s and the move to object-oriented approaches to software development in the 1990s. Its approach to optimization is completely different from the approach of MP.

Simply put, CP finds feasible solutions by rapidly eliminating possibilities, zeroing in on feasible combinations of resource assignments and activities -- when there are too many possible combinations or too many individual constraints regarding sequence and timing for MP to find a solution in an acceptable timeframe. This is sometimes referred to as coping with the "combinatorial explosion" of possibilities.

Constraint Programming approaches optimality via a continuous improvement process based on the systematic comparison of new solutions to a base feasible solution. As a result, CP can find good solutions to large, intricate scheduling and routing problems in minutes when MP would take hours or even days, assuming that an MP model could even find a solution. Note that when you run either a CP or MP model, you can instruct the solving engine to give you its best result after a set time limit -- often the extra time the engine spends searching is only gaining you a small additional improvement. The easiest way to understand the sort of problem CP technology is good at solving is to think of a Gantt chart. It is a time-honored way to visualize "what is being done where" on a project -- a complete picture of all of the available resources and all of the necessary activities done using the available resources over a period of time. It is no surprise that when there are many interdependencies between activities and numerous operating constraints, it can be very difficult to find a feasible solution, much less an optimal one. Add the pursuit and balancing of multiple goals, and it becomes even more difficult. CP technology was designed to handle these tough scheduling problems, finding feasibility first and then polishing the solution to near optimality.

DDJ: What other kinds of problems along these lines is your R&D staff working to solve?

JFA: On the optimization component side, when we ask our customers what they need more of, they insist on the same thing -- more speed! Businesses interested in squeezing out the last ounce of profit from their decision-making are building more and more detailed models. In turn, this demand forces our R&D to a very steep performance gradient. Do you know that in the last 15 years, CPLEX performance has risen three times faster than Intel multi-processor performance? Combined with hardware improvements, that means that in the last 10-12 years ILOG users have seen effective speed-ups of over 2 million times!

The systems need to be robust too. The applications are so diverse, the products need to be diverse. To be versatile we need to be robust, because the diverse application that the product can be used for. To widen the outreach of product, need to improve performance to solve problems you could not before, and faster. More and more industries can use it in so many ways so robust.

Over the decades, ILOG professional services have built literally hundreds of optimization-based custom applications. We leveraged that experience to develop an entire new type of optimization tool: ILOG Optimization Decision Manager (ODM). ODM breaks down the traditional wall between modelers (typically, optimization experts) and developers (typically, IT-oriented software engineers and database gurus), enabling total project team integration. ODM is really a development framework, not a classic optimization component, so it's somewhat of a new direction for our R&D folks.

Now, as you well know, pre-built applications cannot serve every situation. Independent system vendors and enterprise-hosted developers remain a high-focus activity for us. Recognizing the complexity of building custom optimization-based applications, two years ago we began to take a fresh look at simplifying the software development process.

Let me take a step back, to our view of the market for optimization technology. We see two opportunities, both influenced by SOA adoption and the RFID data explosion. The first trend is that buyers of high-value supply chain applications now consider optimization technology a must-have checklist item. They cut through vendor spin to figure out if enterprise processes are, in fact, being optimized. Since the supply chain management application space has notable gaps in terms of optimization, this trend represents an opportunity for ILOG to help in the application space. We believe ILOG R&D is unique in having the skill, the industry experience and the technology to create planning and scheduling applications at this level of detail and complexity. In addition to FPO, that I mentioned previously, we have also recently released Plant PowerOps for integrated planning and scheduling in process industries, and Transport PowerOps, for truck fleet planning. As we integrate R&D from our most recent acquisition, LogicTools, expect us to announce additional offerings in supply chain management.

DDJ: Can you give me some examples of how customers have used it in unique ways?

JFA: It is a testament to the ubiquity and flexibility of optimization that after over 17 years of using our tools, our customers continue to delight us. Since we've already covered supply chain, I'll pick applications in two other areas.

An interesting application from media is the airtime sales system at NBC. They use ILOG optimization to navigate a complex blend of stringent legal and regulatory conditions, satisfy the demanding business requirements of UK's highly competitive media market, ensure fairness and evenness towards its customer base, and make money!

Another unique example is the DARPA-funded work at MIT, where an F-15 fighter pilot guided a T-33 "drone" using natural language commands. Relying on ILOG CPLEX, the 2004 flight tests represent the first time a manned aircraft used a Mixed-Integer Programming-based trajectory calculator to control another unmanned aircraft. For a technology geek, what could be cooler?!

DDJ: Thanks Jean Francois. Is there a web site readers can go to for more information on these topics?

JFA: Yes, they can take a look at the optimization section of our web site.

RELATED ARTICLES Silverlight 2 Ready for Release Are Server Controls Still Useful? NIST Releases Guide to Bluetooth Security Microsoft Kicks Off Embedded Device Competition Automatic Photo Tagging and Visual Image Search		TOP 5 ARTICLES No Top Articles.