ABSTRACT. Constraint Satisfaction Problems (CSPs) play a central role in many applications in Artificial Intelligence and Operations Research. In general, solving CSPs is NP-complete. The structure of CSPs is best described by hypergraphs. Therefore, various forms of hypergraph decompositions have been proposed in the literature to identify tractable fragments of CSPs. However, also the computation of a concrete hypergraph decomposition is a challenging task in itself. In this paper, we report on recent progress in the study of hypergraph decompositions and we outline several directions for future research.

ABSTRACT. Conflict-driven Pseudo-Boolean (PB) solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though PB solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear program (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven PB search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis over linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best of two worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut.

Q&A session (starts at 16:30)

ABSTRACT. Core Guided Maximum Satisfiability (MaxSAT) solvers are the state of the art approaches to finding optimal solutions to maximum satisfiability problems. While Core Boosted MaxSAT solvers provide the state of the art for quickly finding good solution to maximum satisfiability problems. In this paper we explore the use of core-guided and core-boosted methods for constraint programming solvers with explanation. Experimental results show for certain classes of problems core-guided search can significantly outperform traditional branch-and-bound solving approaches for CP problems to optimality. Meanwhile for many classes of problems core-boosted search significantly improves anytime CP optimization performance.

Q&A session (starts at 16:30)

ABSTRACT. Optimization Modulo Theories (OMT) is an extension of SMT that allows for finding models that optimize objective functions. In this paper we aim at bridging the gap between Constraint Programming (CP) and OMT, in both directions. First, we have extended the OMT solver OptiMathSAT with a FlatZinc interface -- which can also be used as a FlatZinc-to-OMT encoder for other OMT solvers. This allows OMT tools to be used in combination with mzn2fzn on the large amount of CP problems coming from the MiniZinc community. Second, we have introduced a tool for translating SMT and OMT problems on the linear arithmetic and bit-vector theories into MiniZinc. This allows MiniZinc solvers to be used on a large amount of SMT/OMT problems.

We have discussed the main issues we had to cope with in either directions. We have performed an extensive empirical evaluation comparing three state-of-the-art OMT-based tools with many state-of-the-art CP tools on (i) CP problems coming from the MiniZinc challenge, and (ii) OMT problems coming mostly from formal verification. This analysis also allowed us to identify some criticalities, in terms of efficiency and correctness, one has to cope with when addressing CP problems with OMT tools, and vice versa.

Q&A session (starts at 16:30)

ABSTRACT. Constraint programming solvers employ intelligent reasoning and search algorithms to solve hard combinatorial problems in much better time than worst-case complexity analysis would suggest. As the algorithms involved get increasingly sophisticated, it becomes harder and harder to be sure that the implementations are correct. Unfortunately, neither software testing nor conventional verification techniques have been much help in addressing this.

An alternative approach, which is discussed in this talk, is to create a certifying algorithm. The idea is that alongside an answer, a solver also outputs a certificate that the answer is correct, and this certificate can then be verified by a much simpler external tool. A solution, on the one hand, is a certificate in itself, because it is only necessary to check that the solution satisfies all constraints. On the other hand, if there is no solution, a proof of this fact needs to be constructed on the fly, aka proof logging, because the solver can not remember all steps that were performed to conclude that no solution exists. Note that the certificate does not verify that the solver is correct, but it does tell us if a solver ever produces a spurious answer (even if it is due to hardware or compiler faults).

Proof logging is already well established in the Boolean Satisfiability (SAT) community, through a format known as DRAT. However, using DRAT to express more complicated reasoning appears to be infeasible in practice. Instead we developed a tool called VeriPB which uses pseudo-Boolean reasoning and cutting planes proofs, together with reverse unit propagation, to give algorithm engineers an easy way of integrating powerful proof logging into existing code.

In this talk I will present our recent work published at AAAI-20 on pseudo-Boolean proof logging for justifying all-different reasoning in the context of constraint programming.

Q&A session (starts at 16:30)

ABSTRACT. Our goal is to identify effective exact approaches to solve the multi-mode resource investment problem. This is a project scheduling problem where a deadline on the latest project completion is imposed and the resource costs need to be minimised.

Q&A session (starts at 16:30)

ABSTRACT. Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search.

We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set.

Q&A session (starts at 16:30)

ABSTRACT. The trend towards a precise, numerical, and data-intensive agriculture brings forward the need to design and combine optimization techniques to obtain decision support methodologies that are efficient, interactive, robust and adaptable. In this paper, we consider the Differential Harvest Problem (\DHP) in precision viticulture. To tackle this problem, we dedicated a specific column generation approach with enumeration techniques and a constraint programming model. Therefore, a set of simulated instances (which differ in field shape, zone shape, and size) was created to perform a parametric study on our different approaches. The specific column generation approach presented in this paper is preliminary work in the development path of more sophisticated resolution methods such as robust optimization and column generation/constraint programming hybridization.

Q&A session (starts at 16:30)

ABSTRACT. We propose a polyhedral cutting plane procedure for computing a lower bound on the optimal solution to multi-agent path finding (MAPF) problems. We obtain our cuts by projecting the polytope representing the solutions to MAPF to lower dimensions. A novel feature of our approach is that the projection polytopes we used to derive the cuts can be viewed as `templates'. By translating these templates spatio-temporally, we obtain different projections, and so the cut generation scheme is reminiscent of the template matching technique from image processing. We use decision diagrams to compactly represent the templates and to perform the cut generation. To obtain the lower bound, we embed our cut generation procedure into a Lagrangian Relax-and-Cut scheme. We incorporate our lower bounds as a node evaluation function in a conflict-based search procedure, and experimentally evaluate its effectiveness.

Q&A session (starts at 16:30)

ABSTRACT. The degree-constrained minimum spanning tree problem, which involves finding a minimum spanning tree of a given graph with upper bounds on the vertex degrees, has found multiple applications in several domains. In this paper, we propose a novel CP approach to tackle this problem where we extend a recent branch-and-bound approach with an adaptation of the LKH local search heuristic to deal with trees instead of tours. Every time a solution is found, it is locally optimised by our new heuristic, thus yielding a tightened cut. Our experimental evaluation shows that this significantly speeds up the branch-and-bound search and hence closes the performance gap to the state-of-the-art bottom-up CP approach.

Q&A session (starts at 16:30)

ABSTRACT. This paper addresses a single machine scheduling problem with non-preemptive jobs to minimize the total electricity cost. Two latest trends in the area of the energy-aware scheduling are considered, namely the variable energy pricing and the power-saving states of a machine. Scheduling of the jobs and the machine states are considered jointly to achieve the highest possible savings. Although this problem has been previously addressed in the literature, the reported results of the state-of-the-art method show that the optimal solutions can be found only for instances with up to 35 jobs and 209 intervals within 3 hours of computation. We propose an elegant pre-processing technique called SPACES for computing the optimal switching of the machine states with respect to the energy costs. The optimal switchings are associated with the shortest paths in an interval-state graph that describes all possible transitions between the machine states in time. This idea allows us to implement efficient integer linear programming and constraint programming models of the problem while preserving the optimality. The efficiency of the models lies in the simplification of the optimal switching representation. The results of the experiments show that our approach outperforms the existing state-of-the-art exact method. On a set of benchmark instances with varying sizes and different state transition graphs, the proposed approach finds the optimal solutions even for the large instances with up to 190 jobs and 1277 intervals within an hour of computation.

Q&A session (starts at 18:45)

ABSTRACT. The cyclic hoist scheduling problem (CHSP) is a well-studied optimisation problem due to its importance in industry. Despite the wide range of solving techniques applied to the CHSP and its variants, the models have remained complicated and inflexible, or have failed to scale up with larger problem instances. This paper re-examines modelling of the CHSP and proposes a new simple, flexible constraint programming formulation. We compare current state-of-the-art solvers on this formulation, and show that modelling in a high-level constraint language leads to both a simple, generic model and to computational results that outperform the state of the art. We further demonstrate that combining integer programming and lazy clause generation, using the multiple cores of modern processors, has potential to improve over either solving approach alone.

Q&A session (starts at 18:45)

ABSTRACT. We address a two-machine no-wait flowshop scheduling problem where setup times are stochastic which could be due to a wide range of factors in manufacturing process, Gonzalez-Neira et al (2017), Wang and Choi (2012). In some real-life production environments, having consecutive operations (no-wait process) is a must, e.g., pharmaceutical, chemical, and plastic industries, Allahverdi (2016), Hall and Sriskandarajah (1996). Moreover, resources used in production need to be arranged before staring a new task. The time needed for this arrangement is defined as setup time which is not always known in advance, Allahverdi (2015). Moreover, minimizing maximum lateness also known as Lmax is vital to reduce the late penalty fees and loss of customer satisfaction. Therefore, minimizing Lmax in a no-wait environment with unknown setup times is important. We first establish a new dominance relation and show that it is, on average, more than 80 % efficient than the existing one in the literature. Moreover, since the problem is NP-hard and infinite possible realizations are possible, it is very unlikely to have an optimal solution for problems of reasonable size by only utilizing dominance relations. There exists no algorithm in the literature for the considered problem, therefore we propose constructive algorithms to minimize the maximum lateness. The performances of the proposed algorithms are evaluated based on extensive simulations. The numerical results show that all the algorithms are at least 15 % better than a benchmark solution. Moreover, we also find that the best performing algorithm is at least 100 % better than the worst one. The average computational time of the newly proposed algorithm is less than a second. Therefore, the proposed algorithm is efficient in reducing the error and also fast.

Q&A session (starts at 18:45)

ABSTRACT. The profitability of any assembly robot installation depends on the production throughput, however it depends to an even greater extent on incurred costs. Most of the cost comes from manually designing the layout and programming the robot as well as production downtime. With ever smaller production series, fewer products share this cost. In this work, we present the dual arm assembly program as an integrated routing and scheduling problem with complex arm-to-arm collision avoidance. We also present a set of high-level layout decisions, and we propose a unified CP model to solve the joint problem. The model is evaluated on realistic instances and real data. The model finds high-quality solutions in short time, and proves optimality for all evaluated problem instances, which demonstrates the potential of the approach.

Q&A session (starts at 18:45)

ABSTRACT. Batch scheduling is a common problem faced in industrial scheduling when groups of jobs must be processed consecutively or simultaneously on the same resource. Motivated by the composites manufacturing industry, we present a complex batch scheduling problem combining two-stage bin packing with hybrid flowshop scheduling. We propose five solution approaches: a constraint programming model, a three-phase logic-based Benders decomposition model, an earliest due date heuristic, and two hybrid heuristic/constraint programming approaches. We then computationally test these approaches on generated problem instances modelled on real-world instances. Numerical results show that heuristic approaches perform comparably to the mathematical models, especially on large instances. The relative success of a simple heuristic suggests that such problems form an interesting challenge for further research in mathematical and constraint programming.

Q&A session (starts at 18:45)

ABSTRACT. We propose a combination of centralized and decentralized approaches to solve the problem of aircraft turnaround scheduling and ground services team/equipment planning in an airport. We first ensure global optimality in terms of minimal delays at the airport level by solving a resource-constrained project scheduling problem (RCPSP). Second, we give the chance to each service provider to allocate their own teams/vehicles to flights in a decentralized way, independently from one another, by letting each use their own specific constraints and objectives. This is modeled either as a multiple traveling salesman problem with time-windows (mTSPTW), or as a vehicle routing problem with time-windows (VRPTW). We propose a lexicographic approach to solve the problem, where we take advantage of both constraint programming (CP) and mixed integer programming (MIP) solvers. We also exploit these models in a matheuristic approach based on large neighborhood search used to reach good solutions in reasonable time for big instances. Unlike the classical VRP objective of minimizing traveling time, we maximize the total slack time between team visits in order to empower robustness. This means there will be enough idle time between visits to absorb most of the minor delays and variations on many factors such as the time to complete single tasks in the aircraft turnaround, aircraft arrival time, etc. The robustness of solutions is then assessed on a discrete-event simulation model. We validate our approach with data provided by a major ground handling company for a day of operations at Barcelona airport.

Q&A session (starts at 18:45)

ABSTRACT. Despite the significative progress made in scheduling in the past years, industrial problems with several hundred tasks remain intractable. We present techniques that can be used to leverage the power of constraint programming to solve an industrial problem with 600 non-preemptive tasks, 90 resources, and sequence-dependent setup times. Our method involves solving the traveling salesperson problem (TSP) as a relaxation of the scheduling problem and using the relaxed solution to guide the branching heuristics. We also explore large neighborhood search. Experiments conducted on a dataset provided by our partner from the textile industry show that we obtain non-optimal but satisfactory solutions.

Q&A session (starts at 18:45)

ABSTRACT. Factor models are central to understanding risk-return trade-offs in finance. Since Fama and French (1993), hundreds of factors have been found to have explanatory power for asset pricing. To construct a factor model, two tasks have to be performed: Feature Selection, selecting a small subset given a large number of factors to overcome overfitting in regression, and Feature Engineering, determining the interactions between the factors. In this work, the process of constructing factor models (not the factors themselves) is examined. A unified, two-step process of dimensionality reduction and nonlinear transformation that produces parsimonious, general factor models is proposed. Comparisons between linear, LASSO- and MIP-based formulations for feature selection models, as well as non-linear feature reduction techniques, are conducted. A second stage generalizes the models by learning nonlinear interactions. Results of computational experiments, on historical financial data, suggest that MIP-based formulations are suitable for the task of financial factor selection and that the second-stage nonlinearity improves accuracy.

Q&A session (starts at 18:45)