S3 offers our customers substantial experience in optimization. Broad areas of optimization where we are proud of our work include:
Continuous functions have derivatives or partial derivatives and those derivatives can be computed, either symbolically or numerically. When derivatives are available, a variety of "gradient"-based methods can be used to seek extremum states of the system. We have encountered these problems in modeling chemistries, orbital mechanics, and other physical systems. Nature often prefers an optimal state. For instance, soap bubbles form in a way that minimizes surface tension, resulting in surfaces of constant mean curvature [see ref. 12]. To simulate real world systems, we often have to compute those naturally occurring optima and inject those into the simulation. Combinatorial systems arise when we have a finite set of choices at each point in a schedule. To illustrate, say we have a circuit board that needs 1000 holes drilled and the cost of drilling is proportional to the distance that the drill head moves. We need to pick a drilling order for the holes that minimizes the distance that the drill head travels [see ref. 13]. Combinatorial problems also come up in job shop and flow shop operations where we need to schedule work onto machines, often with constraints such as the piece needs to be cut out before its edges can be polished. We have also seen shop scheduling problems in the planning of satellite imagery collection where targets are only in view for a brief period in the satellite's orbit. One of our principal investigators wrote his graduate thesis on an important combinatorial optimization problem [ref. 13]. These problems tend to fall into a difficult computational complexity class (typically NP-Complete) and so one consideration is computation time. In the case of circuit board drilling, where many boards will be drilled, it may be worthwhile to spend a lot of compute time to find a very good solution. If the problem is to produce a one-time schedule for thousands of packages to go on trucks in the morning to assure overnight delivery, there may not be enough time available to compute a really good solution and we have to limit compute time and settle for a solution that is good enough. Constrained optimization problems tend to arise where we need to weigh tradeoffs between different ways to do the same thing (the constraints often involve the availability of the different options). One place where we've faced such a problem--and an excellent example of one--is the optimization of telephone networks where the call traffic varies by hour and the question is how many dedicated circuits to install at a fixed monthly fee, and how many "charge-by-minute-of-use" circuits to install over a large network with many endpoints. We have also worked these problems in metabolic networks [see ref. 1] where the materials for a metabolic process can come from multiple sources. In many cases, our optimization work has required robust solutions where we are confident that the decisions will remain efficient even if the conditions of the operating environment cannot be measured precisely, or they may change between the time we compute a schedule and the time we implement it. As an example of the former, we developed algorithms for allocating military resources that maximizes the likelihood of achieving the commander's goals even when the adversary disrupts our estimates of their positional strength using stealth, decoy, and other deceptive tactics [see refs. 3,4,5,7,8,9,10,11]. Sometimes we need to turn the "knobs" of a system continuously to optimize behavior while the system is in use. The system might be as simple as a motor, or as complex as a joint force military team. The subject area concerned with continuously setting the "knobs" of such a system is known as a "control theory" and the problems are known as "control problems". These problems are particularly difficult when the environment acts intelligently against your control solution. Such problems are "game theoretic", and our knobs have to adjust while an adversary turns his or her knobs to defeat us. One of S3's principal investigators wrote his PhD dissertation on a game theoretic control problem dealing with the allocation of military resources in an uncertain battlefield [ref. 11]. Our work in optimization has employed a wide range of algorithmic techniques ranging from evolutionary programming and genetic algorithms [see ref. 1] to linear program solvers, to conjugate gradient techniques, and game trees [see ref. 2]. Sometimes we have developed the algorithms from the ground up, and sometimes we have used off the shelf tools to help out. S3 Principal Investigator Publications and Proceedings on Optimization Problems
|