ABSTRACT. This paper introduces, for the first time, a complete symmetry breaking constraint of polynomial size for a significant class of graphs: the class of uniquely Hamiltonian graphs. We introduce a canonical form for uniquely Hamiltonian graphs and prove that testing whether a given uniquely Hamiltonian graph is canonical can be performed efficiently. Based on this canonicity test, we construct a complete symmetry breaking constraint of polynomial size which is satisfied only by uniquely Hamiltonian graphs which are canonical. We apply the proposed symmetry breaking constraint to show new results regarding the class of uniquely Hamiltonian graphs. Given that it is unknown if there exist polynomial sized complete symmetry breaking constraints for graphs, this paper makes a first step in the direction of identifying specific classes of graphs for which such constraints do exist.

ABSTRACT. Linear modular constraints are a powerful class of constraints that arise naturally in cryptanalysis, checksums, hash functions, and the like. Given their importance, the past few years have witnessed the design of combinatorial solvers with native support for linear modular constraints, and the availability of such solvers has led to the emergence of new applications. While there exist global constraints in CP that consider congruence classes over domain values, linear modular arithmetic constraints have yet to appear in the global constraint catalogue despite their past investigation in the context of model counting for CSPs. In this work, we seek to remedy the situation through a theoretical and empirical investigation of the integration of linear modular constraints into state-of-the-art CP solvers. Contrary to previous belief, we conclude that Gauss-Jordan Elimination based techniques can provide an efficient and scalable way to handle linear modular constraints. On the theoretical side, we first remark on the pairwise independence offered by hash functions based on linear modular constraints, and then discuss the design of hashing-based model counters for CP, supported by empirical results showing the accuracy and computational savings that can be achieved. We further demonstrate the usefulness of the native support for linear modular constraints with an application to checksums.

ABSTRACT. The subgraph isomorphism problem is to find a small ``pattern'' graph inside a larger ``target'' graph. There are excellent dedicated solvers for this problem, but they require substantial programming effort to handle the complex side constraints that often occur in practical applications of the problem; however, general purpose constraint solvers struggle on more difficult graph instances. We show how to combine the state of the art Glasgow Subgraph Solver with the Minion constraint programming solver to get a ``subgraphs modulo theories'' solver that is both performant and flexible. We also show how such an approach can be driven by the Essence high level modelling language, giving ease of modelling and prototyping to non-expert users. We give practical examples involving temporal graphs, typed graphs from software engineering, and costed subgraph isomorphism problems.

ABSTRACT. We address the problem of verifying a constraint by a set of solutions $S$. This problem is present in almost all systems aiming at learning or acquiring constraints or constraint parameters. We propose an original approach based on MDDs. Indeed, the set of solutions can be represented by the MDD denoted by $MDD_S$ . Checking whether $E$ satisfies a given constraint $C$ can be done using $MDD_C$, the MDD that contains the set of solutions of $C$, and by searching if the intersection between $MDD_S$ and $MDD_C$ is equal to $MDD_S$. This step is equivalent to searching whether $MDD_S$ is included in $MDD_C$. Thus, we give an inclusion algorithm to speed up these calculations. Then, we generalize this approach for the computation of global constraint parameters satisfying $E$. Next, we introduce the notion of properties on the MDD nodes and define a new algorithm allowing to compute in only one step the set of parameters we are looking for. Finally, we present experimental results showing the interest of our approach.

ABSTRACT. This paper studies an inter-modal freight transportation problem, motivated by a real-life application regarding a large EU logistics' provider. The problem is comprised by three consecutive stages, namely a) disposition, where orders are picked up by trucks and, after a custom clearance process, are transferred and unloaded to a set of warehouses in Central and Eastern Europe, b) inter-region transport, where the orders are packed into trailers, which are shipped to warehouses in Turkey using different inter-region transport modes, and c) last-mile delivery, where the orders unloaded at the warehouses in Turkey are picked up by vans and delivered to their final destination. The objective is to minimise total transport and tardiness cost. We focus on the design of exact methods, capable to handle large real instances in reasonable time. For that purpose, we formulate a quite elaborate mixed-integer linear program that captures the entire delivery process, under some simplifying assumptions. Taking advantage of the block structure of this model, we offer a Benders' decomposition and prove the validity of a set of optimality cuts and of a subproblem relaxation. We show the impact of this approach on large-scale real instances under user-imposed time limits. Strengthening the master problem with a set of valid inequalities improves significantly both solution quality and running time. The running time can be reduced further by using Constraint Programming for the subproblem.

ABSTRACT. As for any decomposition method, the computational performance of a logic-based Benders decomposition (LBBD) scheme relies on the quality of the feedback information. Therefore, an important acceleration technique in LBBD is to strengthen feasibility cuts by reducing their sizes. This is typically done by solving additional subproblems to evaluate potential cuts. In this paper, we study three strengthening algorithms that differ in the computational efforts made to find stronger cuts and in the guarantees with respect to the strengths of the cuts. In a computational evaluation, we highlight the trade-off between the time spent on the strengthening of the cuts and the cuts' impact on the progress of the LBBD scheme. This evaluation is made for three different problem formulations, using over 2000 instances from five different applications. Our results show that it is usually beneficial to invest the time needed to obtain irreducible cuts. In particular, the use of the depth-first binary search cut-strengthening algorithm gives a good performance. Another observation is that when the subproblem can to be separated into small independent problems, the impact of cut strengthening is dominated by that of the separation, which has an automatic strengthening effect.

ABSTRACT. This contribution deals with the development of a Constraint Programming (CP) and temporal decomposition based solution strategy for a two-stage industrial formulation plant with parallel production units for crop protection chemicals. Optimal scheduling of this plant is difficult, due to the number of units and operations that have to be scheduled while at the same time a high degree of coupling between the operations is present due to the need for synchronizing charging and discharging operations. The problem is further complicated by the presence of optional intermediate storage that leads to alternative branches in the processing sequence of the products. In the investigated problem setting several parallel, non-identical formulation lines, that each consist of three formulation tanks that are fed by a single pre-processing unit per line, produce several intermediates. These intermediates are filled into a variety of types of final containers by parallel, non-identical filling units, operating in a quasi-continuous manner. All intermediates can be stored temporarily in the formulation tanks or in buffer tanks with limited capacity prior to being filled. The buffer tanks are used to decouple the two stages, to increase the capacity utilization of the overall plant. Further characteristics of the production process include sequence- and unit-dependent changeover times, eligibility constraints on the formulation and filling units, synchronization of charging and discharging operations, shift constraints, and unit-dependent processing rates. The demand is known at the beginning of the scheduling horizon and no release or due date related constraints are present. The test problem that is derived from the industrial system includes 21 formulation tanks, 8 filling stations as well as 5 buffer tanks. 78 batches, each consisting of a formulation, a filling, and an optional storing operation, have to be scheduled. The case study has already been investigated by Yfantis et al. (2019). There, Mixed-Integer Linear Programming (MILP) was employed together with a decomposition strategy, and an identical problem instance could be solved for a scheduling horizon of one week. CP has shown to be a promising solution technique on a variety of benchmark problems and industrial cases (Ku and Beck, 2016, Laboire, 2018, Ezra and Zhu, 2019). Its advantages are its rich mathematical syntax, its ability to exploit domain-specific knowledge to improve the search process, and eventually its computational performance on scheduling problems in general. The CP model developed here leads to smaller computation times than the MILP approach for small problem instances of the scheduling problem under consideration. However, solving large-scale instances in a monolithic fashion is infeasible also using CP. Therefore a decomposition algorithm is employed where the overall set of batches is divided into subsets which are scheduled iteratively, fixing scheduling decisions made in previous iterations and reducing the set of feasible time points for subsequent iterations. The partial schedules that result from solving the subproblems are then concatenated to yield the full schedule (cf. Elkamel et al., 1997). The number of batches that are scheduled in each iteration can be chosen by balancing the solution time against the schedule quality. In every iteration, a two-step solution procedure is employed. The first step of each iteration is a makespan optimization, which can be solved computationally efficiently in the CP setting, followed by an optimization of the total completion time in which the makespan is fixed to the previously obtained value. This is necessary to avoid the introduction of delays on some units which do not influence the makespan but reduce the efficiency of the operation of the plant as they cannot be removed in the subsequent iterations. Constraint propagation is known to perform better on max-type objectives, such as makespan, than on sum-type objectives such as completion time (Kovács and Beck, 2011). Therefore the preliminary makespan optimization speeds up the solution procedure noticeably. The decomposition algorithm has been implemented in a moving-horizon fashion, similar to model-predictive control. In each iteration, first a number of batches are scheduled, and the batches with the largest completion times on the filling lines are removed from the solution. The allocation and timing decisions for the remaining batches are fixed for the formulation tanks, filling lines, and buffer tanks. The removed batches are added to the list of batches to be scheduled in the next iteration. In Yfantis et al. (2019) a similar two-step optimization procedure without a moving-horizon approach, was used as the problem could also not be solved using a monolithic approach. Even with the decomposition approach, a computation time of 4.5 hours was required to solve the subproblems to optimality and to obtain a full schedule. The approach did not take advantage of a moving-horizon implementation, all batches scheduled within one iteration were fixed and the sets of batches scheduled in consecutive iterations did not intersect. We compare identical problem instances and decomposition approaches for the MILP and CP formulations and further compare the simple sequential procedure to the moving-horizon approach. The results show that the CP model outperforms the MILP model in terms of computation time while guaranteeing the optimality of the obtained solutions of the subproblems. The moving-horizon approach yields additional improvements in terms of solution quality.

References 1. Baptiste, P., Le Pape, C., Nuijten, W., Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, International Series in Operations Research & Management Science, 2001 2. Kovács, A., Beck, J. C., A global constraint for total weighted completion time of unary resources, Constraints, 16, 1, 100-123 (2011) 3. Elkamel, A., Zentner, M., Pekny, J. F., Reklaitis, G. V., A Decomposition Heuristic for Scheduling the General Batch Chemical Plant, Engineering Optimization, 28, 4, 299-330 (1997) 4. Ezra, W., Zhu, W., A Constraint Programming model for food processing industry: a case for an ice cream processing facility, International Journal of Production Research, 57, 21, 6648-6664 (2019) 5. Ku, W. Y., Beck, J. C., Mixed Integer Programming models for job shop scheduling: A computational analysis, Computers and Operations Research, 73, 165-173 (2016) 6. Laborie, P., An Update on the Comparison of MIP, CP and Hybrid Approaches for Mixed Resource Allocation and Scheduling, 15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 10848, 403-411 (2018) 7. Yfantis, V., Siwcyk, T., Lampe, M., Kloye, N., Remelhe, M., Engell, S., Iterative Medium-Term Production Scheduling of an Industrial Formulation Plant, Computer Aided Chemical Engineering, 46, 19–24 (2019)

ABSTRACT. The Storage Location Assignment Problem in warehousing have been soldomly tackled by exact methods when considering the exact demand over a time horizon (e.g. the set of orders with different items to retrieve). In this presentation we present a novel extended formulation of the problem that is independant from both : i. the warehouse layout and ii. The picker routing policy. These two aspects are convexified in the subproblems. This formulation is solved by a column-generation algorithm with decomposed pricing problems. Several polynomial and exponential families of valid inequalities are derived to enhance the resolution framework. Preliminary results show a major improvement of the dual bound between a compact mixed-integer formulation and the extended one. Further work is ongoing to integrate the column generation algorithm in a competitive Branch-and-Price-and-Cut solution method.

ABSTRACT. This paper proposes two deadline adjustment techniques for scheduling non preemptive tasks subject to precedence relations, release dates and deadlines on a limited number of processors. This decision problem is denoted by P| prec, r_i, d_i|* in standard notations. The first technique is an extension of the Garey and Johnson algorithm that integrates precedence relations in energetic reasoning. The second one is an extension of the Leung, Palem and Pnueli algorithm that builds iteratively relaxed preemptive schedules to adjust deadlines.

The implementation of the two classes of algorithms is discussed and compared on randomly generated instances. We show that the adjustments obtained are slightly different but equivalent using several metrics. However, the time performance of the extended Leung, Palem and Pnueli algorithm is much better than that of the extended Garey and Johnson ones.

ABSTRACT. It is well-known that experience can lead to increased efficiency, yet this is largely unaccounted for in project scheduling. We consider project scheduling problems where the duration of activities can be reduced when scheduled after certain other activities that allow for learning relevant skills. Since per-period availabilities of renewable resources are limited and precedence requirements have to be respected, the resulting optimization problems generalize the resource-constrained project scheduling problem. We introduce four constraint programming formulations that incorporate the alternative learning-based job durations via logical constraints, dynamic interval lengths, multiple job modes, and a bi-objective reformulation, respectively. To provide tight optimality gaps for larger problem instances, we further develop five lower bounding techniques based on model relaxations. We also devise a destructive lower bounding method. We perform an extensive computational study across thousands of instances based on the PSPlib to quantify the impact of project size, potential learning occurrences, and learning effects on the optimal project duration. In addition, we also compare formulation strength and quality of the obtained lower bounds using a state-of-the-art constraint programming solver.

ABSTRACT. Single-machine scheduling where jobs have a penalty for being late or for being rejected altogether is an important (sub)problem in manufacturing, logistics, and satellite scheduling. It is known to be NP-hard in the strong sense, and there is no polynomial-time algorithm that can guarantee a constant-factor approximation (unless P=NP). We provide an exact algorithm that is fixed-parameter tractable in the slack and the maximum number of time windows overlapping at any point in time, i.e., the width. This algorithm has a runtime exponential in these parameters, but quadratic in the number of jobs, even when modeling sequence-dependent setup times. We further provide a fixed-parameter fully-polynomial time approximation scheme (FPTAS) with only this width as a parameter, having a runtime bound that is cubic. Finally, we propose a neighbourhood heuristic similar to the Balas-Simonetti neighbourhood. All algorithms use an efficient representation of the state space inspired by decision diagrams, where partial solutions that are provably dominated are excluded from further consideration. Experimental evidence shows that the exact method significantly outperforms the state-of-the-art on instances where the width is smaller than one third of the number of jobs and finds optimal solutions to previously unsolved instances. The FPTAS is competitive to state-of-the-art heuristics only when the width is significantly smaller, but the neighbourhood heuristic outperforms most other heuristics in runtime or quality.

ABSTRACT. Cable trees are used in industrial products to transmit energy and information between different product parts. To this date, they are mostly assembled by humans and only few automated manufacturing solutions exist using complex robotic machines. For these machines, the wiring plan has to be translated into a wiring sequence of cable plugging operations to be followed by the machine. In this paper, we study and formalize the problem of deriving the optimal wiring sequence for a given layout of a cable tree. We summarize our investigations to model this cable tree wiring problem (CTW) as a traveling salesman problem with atomic, soft atomic, and disjunctive precedence constraints as well as tour-dependent edge costs such that it can be solved by state-of-the-art constraint programming (CP), Optimization Modulo Theories (OMT), and mixed-integer programming (MIP) solvers. It is further shown, how the CTW problem can be viewed as a soft version of the coupled tasks scheduling problem. We discuss various modeling variants for the problem, prove its NP-hardness, and empirically compare CP, OMT, and MIP solvers on a benchmark set of 278 instances. The complete benchmark set with all models and instance data is available on github and was included in the MiniZinc challenge 2020.