**John W. Chinneck**

Systems and Computer Engineering

Carleton University

Ottawa, Canada

I have a special interest in *algorithms*, especially algorithms for *optimization*,
for many reasons:

- Optimization problems are a major part of engineering and business. Better solutions can make or break a business or a technology. A big part of the rapid advance in computing technology, for instance, has been the solution of optimization problems related to sizing and packing more and more devices into computer chips.
- Algorithms, and especially algorithms for optimization, are a major part of computer engineering and computer science. Many computing problems boil down to determining how to do something better or faster. Optimization is a big part of this. In addition, the hardest problems known (those in the NP-complete class) encompass a broad variety of optimization problems.
- Optimization algorithms have fascinating connections to intriguing phenomena such as evolution, brain structure, and the nature of intelligence. Insights from those areas are used in the development of new optimization algorithms, and insights developed from the application of the algorithms can prove useful to researchers in those areas. Much of the work in artificial intelligence is related to optimization algorithms.

The field in which optimization algorithms are developed and applied is
commonly known as *mathematical programming. *Other fields include *operations
research, management science, mathematical optimization, artificial
intelligence, industrial engineering*. These names reflect the historical
development of the fields, but in truth, the lines between them are very fuzzy.
The main thrust is to *solve problems*, and to do that effectively, you
need as many useful tools as you can muster, whether they derive from
mathematical programming, artificial intelligence, or any of the other fields.
The common element is *algorithms*, and that is where I work.

A brief overview of the lines of research that I am pursuing follows below. You should also visit my publications page for further details.

Many optimization problems that arise in business and industry are extremely hard to solve because they involve integer-valued variables or nonlinear relationships, or both simultaneously. Better solution algorithms are needed, and will of great commercial value. Better mixed-integer linear (and nonlinear) programming techniques are of great interest, both academically and commercially.

I have been concentrating lately on algorithms for reaching feasible solutions quickly for both of these classes of problems. Many AI problems can also be cast in this form.

Two trends have greatly affected the practice of mathematical programming: (1) the growth in computing power and effective solution algorithms, and (2) the mass availability of solvers (linear and nonlinear solvers are included in many popular spreadsheet systems for example). Now experts are formulating and solving huge models, and novices are encountering mathematical modeling for the first time. Both experts and novices can benefit from computer assistance if something goes wrong, but until recently, very few appropriate tools have been available. Mathematical programmers are in need of a suitable formulation environment and tools, similar to the code development environments (which may include specialized editors, debuggers, reference tools, etc.) which are available to computer programmers in languages such as C++, Fortran, or Java.

The real barrier in mathematical programming is no longer the actual solution of the model. Now the barrier is the correct design, formulation, debugging, and communication of large and complex models. I am working towards providing software tools that mathematical programmers can use to break through this barrier. You can see a newsletter article (pdf form) which describes this research in more detail.

One major thrust in this area has been the analysis of infeasible models. Mathematical optimization problems can be very large (e.g. hundreds of thousands of constraints, millions of variables for the biggest linear programming problems), and exceedingly complex. When the model is somehow faulty (e.g. infeasible or unbounded), it is extremely difficult to diagnose the problem. I have developed a number of algorithms for "debugging" large mathematical programs (see, for example the MProbe and MINOS(IIS) software).

The algorithms for analyzing infeasible linear programs now appear in most of the leading commerical LP solvers, including CPLEX, LINDO, Gurobi, and XPRESS-MP. Algorithms for analyzing infeasible mixed-integer linear programs have also been created, but require further development (there is considerable commercial interest in this project). Further, the infeasibility analysis algorithms have had some surprising applications:

**Constraint Systems: **The algorithms can be
used to improve backtracking in Constraint Logic Programming (CLP) languages.
Further research is needed.

**Data Classification: **One class of
infeasibility analysis algorithms can be directly applied to the problem of
classifying data, the same task performed by neural networks. See below for
more information.

**Data Analysis:** Useful in finding the “data
depth”, the multi-variable analog of the median point. Useful in screening
massive data sets for errors

**Others:** Applied in radiation therapy
planning, protein folding, automated test assembly, page ranking, finding
sparse solutions to linear problems, etc.

A second major thrust has been the development of general-purpose tools for the analysis of mathematical programs. MProbe is the best example: it provides a suite of tools for analyzing the shape of nonlinear functions of many dimensions and the convexity of nonlinearly-constrained regions, for user-controlled sorting of constraints and variables, etc.

There are many applications in business and industry that could benefit from some form of optimization, whether mathematical, heuristic, or drawn from artificial intelligence. I have been involved in the past with applications involving:

- Task assignment in cloud computing
- Channel assignment in wireless networks
- VLSI chip design
- DSP chip design
- Material flow in manufacturing
- Forest harvest scheduling
- Personnel scheduling
- Room scheduling for examinations
- Energy conservation

Students are also invited to propose applications from their own work, expertise, or interest.

Data classification is a fundamental task in artificial intelligence. Given a set of training examples with known outcomes, the idea is to find a way to correctly classify further instances that are provided later. For example, you may wish to automatically diagnose which patients are likely to develop a certain disease using a classifier developed from a medical database. There are numerous ways to create classifiers, including neural networks, but some excellent new methods are based on mathematical programming, and specifically on the methods for analyzing infeasible linear programs described above. Further development of these ideas is needed.

More recent work has focused on reducing either the number of features that are used in the classifier, or the overall cost of the testing (including both the cost of obtaining the feature data and the costs of misclassification).

The infeasibility analysis algorithm used in the Data Classification research described above shows promise as a good general-purpose heuristic for attacking other combinatorial problems. The underlying algorithm itself can undoubtedly be improved, and fast methods of converting problems to a form in which they can be solved by the algorithm are also needed.

**Question: What kind of background do I need to work with you?**

To work in my field, you need to develop skills in algorithms, optimization
(mathematical, heuristic, and AI), programming languages, and software
development. Probably most important is an *aptitude* for working in these
areas. Some of the specifics can be picked up during your graduate studies at
Carleton University.

**Question: What if I'm an American (or other foreign) citizen?**

Foreign students of all kinds generally require more of their own funding, since tuition fees are higher for foreign students than for domestic students. American students should note that with Canadian universities are actually quite affordable relative to the tuition costs at many US schools.

Feel free to email me with any questions about graduate study under my supervision.