Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems

As indicated by the most widely accepted classification, the Multi-Objective Mathematical Programming (MOMP) methods can be classified as a priori, interactive and a posteriori, according to the decision stage in which the decision maker expresses his/her preferences. Although the a priori methods are the most popular, the interactive and the a posteriori methods convey much more information to the decision maker. Especially, the a posteriori (or generation) methods give the whole picture (i.e. the Pareto set) to the decision maker, before his/her final choice, reinforcing thus, his/her confidence to the final decision. However, the generation methods are the less popular due to their computational effort and the lack of widely available software. The present work is an effort to effectively implement the ε-constraint method for producing the Pareto optimal solutions in a MOMP. We propose a novel version of the method (augmented ε-constraint method - AUGMECON) that avoids the production of weakly Pareto optimal solutions and accelerates the whole process by avoiding redundant iterations. The method AUGMECON has been implemented in GAMS, a widely used modelling language, and has already been used in some applications. Finally, an interactive approach that is based on AUGMECON and eventually results in the most preferred Pareto optimal solution is also proposed in the paper.     

Portfolio construction on the Athens Stock Exchange: a multiobjective optimization approach

In this research article, our purpose is to propose a single-period multiobjective mixed-integer programming model for equity portfolio construction, in order to generate the Pareto optimal portfolios, using a variant of the well-known ε-constraint method. The decision maker's investment policy, i.e. constraints regarding the portfolio structure, is strongly taken into account. An illustrative application in the Athens Stock Exchange market is also presented.     

On the exactness of the ε-constraint method for biobjective nonlinear integer programming

The ε-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness when dealing with biobjective nonlinear integer problems. Under specific assumptions, we prove that the number of subproblems that the method needs to address to detect the complete Pareto front is finite. We report numerical results on portfolio optimization instances built on real-world data and show a comparison with an existing criterion space algorithm.     

Interactive bicriterion decision support for a large scale industrial scheduling system

In this paper we develop an interactive decision analysis approach to treat a large scale bicriterion integer programming problem, addressing a real world assembly line scheduling problem of a manufacturing company. This company receives periodically a set of orders for the production of specific items (jobs) through a number of specialised production (assembly) lines. The paper presents a non compensatory approach based on an interactive implementation of the ε-constraint method that enables the decision maker to achieve a satisfactory goal for each objective separately. In fact, the method generates and evaluates a large number of non dominated solutions that constitute a representative sample of the criteria ranges. The experience with a specific numerical example shows the efficiency and usefulness of the proposed model in solving large scale bicriterion industrial integer programming problems, highlighting at the same time the modelling limitations.     

Equity portfolio construction and selection using multiobjective mathematical programming

A multi-objective mixed integer programming model for equity portfolio construction and selection is developed in this study, in order to generate the Pareto optimal portfolios, using a novel version of the well known ε-constraint method. Subsequently, an interactive filtering process is also proposed to assist the decision maker in making his/her final choice among the Pareto solutions. The proposed methodology is tested through an application in the Athens Stock Exchange.     

An approach to generate comprehensive piecewise linear interpolation of pareto outcomes to aid decision making

Multiple criteria decision making is a well established field encompassing aspects of search for solutions and selection of solutions in presence of more than one conflicting objectives. In this paper, we discuss an approach aimed towards the latter. The decision maker is presented with a limited number of Pareto optimal outcomes and is required to identify regions of interest for further investigation. The inherent sparsity of the given Pareto optimal outcomes in high dimensional space makes it an arduous task for the decision maker. To address this problem, an existing line of thought in literature is to generate a set of approximated Pareto optimal outcomes using piecewise linear interpolation. We present an approach within this paradigm, but one that delivers a comprehensive linearly interpolated set as opposed to its subset delivered by existing methods. We illustrate the advantage in doing so in comparison to stricter non-dominance conditions imposed in existing PAreto INTerpolation method. The interpolated set of outcomes delivered by the proposed approach are non-dominated with respect to the given Pareto optimal outcomes, and additionally the interpolated outcomes along uniformly distributed reference directions are presented to the decision maker. The errors in the given interpolations are also estimated in order to further aid decision making by establishing confidence in achieving true Pareto outcomes in their vicinity. The proposed approach for interpolation is computationally less demanding (for higher number of objectives) and also further amenable to parallelization. We illustrate the performance of the approach using six well established tri-objective test problems and two real-life examples. The problems span different types of fronts, such as convex, concave, mixed, degenerate, highlighting the wide applicability of the approach.     

Additive properties of product sets in the field $$ \mathbb{F}_{p^2 } $$

For given positive integer n and ε > 0 we consider an arbitrary nonempty subset A of a field consisting of p ² elements such that its cardinality exceeds p ^2/n?ε . We study the possibility to represent an arbitrary element of the field as a sum of at most N(n, ε) elements from the nth degree of the set A. An upper estimate for the number N(n, ε) is obtained when it is possible.     

Structural adaptive deconvolution under $${\mathbb{L}_p}$$-losses

In this paper, we address the problem of estimating a multidimensional density f by using indirect observations from the statistical model Y = X + ε. Here, ε is a measurement error independent of the random vector X of interest and having a known density with respect to Lebesgue measure. Our aim is to obtain optimal accuracy of estimation under \({\mathbb{L}_p}\)-losses when the error ε has a characteristic function with a polynomial decay. To achieve this goal, we first construct a kernel estimator of f which is fully data driven. Then, we derive for it an oracle inequality under very mild assumptions on the characteristic function of the error ε. As a consequence, we getminimax adaptive upper bounds over a large scale of anisotropic Nikolskii classes and we prove that our estimator is asymptotically rate optimal when p ∈ [2,+∞]. Furthermore, our estimation procedure adapts automatically to the possible independence structure of f and this allows us to improve significantly the accuracy of estimation.     

Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

Modified Kantorovich theorem and asymptotic approximations of solutions to singularly perturbed systems of ordinary differential equations

The functional equation f(x,ε) = 0 containing a small parameter ε and admitting regular and singular degeneracy as ε → 0 is considered. By the methods of small parameter, a function x _n ⁰(ε) satisfying this equation within a residual error of O(ε ⁿ⁺¹) is found. A modified Newton’s sequence starting from the element x _n ⁰(ε) is constructed. The existence of the limit of Newton’s sequence is based on the NK theorem proven in this work (a new variant of the proof of the Kantorovich theorem substantiating the convergence of Newton’s iterative sequence). The deviation of the limit of Newton’s sequence from the initial approximation x _n ⁰(ε) has the order of O(ε ⁿ⁺¹), which proves the asymptotic character of the approximation x _n ⁰(ε). The method proposed is implemented in constructing an asymptotic approximation of a system of ordinary differential equations on a finite or infinite time interval with a small parameter multiplying the derivatives, but it can be applied to a wider class of functional equations with a small parameters.     

Variants of the $$ \vare psilon $$-constraint method for biobjective integer programming problems: a p plication to p-median-cover problems

We conduct an in-depth analysis of the \(\varepsilon \)-constraint method (ECM) for finding the exact Pareto front for biobjective integer programming problems. We have found up to six possible different variants of the ECM. We first discuss the complexity of each of these variants and their relationship with other exact methods for solving biobjective integer programming problems. By extending some results of Neumayer and Schweigert (OR Spektrum 16:267–276, 1994), we develop two variants of the ECM, both including an augmentation term and requiring \(N+1\) integer programs to be solved, where N is the number of nondominated points. In addition, we present another variant of the ECM, based on the use of elastic constraints and also including an augmentation term. This variant has the same complexity, namely \(N+1\), which is the minimum reached for any exact method. A comparison of the different variants is carried out on a set of biobjective location problems which we call p-median-cover problems; these include the objectives of the p-median and the maximal covering problems. As computational results show, for this class of problems, the augmented ECM with elastic constraint is the most effective variant for finding the Pareto front in an exact manner.     

Elementary Proof of an Estimate for Kloosterman Sums with Primes

A new elementary proof of an estimate for incomplete Kloosterman sums modulo a prime q is obtained. Along with Bourgain’s 2005 estimate of the double Kloosterman sum of a special form, it leads to an elementary derivation of an estimate for Kloosterman sums with primes for the case in which the length of the sum is of order q^0.5+ε, where ε is an arbitrarily small fixed number.     

Asymptotic formula for the convolution of a generalized divisor function

An asymptotic formula is obtained for the sum of terms σ _it (n)σ_-it (N - n) (t is real) over 0 < n < N with a remainder estimated by O _ε((1+|t|)^1+ε N ^3/4+ε) for any ε > 0. As a consequence, Porter’s result on a power scale for the average number of steps in the Euclidean algorithm is improved.     

The Lipschitzianity of convex vector and set-valued functions

It is well known that every scalar convex function is locally Lipschitz on the interior of its domain in finite dimensional spaces. The aim of this paper is to extend this result for both vector functions and set-valued mappings acting between infinite dimensional spaces with an order generated by a proper convex cone C. Under the additional assumption that the ordering cone C is normal, we prove that a locally C-bounded C-convex vector function is Lipschitz on the interior of its domain by two different ways. Moreover, we derive necessary conditions for Pareto minimal points of vector-valued optimization problems where the objective function is C-convex and C-bounded. Corresponding results are derived for set-valued optimization problems.     

Error estimates of numerical methods for the nonlinear Dirac equation in the nonrelativistic limit regime

We present several numerical methods and establish their error estimates for the discretization of the nonlinear Dirac equation(NLDE) in the nonrelativistic limit regime, involving a small dimensionless parameter 0 ε≤ 1 which is inversely proportional to the speed of light. In this limit regime, the solution is highly oscillatory in time, i.e., there are propagating waves with wavelength O(ε~2) and O(1) in time and space,respectively. We begin with the conservative Crank-Nicolson finite difference(CNFD) method and establish rigorously its error estimate which depends explicitly on the mesh size h and time step τ as well as the small parameter 0 ε≤ 1. Based on the error bound, in order to obtain ‘correct' numerical solutions in the nonrelativistic limit regime, i.e., 0 ε■ 1, the CNFD method requests the ε-scalability: τ = O(ε~3) and h= O(ε~(1/2)). Then we propose and analyze two numerical methods for the discretization of NLDE by using the Fourier spectral discretization for spatial derivatives combined with the exponential wave integrator and timesplitting technique for temporal derivatives, respectively. Rigorous error bounds for the two numerical methods show that their ε-scalability is improved to τ = O(ε~2) and h = O(1) when 0 ε■1. Extensive numerical results are reported to confirm our error estimates.     

Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic

The uncapacitated facility location problem (UFLP) is a popular combinatorial optimization problem with practical applications in different areas, from logistics to telecommunication networks. While most of the existing work in the literature focuses on minimizing total cost for the deterministic version of the problem, some degree of uncertainty (e.g., in the customers’ demands or in the service costs) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic UFLP (SUFLP), where optimization goals other than the minimum expected cost can be considered. The development of this simheuristic is structured in three stages: (i) first, an extremely fast savings-based heuristic is introduced; (ii) next, the heuristic is integrated into a metaheuristic framework, and the resulting algorithm is tested against the optimal values for the UFLP; and (iii) finally, the algorithm is extended by integrating it with simulation techniques, and the resulting simheuristic is employed to solve the SUFLP. Some numerical experiments contribute to illustrate the potential uses of each of these solving methods, depending on the version of the problem (deterministic or stochastic) as well as on whether or not a real-time solution is required.     

Proof of the Erdős matching conjecture in a new range

Let s > k ≧ 2 be integers. It is shown that there is a positive real ε = ε(k) such that for all integers n satisfying (s + 1)k ≦ n < (s + 1)(k + ε) every k-graph on n vertices with no more than s pairwise disjoint edges has at most \(\left( {\begin{array}{*{20}{c}} {\left( {s + 1} \right)k - 1} \\ k \end{array}} \right)\) edges in total. This proves part of an old conjecture of Erd?s.     

Spectrum of a model three-particle Schrödinger operator

We study the spectrum of a model three-particle Schrödinger operator H(ε), ε > 0. We prove that for a sufficiently small ε > 0, this operator has no bound states and no two-particle branches of the spectrum. We also obtain an estimate for the small parameter ε.     

Eigenvalue analysis of constrained minimization problem for homogeneous polynomial

In this paper, the concepts of Pareto H-eigenvalue and Pareto Z-eigenvalue are introduced for studying constrained minimization problem and the necessary and sufficient conditions of such eigenvalues are given. It is proved that a symmetric tensor has at least one Pareto H-eigenvalue (Pareto Z-eigenvalue). Furthermore, the minimum Pareto H-eigenvalue (or Pareto Z-eigenvalue) of a symmetric tensor is exactly equal to the minimum value of constrained minimization problem of homogeneous polynomial deduced by such a tensor, which gives an alternative methods for solving the minimum value of constrained minimization problem. In particular, a symmetric tensor \({\mathcal {A}}\) is strictly copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is positive, and \({\mathcal {A}}\) is copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is non-negative.     

Geometric properties of the ridge function manifold

We study geometrical properties of the ridge function manifold \(\mathcal{R}_n\) consisting of all possible linear combinations of n functions of the form g(a· x), where a·x is the inner product in \({\mathbb R}^d\). We obtain an estimate for the ε-entropy numbers in terms of smaller ε-covering numbers of the compact class G _n,s formed by the intersection of the class \(\mathcal{R}_n\) with the unit ball \(B\mathcal{P}_s^d\) in the space of polynomials on \({\mathbb R}^d\) of degree s. In particular we show that for n?≤?s ^d???1 the ε-entropy number H _ε (G _n,s,L _q ) of the class G _n,s in the space L _q is of order nslog1/ε (modulo a logarithmic factor). Note that the ε-entropy number \(H_\varepsilon(B\mathcal{P}_s^d,L_q)\) of the unit ball is of order s ^d log1/ε. Moreover, we obtain an estimate for the pseudo-dimension of the ridge function class G _n,s.