Mathematics of Information Technology and Complex Systems

Project Highlights
Team Members
Partner Organizations
Seminar Series


We envisage two approaches for formulating the optimization models: The first consists of developing integer programming models based  on a single criterion and than on multiple criteria. This is a natural approach since a route plan is based on the idea of whether a given geographical area (cell) belongs or not to the path. The second approach will be based on constraint programming. This approach allows a clean separation between the statement of the problem (the variables and the constraints) and the resolution algorithms. In particular, it will allow us to search for operationally feasible plans and take into account logical constraints in addition to numerical constraints. The challenges we face are three-fold due to the multicriteria aspects, uncertainty, and complexity:

Multiple criteria: The first step is to identify and select the performance criteria associated with a mission such as well as the constraints that will be taken into account and the level of detail (e.g. individual mission vs. aggregate plan). Decision-makers often respond well to a “natural” representation of their preferences through a set of thresholds. These may for instance include (i) minimally acceptable performance levels (ii) “good performance” thresholds beyond which additional betterment is of lesser interest. The language of thresholds is intuitive, quite general, and accommodates qualitative rating scales. All these aspects must be validated with end-users.

Uncertainty in dynamic contexts: Observation generally conditions future courses of action. In a search context, the converse (actions influencing future observation opportunities) can also be expected. Stochastic programs where actions influence future states are known to be considerably more difficult. One avenue around this could consist in discretizing the observation decision loop. However, balancing model accuracy against model complexity will not be a trivial task.

Dealing with complexity: Strategies to overcome complexity are model-specific. We may resort to decomposition, a priori decomposition (a fixed hierarchy of sub-models), and algorithmic decomposition (e.g. column generation). We may also resort to heuristics to solve sub-models. Extensive experimentation will be required and measures will be defined to evaluate solutions' quality.

©2009 Université Laval