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.     

Robustness and duality in linear programming

In this paper, we consider a linear program in which the right hand sides of theconstraints are uncertain and inaccurate. This uncertainty is represented byintervals, that is to say that each right hand side can take any value in itsinterval regardless of other constraints. The problem is then to determine arobust solution, which is satisfactory for all possible coefficient values.Classical criteria, such as the worst case and the maximum regret, are appliedto define different robust versions of the initial linear program. Morerecently, Bertsimas and Sim have proposed a new model that generalizes the worstcase criterion. The subject of this paper is to establish the relationshipsbetween linear programs with uncertain right hand sides and linear programs withuncertain objective function coefficients using the classical duality theory. Weshow that the transfer of the uncertainty from the right hand sides to theobjective function coefficients is possible by establishing new dualityrelations. When the right hand sides are approximated by intervals, we alsopropose an extension of the Bertsimas and Sim's model and we show that themaximum regret criterion is equivalent to the worst case criterion.     

Computing and minimizing the relative regret in combinatorial optimization with interval data

We consider combinatorial optimization problems with uncertain parameters of the objective function, where for each uncertain parameter an interval estimate is known. It is required to find a solution that minimizes the worst-case relative regret. For minmax relative regret versions of some subset-type problems, where feasible solutions are subsets of a finite ground set and the objective function represents the total weight of elements of a feasible solution, and for the minmax relative regret version of the problem of scheduling n jobs on a single machine to minimize the total completion time, we present a number of structural, algorithmic, and complexity results. Many of the results are based on generalizing and extending ideas and approaches from absolute regret minimization to the relative regret case.     

Minimax regret solution to multiobjective linear programming problems with interval objective functions coefficients

The current paper focuses on a multiobjective linear programming problem with interval objective functions coefficients. Taking into account the minimax regret criterion, an attempt is being made to propose a new solution i.e. minimax regret solution. With respect to its properties, a minimax regret solution is necessarily ideal when a necessarily ideal solution exists; otherwise it is still considered a possibly weak efficient solution. In order to obtain a minimax regret solution, an algorithm based on a relaxation procedure is suggested. A numerical example demonstrates the validity and strengths of the proposed algorithm. Finally, two special cases are investigated: the minimax regret solution for fixed objective functions coefficients as well as the minimax regret solution with a reference point. Some of the characteristic features of both cases are highlighted thereafter.     

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 accuracy,robustness and tolerances in vector Boolean optimization

A Boolean programming problem with a finite number of alternatives where initial coefficients (costs) of linear payoff functions are subject to perturbations is considered. We define robust solution as a feasible solution which for a given set of realizations of uncertain parameters guarantees the minimum value of the worst-case relative regret among all feasible solutions. For the Pareto optimality principle, an appropriate definition of the worst-case relative regret is specified. It is shown that this definition is closely related to the concept of accuracy function being recently intensively studied in the literature. We also present the concept of robustness tolerances of a single cost vector. The tolerance is defined as the maximum level of perturbation of the cost vector which does not destroy the solution robustness. We present formulae allowing the calculation of the robustness tolerance obtained for some initial costs. The results are illustrated with several numerical examples.     

Active-constraint variable ordering for faster feasibility of mixed integer linear programs

The selection of the branching variable can greatly affect the speed of the branch and bound solution of a mixed-integer or integer linear program. Traditional approaches to branching variable selection rely on estimating the effect of the candidate variables on the objective function. We present a new approach that relies on estimating the impact of the candidate variables on the active constraints in the current LP relaxation. We apply this method to the problem of finding the first feasible solution as quickly as possible. Empirical experiments demonstrate a significant improvement compared to a state-of-the art commercial MIP solver.     

A branch and bound method for the solution of multiparametric mixed integer linear programming problems

In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch and bound strategy that involves the solution of a multiparametric linear programming sub-problem at leaf nodes and appropriate comparison procedures to update the tree. McCormick relaxation procedures are employed to overcome the presence of bilinear terms in the model. The algorithm generates an envelope of parametric profiles, containing the optimal solution of the mp-MILP problem. The parameter space is partitioned into polyhedral convex critical regions. Two examples are presented to illustrate the steps of the proposed algorithm.     

Linear programming with interval coefficients

In order to solve a linear programme, the model coefficients must be fixed at specific values, which implies that the coefficients are perfectly accurate. In practice, however, the coefficients are generally estimates. The only way to deal with uncertain coefficients is to test the sensitivity of the model to changes in their values, either singly or in very small groups. We propose a new approach in which some or all of the coefficients of the LP are specified as intervals. We then find the best optimum and the worst optimum for the model, and the point settings of the interval coefficients that yield these two extremes. This provides the range of the optimised objective function, and the coefficient settings give some insight into the likelihood of these extremes.     

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.     

Using modified maximum regret for finding a necessarily efficient solution in an interval MOLP problem

The current research concerns multiobjective linear programming problems with interval objective functions coefficients. It is known that the most credible solutions to these problems are necessarily efficient ones. To solve the problems, this paper attempts to propose a new model with interesting properties by considering the minimax regret criterion. The most important property of the new model is attaining a necessarily efficient solution as an optimal one whenever the set of necessarily efficient solutions is nonempty. In order to obtain an optimal solution of the new model, an algorithm is suggested. To show the performance of the proposed algorithm, numerical examples are given. Finally, some special cases are considered and their characteristic features are highlighted.     

A nonlinear interval number programming method for uncertain optimization problems

In this paper, a method is suggested to solve the nonlinear interval number programming problem with uncertain coefficients both in nonlinear objective function and nonlinear constraints. Based on an order relation of interval number, the uncertain objective function is transformed into two deterministic objective functions, in which the robustness of design is considered. Through a modified possibility degree, the uncertain inequality and equality constraints are changed to deterministic inequality constraints. The two objective functions are converted into a single-objective problem through the linear combination method, and the deterministic inequality constraints are treated with the penalty function method. The intergeneration projection genetic algorithm is employed to solve the finally obtained deterministic and non-constraint optimization problem. Two numerical examples are investigated to demonstrate the effectiveness of the present method.     

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.     

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.     

Proximity search for 0-1 mixed-integer convex programming

In this paper we investigate the effects of replacing the objective function of a 0-1 mixed-integer convex program (MIP) with a “proximity” one, with the aim of using a black-box solver as a refinement heuristic. Our starting observation is that enumerative MIP methods naturally tend to explore a neighborhood around the solution of a relaxation. A better heuristic performance can however be expected by searching a neighborhood of an integer solution—a result that we obtain by just modifying the objective function of the problem at hand. The relationship of this approach with primal integer methods is also addressed. Promising computational results on different proof-of-concept implementations are presented, suggesting that proximity search can be quite effective in quickly refining a given feasible solution. This is particularly true when a sequence of similar MIPs has to be solved as, e.g., in a column-generation setting.     

Possibility linear programming with trapezoidal fuzzy numbers

Fuzzy linear programming with trapezoidal fuzzy numbers (TrFNs) is considered and a new method is developed to solve it. In this method, TrFNs are used to capture imprecise or uncertain information for the imprecise objective coefficients and/or the imprecise technological coefficients and/or available resources. The auxiliary multi-objective programming is constructed to solve the corresponding possibility linear programming with TrFNs. The auxiliary multi-objective programming involves four objectives: minimizing the left spread, maximizing the right spread, maximizing the left endpoint of the mode and maximizing the middle point of the mode. Three approaches are proposed to solve the constructed auxiliary multi-objective programming, including optimistic approach, pessimistic approach and linear sum approach based on membership function. An investment example and a transportation problem are presented to demonstrate the implementation process of this method. The comparison analysis shows that the fuzzy linear programming with TrFNs developed in this paper generalizes the possibility linear programming with triangular fuzzy numbers.     

The Robust Set Covering Problem with interval data

We study the Set Covering Problem with uncertain costs. For each cost coefficient, only an interval estimate is known, and it is assumed that each coefficient can take on any value from the corresponding uncertainty interval, regardless of the values taken by other coefficients. It is required to find a robust deviation (also called minmax regret) solution. For this strongly NP-hard problem, we present and compare computationally three exact algorithms, where two of them are based on Benders decomposition and one uses Benders cuts in the context of a Branch-and-Cut approach, and several heuristic methods, including a scenario-based heuristic, a Genetic Algorithm, and a Hybrid Algorithm that uses a version of Benders decomposition within a Genetic Algorithm framework.     

Network planning under uncertainty with an application to hydropower generation

Summary We present a general modeling framework for therobust optimization of linear network problems with uncertainty in the values of the right-hand side. In contrast to traditional approaches in mathematical programming, we use scenarios to characterize the uncertainty. Solutions are obtained for each scenario and these individual scenarios are aggregated to yield a nonanticipative or implementable policy that minimizes the regret of wrong decisions. A given solution is termed robust if it minimizes the sum over the scenarios of the weighted upper difference between the objective function value for the solution and the objective function value for the optimal solution for each scenario, while satisfying certain nonanticipativity constraints. This approach results in a huge model with a network submodel per scenario plus coupling constraints. Several decomposition approaches are considered, namely Dantzig-Wolfe decomposition, various types of Benders decomposition and different quadratic network approaches for approximating Augmented Lagrangian decomposition. We present computational results for these methods, including two implementation versions of the Lagrangian based method: a sequential implementation and a parallel implementation on a network of three workstations.     

Bilevel linear programming with ambiguous objective function of the follower

Bilevel linear optimization problems are the linear optimization problems with two sequential decision steps of the leader and the follower. In this paper, we focus on the ambiguity of coefficients of the follower in his objective function that hinder the leader from exactly calculating the rational response of the follower. Under the assumption that the follower’s possible range of the ambiguous coefficient vector is known as a certain convex polytope, the leader can deduce the possible set of rational responses of the follower. The leader further assumes that the follower’s response is the worst-case scenario to his objective function, and then makes a decision according to the maximin criteria. We thus formulate the bilevel linear optimization problem with ambiguous objective function of the follower as a special kind of three-level programming problem. In our formulation, we show that the optimal solution locates on the extreme point and propose a solution method based on the enumeration of possible rational responses of the follower. A numerical example is used to illustrate our proposed computational method.     

最小最大后悔准则下新增设施选址策略研究

基于新增设施选址问题,考虑网络节点权重不确定性,以设施中最大负荷量最小为目标,提出最小最大后悔准则下的新增设施选址问题。在网络节点权重确定时,通过证明将网络图中无穷多个备选点离散为有限个设施候选点,设计了时间复杂度为O(mn²)的多项式算法;在节点权重为区间值时,通过分析最大后悔值对应的最坏情境权重结构,进而确定最大后悔值最小的选址,提出时间复杂度为O(2ⁿm²n³)的求解算法;最后给出数值算例。