Research Opportunities for Graduate Students

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:

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.

Better Optimization Algorithms

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.

Formulation Assistance for Mathematical Programmers

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.

Applications

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:

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

Data Classification

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).

Combinatorial Problem Solver

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.

INFORMATION FOR PROSPECTIVE STUDENTS

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.