We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an $s$-$t$-graph $D(V,A)$ and for each arc a nominal length $c(a)$ and a maximal increase $d(a)$ of its length. … Read more
In this paper, we study the performance of affine policies for two-stage adjustable robust optimization problem with uncertain right hand side belonging to a budgeted uncertainty set. This is an important class of uncertainty sets widely used in practice where we can specify a budget on the adversarial deviations of the uncertain parameters from the … Read more
In many optimization problems uncertain parameters appear in a convex way, which is problematic as common techniques can only handle concave uncertainty. In this paper, we provide a systematic way to construct conservative approximations to such problems. Specifically, we reformulate the original problem as an adjustable robust optimization problem in which the nonlinearity of the … Read more
We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones of the copositive matrix cone. We show that the copositive relaxation gap of … Read more
We consider a system with an evolving state that can be stopped at any time by a decision maker (DM), yielding a state-dependent reward. The DM does not observe the state except for a limited number of monitoring times, which he must choose, in conjunction with a suitable stopping policy, to maximize his reward. Dealing … Read more
In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to … Read more
We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the … Read more
We study the robust resource constrained shortest path problem (RCSPP) under uncertainty in cost and multiple resource consumption. Contrary to the deterministic RCSPP where the cost and the consumption of resources on an arc are known and fixed, the robust RCSPP models the case where both the cost and the resource consumption are random, and … Read more
We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to … Read more
Although Robust Optimization is a powerful technique in dealing with uncertainty in optimization, its solutions can be too conservative when it leads to an objective value much worse than the nominal solution or even to infeasibility of the robust problem. In practice, this can lead to robust solutions being disregarded in favor of the nominal … Read more