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.     

Robust multi-market newsvendor models with interval demand data

We present a robust model for determining the optimal order quantity and market selection for short-life-cycle products in a single period, newsvendor setting. Due to limited information about demand distribution in particular for short-life-cycle products, stochastic modeling approaches may not be suitable. We propose the minimax regret multi-market newsvendor model, where the demands are only known to be bounded within some given interval. In the basic version of the problem, a linear time solution method is developed. For the capacitated case, we establish some structural results to reduce the problem size, and then propose an approximation solution algorithm based on integer programming. Finally, we compare the performance of the proposed minimax regret model against the typical average-case and worst-case models. Our test results demonstrate that the proposed minimax regret model outperformed the average-case and worst-case models in terms of risk-related criteria and mean profit, respectively.     

Lexicographic α-robustness: An alternative to min–max criteria

Robustness in Operations Research/Decision Aid is often associated with min–max and min–max regret criteria. This common approach to determine robust solutions consists in finding a solution which minimizes the maximal cost or regret. Nevertheless, these criteria are known to be too conservative. In this paper, we present and study a new robustness approach, called lexicographic α-robustness, which compensates for this major drawback and many others. Furthermore, we establish a link between lexicographic α-robustness and a third robustness approach called p-robustness.     

Some inverse optimization problems under the Hamming distance

Given a feasible solution to a particular combinatorial optimization problem defined on a graph and a cost vector defined on the arcs of the graph, the corresponding inverse problem is to disturb the cost vector such that the feasible solution becomes optimal. The aim is to optimize the difference between the initial cost vector and the disturbed one. This difference can be measured in several ways. We consider the Hamming distance measuring in how many components two vectors are different, where weights are associated to the components. General algorithms for the bottleneck or minimax criterion are described and (after modification) applied to the inverse minimum spanning tree problem, the inverse shortest path tree problem and the linear assignment problem.     

Approximation algorithms for deterministic continuous-review inventory lot-sizing problems with time-varying demand

This work deals with the continuous time lot-sizing inventory problem when demand and costs are time-dependent. We adapt a cost balancing technique developed for the periodic-review version of our problem to the continuous-review framework. We prove that the solution obtained costs at most twice the cost of an optimal solution. We study the numerical complexity of the algorithm and generalize the policy to several important extensions while preserving its performance guarantee of two. Finally, we propose a modified version of our algorithm for the lot-sizing model with some restricted settings that improves the worst-case bound.     

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.     

On the Stochastic Non-sequential Production-planning Problem

This paper examines a stochastic non-sequential capacitated production-planning problem where the demand of each period is a continuous random variable. The stochastic non-sequential production-planning problem is examined with sequence-independent and then with sequence-dependent set-up costs, and the worst-case error determined when an approximate solution is obtained by solving the deterministic equivalent. We prove in general that the worst-case error is not dependent on the nature of the set-up cost, and identify a family of approximations for the stochastic non-sequential production-planning problem.     

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.     

Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems

We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when compared to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We analyze the strategies and deduce conditions under which they result in improved theoretical worst-case complexity. We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30–75% depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.     

Worst-case portfolio optimization with proportional transaction costs

We study optimal asset allocation in a crash-threatened financial market with proportional transaction costs. The market is assumed to be either in a normal state, in which the risky asset follows a geometric Brownian motion, or in a crash state, in which the price of the risky asset can suddenly drop by a certain relative amount. We only assume the maximum number and the maximum relative size of the crashes to be given and do not make any assumptions about their distributions. For every investment strategy, we identify the worst-case scenario in the sense that the expected utility of terminal wealth is minimized. The objective is then to determine the investment strategy which yields the highest expected utility in its worst-case scenario. We solve the problem for utility functions with constant relative risk aversion using a stochastic control approach. We characterize the value function as the unique viscosity solution of a second-order nonlinear partial differential equation. The optimal strategies are characterized by time-dependent free boundaries which we compute numerically. The numerical examples suggest that it is not optimal to invest any wealth in the risky asset close to the investment horizon, while a long position in the risky asset is optimal if the remaining investment period is sufficiently large.     

Strict feasibility and solvability for vector equilibrium problems in reflexive Banach spaces

The purpose of this paper is to investigate nonemptiness and boundedness of the solution set for a vector equilibrium problem with strict feasibility in reflexive Banach spaces. We introduce the concept of strict feasibility for a vector equilibrium problem, which recovers the existing concepts of strict feasibility introduced for variational inequalities. We prove that a pseudomonotone vector equilibrium problem has a nonempty bounded solution provided that it is strictly feasible in the strong sense.     

The unit commitment model with concave emissions costs: a hybrid Benders’ Decomposition with nonconvex master problems

We present a unit commitment model which determines generator schedules, associated production and storage quantities, and spinning reserve requirements. Our model minimizes fixed costs, fuel costs, shortage costs, and emissions costs. A constraint set balances the load, imposes requirements on the way in which generators and storage devices operate, and tracks reserve requirements. We capture cost functions with piecewise-linear and (concave) nonlinear constructs. We strengthen the formulation via cut addition. We then describe an underestimation approach to obtain an initial feasible solution to our model. Finally, we constitute a Benders’ master problem from the scheduling variables and a subset of those variables associated with the nonlinear constructs; the subproblem contains the storage and reserve requirement quantities, and power from generators with convex (linear) emissions curves. We demonstrate that our strengthening techniques and Benders’ Decomposition approach solve our mixed integer, nonlinear version of the unit commitment model more quickly than standard global optimization algorithms. We present numerical results based on a subset of the Colorado power system that provide insights regarding storage, renewable generators, and emissions.     

A fast approximation algorithm for the multicovering problem

The multicovering problem is: MIN cx subject to Ax≥b, xϵ{0, 1}ⁿ, where A is a matrix whose elements are all zero or one and b is a vector of positive integers. We present a fast heuristic for this important class of problems and analyze its worst-case performance: the ratio of the heuristic value to the optimum does not exceed the maximum row sum of the matrix A. The heuristic algorithm also provides a feasible dual solution vector that is useful in generating lower bounds on the value of the optimum.     

Robust optimization analysis for multiple attribute decision making problems with imprecise information

This paper considers ranking decision alternatives under multiple attributes with imprecise information on both attribute weights and alternative ratings. It is demonstrated that regret results from the decision maker??s inadequate knowledge about the true scenario to occur. Potential optimality analysis is a traditional method to evaluate alternatives with imprecise information. The essence of this approach is to identify any alternative that outperforms the others in its best-case scenario. Our analysis shows that potential optimality analysis is optimistic in nature and may lead to a significant loss if an unfavorable scenario occurs. We suggest a robust optimization analysis approach that ranks alternatives in terms of their worst-case absolute or relative regret. A robust optimal alternative performs reasonably well in all scenarios and is shown to be desirable for a risk-concerned decision maker. Linear programming models are developed to check robust optimality.     

A robust optimization approach for multicast network coding under uncertain link costs

Network coding is a technique that can be used to improve the performance of communication networks by performing mathematical operations at intermediate nodes. An important problem in coding theory is that of finding an optimal coding subgraph for delivering network data from a source node throughout intermediate nodes to a set of destination nodes with the minimum transmission cost. However, in many real applications, it can be difficult to determine exact values or specific probability distributions of link costs. Establishing minimum-cost multicast connections based on erroneous link costs might exhibit poor performance when implemented. This paper considers the problem of minimum-cost multicast using network coding under uncertain link costs. We propose a robust optimization approach to obtain solutions that protect the system against the worst-case value of the uncertainty in a prespecified set. The simulation results show that a robust solution provides significant improvement in worst-case performance while incurring a small loss in optimality for specific instances of the uncertainty.     

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.     

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.     

A robust optimization model for multi-site production planning problem in an uncertain environment

This paper addresses the multi-site production planning problem for a multinational lingerie company in Hong Kong subject to production import/export quotas imposed by regulatory requirements of different nations, the use of manufacturing factories/locations with regard to customers’ preferences, as well as production capacity, workforce level, storage space and resource conditions at the factories. In this paper, a robust optimization model is developed to solve multi-site production planning problem with uncertainty data, in which the total costs consisting of production cost, labor cost, inventory cost, and workforce changing cost are minimized. By adjusting penalty parameters, production management can determine an optimal medium-term production strategy including the production loading plan and workforce level while considering different economic growth scenarios. The robustness and effectiveness of the developed model are demonstrated by numerical results. The trade-off between solution robustness and model robustness is also analyzed.     

Stochastic and minimum regret formulations for transmission network expansion planning under uncertainties

After deregulation of the Power sector, uncertainty has increased considerably. Vertically integrated utilities were unbundled into independent generation, transmission and distribution companies. Transmission network expansion planning (TNEP) is now performed independent from generation planning. In this environment TNEP must include uncertainties of the generation sector as well as its own. Uncertainty in generation costs affecting optimal dispatch and uncertainty in demand loads are captured through composite scenarios. Probabilities are assigned to different scenarios. The effects of these uncertainties are transferred to the objective function in terms of total costs, which include: generation (dispatch), transmission expansion and load curtailment costs. Two formulations are presented: stochastic and minimum regret. The stochastic formulation seeks a design with minimum expected cost. The minimum regret formulation seeks a design with robust performance in terms of variance of the operational costs. Results for a test problem and a potential application to a real system are presented.