Max–max,max–min,min–max and min–min knapsack problems with a parametric constraint

4OR - Max–max, max–min, min–max and min–min optimization problems with a knapsack-type constraint containing a single numerical parameter are studied. The goal is to present...     

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.     

On the resolution of certain discrete univariate max–min problems

Graph coloring is a classical NP-hard combinatorial optimization problem with many practical applications. A broad range of heuristic methods exist for tackling the graph coloring problem: from fast greedy algorithms to more time-consuming metaheuristics. Although the latter produce better results in terms of minimizing the number of colors, the former are widely employed due to their simplicity. These heuristic methods are centralized since they operate by using complete knowledge of the graph. However, in real-world environmets where each component only interacts with a limited number of other components, the only option is to apply decentralized methods. This paper explores a novel and simple algorithm for decentralized graph coloring that uses a fixed number of colors and iteratively reduces the edge conflicts in the graph. We experimentally demonstrate that, for most of the tested instances, the new algorithm outperforms a recent and very competitive algorithm for decentralized graph coloring in terms of coloring quality. In our experiments, the fixed number of colors used by the new algorithm is controlled in a centralized manner.     

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.     

Solving fuzzy multi-objective linear programming problems using deviation degree measures and weighted max–min method

This paper proposes a method for solving fuzzy multi-objective linear programming (FMOLP) problems where all the coefficients are triangular fuzzy numbers and all the constraints are fuzzy equality or inequality. Using the deviation degree measures and weighted max–min method, the FMOLP problem is transformed into crisp linear programming (CLP) problem. If decision makers fix the values of deviation degrees of two side fuzzy numbers in each constraint, then the δ-pareto-optimal solution of the FMOLP problems can be obtained by solving the CLP problem. The bigger the values of the deviation degrees are, the better the objectives function values will be. So we also propose an algorithm to find a balance-pareto-optimal solution between two goals in conflict: to improve the objectives function values and to decrease the values of the deviation degrees. Finally, to illustrate our method, we solve a numerical example.     

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).     

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.     

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$.     

General approach to filtering with fractional brownian noises — application to linear systems

At first a general approach is proposed to filtering in systems where the observation noise is a fractional Brownian motion. It is shown that the problem can be handled in terms of some appropriate semimartingale and analogs of the classical innovation process and fundamental filtering theorem are obtained. Then the problem of optimal filtering is completely solved for Gaussian linear systems with fractional Brownian noises. Closed form simple equations are derived both for the mean of the optimal filter and the variance of the filtering error. Finally the results are explicited in various specific cases     

Analytical solution to nonlinear oscillation system of the motion of a rigid rod rocking back using max–min approach

This paper used an ideal periodic solution which is called max–min approach (MMA) to evaluate oscillation systems with nonlinearity terms such as motion of a rigid rod rocking back. This method introduces an alternative to overcome the difficulty of computing the periodic behavior of the oscillation problems in engineering. To assess the accuracy of solutions, the results were compared with the exact ones. The most significant features of this method are the simplicity and the excellent agreement with the exact results for the various parameters. Furthermore, the results reveal that one iteration leads to high accuracy of the solution. This solution may be useful for the explanation of some practical physical problems.     

Min–max and min–max (relative) regret approaches to representatives selection problem

The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min?Cmax and min?Cmax (relative) regret approaches are used for making a selection decision. The arising min?Cmax, min?Cmax regret and min?Cmax relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.     

From Sturm–Liouville problems to fractional and anomalous diffusions

Some fractional and anomalous diffusions are driven by equations involving fractional derivatives in both time and space. Such diffusions are processes with randomly varying times. In representing the solutions to those equations, the explicit laws of certain stable processes turn out to be fundamental. This paper directs one’s efforts towards the explicit representation of solutions to fractional and anomalous diffusions related to Sturm–Liouville problems of fractional order associated to fractional power function spaces. Furthermore, we study a new version of Bochner’s subordination rule and we establish some connections between subordination and space-fractional operators.     

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.     

The first-order approach to the principal–agent problems under inequality aversion

This paper considers the principal–agent problems under inequality aversion. We identify sufficient conditions for the first-order approach to be valid. Our results suggest that the first-order approach is restricted in the presence of inequality aversion.     

An alternative approach to the Faber–Krahn inequality for Robin problems

We give a simple proof of the Faber–Krahn inequality for the first eigenvalue of the p-Laplace operator with Robin boundary conditions. The techniques introduced allow to work with much less regular domains by using test function arguments. We substantially simplify earlier proofs, and establish the sharpness of the inequality for a larger class of domains at the same time.     

On the polynomial mixed 0–1 fractional programming problems

This paper proposes a new method of solving polynomial mixed 0–1 fractional programming (P01FP) problems to obtain a global optimum. Given a polynomial 0–1 term x₁x₂,…,x_ny, where x_i is a 0–1 variable and y is a continuous variable; we develop a linearization technique to transfer the x₁x₂,…,x_ny term into a set of mixed 0–1 linear inequalities. Based on this technique, the P01FP can then be solved by a branch-and-bound method to obtain the global solution.     

An inference–proof approach to privacy-preserving horizontally partitioned linear programs

Mangasarian (Optim. Lett., 6(3), 431–436, 2012) proposed a constraints transformation based approach to securely solving the horizontally partitioned linear programs among multiple entities—every entity holds its own private equality constraints. More recently, Li et al. (Optim. Lett., doi:10.1007/s11590-011-0403-2, 2012) extended the transformation approach to horizontally partitioned linear programs with inequality constraints. However, such transformation approach is not sufficiently secure – occasionally, the privately owned constraints are still under high risk of inference. In this paper, we present an inference–proof algorithm to enhance the security for privacy-preserving horizontally partitioned linear program with arbitrary number of equality and inequality constraints. Our approach reveals significantly less information than the prior work and resolves the potential inference attack.