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.     

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.     

A tabu search algorithm for the minmax regret minimum spanning tree problem with interval data

This paper deals with the strongly NP-hard minmax regret version of the minimum spanning tree problem with interval costs. The best known exact algorithms solve the problem in reasonable time for rather small graphs. In this paper an algorithm based on the idea of tabu search is constructed. Some properties of the local minima are shown. Exhaustive computational tests for various classes of graphs are performed. The obtained results suggest that the proposed tabu search algorithm quickly outputs optimal solutions for the smaller instances, previously discussed in the existing literature. Furthermore, some arguments that this algorithm performs well also for larger instances are provided.     

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.     

Heuristic algorithms for the minmax regret flow-shop problem with interval processing times

An uncertain version of the permutation flow-shop with unlimited buffers and the makespan as a criterion is considered. The investigated parametric uncertainty is represented by given interval-valued processing times. The maximum regret is used for the evaluation of uncertainty. Consequently, the minmax regret discrete optimization problem is solved. Due to its high complexity, two relaxations are applied to simplify the optimization procedure. First of all, a greedy procedure is used for calculating the criterion’s value, as such calculation is NP-hard problem itself. Moreover, the lower bound is used instead of solving the internal deterministic flow-shop. The constructive heuristic algorithm is applied for the relaxed optimization problem. The algorithm is compared with previously elaborated other heuristic algorithms basing on the evolutionary and the middle interval approaches. The conducted computational experiments showed the advantage of the constructive heuristic algorithm with regards to both the criterion and the time of computations. The Wilcoxon paired-rank statistical test confirmed this conclusion.

     

Complexity of minimizing the total flow time with interval data and minmax regret criterion

We consider the minmax regret (robust) version of the problem of scheduling n jobs on a machine to minimize the total flow time, where the processing times of the jobs are uncertain and can take on any values from the corresponding intervals of uncertainty. We prove that the problem in NP-hard. For the case where all intervals of uncertainty have the same center, we show that the problem can be solved in O(nlogn) time if the number of jobs is even, and is NP-hard if the number of jobs is odd. We study structural properties of the problem and discuss some polynomially solvable cases.     

A 2-approximation for minmax regret problems via a mid-point scenario optimal solution

In this note, a 2-approximation method for minmax regret optimization problems is developed which extends the work of Kasperski and Zielinski [A. Kasperski, P. Zielinski, An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters 97 (2006) 177-180] from finite to compact constraint sets.     

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.     

The minmax regret gradual covering location problem on a network with incomplete information of demand weights

The gradual covering location problem seeks to establish facilities on a network so as to maximize the total demand covered, allowing partial coverage. We focus on the gradual covering location problem when the demand weights associated with nodes of the network are random variables whose probability distributions are unknown. Using only information on the range of these random variables, this study is aimed at finding the “minmax regret” location that minimizes the worst-case coverage loss. We show that under some conditions, the problem is equivalent to known location problems (e.g. the minmax regret median problem). Polynomial time algorithms are developed for the problem on a general network with linear coverage decay functions.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines

The paper proposes a Mixed Integer Programming (MIP) formulation of the scheduling problem with total flow criterion on a set of parallel unrelated machines under an uncertainty context about the processing times. To model the problem we assume that lower and upper bounds are known for each processing time. In this context we consider an optimal minmax regret schedule as a suitable approximation to the optimal schedule under an arbitrary choice of the possible processing times.     

An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path problem (RSP) is a generalization of SP. In the former, the cost of each arc is defined by an interval of possible values for the arc cost. The objective is to minimize the maximum relative regret of the path from the source to the destination. This problem is known as the minmax relative regret RSP and it is NP-Hard. We propose a mixed integer linear programming formulation for this problem. The CPLEX branch-and-bound algorithm based on this formulation is able to find optimal solutions for all instances with 100 nodes, and has an average gap of 17 % on the instances with up to 1,500 nodes. We also develop heuristics with emphasis on providing efficient and scalable methods for solving large instances for the minmax relative regret RSP, based on Pilot method and random-key genetic algorithms. To the best of our knowledge, this is the first work to propose a linear formulation, an exact algorithm and metaheuristics for the minmax relative regret RSP.     

A Minmax Regret Linear Regression Model Under Uncertainty in the Dependent Variable

This paper analyzes the simple linear regression model corresponding to a sample affected by errors from a non-probabilistic viewpoint. We consider the simplest case where the errors just affect the dependent variable and there only exists one explanatory variable. Moreover, we assume the errors affecting each observation can be bounded. In this context the minmax regret criterion is used in order to obtain a regression line with nearly optimal goodness of fit for any true values of the dependent variable. Theoretical results as well as numerical methods are stated in order to solve the optimization problem under different residual cost functions.     

Some tractable instances of interval data minmax regret problems

In this paper, we provide polynomial and pseudopolynomial algorithms for classes of particular instances of interval data minmax regret graph problems. These classes are defined using a parameter that measures the distance from well-known solvable instances. Tractable cases occur when the parameter is bounded by a constant.     

Approximating a two-machine flow shop scheduling under discrete scenario uncertainty

This paper deals with the two machine permutation flow shop problem with uncertain data, whose deterministic counterpart is known to be polynomially solvable. In this paper, it is assumed that job processing times are uncertain and they are specified as a discrete scenario set. For this uncertainty representation, the min-max and min-max regret criteria are adopted. The min-max regret version of the problem is known to be weakly NP-hard even for two processing time scenarios. In this paper, it is shown that the min-max and min-max regret versions of the problem are strongly NP-hard even for two scenarios. Furthermore, the min-max version admits a polynomial time approximation scheme if the number of scenarios is constant and it is approximable with performance ratio of 2 and not (4/3 − ?)-approximable for any ? > 0 unless P = NP if the number of scenarios is a part of the input. On the other hand, the min-max regret version is not at all approximable even for two scenarios.     

Restricted Robust Uniform Matroid Maximization Under Interval Uncertainty

For the problem of selecting p items with interval objective function coefficients so as to maximize total profit, we introduce the r-restricted robust deviation criterion and seek solutions that minimize the r-restricted robust deviation. This new criterion increases the modeling power of the robust deviation (minmax regret) criterion by reducing the level of conservatism of the robust solution. It is shown that r-restricted robust deviation solutions can be computed efficiently. Results of experiments and comparisons with absolute robustness, robust deviation and restricted absolute robustness criteria are reported. This work is supported by a grant from Turkish Academy of Science(TUBA).     

Differential games without pure strategy saddle-point solutions

In some two-player, zero-sum differential games, pure strategy saddle-point solutions do not exist. For such games, the concept of a minmax strategy is examined, and sufficient conditions for a control to be a minmax control are presented. Both the open-loop and the closed-loop cases are considered.The research was partially supported by ONR under Contract No. N00014-69-A-0200-12. An earlier version of this paper was presented at the Eleventh Annual Allerton Conference on Circuit and System Theory, Monticello, Illinois, 1973.The author wishes to acknowledge his many valuable discussions of this problem with Professor G. Leitmann and also to thank one of the reviewers for his suggestions for simplifying the proof of Theorem 2.1.     

A note on the minmax regret centdian location on trees

The minmax regret optimization model of the doubly weighted centdian location on trees is considered. Assuming that both types of weights, demands and relative importance of the customers, are partially known through interval estimates, an exact algorithm of complexity O(n³logn) is derived. This bound is improved in some special cases.     

广义多目标minmax问题的最优性条件和极大熵方法

本文讨论了广义多目标minmax问题的最优性条件。利用极大熵逼近函数，研究了广义多目标minmax；问题的逼近问题，在较弱的条件下，证明了由极大熵逼近函数导出的多目标逼近问题的临界点的任一极限点均为原广义多目标minmax问题的临界点。