We extend the standard concept of robust optimization by the introduction of an alternative solution. In contrast to the classic concept, one is allowed to chose two solutions from which the best can be picked after the uncertain scenario has been revealed. We focus in this paper on the resulting robust problem for combinatorial problems with bounded uncertainty sets. We present a reformulation of the robust problem which decomposes it into polynomially many subproblems. In each subproblem one needs to find two solutions which are connected by a cost function which penalizes if the same element is part of both solutions. Using this reformulation, we show how the robust problem can be solved efficiently for the unconstrained combinatorial problem, the selection problem, and the minimum spanning tree problem. The robust problem corresponding to the shortest path problem turns out to be NP-complete on general graphs. However, for series-parallel graphs, the robust shortest path problem can be solved efficiently. Further, we show how approximation algorithms for the subproblem can be used to compute approximate solutions for the original problem.
We investigate a PDE-ODE system describing cancer cell invasion in a tissue network. The model is an extension of the multiscale setting in [28,40], by considering two subpopulations of tumor cells interacting mutually and with the surrounding tissue. According to the go-or-grow hypothesis, these subpopulations consist of moving and proliferating cells, respectively. The mathematical setting also accommodates the effects of some therapy approaches. We prove the global existence of weak solutions to this model and perform numerical simulations to illustrate its behavior for different therapy strategies.
We present a new approach to handle uncertain combinatorial optimization problems that uses solution ranking procedures to determine the degree of robustness of a solution. Unlike classic concepts for robust optimization, our approach is not purely based on absolute quantitative performance, but also includes qualitative aspects that are of major importance for the decision maker.
We discuss the two variants, solution ranking and objective ranking robustness, in more detail, presenting problem complexities and solution approaches. Using an uncertain shortest path problem as a computational example, the potential of our approach is demonstrated in the context of evacuation planning due to river flooding.
We consider the problem to evacuate several regions due to river flooding, where sufficient time is given to plan ahead. To ensure a smooth evacuation procedure, our model includes the decision which regions to assign to which shelter, and when evacuation orders should be issued, such that roads do not become congested.
Due to uncertainty in weather forecast, several possible scenarios are simultaneously considered in a robust optimization framework. To solve the resulting integer program, we apply a Tabu search algorithm based on decomposing the problem into better tractable subproblems. Computational experiments on random instances and an instance based on Kulmbach, Germany, data show considerable improvement compared to an MIP solver provided with a strong starting solution.
In this paper, we discuss the problem of approximating ellipsoid uncertainty sets with bounded (gamma) uncertainty sets. Robust linear programs with ellipsoid uncertainty lead to quadratically constrained programs, whereas robust linear programs with bounded uncertainty sets remain linear programs which are generally easier to solve.
We call a bounded uncertainty set an inner approximation of an ellipsoid if it is contained in it. We consider two different inner approximation problems. The first problem is to find a bounded uncertainty set which sticks close to the ellipsoid such that a shrank version of the ellipsoid is contained in it. The approximation is optimal if the required shrinking is minimal. In the second problem, we search for a bounded uncertainty set within the ellipsoid with maximum volume. We present how both problems can be solved analytically by stating explicit formulas for the optimal solutions of these problems.
Further, we present in a computational experiment how the derived approximation techniques can be used to approximate shortest path and network flow problems which are affected by ellipsoidal uncertainty.
We propose and study a strongly coupled PDE-ODE-ODE system modeling cancer cell invasion through a tissue network
under the go-or-grow hypothesis asserting that cancer cells can either move or proliferate. Hence our setting features
two interacting cell populations with their mutual transitions and involves tissue-dependent degenerate diffusion and
haptotaxis for the moving subpopulation. The proliferating cells and the tissue evolution are characterized by way of ODEs
for the respective densities. We prove the global existence of weak solutions and illustrate the model behaviour by
numerical simulations in a two-dimensional setting.
We propose and analyze a multiscale model for acid-mediated tumor invasion
accounting for stochastic effects on the subcellular level.
The setting involves a PDE of reaction-diffusion-taxis type describing the evolution of the tumor cell density,
the movement being directed towards pH gradients in the local microenvironment,
which is coupled to a PDE-SDE system characterizing the
dynamics of extracellular and intracellular proton concentrations, respectively.
The global well-posedness of the model is shown and
numerical simulations are performed in order to illustrate the solution behavior.
We propose a multiscale model for tumor cell migration in a tissue network. The system of equations involves a structured population model for the tumor cell density, which besides time and
position depends on a further variable characterizing the cellular state with respect to the amount
of receptors bound to soluble and insoluble ligands. Moreover, this equation features pH-taxis and
adhesion, along with an integral term describing proliferation conditioned by receptor binding. The
interaction of tumor cells with their surroundings calls for two more equations for the evolution of
tissue fibers and acidity (expressed via concentration of extracellular protons), respectively. The
resulting ODE-PDE system is highly nonlinear. We prove the global existence of a solution and
perform numerical simulations to illustrate its behavior, paying particular attention to the influence
of the supplementary structure and of the adhesion.
We consider the multiscale model for glioma growth introduced in a previous work and extend it to account
for therapy effects. Thereby, three treatment strategies involving surgical resection, radio-, and
chemotherapy are compared for their efficiency. The chemotherapy relies on inhibiting the binding
of cell surface receptors to the surrounding tissue, which impairs both migration and proliferation.
In this paper we propose a phenomenological model for the formation of an interstitial gap between the tumor and the stroma. The gap
is mainly filled with acid produced by the progressing edge of the tumor front. Our setting extends existing models for acid-induced tumor invasion models to incorporate
several features of local invasion like formation of gaps, spikes, buds, islands, and cavities. These behaviors are obtained mainly due to the random dynamics at the intracellular
level, the go-or-grow-or-recede dynamics on the population scale, together with the nonlinear coupling between the microscopic (intracellular) and macroscopic (population)
levels. The wellposedness of the model is proved using the semigroup technique and 1D and 2D numerical simulations are performed to illustrate model predictions and draw
conclusions based on the observed behavior.