A well known technique to reduce the search space in integer programming is known as variable fixing or reduced cost strengthening . The reduced costs given by an optimal dual solution of the linear relaxation can be used to strengthen the bounds of the variables but this filtering is incomplete. We show how reduced costs can be used to achieve Arc-Consistency (AC), i.e. a complete filtering, of a global constraint with a cost variable and an assignment cost for each value. We assume that an ideal Integer Linear Programming (ILP) formulation is available i.e. the convex hull of the characteristic vectors of the supports is known. A detailed analysis of reduced cost based filtering is proposed. We characterize arc-consistency based on complementary slackness i.e. completeness of reasoning as opposed to only optimality. We also give a simple sufficient condition allowing a set of dual solutions to ensure arc-consistency through reduced costs. In practice, when the constraint has a such an ideal ILP, n dual solutions are always enough to achieve AC (where n is the number of variables of the global constraint). It extends the work presented in [26] for satisfaction problems and in [17] for the specific case of the minimum weighted alldifferent constraint. Our analysis is illustrated on constraints related to the assignment and shortest path problem and also demonstrated on the weighted stable set problem in chordal graphs. A novel AC algorithm is proposed in this latter case based on reduced costs.

A convex partition of a point set P in the plane is a planar partition of the convex hull of P into empty convex polygons or internal faces whose extreme points belong to P. In a convex partition, the union of the internal faces give the convex hull of P and the interiors of the polygons are pairwise disjoint. Moreover, no polygon is allowed to contain a point of P in its interior. The problem is to find a convex partition with the minimum number of internal faces. The problem has been shown to be NP-hard and was recently used in the CG:SHOP Challenge 2020. We propose a new integer linear programming (IP) formulation that considerably improves over the existing one. It relies on the representation of faces as opposed to segments and points. A number of geometric properties are used to strengthen it. Data sets of 100 points are easily solved to optimality and the lower bounds provided by the model can be computed up to 300 points.

An incomplete filtering technique known as variable fixing has been used in integer programming for a long time. It relies on the reduced costs of the variables given by an optimal dual solution of the linear relaxation. Reduced-costs are used to detect some of the 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known. Reduced cost based filtering was introduced in CP for a global constraint referred to as MINIMUM WEIGHT ALLDIFFERENT and to the best of our knowledge, no analysis of this filtering technique has ever been performed. We therefore propose an analysis of reduced costs filtering for this constraint, showing that arc-consistency can be achieved with reduced-costs of n dual solutions and that this bound is sharp. For ALLDIFFERENT, a single dual solution is enough. From a practical side, our end goal is the design of incomplete but anytime primal-dual filtering approaches. We illustrate this idea on the MINIMUM WEIGHT ALLDIFFERENT where a near-complete filtering can be done in shorter times.

We study several generic tree search techniques applied to the Sequential Ordering Problem.This study enables us to propose a simple yet competitive tree search.It consists of an iterative beam search that favors search over inference and integrates prunings that are inspired by dynamic programming.The resulting method proves optimality on half of the SOPLIB instances, 10 to 100 times faster than other existing methods.Furthermore, it finds new best-known solutions on 6 among 7 open instances of the benchmark in a small amount of time.These results highlight that there is a category of problems (containing at least SOP) where an anytime tree search is extremely efficient (compared to classical meta-heuristics) but was underestimated.

The color coding technique is used to solve subgraph isomorphism problems, in particular path problems. One color among C is randomly assigned to each vertex of the graph and if distinct colors are given to the vertices of the desired subgraph, it can be found efficiently by dynamic programming. These two phases are repeated until the subgraph is found with a high probability, which can require a large number of iterations. We propose new coloring strategies that take advantage of the graph structure to increase this probability and thus reduce the number of iterations. They provide a guaranteed improvement over the original color coding technique based on a particular structural parameter related to the bandwidth. When this parameter is smaller than the number C of colors, we prove that only C calls to the dynamic program are needed to find the subgraph.

Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. We analyze the application of Lagrangian decomposition, a classical tool in mathematical programming, to cost partitioning of operator-counting heuristics. This allows us to view the computation as an iterative process that can be seeded with any cost partitioning and that improves over time. In the case of non-negative cost partitioning of abstraction heuristics the computation reduces to independent shortest path problems and does not require an LP solver.

Many problems, and in particular routing problems, require to find one or many circuits in a weighted graph. The weights often express the distance or the travel time between vertices. We propose in this paper various filtering algorithms for the weighted circuit constraint which maintain a circuit in a weighted graph. The filtering algorithms are typical cost based filtering algorithms relying on relaxations of the Traveling Salesman Problem. We investigate three bounds and show that they are incomparable. In particular we design a filtering algorithm based on a lower bound introduced in 1981 by Christophides et al.. This bound can provide stronger filtering than the classical Held and Karp’s approach when additional information, such as the possible positions of the clients in the tour, is available. This is particularly suited for problems with side constraints such as time windows.

Data centre energy requirements have grown massively in the last few years. One of the optimisation challenges for reducing its energy requirements is to keep servers well utilised by deciding which Virtual Machines (VMs) to migrate, where to migrate, when to migrate, and, when and which servers to switch on/off. Achieving this goal optimally requires the capability of predicting the future time-variable resource demands of VMs accurately and computing the plan for migrating VMs for efficient workload consolidation quickly. We call this Proactive Workload Consolidation Problem (PWCP). Solving PWCP as a giant monolithic problem with infinite time windows is impossible both for forecasting demands and optimal assignments of VMs to servers. We formulate PWCP in a more realistic way by defining a time window of a particular size in which the information is known more accurately and solve a - possibly infinite - sequence of optimisation problems moving forwards in time. The question is how far one is required to look ahead in terms of the number time-periods and still retain the minimum energy cost of a given horizon without violating the Service Level Agreements (SLAs). We perform investigations to understand the relationship between the number of time-periods considered in one optimisation step and migration-limits on the SLAs, energy cost, server-transition cost and migration cost. Our results suggest that looking ahead by only a few more time-periods can lead to more efficient resource provisioning over the entire horizon and consequently higher energy efficiency and close to no SLA violations.

We describe a constraint-based timetabling system that was developed for the dental school based at Cork University Hospital in Ireland. This system has been deployed since 2010. Dental school timetabling differs from other university course scheduling in that certain clinic sessions can be used by multiple courses at the same time, provided a limit on room capacity is satisfied. Starting from a constraint programming solution using a web interface, we have moved to a mixed integer programming-based solver to deal with multiple objective functions, along with a dedicated Java application, which provides a rich user interface. Solutions for the years 2010, 2011 and 2012 have been used in the dental school, replacing a manual timetabling process, which could no longer cope with increasing student numbers and resulting resource bottlenecks. The use of the automated system allowed the dental school to increase student numbers to the maximum possible given the available resources. It also provides the school with a valuable “what-if” analysis tool.

This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances.

We present an application focused on the design of resilient long-reach passive optical networks. We specifically consider dual parented networks whereby each customer must be connected to two metro sites via a local exchange sites. An important property of such a placement is resilience to single metro node failure. The objective of the application is to determine the optimal position of a set of metro-nodes such that the total optical fibre length is minimised. We prove that the decision variant of this problem is NP-Complete. We present three alternative combinatorial optimisation approaches to finding an optimal metro node placement using: a mixed integer linear programming formulation of the problem, a hybrid approach that uses clustering as a preprocessing step, and, finally, a local search approach. We consider a detailed case-study based on a network for Ireland. The hybrid approach scales well and finds solutions that are close to optimal, with a runtime that is two orders-of-magnitude better than the MIP model. The local search approach is consistently good on all benchmarks.

We present a novel approach to itemset mining whereby the set of all itemsets are compiled into a compact form, closely related to binary decision diagrams. While there were previous attempts to utilize decision diagrams for storing the set of frequent itemsets this is the first approach that does not rely on backtrack search to generate such a set. Our empirical evaluation demonstrates that our approach is complementary to current approaches.