Approximate dynamic programming for stochastic linear control problems on compact state spaces

This paper addresses Markov Decision Processes over compact state and action spaces. We investigate the special case of linear dynamics and piecewise-linear and convex immediate costs for the average cost criterion. This model is very general and covers many interesting examples, for instance in inventory management. Due to the curse of dimensionality, the problem is intractable and optimal policies usually cannot be computed, not even for instances of moderate size.     

A flow model based on polylinking system

We extend recent work on nonlinear optimal control problems with integer restrictions on some of the control functions (mixed-integer optimal control problems, MIOCP). We improve a theorem (Sager et?al. in Math Program 118(1): 109–149, 2009) that states that the solution of a relaxed and convexified problem can be approximated with arbitrary precision by a solution fulfilling the integer requirements. Unlike in previous publications the new proof avoids the usage of the Krein-Milman theorem, which is undesirable as it only states the existence of a solution that may switch infinitely often. We present a constructive way to obtain an integer solution with a guaranteed bound on the performance loss in polynomial time. We prove that this bound depends linearly on the control discretization grid. A numerical benchmark example illustrates the procedure. As a byproduct, we obtain an estimate of the Hausdorff distance between reachable sets. We improve the approximation order to linear grid size h instead of the previously known result with order ${\sqrt{h}}$ (H?ckl in Reachable sets, control sets and their computation, augsburger mathematisch-naturwissenschaftliche schriften. Dr. Bernd Wi?ner, Augsburg, 1996). We are able to include a Special Ordered Set condition which will allow for a transfer of the results to a more general, multi-dimensional and nonlinear case compared to the Theorems in Pietrus and Veliov in (Syst Control Lett 58:395–399, 2009).     

An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization within the procedure, which can complicate the analysis. We suggest a different, polyhedral viewpoint to design contention resolution schemes, which avoids to deal explicitly with the randomization in the second step. This is achieved by focusing on the marginals of a dropping procedure. Apart from avoiding one source of randomization, our viewpoint allows for employing polyhedral techniques. Both can significantly simplify the construction and analysis of contention resolution schemes. We show how, through our framework, one can obtain an optimal monotone contention resolution scheme for bipartite matchings, which has a balancedness of 0.4762. So far, only very few results are known about optimality of monotone contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings. Furthermore, we derive a monotone contention resolution scheme for matchings that significantly improves over the previously best one. More precisely, we obtain a balancedness of 0.4326, improving on a prior 0.1997-balanced scheme. At the same time, our scheme implies that the currently best lower bound on the correlation gap for matchings is not tight. Our results lead to improved approximation factors for various constrained submodular function maximization problems over a combination of matching constraints with further constraints.

     

Bulk-Robust combinatorial optimization

Mathematical Programming - We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial...     

Computational complexity of impact size estimation for spreading processes on networks

Spreading processes on networks are often analyzed to understand how the outcome of the process (e.g. the number of affected nodes) depends on structural properties of the underlying network. Most available results are ensemble averages over certain interesting graph classes such as random graphs or graphs with a particular degree distributions. In this paper, we focus instead on determining the expected spreading size and the probability of large spreadings for a single (but arbitrary) given network and study the computational complexity of these problems using reductions from well-known network reliability problems. We show that computing both quantities exactly is intractable, but that the expected spreading size can be efficiently approximated with Monte Carlo sampling. When nodes are weighted to reflect their importance, the problem becomes as hard as the s-t reliability problem, which is not known to yield an efficient randomized approximation scheme up to now. Finally, we give a formal complexity-theoretic argument why there is most likely no randomized constant-factor approximation for the probability of large spreadings, even for the unweighted case. A hybrid Monte Carlo sampling algorithm is proposed that resorts to specialized s-t reliability algorithms for accurately estimating the infection probability of those nodes that are rarely affected by the spreading process.     

Stochastic convergence of random search methods to fixed size Pareto front approximations

In this paper we investigate to what extent random search methods, equipped with an archive of bounded size to store a limited amount of solutions and other data, are able to obtain good Pareto front approximations. We propose and analyze two archiving schemes that allow for maintaining a sequence of solution sets of given cardinality that converge with probability one to an ?-Pareto set of a certain quality, under very mild assumptions on the process used to sample new solutions. The first algorithm uses a hierarchical grid to define a family of approximate dominance relations to compare solutions and solution sets. Acceptance of a new solution is based on a potential function that counts the number of occupied boxes (on various levels) and thus maintains a strictly monotonous progress to a limit set that covers the Pareto front with non-overlapping boxes at finest resolution possible. The second algorithm uses an adaptation scheme to modify the current value of ? based on the information gathered during the run. This way it will be possible to achieve convergence to the best (smallest) ? value, and to a corresponding solution set of k solutions that ?-dominate all other solutions, which is probably the best possible result regarding the limit behavior of random search methods or metaheuristics for obtaining Pareto front approximations.     

A technique for obtaining true approximations for k-center with covering constraints

Mathematical Programming - There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem...     

Chain-constrained spanning trees

Mathematical Programming - We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being...     

An adaptive routing approach for personal rapid transit

Personal Rapid Transit (PRT) is a public transportation mode, in which small automated vehicles transport passengers on demand. Central control of the vehicles leads to interesting possibilities for optimized routings. The complexity of the involved routing problems together with the fact that routing algorithms for PRT essentially have to run in real-time often leads to the choice of fast greedy approaches. The most common routing approach is arguably a sequential one, where upcoming requests are greedily served in a quickest way without interfering with previously routed vehicles. The simplicity of this approach stems from the fact that a chosen route is never changed later. This is as well the main drawback of it, potentially leading to large detours. It is natural to ask how much one could gain by using a more adaptive routing strategy. This question is the main motivation of this article. In this paper, we first suggest a simple mathematical model for PRT, and then introduce a new adaptive routing algorithm that repeatedly uses solutions to an LP as a guide to route vehicles. Our routing approach incorporates new requests in the LP as soon as they appear, and reoptimizes the routing of all currently used vehicles, contrary to sequential routing. We provide preliminary computational results that give first evidence of the potential gains of an adaptive routing strategy, as used in our algorithm.