On the complexity of minmax regret linear programming

We consider linear programming problems with uncertain objective function coefficients. For each coefficient of the objective function, an interval of uncertainty is known, and it is assumed that any coefficient can take on any value from the corresponding interval of uncertainty, regardless of the values taken by other coefficients. It is required to find a minmax regret solution. This problem received considerable attention in the recent literature, but its computational complexity status remained unknown. We prove that the problem is strongly NP-hard. This gives the first known example of a minmax regret optimization problem that is NP-hard in the case of interval-data representation of uncertainty but is polynomially solvable in the case of discrete-scenario representation of uncertainty.     

On the approximability of adjustable robust convex optimization under uncertainty

In this paper, we consider adjustable robust versions of convex optimization problems with uncertain constraints and objectives and show that under fairly general assumptions, a static robust solution provides a good approximation for these adjustable robust problems. An adjustable robust optimization problem is usually intractable since it requires to compute a solution for all possible realizations of uncertain parameters, while an optimal static solution can be computed efficiently in most cases if the corresponding deterministic problem is tractable. The performance of the optimal static robust solution is related to a fundamental geometric property, namely, the symmetry of the uncertainty set. Our work allows for the constraint and objective function coefficients to be uncertain and for the constraints and objective functions to be convex, thereby providing significant extensions of the results in Bertsimas and Goyal (Math Oper Res 35:284–305, 2010) and Bertsimas et al. (Math Oper Res 36: 24–54, 2011b) where only linear objective and linear constraints were considered. The models in this paper encompass a wide variety of problems in revenue management, resource allocation under uncertainty, scheduling problems with uncertain processing times, semidefinite optimization among many others. To the best of our knowledge, these are the first approximation bounds for adjustable robust convex optimization problems in such generality.     

New models for the robust shortest path problem: complexity, resolution and generalization

In optimization, it is common to deal with uncertain and inaccurate factors which make it difficult to assign a single value to each parameter in the model. It may be more suitable to assign a set of values to each uncertain parameter. A scenario is defined as a realization of the uncertain parameters. In this context, a robust solution has to be as good as possible on a majority of scenarios and never be too bad. Such characterization admits numerous possible interpretations and therefore gives rise to various approaches of robustness. These approaches differ from each other depending on models used to represent uncertain factors, on methodology used to measure robustness, and finally on analysis and design of solution methods. In this paper, we focus on the application of a recent criterion for the shortest path problem with uncertain arc lengths. We first present two usual uncertainty models: the interval model and the discrete scenario set model. For each model, we then apply a criterion, called bw-robustness (originally proposed by B. Roy) which defines a new measure of robustness. According to each uncertainty model, we propose a formulation in terms of large scale integer linear program. Furthermore, we analyze the theoretical complexity of the resulting problems. Our computational experiments perform on a set of large scale graphs. By observing the results, we can conclude that the approved solvers, e.g. Cplex, are able to solve the mathematical models proposed which are promising for robustness analysis. In the end, we show that our formulations can be applied to the general linear program in which the objective function includes uncertain coefficients.     

Strong duality for robust minimax fractional programming problems

We develop a duality theory for minimax fractional programming problems in the face of data uncertainty both in the objective and constraints. Following the framework of robust optimization, we establish strong duality between the robust counterpart of an uncertain minimax convex–concave fractional program, termed as robust minimax fractional program, and the optimistic counterpart of its uncertain conventional dual program, called optimistic dual. In the case of a robust minimax linear fractional program with scenario uncertainty in the numerator of the objective function, we show that the optimistic dual is a simple linear program when the constraint uncertainty is expressed as bounded intervals. We also show that the dual can be reformulated as a second-order cone programming problem when the constraint uncertainty is given by ellipsoids. In these cases, the optimistic dual problems are computationally tractable and their solutions can be validated in polynomial time. We further show that, for robust minimax linear fractional programs with interval uncertainty, the conventional dual of its robust counterpart and the optimistic dual are equivalent.     

An Exact Formula for Radius of Robust Feasibility of Uncertain Linear Programs

We present an exact formula for the radius of robust feasibility of uncertain linear programs with a compact and convex uncertainty set. The radius of robust feasibility provides a value for the maximal ‘size’ of an uncertainty set under which robust feasibility of the uncertain linear program can be guaranteed. By considering spectrahedral uncertainty sets, we obtain numerically tractable radius formulas for commonly used uncertainty sets of robust optimization, such as ellipsoids, balls, polytopes and boxes. In these cases, we show that the radius of robust feasibility can be found by solving a linearly constrained convex quadratic program or a minimax linear program. The results are illustrated by calculating the radius of robust feasibility of uncertain linear programs for several different uncertainty sets.     

Robust linear semi-infinite programming duality under uncertainty

In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. We then establish that the closed-convex robust moment cone condition in the case of constraint-wise uncertainty is in fact necessary and sufficient for robust duality. In other words, the robust moment cone is closed and convex if and only if robust duality holds for every linear objective function of the program. In the case of uncertain problems with affinely parameterized data uncertainty, we establish that robust duality is easily satisfied under a Slater type constraint qualification. Consequently, we derive robust forms of the Farkas lemma for systems of uncertain semi-infinite linear inequalities.     

Minimising the maximum relative regret for linear programmes with interval objective function coefficients

The minimax relative regret solution to a linear programme with interval objective function coefficients can be found using an algorithm that, at each iteration, solves a linear programme to generate a candidate solution and a mixed integer programme (MIP) to find the corresponding maximum regret. This paper first shows that there exists a regret-maximising solution in which all uncertain costs are at a bound, and then uses this to derive a MIP formulation that maximises the regret of a candidate solution. Computational experiments demonstrate that this approach is effective for problems with up to 50 uncertain objective function coefficients, significantly improving upon the existing enumerative method.     

Robust regret for uncertain linear programs with application to co-production models

This paper considers the regret optimization criterion for linear programming problems with uncertainty in the data inputs. The problems of study are more challenging than those considered in previous works that address only interval objective coefficients, and furthermore the uncertainties are allowed to arise from arbitrarily specified polyhedral sets. To this end a safe approximation of the regret function is developed so that the maximum regret can be evaluated reasonably efficiently by leveraging on previous established results and solution algorithms. The proposed approach is then applied to a two-stage co-production newsvendor problem that contains uncertainties in both supplies and demands. Computational experiments demonstrate that the proposed regret approximation is reasonably accurate, and the corresponding regret optimization model performs competitively well against other optimization approaches such as worst-case and sample average optimization across different performance measures.     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

Strong duality in robust semi-definite linear programming under data uncertainty

This article develops the deterministic approach to duality for semi-definite linear programming problems in the face of data uncertainty. We establish strong duality between the robust counterpart of an uncertain semi-definite linear programming model problem and the optimistic counterpart of its uncertain dual. We prove that strong duality between the deterministic counterparts holds under a characteristic cone condition. We also show that the characteristic cone condition is also necessary for the validity of strong duality for every linear objective function of the original model problem. In addition, we derive that a robust Slater condition alone ensures strong duality for uncertain semi-definite linear programs under spectral norm uncertainty and show, in this case, that the optimistic counterpart is also computationally tractable.     

An interactive method of tackling uncertainty in interval multiple objective linear programming

Mathematical programming models for decision support must explicitly take account of the treatment of the uncertainty associated with the model coefficients along with multiple and conflicting objective functions. Interval programming just assumes that information about the variation range of some (or all) of the coefficients is available. In this paper, we propose an interactive approach for multiple objective linear programming problems with interval coefficients that deals with the uncertainty in all the coefficients of the model. The presented procedures provide a global view of the solutions in the best and worst case coefficient scenarios and allow performing the search for new solutions according to the achievement rates of the objective functions regarding both the upper and lower bounds. The main goal is to find solutions associated with the interval objective function values that are closer to their corresponding interval ideal solutions. It is also possible to find solutions with non-dominance relations regarding the achievement rates of the upper and lower bounds of the objective functions considering interval coefficients in the whole model.     

Linear bilevel programming with interval coefficients

In this paper, we address linear bilevel programs when the coefficients of both objective functions are interval numbers. The focus is on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. We prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range.     

Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple linear program.     

On the information-based complexity of stochastic programming

Existing complexity results in stochastic linear programming using the Turing model depend only on problem dimensionality. We apply techniques from the information-based complexity literature to show that the smoothness of the recourse function is just as important. We derive approximation error bounds for the recourse function of two-stage stochastic linear programs and show that their worst case is exponential and depends on the solution tolerance, the dimensionality of the uncertain parameters and the smoothness of the recourse function.     

Robust combinatorial optimization with variable budgeted uncertainty

We introduce a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. In particular, we study the variable budgeted uncertainty, an extension of the budgeted uncertainty introduced by Bertsimas and Sim. Variable budgeted uncertainty can provide the same probabilistic guarantee as the budgeted uncertainty while being less conservative for vectors with few non-zero components. The feasibility set of the resulting optimization problem is in general non-convex so that we propose a mixed-integer programming reformulation for the problem, based on the dualization technique often used in robust linear programming. We show how to extend these results to non-binary variables and to more general multifunctions involving uncertainty set defined by conic constraints that are affine in the problem variables. We present a computational comparison of the budgeted uncertainty and the variable budgeted uncertainty on the robust knapsack problem. The experiments show a reduction of the price of robustness by an average factor of 18 %.     

Smoothed analysis of integer programming

We present a probabilistic analysis of integer linear programs (ILPs). More specifically, we study ILPs in a so-called smoothed analysis in which it is assumed that first an adversary specifies the coefficients of an integer program and then (some of) these coefficients are randomly perturbed, e.g., using a Gaussian or a uniform distribution with small standard deviation. In this probabilistic model, we investigate structural properties of ILPs and apply them to the analysis of algorithms. For example, we prove a lower bound on the slack of the optimal solution. As a result of our analysis, we are able to specify the smoothed complexity of classes of ILPs in terms of their worst case complexity. This way, we obtain polynomial smoothed complexity for packing and covering problems with any fixed number of constraints. Previous results of this kind were restricted to the case of binary programs.      

A note on issues of over-conservatism in robust optimization with cost uncertainty

We identify and discuss issues of hidden over-conservatism in robust linear optimization, when the uncertainty set is polyhedral with a budget of uncertainty constraint. The decision-maker selects the budget of uncertainty to reflect his degree of risk aversion, i.e. the maximum number of uncertain parameters that can take their worst-case value. In the first setting, the cost coefficients of the linear programming problem are uncertain, as is the case in portfolio management with random stock returns. We provide an example where, for moderate values of the budget, the optimal solution becomes independent of the nominal values of the parameters, i.e. is completely disconnected from its nominal counterpart, and discuss why this happens. The second setting focusses on linear optimization with uncertain upper bounds on the decision variables, which has applications in revenue management with uncertain demand and can be rewritten as a piecewise linear problem with cost uncertainty. We show in an example that it is possible to have more demand parameters equal their worst-case value than what is allowed by the budget of uncertainty, although the robust formulation is correct. We explain this apparent paradox.     

Minmax regret linear resource allocation problems

For minmax regret versions of some basic resource allocation problems with linear cost functions and uncertain coefficients (interval-data case), we present efficient (polynomial and pseudopolynomial) algorithms. As a by-product, we obtain an algorithm for the interval data minmax regret continuous knapsack problem.     

A finite algorithm for the least two-norm solution of a linear program 1

By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overtaxation techniques). In this way large sparse linear programs can be handled.

In this paper we give a new computational criterion to check whether the solution of the perturbed quadratic program provides the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper.

We also describe an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iteration.s     

Pessimistic,optimistic, and minimax regret approaches for linear programs under uncertainty

Uncertain data appearing as parameters in linear programs can be categorized variously. This paper deals with merely probability, belief (necessity), plausibility (possibility), and random set information of uncertainties. However, most theoretical approaches and models limit themselves to the analysis involving merely one kind of uncertainty within a problem. Moreover, none of the approaches concerns itself with the fact that random set, belief (necessity), and plausibility (possibility) convey the same information. This paper presents comprehensive methods for handling linear programs with mixed uncertainties which also preserve all details about uncertain data. We handle mixed uncertainties as sets of probabilities which lead to optimistic, pessimistic, and minimax regret in optimization criteria.