Featured post

Introduction

Among the types of posts you may find in this Blog:

  • Citations: Brief “shout outs” to recent papers citing my work
  • Ideas: Research ideas or other thoughts that might (or might not) be worth pursuing
  • Mentoring: In particular, tips related to my tutorials on “How to Be a Ph.D. Student” and “Presenting a Paper”
  • News: Occasional news about my activities, the Insight centre, Constraint Programming and Artificial Intelligence
  • Papers: A look back at my old papers, with an eye to current relevance

Note that I may edit posts — including this one 🙂 after their original posting.

Comments are encouraged. Use “Leave a Reply”.

Note that you can subscribe to the blog via RSS or follow via email. See the sidebar.

Queens

Quanta has an article “Mathematician Answers Chess Problem About Attacking Queens“. I thought at first that the headline was a bit strange as we in Constraint Programming, and others, have been solving the n-Queens problem for many years now: how to place n queen chess pieces on an nxn board such that they don’t attack each other. However, the headline is referring not to the problem of finding solutions per se, but to the question of how many solutions there are for any n, for which there has not been any precise answer (other than finding them all). Michael Simkin of Harvard hasn’t actually found a precise answer either, but he has apparently made good progress on narrowing it down. According to the Quanta article “Simkin proved that for huge chessboards with a large number of queens, there are approximately (0.143n)n configurations”.

This also reminded me that there are ways of constructing solutions for the n-Queens problem without search, e.g. Constructions for the Solution of the m Queens Problem, which I conveniently ignore because the problem of searching for a solution has been so useful for both teaching and research in CP. More generally, one can go down quite a rabbit hole with the n-Queens problem, not surprising for a problem that was first published, as the 8-Queens problem, in 1848, and studied by Gauss. There is an n-Queens bibliography online with 336 entries.

Abstracting methods developed for a specific application is, of course, a good “meta-heuristic” for seeking new, more general methods for Constraint Programming. For well-studied problems like n-Queens or graph coloring, I suspect that there is a good deal that is still lurking in the older literature, or appearing in new publications, that could be mined to advance CP.

I Spy With My Little Eye

A golden age of surveys/overviews may be upon us. I’ve just added three new items to the Surveys, Overviews, Bibliographies section of the Constraints Resources site. And they deal with the hot AI topics of learning and explanation.

Explanation in Constraint Satisfaction: A Survey. Sharmi Dev Gupta, Begum Genc and Barry O’Sullivan. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence

End-to-End Constrained Optimization Learning: A Survey. James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck and Bryan Wilder. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence

An overview of machine learning techniques in constraint solving. Andrei Popescu, Seda Polat-Erdeniz, Alexander Felfernig, Mathias Uta, Müslüm Atas, Viet-Man Le, Klaus Pilsl, Martin Enzelsberger & Thi Ngoc Trang Tran.  Journal of Intelligent Information Systems

Opportunities

This looks like a great research program that Ferdinando Fioretto is advertising a Ph.D. position for:

A Ph.D. opening is available for candidates interested in the intersection of deep learning and combinatorial optimization. The position will start in January 2022. Topics of interest include: – Supervised Learning for speeding up the resolution of constrained optimization problems; – Reinforcement Learning for dynamic and combinatorial problems; – Graph Neural Network models for graph-structured constrained optimization problems; – Theoretical guarantees for ML-enhanced constraint optimizers; – Physics informed deep learning; The project will combine fundamental aspects of optimization, constrained reasoning, and learning to develop integrated optimization and learning systems. The ideal candidate will have a strong background in mathematics and optimization theory and a strong interest in machine learning and constraint reasoning. Students who majored in Computer Science, Mathematics, Statistics, or Physics are welcome to apply. An MS degree and/or publications in leading international venues will be an advantage. TO APPLY: Applications should be submitted at ffiorett@syr.edu and candidates should include their statement of purpose, resume, and transcript (if available).

Similarly for this assistant professor opening at TU Eindhoven:

As a successful applicant, you will work on the interface between Artificial Intelligence and decision-making methods. Examples of research directions include but are not limited to: using machine learning (such as predictive modelling and reinforcement learning) to find better solutions to optimization problems, developing decision support tools that combine data-driven models with knowledge-based models. With an embedding of the position in the school of Industrial Engineering, special attention will be paid to applications of the methods and tools in domains such as logistics, transportation, service industries, high-tech manufacturing, and healthcare.

Great to see these positions that resonate with the Pursuit of the Holy Grail.

Meta

Looking for papers on explanation for constraint satisfaction I ran across Meta-explanation in a Constraint Satisfaction Solver by the pioneering French AI scientist Jacques Pitrat. From the abstract:

Meta-explaining is useful to a human or an artificial researcher in order to learn how to use its knowledge efficiently. For instance, when the system RESEARCHER solves the same prob- lem using two different methods, it can meta-explain why it finds a more elegant solution with one of them. 

It might be interesting to compare Pitrat’s work here to the work I did with Chavalit Likitvivatanavong and Rick Wallace in Deriving Explanations and Implications for Constraint Satisfaction Problems.

Pitrat’s paper is related to a very ambitious — and very “meta” — research agenda that he was pursuing. See A Step toward an Artificial Artificial Intelligence Scientist, Artificial Beings: The Conscience of a Conscious Machine, and his blog. Unfortunately Pitrat passed away recently; the record of a day of tribute can be found here

Call for Submissions to PTHG-21

PTHG-21: The Fifth Workshop on Progress Towards the Holy Grail

October 25th, 2021, at CP2021

This Workshop is one of a series.

Note: CP2021 and its workshops are virtual, with free registration.

Description:

In 1996 the paper “In Pursuit of the Holy Grail” (also here) proposed that Constraint Programming was well-positioned to pursue the Holy Grail of computer science: the user simply states the problem and the computer solves it. It was followed about a decade later by “Holy Grail Redux“, and then about a decade after that by “Progress Towards the Holy Grail“. This series of workshops aims to encourage and disseminate progress towards that goal, in particular regarding work on automating:

  • Acquisition: user-interaction, learning, debugging, maintaining, etc. 
  • Reformulation: transformation for efficient solution, redundant models, etc. 
  • Solving: adaptive parameter tuning, automated selection from portfolios, learning heuristics, deep learning, etc. 
  • Explanation: reasons for failure, implications for choices, etc. 

Of particular interest is the intersection of the Holy Grail goal with the increasing attention being paid to machine learning, explainable AI, and human-centric AI.

Organizing Committee:

Chair: Eugene Freuder, University College Cork, Ireland, eugene.freuder@insight-centre.org 

Christian Bessiere, University of Montpellier, France 

Tias Guns, KU Leuven, Belgium 

Lars Kotthoff, University of Wyoming, USA  

Ian Miguel, University of St Andrews, Scotland  

Michela Milano, University of Bologna, Italy 

Helmut Simonis, University College Cork, Ireland 

Submissions:

Submissions may be of any length, and in any format. They may be abstracts, position papers, technical papers, or demos. They may review your own previous work or survey a topic area. They may present new research or suggest directions for further progress. They may propose research roadmaps, demonstration domains, or collaborative projects. They may be proposals for measuring progress, and, in particular, for data sets or competitions to stimulate and compare progress. 

Previously Published Track. Authors are encouraged to submit to this track pointers to relevant papers that they have published elsewhere since the date of the last workshop, PTHG-20, September 7, 2020. The objective is to further the Workshop goal of disseminating progress in this area. 

Submissions should be emailed, in PDF form, with subject line “PTHG-21 Submission”, directly to the Workshop chair, at: eugene.freuder@insight-centre.org.

Submissions to the Previously Published Track should be in the form of a PDF that clearly identifies it as a submission to the Previously Published Track, contains bibliographic information on the previous publication, and provides a URL pointing to the paper (if possible without violating copyright, to a full version of the paper).

Authors may make multiple submissions if they wish. All submissions that appropriately address the topic of the workshop will be accepted as is, without further revision, and will be made available at the workshop website.

The deadline for submissions is September 15, 2021. Decisions on acceptance will be sent by September 20, 2021. 

Authors of accepted submissions will be expected to upload a video presentation of the requested length by September 30, 2021; otherwise the submission will be withdrawn from the program and proceedings (if any). The conference will host these videos. Details of the upload process will become available. 

Website: PTHG-21: The Fifth Workshop on Progress Towards the Holy Grail

Small Islands

Semantic Scholar has informed me that my chapter with Alan Mackworth in the Handbook of Constraint Programming on Constraint Satisfaction: An Emerging Paradigm has been cited in the PREFACE to the proceedings of the International Conference on Small Islands Community: Momentum of Transformation of Small Islands Community in New Normal Era 12th December 2020, Maluku, Indonesia.

This was quite intriguing. However, it seems clear that we weren’t, in fact, cited in the preface. Perhaps in one of the papers? There are several papers in the proceedings that I would be particularly intrigued to see our connection to:

Community structure of conches (Strombus spp) in seagrass bed of Haria, Central Maluku, Indonesia

Fattening of mangrove crab (Scylla serrata) in wooden pen and plastic container

Feeding habits of giant trevally Caranx ignobilis (Carangidae) rearing in floating cage nets

Utilization of garlic as traditional fish handling in Molluccas Islands: case study on layang fish (Decapterus macrosoma, BLECKER)

Chemical properties of dried anchovy (Stolephorus sp) from Buru Island

Any of these would provide excellent further support for the claim I made in my IJCAI-20 award talk for The Ubiquity of Constraints. However, I fear Semantic Scholar has just been misled somehow.

Citation Sighting

I won’t pretend to be inundated with citations, but it is pleasant to still be getting them, and Semantic Scholar can make it easy to hear about them, by sending you emails. However, as we’ll see Semantic Scholar can sometimes use a little help 🙂 (I want to be clear though that my intention is not to diss Semantic Scholar, which is a wonderful service.)

Here are 6 citations for 6 papers that Semantic Scholar alerted me to in the past 6 days:

I received a notice that “Who ? What ? Where ? When ? Why ? and How ? 2” had cited Explaining ourselves: Human-aware constraint reasoning. Interesting title, but actually it turns out that the citing paper is titled Explainable Security. It appeared in Proceedings of the 6th Workshop on Hot Issues in Security Principles and Trust (HotSpot 2020) (another interesting title). The authors, Viganò and Magazzeni, propose “a new paradigm in security research: Explainable Security (XSec)” and discuss ‘the “Six Ws” of XSec (Who? What? Where? When? Why? and How?)’. So that explains part of the mystery of Semantic Scholar’s title for the paper, but it is still a mystery.

I was informed that Error Function Learning with Interpretable Compositional Networks for Constraint-Based Local Search cited two of my papers, In Pursuit of the Holy Grail and Progress Towards the Holy Grail. Semantic Scholar’s listing of the first paper in the References points to an entry that itself claims only 10 citations. That seemed low to me, and then I realized it was the version of the paper in ACM Computing Surveys. The version in the Constraints journal, which is the one the paper actually cites, has 59 citations. Semantic Scholar includes the second paper three times in the References, but twice in odd ways, which if hovered over declare that the paper is not yet in Semantic Scholar’s corpus.

In fact, the paper cites three of my papers; it also cites Holy Grail Redux. However, Semantic Scholar thinks Holy Grail Redux was authored by “S. Nadis” so I was not notified of this citation. Perhaps S. Nadis was and is wondering why. When you click through on Holy Grail Redux in Semantic Scholar’s list of References for this paper you arrive at a listing for Holy Grail Redux where the “Topics from this paper” include only “Bad Mojo”, and when you click on View via Publisher, you end up here!

Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems, which I co-authored with Mike Quinn was cited by two papers. In Neural Regret-Matching for Distributed Constraint Optimization Problems, Yanchen Deng , Runshen Yu , Xinrun Wang and Bo An are “incorporating deep neural networks in solving DCOPs for the first time”. In Utility distribution matters: enabling fast belief propagation for multi-agent optimization with dense local utility function Yanchen Deng and Bo An: “theoretically show the correctness and superiority of our proposed algorithms”.

Finally, Semantic Scholar informed me that Exploring Automatic Fitness Evaluation for Evolutionary Typesetting cited a paper, Creating Personalized Documents: An Optimization Approach, which I wrote with Lisa Purvis, Steven Harrington and Barry O’Sullivan. In their paper Sérgio M. Rebelo, Tiago Martins, J. Bicker and P. Machado “present an evolutionary system for the automatic typesetting of typographic posters”. In our paper we “formalized custom document creation as a multiobjective optimization problem, and use a genetic algorithm to assemble and transform compound personalized documents”. Unfortunately, while Semantic Scholar knew enough to alert me to the citation, the one reference it lists at the citing paper’s webpage is not our paper.

I received the first notice from Semantic Scholar on June 20th and the last on June 25th, so 6 citations for 6 papers in 6 days. Just a nice coincidence, not any kind of record to be sure. Google Scholar says that Geoffrey Hinton received 85,082 citations in 2020, which works out to approximately 233 per day. Well actually “only” approximately 232, because 2020 was a leap year.

It did feel like a long year, didn’t it.

Ban the Bullets

Presentations are often full of bullet point slides. Ostensibly this is to help the audience identify and recall the main points of the talk. In practice, the bullet points serve as a crutch for the speaker. In the worst case, the talk devolves largely into a verbatim recitation of densely packed bullet points: a guaranteed soporific. In any case, the speaker is competing with the slides. Should the audience members read the bullet points or listen to the speaker? They try to do both, but people are notoriously bad at multi-tasking.

For boring speakers, I may read the bullet points quickly, and if that seems sufficient, I can return to my email until the next slide, while the speaker drones on. For more interesting speakers, I may purposely ignore the bullet points to focus on the speaker. There may be information in the bullet points that the speaker does not address, but rather than worrying about reading it before the slide changes, I can console myself with the knowledge that my memory of the talk will be subject to rapid exponential decay anyway.

So if not bullets, what should be on the slides? I plan to address that in a future post.