PhD Defence Thomas Bosman

Bosman, Thomas
Logistics & Operations Research

Dissertation title
Relax, Round, Reformulate: Near-Optimal Algorithms for Planning Problems in Network Design and Scheduling

Date and location
November 26, 2019 at 9:45 in the Aula of the Main Building of the Vrije Universiteit Amsterdam

Relax, Round, Reformulate: Near-Optimal Algorithms for Planning Problems in Network Design and Scheduling
Bosman, ThomasThree chapters of this thesis are based on published papers. One chapter contains unpublished results.
In Chapter 1 we study the masked VPN problem. This problem deals with routing uncertain and varying traffic patterns in a network. We are given a set of terminals in a network G, together with a second graph H on the terminals (the mask graph) that encodes which terminal pairs might communicate with each other. Every terminal has a standardized, unit capacity connection with the network it may use to communicate with other terminals at any time. For every commmlicating terminal pair (according to H), we need to pick a connecting path through the network G. Subsequently we must install sufficient capacity in the network such that every traffic pattern that is feasible under these constraints can be routed via the predetermined paths. The masked VPN problem asks for a minimum cost solution to this problem.
The masked VPN problem generalizes the VPN problem, which can be seen as a special case where every terminal pair communicates, or H is a clique. This problem has an elegant polynomial time solution that looks like a star embedded into the network.
While such results are out of the question for general H (when H is star, the problem reduces to the APX-hard Steiner tree problem), we establish an analogous theorem for H a cycle. In this case, the optimal solution looks like a cycle with spokes embedded into the network, a topology that can be optimized in polynomial time using dynamic programing. We also show that the problem is solvable in polynomial time for H a tree of bounded degree, generalizing a known result for Steiner tree with a bow1ded number of terminals.
In Chapter 2 we look at subadditive inventory problems, including the well-studied inventory routing problem (IRP) and the submodular joint replenishment problem (SJRP). In subadditive inventory problems, N nodes need to be served over some finite time horizon 1, ..., T. Multiple nodes may be served simultaneously, and the cost for this is expressed by some subadditive ordering cost function. Demand can be served exactly on time, or at any point prior to that, in which case a holding cost needs to be paid for the intervening period. The goal is to balance these cost factors so as to minimize the total cost of the schedule. The IRP is the special case of this problem where the ordering cost are induced by the cost of a minimum length route serving all nodes from some depot.
The submodular joint replenishment problem is the case where the ordering cost function is submodular. We provide the first sublogarithmic approximation algorithm for these two problems, both attaining an approximation ratio of O(log log min(N, T)). This improves the previous best known O(log N), O(log T) approximation ratios (using two different algorithms), as well as the O(log T / log log T) approximation algorithm for the special case of polynomial holding cost. We also provide general purpose results for the subadditive inventory problem, bounding the length of the time horizon in terms of the number of nodes N, unifying approximation ratios for both parameters in a single algorithm.
In Chapter 3 we study replenishment problems with fixed turnover times (RFTT). Here, we consider a metric with client that need to be replenished (repeatedly) over an infinite time horizon. After each replenishment, the nodes will need to be revisited within a fixed time period. Consequently, the effect of visiting a client early propagates, i.e. the next visit will also need to happen earlier. This property differentiates the RFTT from models typically studied in literature. The study of the RFTT is motivated by applications in practice for which the fixed turnover time is more natural, for example the replenishment of ATMs. After every replenishment an ATM has a full stock of cash, which starts depleting at a steady rate immediately. The ATM will need to be revisited before it runs out again.
We consider the objectives of minimizing the average distance per day as well as the maximum distance per day. We provide constant factor approximation for both objectives when distance is given by a tree metric, and logarithmic approximations for the general case.
In Chapter 4 we look at fixed order scheduling on parallel machines. In this setting, jobs with processing times and weights need to be processed on identical machines so as to minimize the total weighted completion time. The caveat is that the jobs arrive with a predetermined order, and this order must be respected on every machine (but not across machines). This prevents us from processing the jobs according to Smith's ratio on the individual machines, as would have been optimal otherwise.
We derive a constant factor approximation for this problem and proof a number of structural results along the way. A powerful concept here is a natural partial order we can define on the jobs, found as the intersection of the input ordering and the order of the Smith ratios. We can show that there is always an optimal schedule whose machine assignment is monotone with respect to this partial order. This drastically reduces the degrees of freedom one has in setting up a schedule. Not only does this make reasoning about the problem much simpler, we also show that by dropping some terms from the objective (at the loss of a constant factor), the problem becomes polynomial time solvable. Additionally we give a QPTAS for the special case of unit processing times, and provide some evidence that techniques previously successful on other scheduling problems with completion time objective are bound to fail on this problem.