Modeling Rostering Problems in SAT,
Valentin Mayer-Eichberger.
Automatic creation of feasible rosters is a hard search problem. In this talk I want to share my experience in modeling a real industrial rostering problem in SAT.
Aside from some motivation and introduction for this project, I want to categorize requirements for rostering and present some "tricks of the trade" in modeling for SAT solving. I believe that these types of tricks could lead to some kind of methodology in Boolean modeling.
An Optimal Arc Consistency Algorithm for the AtMostSeqCard Constraint,
Mohamed Siala.
The AtMostSeqCard constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n-q+1 constraints Atmost u on each subsequence of size q.
This constraint is useful in car-sequencing and crew-rostering problems. In [van Hoeve et al. 2009], two algorithms designed for the AmongSeq constraint were adapted to this constraint with a O(2^q . n) and O(n^3) worst case time complexity, respectively. In [Maher et al. 2008], another algorithm similarly adaptable to filter the AtMostSeqCard constraint with a time complexity of O(n^2) was proposed.
In this talk, we introduce an algorithm for achieving Arc Consistency on the AtMostSeqCard constraint with a O(n) (hence optimal) worst case time complexity. We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problmes.
Constraint-based Code Generation (Part I),
Gabriel Hjort Blindell.
Code generation is one of the oldest computer science problems where high-level
programs are translated into assembly code targeting a specific processor. Since
code generation consists of several interdependent NP-complete tasks,
conventional compilers solve each task separately using non-optimal heuristics.
In this presentation we introduce a constraint-based approach to code generation
where these tasks are captured by a unified model. This allows a more flexible
approach to code generation where all tasks are solved simultaneously. We
describe how to model instruction selection with constraints. Joint work
with Roberto Castañeda Lozanor,
Mats Carlsson,
Frej Drejhammar and
Christian Schulte.
Constraint-based Code Generation (Part II),
Roberto Castañeda Lozanor.
Joint work
with Gabriel Hjort Blindell,
Mats Carlsson,
Frej Drejhammar and
Christian Schulte.
15.20-16.00 Coffee break
16.00-17.40 Network and Routing Problems
Using Constraint Programming to Find Solutions to the Virtual Network Mapping Problem with Delay, Routing and Location Constraints,
Johanne Inführ and Günther Raidl.
The Virtual Network Mapping Problem with Delay, Routing
and Location constraints arises in the context of Future Internet research.
Multiple virtual networks with different characteristics are created to suit
specific applications. These virtual networks, with all of the resources
they require, need to be realized in one physical network. In this work,
we use Constraint Programming to find solutions to this problem. We
refine a basic Constraint Programming approach by utilizing customized
branching and propagation strategies and propose a hybridization with
Integer Linear Programming, the result of which outperforms both pure
techniques.
Constraint Programming for Path Planning with Uncertainty: Solving the Optimal Search Path problem, Michael Morin.
The optimal search path (OSP) problem is a single-sided detection search problem where the location and the detectability of a moving object are uncertain. A solution to this NP-hard problem is a path on a graph that maximizes the probability of finding an object that moves according to a known motion model. We developed constraint programming models to solve this probabilistic path planning problem for a single indivisible searcher. These models include a simple but powerful branching heuristic as well as strong filtering constraints. We present our experimentation and compare our results with existing results in the literature. The OSP problem is particularly interesting in that it generalizes to various probabilistic search problems such as intruder detection, malicious code identification, search and rescue, and surveillance. Joint work with
Anika-Pascale Papillon,
Irène Abi-Zeid,
François Laviolette and
Claude-Guy Quimper.
A constraint programming based approach for planning milk runs,
Anne Meyer.
Milk runs - a logistics concept of lean manufacturing - can
be modelled as a Periodic Vehicle Routing Problem (PVRP) with additional
requirements on regularity and robustness. We propose a CP
formulation for PVRPs based on an existing VRP model, which can be
easily extended. Furthermore, we suggest a CP based Parallel Insertion
Heuristic to construct feasible starting solutions and a Large Neighborhood
Search as a local search improvement technique. For the latter we
present different adaptions to the PVRP case, amongst them a new relatedness
measure improved with regard to (client specic) side constraints.
Robust Network Design using Inverse Programming,
Christina Burt.
We study a long-term network design problem involving selecting mode of transport, new hubs and capacity expansion opportunities. As a strategic problem, the ideal solution would instruct decision makers of the best timing to incorporate new transport modes and hubs. Modelled as a capacitated multi-commodity flow problem with side constraints on a time-space network, this problem is computationally difficult to solve even for the deterministic case, on a practical time scale. In this talk, we use powerful optimisation tools to determine useful information about the solution space, which is nondeterministic. We present an inverse programming approach to determine the cost vectors that would make proposed solutions optimal and show how these vectors can aid good decision making.
New exact formulation for the variation of Traveling Salesman Problem, ATSP, m-TSP and STSP based on a Transshipment Problem, Nahid Jafari.
The traveling salesman problem (TSP) is a much-studied NP-hard problem in combinatorial optimization in which the aim is to determine the least cost Hamiltonian cycle (tour) in a given
network. The TSP is widely studied for its outward simplicity, its mathematical challenges and its practical application to problems in routing, scheduling, and manufacturing.
Many current solution methods for the TSP use an integer programming (IP) formulation in which a binary variable is used to indicate whether a particular arc is included in the tour. In this approach, the TSP (or ATSP) problem is often written in the form of an assignment problem (AP). In contrast, in this work we present a novel IP formulation which treats the ATSP problem as a transshipment problem.
From the literature, it is clear that the AP-based algorithms perform very well in those instances in which the distance/cost matrix contains uniformly randomly generated integers. However, it has been observed (Fischetti 1997) that a class of ATSP problems, including certain real world instances cannot be solved efficiently by standard IP methods such as branch and bound.
The main purpose of this work is to present a novel, exact model which provides a solution to the ATSP and the other variations of the TSP, and which is competitive with existing AP methods. We propose an innovative formulation for the ATSP using the concept of a transshipment problem. We then extend our formulation to address the "Multi-Traveling Salesman problem" (m-TSP) and the "Selective Traveling Salesman Problem" (STSP).
Joint work with John Hearne and Ian Groundy.
18.00-18.40 Stochastic approaches
A Two-Phase Stochastic Mixed-Integer Programming Based Approach for
Empty Container Coordination Management, Hosein Khakbaz.
Empty containers need to be repositioned globally between seaports and regionally between consignees, inland depots and terminals in order to fulfil the overall empty container demand. It has been reported that the cost of repositioning empty container accounting for 27 percent of the total world fleet running cost. Previous research has focused primarily on empty container repositioning between seaports or on inland empty container repositioning. However, little research has been conducted on the coordination mechanisms of empty container repositioning from overseas ports and inland positioning in an uncertain environment.
This paper develops a semi-centralised two-phase stochastic mixed-integer model for operational coordination management of empty containers in a multi-community, multi-level, multi-period shipping network .The proposed model not only ensures an efficient and rational allocation of empty containers in the shipping network but also tries to optimise the local operations. The overall model consists of two phases. First, head quarter makes weekly decision about the target resource delivery to the ports. This phase is performed by a mixed-integer multistage stochastic linear optimisation model based on weekly information from all ports. These decisions make a framework for operational real time decisions at the local level. Then, after receiving this framework about the target delivery of the week, the ports develop their own empty container management policy by a linear multi-criteria, multi-stage, stochastic programming model at the regional level based on daily information that also takes into account a possible shortfall between the target delivery and actual demand while keeping balanced flow of the whole network.
The utilization of the proposed model is demonstrated with a real case consisting of 8 ports, 5 routes in 5 weeks time. The results illustrate that the proposed semi-centralised two-phase stochastic coordination model assists shipping companies to better satisfy empty container demands under uncertain parameters.
Transmission Loss modelling for Short Term Operational Planning of Power Systems, Appalasamy Sashirekha, Jones Owen Dafydd,
Gan Heng Soonh, Moin Noor Hasnah and Tan Ching Sin.
Two major and crucial power system short term operation and planning problems
are the unit commitment(UC) and economic dispatch(ED) . UC is the problem of
determining the optimal set of generating units to be in service during a scheduling
period, and also for how long they are to be in service whereas ED is the problem of
determining an economic distribution of the generation for a given schedule in a static environment. Both of these problems are modelled as an aggregated supply and demand problem, therefore the accuracy of the transmission loss model used in the problem is crucial to ensure the optimality and feasibility of the solution. Due to the current increasing penetration of renewable energies into the power system, uncertainties in the power system planning has increased ,adding greater error to solutions obtained through deterministic approaches. Hence, we are currently looking into statistical modelling techniques to model the transmission loss. Past approaches had applied an assumption based theoretically developed formula that approximates the true loss. Hypothetically our developed model would be at least as accurate as the theoretical models but with an enhanced computational time for a volatile demand. This model would than be embedded into our final UC and ED stochastic optimization model. Simulations of power flow are currently carried out using MATPOWER on a benchmark problem with 9 nodes consisting of 3 generator nodes and 6 demand nodes. Current results are reported.