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 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 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 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.
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.
For the prediction of digging forces from a granular material simulation, the
Nonsmooth Contact Dynamics Method is examined. First, the equations of motion
for nonsmooth mechanical systems are laid out. They are a differential
variational inequality that has the same structure as classical discrete algebraic equations. Using a Galerkin projection in time, it becomes possible to derive
nonsmooth versions of the classical SHAK and RATTLE integrators.
A matrix-free Interior Point Method is used for the complementarity
problems that need to be solved in every time step. It is shown that this method
outperforms the Projected Gauss-Jacobi method by several orders of magnitude
and produces the same digging force result as the Discrete Element Method in comparable computing time.
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.
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 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 propose and study a strongly coupled PDE-ODE system with tissue-dependent degenerate diffusion and haptotaxis that can serve as a model prototype for cancer cell invasion through the
extracellular matrix. We prove the global existence of weak solutions and illustrate the model behaviour by numerical simulations for a two-dimensional setting.