S3 Home‎ > ‎Our Work‎ > ‎

Optimization

S3 offers our customers substantial experience in optimization. Broad areas of optimization where we are proud of our work include:

  • Optimization of Continuous Functions: Physical models provide rich example problems.
  • Combinatorial Optimization: Shop scheduling and routing problems for example.
  • Constrained Optimization: Resource planning is an example. 
  • Robust Solutions: Decisions that are only minimally sensitive to changes in the operating environment.
  • Control Solutions: Systems where we need to continuously adjust the knobs to maintain an efficient, desired, or optimal state.

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
  1. "A Retrodiction Approach Using a Genetic Algorithm to Analyze the Mycolic Acid Pathway", Jamie Lawson, Rajdeep Singh, Steven Phung, Michael Hultner, Ross Henderson, submitted to PLoS Biology, 2012.
  2. Quantifying the security of physical facilities: a game theoretic framework", Rajdeep Singh, Kartik Ariyur, Allerton Conference, 2012.
  3. “Deception Robust Control for Automated Cyber Defense Resource Allocation”, Jamie Lawson, Rajdeep Singh, Michael Hultner, Kartik Ariyur, The First IEEEConference on Cognitive Methods in Situation Awareness and Decision Support, 2011.
  4. ”Deception Robust Control for a Self-Organizing Network of Unattended Sensors”, Rajdeep Singh and Jamie Lawson, Proceedings of the 14th World Multi-Conference on Systemics, Cybernetics and Informatics: WM-SCI 2010.
  5. "Hypothesis-driven Information Fusion in Adverarial, Deceptive Environments", Alexander Kott, William M. McEneaney, Rajdeep Singh, Wes Milks, Elsevier Journal of Information Fusion 2010.
  6. “A Self-Organizing System for Regulating Dataflow Through Highly Bandwidth Constrained Wireless Networks”, Jamie Lawson, Richard Dillon, Dennis Hsu, Proceedings of the International Conference on Wireless Networks, WORLDCOMP Las Vegas, NV, 2008 (also served as Conference Session Chair).
  7.  “Robustness Against Deception in Unmanned Vehicle Decision Making”, W. McEneaney and R. Singh, Proc. 3rd Intl. Workshop on Multi-Agent Robotic Systems, Angers, France, 2007.
  8. “A Computationally-Feasible Algorithm for Estimation of Opponent Strength in Urban Combat", William M. McEneaney, Rajdeep Singh, Proc. 12th ICCRTS, Newport, 2007.
  9. "Robustness Against Deception", Adversarial Reasoning:Computational Approaches to Reading the Opponent's Mind, W.M. McEneaney, R. Singh, Chapman and Hall/CRC Press, 2007.
  10. "Deception-Enabled Control Theory for Stochastic Games with One-Sided Information", William M. McEneaney, Rajdeep Singh, Proc. Math. Theory of Networks and Systems, Kyoto, Japan, 2006.
  11. "Deception in two-player zero-sum stochastic games: Theory and application to warfare games", University of California at San Diego, thesis, 2006.
  12. "On the Shapes of Completely Wetted Two-Dimensional Powder Compacts for Applications to Sintering", J. C. Schon, R. Frost, M. Chu, J. Lawson and P. Salamon, Journal of Applied Physics, 71, 3266 (1992).
  13. Fast Heuristics for the Euclidean Traveling Salesman Problem, Jamie R. Lawson, San Diego State University Press, thesis, 1991.