Min–max and min–max regret versions of combinatorial optimization problems: A survey

Min–max and min–max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min–max and min–max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s–t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.     

Implicit extremes and implicit max–stable laws

Let X ₁, ? , X _n be iid random vectors and f≥0 be a homogeneous non–negative function interpreted as a loss function. Let also k(n)=Argmax _{i=1c? , n} f(X _i ). We are interested in the asymptotic behavior of X _k(n) as n→∞. In other words, what is the distribution of the random vector leading to maximal loss. This question is motivated by a kind of inverse problem where one wants to determine the extremal behavior of X when only explicitly observing f(X). We shall refer to such types of results as implicit extremes. It turns out that, as in the usual case of explicit extremes, all limit implicit extreme value laws are implicit max–stable. We characterize the regularly varying implicit max–stable laws in terms of their spectral and stochastic representations. We also establish the asymptotic behavior of implicit order statistics relative to a given homogeneous loss and conclude with several examples drawing connections to prior work involving regular variation on general cones.     

Explicit min–max polynomials on the disc

Denote by ${\Pi }_{n+m?1}^2?\{{\sum }_{0\le i+j\le n+m?1}{c}_{i,j}{x}^i{y}^j:c_{i,j}\in \mathbb{R}\}$ the space of polynomials of two variables with real coefficients of total degree less than or equal to $n+m?1$. Let $b_0,b_1,\dots ,b_l\in \mathbb{R}$ be given. For $n,m\in \mathbb{N},n\ge l+1$ we look for the polynomial $b_0{x}^n{y}^m+b_1{x}^{n?1}{y}^{m+1}+?+b_l{x}^{n?l}{y}^{m+l}+q(x,y),q(x,y)\in {\Pi }_{n+m?1}^2$, which has least maximum norm on the disc and call such a polynomial a min–max polynomial. First we introduce the polynomial $2P_{n,m}(x,y)=x{G}_{n?1,m}(x,y)+y{G}_{n,m?1}(x,y)=2x^n{y}^m+q(x,y)$ and $q(x,y)\in {\Pi }_{n+m?1}^2$, where $G_{n,m}(x,y)?1/2^{n+m}(U_n\left(x\right)U_m\left(y\right)+U_{n?2}\left(x\right)U_{m?2}\left(y\right))$, and show that it is a min–max polynomial on the disc. Then we give a sufficient condition on the coefficients $b_j,j=0,\dots ,l,l$ fixed, such that for every $n,m\in \mathbb{N},n\ge l+1$, the linear combination ${\sum }_{\nu =0}^l{b}_{\nu }{P}_{n?\nu ,m+\nu }(x,y)$ is a min–max polynomial. In fact the more general case, when the coefficients $b_j$ and $l$ are allowed to depend on $n$ and $m$, is considered. So far, up to very special cases, min–max polynomials are known only for $x^n{y}^m$,$n,m\in {\mathbb{N}}_0$.     

A smoothing algorithm for finite min–max–min problems

We generalize a smoothing algorithm for finite min–max to finite min–max–min problems. We apply a smoothing technique twice, once to eliminate the inner min operator and once to eliminate the max operator. In mini–max problems, where only the max operator is eliminated, the approximation function is decreasing with respect to the smoothing parameter. Such a property is convenient to establish algorithm convergence, but it does not hold when both operators are eliminated. To maintain the desired property, an additional term is added to the approximation. We establish convergence of a steepest descent algorithm and provide a numerical example.     

Semidefinite programming for min–max problems and games

We consider two min–max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796–817, 2001; Math Program B 112:65–92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min–max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.     

Modeling max–min fair bandwidth allocation in BitTorrent communities

This paper gives an exact mathematical programming model and algorithm of the max–min fairness bandwidth allocation problem in multi-swarm peer-to-peer content sharing community. The proposed iterative method involves solution of LP and MILP problems of large scale. Based on real-world data traces, numerical experiments demonstrate that the new algorithm is computationally faster than an earlier developed one for larger problem sizes, and it provides better numerical stability. Moreover, even if its execution is stopped after some initial steps it still grants feasible solution with good approximation to max–min fairness.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

Perron–Frobenius theorem for hypermatrices in the max algebra

Recently, there have been many intriguing new developments in the study of hypermatrices and their associated eigenvalue problems. In particular, results coming from the matrix setting when studying the max algebra have shown especially attractive combinatorial features. We now extend this max algebra setting into the realm of hypermatrices. Considering that the max algebra has shown particular significance in optimization problems for the matrix setting, we look to examine and extend these results in the higher order conditions. Furthermore, we establish some algebraic properties for hypermatrices and then proceed to extend the Perron–Frobenius Theorem for this setting and prove the existence of a unique eigenvalue. We continue by stating a result from Nussbaum, that the Min–Max theorem holds, and provide a proof for completeness. For strongly increasing hypermatrices, an iterative algorithm which converges to our unique eigenvalue is given. Finally, we conclude with an analysis of our results in the hypergraph setting.     

A weighted max–min model for fuzzy goal programming

After Narasimhan's pioneering study of applying fuzzy set theory to goal programming in 1980, many achievements in the field have been recorded. Most of them followed the max–min approach. However, when objectives have different levels of importance, only the weighted additive model of Tiwari et al. seems to be applicable. However, the shortcoming of the additive model is that the summation of quasiconcave functions may not be quasiconcave. This study proposes a novel weighted max–min model for fuzzy goal programming (FGP) and for fuzzy multiple objective decision-making. The proposed model adapts well to even the most complicated membership functions. Numerical examples demonstrate that the proposed model can be effectively incorporated with other approaches to FGP and is superior to the weighted additive approach.     

A generalized min–max theorem for functionals of strongly indefinite sign

We consider non-linear Schrödinger equations of the following type: $$\begin{aligned} \left\{ \begin{array}{l} -\Delta u(x) + V(x)u(x)-q(x)|u(x)|^\sigma u(x) = \lambda u(x), \quad x\in \mathbb{R }^N \\ u\in H^1(\mathbb{R }^N)\setminus \{0\}, \end{array} \right. \end{aligned}$$ where $N\ge 1$ and $\sigma >0$ . We will concentrate on the case where both $V$ and $q$ are periodic, and we will analyse what happens for different values of $\lambda $ inside a spectral gap $]\lambda ^-,\lambda ^+[$ . We derive both the existence of multiple orbits of solutions and the bifurcation of solutions when $\lambda \nearrow \lambda ^+$ . Thereby we use the corresponding energy function ${I_\lambda }$ and we derive a new variational characterization of multiple critical levels for such functionals: in this way we get multiple orbits of solutions. One main advantage of our new view on some specific critical values $c_0(\lambda )\le c_1(\lambda )\le \cdots \le c_n(\lambda )\le \cdots $ is a multiplicity result telling us something about the number of critical points with energies below $c_n(\lambda )$ , even if for example two of these values $c_i(\lambda )$ and $c_j(\lambda )$ ( $0\le i<j\le n$ ) coincide. Let us close this summary by mentioning another main advantage of our variational characterization of critical levels: we present our result in an abstract setting that is suitable for other problems and we give some hints about such problems (like the case corresponding to a Coulomb potential $V$ ) at the end of the present paper.     

Constrained inverse min–max spanning tree problems under the weighted Hamming distance

In this paper, we consider the constrained inverse min–max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times. This research is supported by the National Natural Science Foundation of China (Grant No. 10601051).     

A min–max vehicle routing problem with split delivery and heterogeneous demand

In this article, we introduce a new variant of min–max vehicle routing problem, where various types of customer demands are satisfied by heterogeneous fleet of vehicles and split delivery of services is allowed. We assume that vehicles may serve one or more types of service with unlimited service capacity, and varying service and transfer speed. A heuristic solution approach is proposed. We report the solutions for several test problems.     

A novel piecewise linear classifier based on polyhedral conic and max–min separabilities

In this paper, an algorithm for finding piecewise linear boundaries between pattern classes is developed. This algorithm consists of two main stages. In the first stage, a polyhedral conic set is used to identify data points which lie inside their classes, and in the second stage we exclude those points to compute a piecewise linear boundary using the remaining data points. Piecewise linear boundaries are computed incrementally starting with one hyperplane. Such an approach allows one to significantly reduce the computational effort in many large data sets. Results of numerical experiments are reported. These results demonstrate that the new algorithm consistently produces a good test set accuracy on most data sets comparing with a number of other mainstream classifiers.