Domain-independent dynamic programming (DIDP) is a general-purpose system for modeling and solving combinatorial optimization problems based on dynamic programming (DP). The aim of the DIDP system is to declaratively model problems in a DP-based formulation and then solve the formulation with a general-purpose solver. To date, we have implemented a number of solvers based on heuristic search as studied extensively in AI. Our numerical results have shown that DIDP out-performs state-of-the-art MIP and CP approaches on a variety of combinatorial problem benchmarks including traveling salesperson with time windows, orienteering, single machine scheduling, and assembly line balancing. In this presentation, we provide an overview of the DIDP modeling and solving approaches and recent numerical results. We then provide a detailed examination of the models and solver behavior for selected problem classes to elucidate problem characteristics that lend themselves to strong DIDP performance.

In the past, there have been many approaches to integrate ideas from SAT into MIP solving and vice versa. In particular, conflict analysis, originally developed for SAT, has been established as a standard in modern MIP solvers to compute stronger cutting planes from conflicts that were derived during the search. An important difference between conflict analysis in MIP and SAT is, however, that MIP uses conflict analysis mostly as an add-on to improve the LP-relaxation during a branch-and-bound procedure while for SAT it constitutes the actual solving method, also called Conflict-Driven Clause learning (CDCL). This raises the question if we could similarly develop a MIP solver that is built exclusively on lazy methods rather than branch-and-bound, i.e. on successively learning constraints from conflicts that occur during the search. In this talk, we will present a first version of such a lazy MIP solver which we developed as an extension to our constraint programming (CP) engine LazyCP which previously used pseudo-Boolean methods to solve finite-domain CPs. We will present some first computational results and discuss some observed strengths, weaknesses and potential improvements to the “lazy approach” of solving MIPs.

Before a combinatorial search problem can be solved with constraint solving or a related technique it must first be modelled: a set of variables chosen to represent the decisions we must make in solving the problem, and a set of constraints specifying allowed combinations of variable assignments. Since the search spaces involved can be vast, an effective model of a problem of interest has a very significant impact on the solving process. Steps such as breaking symmetry and/or adding implied constraints to aid the solver in making inferences and therefore detecting dead ends earlier in search can be used to improve an initial model. If performance remains unsatisfactory, a more aggressive step that can be taken is the addition of streamliner constraints, which are not guaranteed to be sound but are designed to focus effort on a highly restricted but promising portion of the search space. When the concept was originally introduced, generating effective streamliner constraints was a manual, difficult and time-consuming task. This talk will present an automated approach to the generation, search and selection of streamliner portfolios to produce a substantial reduction in search across a diversity of problems.

Constraint Acquisition (CA) is a fundamental symbolic learning approach which learns concepts under the form of constraint networks. By classifying positive and negative instances, CA progressively eliminates constraints from a bias containing all possible constraints between variables. When a CA process raises queries to an external oracle, the learning approach becomes active. In recent years, query-based CA has become a popular method to acquire knowledge under the form of constraint networks, to handle partial answers over positive and negative instances, to deal with uncertainty in data instances, and acquire qualitative constraints. This talk surveys existing query-based CA methods and presents its main application areas which range from robotics to software engineering. Deploying query-based CA for explaining the results of classification models developed with opaque machine learning models is an important perspective of this symbolic learning approach.