The constraint programming community has intensively studied the concept of consistency as a means to reduce backtracking. We show how cutting planes can achieve a form of consistency by excluding inconsistent partial assignments -- that is, partial assignments that cannot be extended to a full feasible assignment. This leads to a reinterpretation of cutting planes as a consistency maintenance mechanism rather than a means of strengthening bounds. We find that cuts selected for this task can, at least in some contexts, reduce branching search more effectively than traditional separating cuts. In fact, traditional branch-and-cut algorithms can benefit from this feature of cutting planes even while using them to tighten bounds. Consistency concepts may therefore offer a new perspective on integer programming that can lead to a better understanding of what makes branching methods work.

We study a multi-period home health care routing and scheduling problem (HHCRSP), which requires consistent assignment of care workers and visit times for each patient. This problem is similar to the consistent vehicle routing problem (ConVRP), known as NP-hard. The uncertainty in travel and service times is a real-world assumption, which makes finding consistent routes and schedules even more challenging. This paper proposes a novel approach that integrates stochastic travel and service times into the deterministic consistent HHCRSP through a chance-constraint approach. We model these chance-constraints in two ways: a scenario-based and an extreme value theory-based (ETV-based) approximation. To solve practical-sized instances of this problem, we decompose it into a master problem (MP) and a set of subproblems (SP). We use branch-and-check (B&Ch) to solve the MP through mixed integer linear programming and the SPs through constraint programming. Our computational experiments demonstrate that our stochastic models, especially the ETV-based approximation model, outperform the deterministic model in terms of service levels at a low cost. We study the efficiency of this approach under different types of uncertainty.

This talk introduces C++DDOpt, a C++ library offering both a modeling and a solving interface for solving combinatorial optimization problems using decision diagram-based optimization solvers. Currently this optimization technology is accessible via lower-level programming languages which limits easy modeling experimentation and wider adoption. C++DDOpt allows to represent state-based models in an intuitive manner. These models are specifications which are used to automatically compile relaxed and restricted decision diagrams, as well as the search process. We demonstrate the functionality of C++DDOpt on a variety of classic combinatorial optimization problems and demonstrate its effectiveness.