Thinking big – from constraint programming to the Holy Grail: an interview with Gene Freuder

Welcome back to AI pioneers. In this interview we speak to eminent computer scientist Gene Freuder, tracing constraint programming from the early days of machine vision to the rise of generative AI. We discuss the applications of constraint programming, where the field of AI might be headed, how to give a good conference talk, and more.

Could you tell me a bit about your background and what drew you to the field of constraint programming?

I started out with pure math as an undergrad until it became too abstract even for me, so I drifted towards mathematical logic. This might sound strange because some might say it’s even more abstract, but I felt at least it had a subject – mathematics.

And then I found myself in artificial intelligence. I was at the MIT AI lab, as a part of what was known as the Copy Demo project. This project had a machine vision component where a basic form of constraint processing was used. This led me into what became known as the field of constraint programming. It’s a nice subject in that even though it’s a specific subfield, it can have many different applications in other areas.

What is constraint programming?

If you’ve ever played the Sudoku puzzle, then you’ve solved a constraint satisfaction problem. Puzzles like this are a nice way to introduce students to the field. If you’re someone like me, almost every problem looks like a constraint satisfaction problem. I’m aware of the old adage that if your only tool is a hammer, everything looks like a nail, but there are in fact a broad variety of problems that fall into the categories of constraint satisfaction or optimization problems.

The basic idea is this: you have some problem variables, values that you can assign to those variables, and there are constraints on what combinations of values you can use. You could have, for example, scheduling problems or design problems. One thing that happens if you tell people about that is they say, “Well, that’s sort of limited. What about…?” And the answer to the “what about” question, almost inevitably, seems to be yes, we have thought of that and we’ve extended the paradigm in that direction. For example, you can optimize and not just satisfy; there are soft constraints as well as hard constraints.

It’s one of those fields that isn’t as well known, but is in many applications. I once thought that we should adopt a motto like “constraint programming inside” – like Intel’s “Intel Inside” – so that people could tell that there was constraint programming in there, which they might not otherwise realize. But that’s hard to implement.

Constraint programming sounds so broad that it seems like it can be applied to many domains. I can see why it’s easily missed, as it must be ubiquitous.

Yes, people may be experiencing the applications of constraint programming without even realizing it. I was told at some point that the locomotives on the French railroads were scheduled using constraint satisfaction.

It has some overlap with Operations Research, which is another field that perhaps suffers in similar ways to constraint programming. I once read an article in a newspaper with a headline something like “the most important field you’ve never heard of,” and it was talking about operations research in that case, but I think that might apply to constraint programming as well.

Another problem we share with operations research is that we don’t have a very flashy name. Constraint programming is almost a negative, because “constraints” is a negative word. We do have some nice, positive words associated with the field, like relaxation and satisfaction and optimization. But if I wrote a paper on “optimizing satisfaction for relaxation,” people might think I was writing some new-age holistic health paper.

What was the state of the field when you started out, and what’s been the biggest thing that’s changed over time?

It was early days when I started out, and there was this big link to machine vision at the time. Fairly early on in my career, there was an ACM workshop on strategic directions in computing research, which included a working group on constraint programming. We were encouraged to think strategically, which I was grateful for, because we tend to all be caught up in the everyday. It’s great to step back now and again and think long term.

My idea at the time was the pursuit of the Holy Grail of computer science. In effect, this is to make the computer disappear. You tell the computer your problem and it solves it, without your needing to know how to program. In fact, that picture is coming to pass now with these chatbots. It’s a bit like in the movie 2001: A Space Odyssey. There’s this computer called HAL, which was of course a play on the letters of IBM. You tell HAL what you want, and it understands and does it. I had in mind something like that, but without HAL’s paranoia.

I thought that constraint programming was a particularly fertile field to pursue a holy grail like that, because it was declarative, so it seemed particularly well designed for you to just state your problem. There was a lot of talk at the time about the distinction between declarative languages and others. And behind the scene, there were these powerful algorithms that, in theory, could solve any constraint problem once you’d properly stated it as one. Of course, it might take the age of the universe to solve it – there’s a lot of devil in the details of how you properly model and solve a problem.

So I set this Holy Grail: that you would just go up to the computer, say what your problem is, and it would solve it, without further human instruction. Over the years that’s functioned as a lodestar for me, and I’m happy to say, as one for the field.

That comes back to your question about where the field has gone or where it’s going now. The goal of the Holy Grail is consistent with advancing the field in terms of acquiring problems, solving problems, explaining the results, and doing it in an automated way. It fits well now with the current interest in machine learning. There’s a lot of interesting work going on now in combining machine learning, especially LLMs, with constraint programming.

How do AI and constraint programming complement each other?

I’ve been in AI for decades, so I consider myself to be an AI person. As such, I take constraint satisfaction to be an important subfield of artificial intelligence. Constraint programming is a broad, multidisciplinary community and can also welcome people from operations research, programming languages, and other fields.

Where do you think the field of AI is heading?

I think many people believe that the way forward is not pure generative AI. In particular, neurosymbolic approaches can be a very profitable way to proceed. Both the neuro-oriented work and the symbolic-oriented work have their strengths and weaknesses, and together they can provide a more powerful whole. We’re certainly interested in that in terms of bringing together constraint programming and machine learning.

There’s a lot of excitement in this area at the moment. For example, there were related workshops at this year’s Constraint Programming conference. There was a tutorial at IJCAI on LLMs for Constraint Modeling this summer. I’m co-editing a special track of JAIR on Constraint Programming and Machine Learning. And there’s a special issue of the Constraints journal on Large Language Models for Combinatorial Constraint Solving underway. I think we’ll see some more really interesting results coming out.

What are some examples of problems where you would use constraint programming and LLMs together?

You can envision an LLM as a front end and a constraint solver as a back end. You can present the problem to an LLM, which can be good at reading text or even conversing with people, and then you can build a model which you send off to a constraint solver. A lot of progress has been made in this area already.

I think a frontier area at the moment is conversational constraint solving. There’s been some remarkable success in building systems that can look at benchmark problems available in the literature and work from those to a solution. That’s a static situation, but there’s also interactive work emerging. In the real world, if you want to schedule the machines on your factory floor, for example, I don’t think you would normally come with a complete specification of the problem to hand off for solving. There are conversations involved to explain what the constraints are and what the problem is.

I remember back in the old days when rule-based reasoning was the latest and greatest thing. Someone described to me the process where you’d come into a city and book a hotel room, go to the customer, they’d explain their problem, and you’d go home that night, sit in your hotel room, and program out the rules, then come back the next day. They’d say, “That’s good, but we haven’t taken this into account,” and then you’d go back to your hotel room and rewrite it, and come back the next day. This would be an iterative process where you’d hopefully converge on a solution that really satisfied the customer.

It’s a similar kind of thing now where you would like to have a conversation with the computer. You describe your problem, see what the results are, and decide, “Well, I forgot this constraint,” or “That won’t work, I need to do something else.” There’s a demo, CHAT-Opt, available at KU Leuven, where you can have a conversation with the demo, to define and solve a problem.

The thing about LLMs is that they can do very surprising things, both in a good sense and a bad sense. Just for fun, I dabble with them a bit, and over the years have collected instances of them being incredibly stupid. I had a conversation with one some years back where I was trying to see how well it could generalize, and it thought that 2 was an odd number. I corrected it, and then a few moments later it was making the same mistake. But these systems have continued to evolve and improve, and there are people in our field who have come up with some really remarkable results.

In another case, I played around with some publicly available tool that purported to build an app for you. I fed it this problem that was not actually solvable, and it promptly came up with an impossible solution. However, when I more recently tried this with the CHAT-Opt demo posted at KU Leuven, that system was smart – it recognized that the problem was unsolvable. It then allowed me to play around with it, weaken or remove the constraints, and come up with a version that was solvable. That kind of system is really quite exciting.

Do you think we’ll ever have AI that could not just solve constraint problems, but come up with new ideas and give itself problems to solve? In the same way that humans can examine the environment and work out which problems we should care about and be solving.

That’s an interesting question. I’m trying to think to what extent it’s been addressed up until now.

The first question is, how do you explain to the machine what it is that you want to do? It’s one thing if you have a problem and say, “Okay, this is my problem,” and you may have some trouble expressing exactly what it is, but you’re at least able to describe it. In its basic form, often you may have a problem that’s already being solved somehow.

For example, if you have someone at a hospital who schedules the nurses, maybe you can program this more efficiently. There’s an analogy here with the days of rule-based programming. One of the advantages of going through the process of trying to write a rule-based program to solve a problem is that in that process, you could extract and define the problem more rigorously. It could be a similar situation for constraint-based programming.

This makes me think of an example from Patrick Winston, one of the legendary AI pioneers. I did my thesis work under him. He liked to use an example of determining whether young chicks were male or female. There’s somebody who would stand at an assembly line, pick out the young roosters and toss them aside. The process of determining the sex of the chicks at that age was apparently like an art – you couldn’t really say exactly how these people did it, but they were able to do it. So there are problems like that. The question there is, can you extract the constraints that would enable somebody to automate that process. So one issue is, can you define a problem precisely enough to hand it off for automation?

With your question, I think you may be going even further. Can you find what interesting problems would be, or take something very ill-defined and turn it into a refined problem? I wouldn’t be surprised if there’s more going on in that direction, but as you can see, I’m thinking out loud here. How does one exactly define that problem, and turn it into a problem you can work on, evaluate, and publish a paper?

There is a lot of potential in new AI systems.

Definitely. One other aspect I’m interested in is whether these systems can function as research assistants, to suggest new ideas that you can then pursue. I played around with a chatbot a while back where I asked it to generate a variable ordering heuristic for constraint satisfaction problems that had not been tried before.
What it came up with sounded promising – it didn’t sound exactly like something I knew was already in the literature, and it seemed like something possible to try.

This was a long conversation, and it offered to implement it, test it, and write a paper. I wouldn’t have submitted a paper it produced, but I played around with it. It came up with some experimental results that looked promising. At some point I kept pushing it, and it admitted it hadn’t actually conducted those experiments – it had made up the results. When I pushed it, it purportedly did conduct the experiments. Unsurprisingly, those results weren’t as good as the ones it had made up.

I think in some ways they might be regarded as a particular kind of graduate student who’s incredibly hard-working and fast, but lacks the common sense or the basic feel for the field that a mature researcher would have. So they can be very useful and maybe even can be taught to improve, but you have to be careful.

What else interests you?

One of my hobby horses is talks. I don’t claim to be the world’s greatest speaker, but I’ve sat through a lot of bad talks, and I do think about what makes for a good talk or a bad one. I’ve actually given some tutorials at conferences on how to give a talk – not because I necessarily think I’m naturally a great speaker, but because I’ve thought about it and have some heuristics for doing it.

I have another page on my website that lists some of these pieces of advice. For example, varying the tone of your voice is important. Understandably, a lot of people – especially young people giving a talk for the first time, and maybe not in their native language – tend to speak in a monotone that after a while can put you to sleep. If you use your voice to go up and down, make the volume louder and softer, pause and so on, it makes you sound more engaging. There are various heuristics like that.

If I had to boil it down to one word for what can make the difference between a good, engaging talk that people remember, and one that they don’t – it’s enthusiasm. On stage, people don’t always show it, even though they must be passionate about their research to have worked on their thesis for five years. If a speaker doesn’t seem enthusiastic about what they’re saying, why should you be enthusiastic about it? If they are enthusiastic, it makes a huge difference.

I think there are probably more introverts in computer science than in, say, acting – I think I’m naturally introverted. Jung once said that none of us are 100% introverted or 100% extroverted, if we were, we’d be in an asylum. Everyone can pull out some bit of extroversion for a talk, some time when they were excited and enthusiastic and showed it.

In my case, when I was accepted into college and got the telegram, I came running into the living room of our house and did a somersault over the couch, and my parents were probably looking at each other thinking, “Who is this kid, what did he do with our child?” Because I’m not naturally that way, as some people are. But you can draw on whatever bit of extroversion you have. I try to do that when I’m speaking. I suspect in my case it just brings me up to a normal level; I think I’m being very enthusiastic and probably not showing it as much as I’d like to.

On the topic of advice – what would you tell someone starting a PhD in the field of AI or constraint programming today?

Another good question. It’s understandable to ask someone at my stage of career, though it’s not entirely clear that I’m in the best position to answer it. Thinking in terms of somebody starting a PhD, in particular, and looking for a thesis topic – I’d say think big. This is an occasion when you’ll have years to think hard about a particular problem, and it’s an opportunity you may not have quite the same way again. You’d be going off to work either in industry, where somebody may be telling you to some extent what to do, or at a university, where you have a lot of freedom, but you may also be teaching at nine o’clock and attending a committee meeting at ten.

So take that opportunity to think big and to come up with a really ambitious goal. We talked earlier about strategic thinking. Take the time to step back and think: what is a big problem in my field? What is something that, if I accomplish it, people would really sit up and take notice? What are the big challenges for the field, where would we like to be in ten, twenty years? Try to set up some big, challenging goal for yourself.

On the other hand, I tend to be a kind of conservative person in some ways, and I wouldn’t put all my eggs in that basket. I’d have a backup plan. If I wasn’t able to accomplish that big goal, maybe some partial result or other backup problem would be a good thesis. You don’t want to be sitting there for the next thirty years tackling an impossible problem and never getting your PhD. But to some extent, take the opportunity to think big and come up with something that would really be significant if you were able to accomplish it, or even make an impressive step towards accomplishing it.

You recently sat on the AAAI presidential panel on the future of AI research. Is there anything the field should be paying more attention to right now?

The AAAI presidential panel that Francesca Rossi organised on the future was trying to look into the future and determine where we should be going. I was involved in the reasoning aspect of that. There was interest in not relying totally on the neural aspects of AI, but recognising that the more formal methods – where you’re able to establish results in a formal, provable way, as opposed to obtaining probabilistic possibilities – were important to keep in mind. We don’t want to get carried away totally by the newer approaches.

I think even people who are primarily generative-AI people would recognise that the new generative AI approach has not achieved everything we want to achieve, and probably can’t by itself. We may need new ideas, or at the very least, we may need to keep the older things in mind. This is contrary to how it can be portrayed in the media.

Coming back to the neurosymbolic approach I was talking about earlier, where we’re combining constraint programming with LLMs, combining the classical AI approaches with the new generative AI approaches can lead to progress there.

We conducted a survey in connection with that presidential panel where, in particular, we asked people whether the hype about AI matched reality. There was considerable scepticism, more so among the older respondents, as to whether the hype matched the reality. I think we’re still struggling now to determine to what extent current progress in AI has succeeded, to what extent we still have to be wary of it, and to what extent we need to move beyond it – whether that means moving in a new direction, or combining the old with the new. This is also hard to measure as progress in AI is a moving target.

I have some bias in this area, as someone who’s been around a long time, but I do have considerable appreciation for what’s been accomplished recently with generative AI. However, I want to remind people that it’s not all of AI. There’s a lot that’s been done that’s still valuable and still worth pursuing, whether on its own or in conjunction with new approaches, that we need to keep in mind and keep working on.

About Gene Freuder

Gene Freuder is a University College Cork Emeritus Professor of Computer Science. He is now back in the U.S., in Cambridge, MA, and has an appointment as an Associate of the Harvard John A. Paulson School of Engineering and Applied Sciences. Gene was honored to receive the IJCAI Research Excellence Award in 2020, and he is the President of the recently formed Artificial Intelligence Scientific Organizations Coordinating Council. He served as a Councilor of the Association for the Advancement of Artificial Intelligence (AAAI), on the AAAI 2025 Presidential Panel on the Future of AI Research, and currently serves on the AAAI Council’s Conference Committee. Gene recently co-organized AAAI Conference “Bridges” on Constraint Programming and Machine Learning, and is also co-editing a JAIR Special Track on Constraint Programming and Machine Learning.

Ella Scallan is Assistant Editor for AIhub

Ella Scallan is Assistant Editor for AIhub