Prof. Willem-Jan van Hoeve on the Beauty of Constraint Programming, and Teaching with the Whole Story in Mind
Willem-Jan van Hoeve has had quite a broad career. With a background in the fields of mathematical optimization, computer science, and artificial intelligence, he has worked on the theory and framework of the way we solve problems. Along the way, he has developed a particular interest in constraint programming as an approach.
Further to that, he has applied all this to make an impact in business and industry. His love for bridging the gap from theory to practice has led him to acting as a consultant and practitioner to tackle business problems large and small.
And, as a professor, he has enjoyed passing on these values to students. In the classroom, he's always believed in taking a hands-on approach, giving students the chance to put their skills to use in real-world problems. Now, as Associate Dean of Education at Carnegie Mellon University's Tepper School of Business, he is also taking a role in developing the way young scholars and future practitioners are schooled.
In our recent interview, we talk to him about all of this, as well as the Constraint Programming course he'll teach this summer at AIMMS Campus.
You're a professor and practitioner in optimization. Tell us about your journey to your current position.
I first encountered this mathematical optimization when I was doing my master's degree at the University of Twente in the Netherlands. I did my master's thesis on mathematical optimization, in particular the use of constraint programming in AIMMS, with Jan Bisschop [founder of AIMMS].
Then I did a PhD in computer science at the Center for Mathematics and Computer Science, CWI in Amsterdam University. I focused more on the algorithmic side of optimization. I tried to bridge algorithms from computer science with those coming from the mathematical optimization community--which is a very powerful combination.
After that I went to Cornell as a postdoctoral researcher. I looked more at the use of artificial intelligence for solving combinatorial optimization problems and integrating those techniques into either, say, constraint programming or mathematical optimization.
So there are these three areas of, let's say, the computer science point of view of algorithms, mathematical optimization, and artificial intelligence. There's a very interesting synergy in between those three areas, and I'm right in the middle.
And then I went to teach at the Tepper School of Business at Carnegie Mellon University. This is a Business School, but we have a group that is very technical, very methodological. I work on some applications, but I do most of my work on methodology of optimization technology.
What particular areas have you worked in?
I've always been intrigued by problems that are very challenging from both a theoretical and practical point of view. Finding good ways to represent them is a challenge. In general, mathematical optimization tries to structure a systematic approach to represent those problems. Of course, a product like AIMMS can help with that.
But then you need methodologies to solve them efficiently, ideally to proven optimality, and so you have different techniques for this. One of the techniques is constraint programming, which I will cover in a course at AIMMS Campus.
Some complex problems can be relatively small in terms of problem scope. Let's think about, say, an employee scheduling problem for maybe 20 employees. Sounds small, right? 20 employees. But it can already be very complex to find a good schedule satisfying all constraints and especially one that finds the optimal solution, relative to some objective.
Routing problems are another branch of application that I've been looking at for many years now, both from a theoretical point of view and also from a practical point of view. Like vehicle routing, truck routing, last mile delivery for delivery services, snowplow routing, and so on. I've worked with several companies in this space, like FedEx. And I've seen how automation can make an impact in practice.
And a similarly complex stream of work is in the context of machine scheduling, where projects sometimes have to undergo several operations in a certain sequence.
What projects are you currently working on?
More recently I've looked more into data mining and machine learning applications.
Machine learning and data mining aim to predict things based on past data. But unconstrained prediction is not always useful in practice, and certain things you want to predict have structure. For example, a sequential structure.
For example, a music streaming service gives you recommendations of songs to listen to. They want to know, is there an algorithm to predict which song to recommend to you in a sequence, so that you maximize the user satisfaction and minimize their skip rate?
To find that, you need to somehow incorporate the structural sequential information of this data. You cannot just look at the songs individually. You have to understand the pattern of songs preceding a specific decision about a song. And then based on that, have a more structural prediction.
And that typically comes with some constraints, such as that the time between touchpoints is within a certain range. Such constraints are very much like what we do with mathematical optimization. To carve out a structure that I'm interested in predicting is similar to how I would optimize over a structured space of decisions.
But now the task is not to find an optimal solution, but to predict some outcome. And that's something I've been working on in the most recent couple of years, and I mix ideas from constraint programming and mathematical optimization algorithms with data mining and machine learning.
|“To carve out a structure for prediction with machine learning and data mining is similar to how I would optimize over a structured space of decisions. I mix in ideas from constraint programming and mathematical optimization algorithms.”
We are pleased to have you on our program again for AIMMS Campus 2023. What was your favorite thing about teaching at AIMMS Campus last year?
I think my favorite thing was that the group of participants was very diverse. You get questions that are sometimes unexpected. And that's fun!
Having a group from a broad range of industries, they all had different applications they could potentially apply this to. And as a practitioner, I like to see what they're working on and offer them advice or guidance on how they could apply this in practice. So, the broad audience is the most interesting part for me.
Can you tell us what you plan for your Constraint Programming course at AIMMS Campus this year?
I'll be teaching Constraint Programming as a 2-day course.
Most people who study mathematical optimization use techniques from linear and integer programming, but constraint programming uses very different modeling ideas. You don't need linear constraints, for example; you can use other types of constraints as well, such as logical constraints. The variables that you're working with don't need to be numeric. You could say, I have a set of options, and pick me one of these elements in the set. The whole framework is much richer. And it allows you to do very smart modeling, and very different modeling than linearizing everything as you would do in integer programming.
If you look at standard industrial engineering or operations research curriculum, and look at optimization courses, a lot of the work is done in carving out the problem in terms of variables, objectives and constraints. And then you write it down in words or some mathematical formula, which can be nonlinear as long as it captures the structure of your problem. But then a lot of the work in classical optimization is trying to map the problem onto a model that the solver can handle, almost always a linear solver.
So you need to introduce modeling tricks. Meaning, how to convert a problem into linear form, so a solver can accepts it, and then can solve it quickly.
You don't always have to do this linearization--say you have lots of logical constraints, and the solver can handle those directly. In constraint programming, that's the case: the solver can natively accept and handle logical constraints, and other constraints that are richer.
For example, there are a special set of constraints in constraint programming around machine scheduling. And there are special building blocks, your model activities and resources, that allow you to very concisely express a scheduling problem in that language. So you can build your model using activities and resources.
It's very intuitive--the beauty of constraint programming is it can use this structure, represented by these building blocks, to speed up the algorithms. Under the hood of the solver is a whole range of algorithms that are tailored towards the specific constraints that you embed in the structure, whether logical or scheduling or combinatorial. And that rich modeling information has to be given to the solver at that modeling level, so that the solver can invoke those algorithms. And then it can do much more powerful inference and solve these things much more efficiently.
|“The beauty of constraint programming is, it can use a structure represented by building blocks to speed up the algorithms. Under the hood is a whole range of algorithms that are tailored towards the specific constraints that you embed in the structure.”
That's interesting -- so you're saying, before students can learn Constraint Programming, they usually have to learn to let go of the Linear Programming methods they've been trained in. How do you approach this as an instructor?
The whole first day of the AIMMS Campus course will be about getting accustomed to a different mindset. If people are already so familiar with linear and integer programming, can we now break away from that thinking, and can we think differently? Can we stay at the higher level? That is something that typically takes time for most people to digest, but we'll do a series of exercises where people get used to the idea.
There is a world beyond linear optimization! And once we have the basics under our belts, we can then look into more advanced algorithms and advanced modeling constructs.
In terms of teaching style, I like to go into practical applications as soon as possible. We do a modeling exercise, then we explain a little bit what's going on behind the scenes, and we go progressively into more complex applications.
It is in the Operations Research track of AIMMS Campus. This course will be more practical than theoretical. We want to see it in action! Of course, we'll look at some of the methodology, some of the algorithms behind the solver, to build trust. If I'm going to use any solver, I want to understand somewhat what the solver is doing. Enough so that I can trust it, that the result makes sense to me.
|“There is a world beyond linear optimization! … I want to give students the high-level insight to know if they should go for integer programming or constraint programming, and why.”
The students who were in your course last year, ranged from bachelors to postgraduate and even professionals. So it's designed as an open-level course?
Yes, absolutely. And I and I think some people didn't have that much formal training in optimization, so for them, it was maybe not very easy to get through all the details, but I made sure to have some exercises that were accessible for everyone. So if you can work with AIMMS in a company setting, you should be able to do these exercises even if you don't have a formal background in mathematics or optimization. In that case you may not get everything out of it, which is understandable, but maybe it gives you a glimpse of what you can do. For the ones with advanced knowledge in the area, I had different levels of difficulty for these exercises, so I think everybody had had fun.
Students from last year's Constraint Programming course had great things to say. Why do you think this subject is so attractive to students?
It depends on who you ask. If you are a practitioner, then constraint programming is exciting because it has potential to solve your problem better than with other techniques. And from a purely intellectual point of view, I think that potential is also what most people find intriguing. This is a course that they may not have seen before in their studies. Constraint programming is an established technology...but in many parts of the world it is, it is not typically in the curriculum of industrial engineering. It is in that sense a much smaller field than integer programming.
This summer course at AIMMS Campus gives people an opportunity to learn more about it. Two days is not a lot, but it gives you a glimpse of what it can do. And maybe it gives them a sense of the potential, and then they can take an online course or a workshop. There are many conferences in constraint programming where they can learn more.
I focus for this particular two days on the modeling aspect mostly. It will be mostly geared towards identifying what are the problems for which constraint programming is most suitable or most applicable. So if there is a problem that is better solved by integer programming, I go for integer programming. But there are some problems that I would approach with constraint programming right off the bat, because from experience I know that it's probably going to be better. I want to give students the high-level insight to know if they should go for integer programming or constraint programming, and why.
|“You have to tell students the whole story. If I claim that something is relevant and important, I have to give a motivation.”
Tell us more about your approach to teaching? It sounds like you like to get hands-on.
Oh, absolutely, yes. Especially for something like this Campus course. But also in my normal academic courses, everything is geared towards that final implementation, the hands-on case. I always ask the question: why should we spend our time on this? Basically, I want do things that are relevant. The motivation is super important, and I have to close that loop at the very end, prove its relevance. You have to tell students the whole story. If I claim that something is relevant and important, I have to give a motivation. Then I explain what it should do, why it is better than other methods, and then at the end I'll give you an example and then we have another hands-on exercise, and we'll see together that indeed this can have an impact.
There’s more to come--in part 2 of our interview (coming soon) we’ll dive into Willem-Jan’s approach to experiential learning...