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.
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. Over the last several years 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, IBM's OSL, 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.
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:
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.
The infeasibility analysis algorithm used in the Data Classification research described above shows promise as a good general-purpose heuristic for attacking other problems in the NP class. The underlying algorithm itself can undoubtedly be improved, and fast methods of converting NP problems to a form in which they can be solved by the algorithm are also needed.
There are some very interesting connections between logic models (e.g. the "satisfiability problem") and a class of linear programming model known as processing networks. These ideas need further development. There are potentially widespread ramifications of being able to solve some classes of logic problems via mathematical programming.
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 my background is not Electrical Engineering or Computer Science?
In addition to the M.Eng. and Ph.D. in Electrical Engineering, the Department offers the M.Sc. in Information and Systems Science for students who do not have an undergraduate degree in EE or CS. However, you will need some basic mathematics and computing, as well as a very good record in a quantitative or scientific undergraduate program to gain admission. Note that Computer Science graduates are considered for direct admission to our M.Eng. in Electrical Engineering.
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 the exchange rate between the U.S. and the Canadian dollar, Canadian universities are actually quite affordable. American students should also take note of the fact that many of my projects are in conjunction with U.S. companies
Feel free to email me with any questions about graduate study under my supervision.