Global tolerances in the problems of combinatorial optimization with an additive objective function

It is known that by means of minimal values of tolerances one can obtain necessary and sufficient conditions for the uniqueness of the optimal solution of a combinatorial optimization problem (COP) with an additive objective function and the set of nonembedded feasible solutions. Moreover, the notion of a tolerance is defined locally, i.e., with respect to a chosen optimal solution. In this paper we introduce the notion of a global tolerance with respect to the whole set of optimal solutions and prove that the nonembeddedness assumption on the set of feasible solutions of the COP can be relaxed, which generalizes the well known relations for the extremal values of the tolerances. In particular, we formulate a new criterion for the uniqueness of the optimal solution of the COP with an additive objective function, which is based on certain equalities between locally and globally defined tolerances.     

Approximating a class of combinatorial problems with rational objective function

In the late seventies, Megiddo proposed a way to use an algorithm for the problem of minimizing a linear function a ₀ + a ₁ x ₁ + . . . + a _n x _n subject to certain constraints to solve the problem of minimizing a rational function of the form (a ₀ + a ₁ x ₁ + . . . + a _n x _n )/(b ₀ + b ₁ x ₁ + . . . + b _n x _n ) subject to the same set of constraints, assuming that the denominator is always positive. Using a rather strong assumption, Hashizume et al. extended Megiddo’s result to include approximation algorithms. Their assumption essentially asks for the existence of good approximation algorithms for optimization problems with possibly negative coefficients in the (linear) objective function, which is rather unusual for most combinatorial problems. In this paper, we present an alternative extension of Megiddo’s result for approximations that avoids this issue and applies to a large class of optimization problems. Specifically, we show that, if there is an α-approximation for the problem of minimizing a nonnegative linear function subject to constraints satisfying a certain increasing property then there is an α-approximation (1/α-approximation) for the problem of minimizing (maximizing) a nonnegative rational function subject to the same constraints. Our framework applies to covering problems and network design problems, among others.     

On computing objective function values in multiple objective quadratic-linear programming

In this paper, we will consider the computation of objective function values when a nondominated frontier is searched in multiple objective quadratic-linear programming (MOQLP). Reference directions and weighted-sums constitute a methodological basis for the search. This idea leads to a parametric linear complementarity model formulation. A critical task of making a search procedure efficient, is to compute the changes in quadratic and linear objective functions efficiently when a search direction is changed or a basis change is performed. Those changes in objective functions can be computed by a so-called direct or indirect method. The direct method is a straightforward one and based on the use of unit changes in basic decision variables. Instead, the indirect method utilizes some other basic variables of the model. We will introduce the indirect method and make theoretical and empirical comparisons between the methods. Based on the comparisons, we point out that the indirect method is clearly much more efficient than the direct one.     

Internal modelling of objective functions for global optimization

Global optimization requires an adequate internal representation of the objective function for success in a reasonable number of function evaluations. A method for determining the location of a new function evaluation, based on a representation using a stationary stochastic process model, is investigated and some results are given.     

The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems

Due to the growing interest in approximation for multiobjective optimization problems (MOPs), a theoretical framework for defining and classifying sets representing or approximating solution sets for MOPs is developed. The concept of tolerance function is proposed as a tool for modeling representation quality. This notion leads to the extension of the traditional dominance relation to \(t\hbox {-}\)dominance. Two types of sets representing the solution sets are defined: covers and approximations. Their properties are examined in a broader context of multiple solution sets, multiple cones, and multiple quality measures. Applications to complex MOPs are included.     

The Karush–Kuhn–Tucker optimality conditions in an optimization problem with interval-valued objective function

The KKT conditions in an optimization problem with interval-valued objective function are derived in this paper. Two solution concepts of this optimization problem are proposed by considering two partial orderings on the set of all closed intervals. In order to consider the differentiation of an interval-valued function, we invoke the Hausdorff metric to define the distance between two closed intervals and the Hukuhara difference to define the difference of two closed intervals. Under these settings, we derive the KKT optimality conditions.     

The KKT optimality conditions in a class of generalized convex optimization problems with an interval-valued objective function

In this paper, we study the Karush–Kuhn–Tucker optimality conditions in a class of nonconvex optimization problems with an interval-valued objective function. Firstly, the concepts of preinvexity and invexity are extended to interval-valued functions. Secondly, several properties of interval-valued preinvex and invex functions are investigated. Thirdly, the KKT optimality conditions are derived for LU-preinvex and invex optimization problems with an interval-valued objective function under the conditions of weakly continuous differentiablity and Hukuhara differentiablity. Finally, the relationships between a class of variational-like inequalities and the interval-valued optimization problems are established.     

Improving the efficiency of DC global optimization methods by improving the DC representation of the objective function

There are infinitely many ways of representing a d.c. function as a difference of convex functions. In this paper we analyze how the computational efficiency of a d.c.optimization algorithm depends on the representation we choose for the objective function, and we address the problem of characterizing and obtaining a computationally optimal representation. We introduce some theoretical concepts which are necessary for this analysis and report some numerical experiments.      

Extremal extension of a finitely additive measure

Translated from Matematicheskie Zametki, Vol. 43, No. 1, pp. 25–30, January, 1988.     

Solving nonlinearly constrained global optimization problem via an auxiliary function method

This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems.     

The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization

A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising boxes, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.     

On an additive representation function

Let A be an infinite subset of natural numbers, and X a positive real number. Let r(n) denotes the number of solution of the equation n=a₁+a₂ where a₁?a₂ and a₁, a₂∈A. Also let |A(X)| denotes the number of natural numbers which are less than or equal to X and belong to A. For those A which satisfy the condition that for all sufficiently large natural numbers n we have r(n)≠1, we improve the lower bound of |A(X)| given by Nicolas et. al. [NRS98]. The bound which we obtain is essentially best possible.     

Solving combinatorial problems with combined Min-Max-Min-Sum objective and applications

The purpose of this paper is to introduce and study a new class of combinatorial optimization problems in which the objective function is the algebraic sum of a bottleneck cost function (Min-Max) and a linear cost function (Min-Sum). General algorithms for solving such problems are described and general complexity results are derived. A number of examples of application involving matchings, paths and cutsets, matroid bases, and matroid intersection problems are examined, and the general complexity results are specialized to each of them. The interest of these various problems comes in particular from their strong relation to other important and difficult combinatorial problems such as: weighted edge coloring of a graph; optimum weighted covering with matroid bases; optimum weighted partitioning with matroid intersections, etc. Another important area of application of the algorithms given in the paper is bicriterion analysis involving a Min-Max criterion and a Min-Sum one.     

Modified objective function method in nonsmooth vector optimization over cones

In this paper optimality for a nonsmooth vector optimization problem having generalized cone-invex objective and constraint functions is considered. An equivalent $\eta $ -approximated vector optimization problem is constructed by a modification of the objective function. The relationships between weakly efficient solutions and saddle points of the two problems are studied.     

The Karush-Kuhn-Tucker optimality conditions for the optimization problem with fuzzy-valued objective function

The Karush-Kuhn-Tucker (KKT) conditions for an optimization problem with fuzzy-valued objective function are derived in this paper. A solution concept of this optimization problem is proposed by considering an ordering relation on the class of all fuzzy numbers. The solution concept proposed in this paper will follow from the similar solution concept, called non-dominated solution, in the multiobjective programming problem. In order to consider the differentiation of a fuzzy-valued function, we use the Hausdorff metric to define the distance between two fuzzy numbers and the Hukuhara difference to define the difference of two fuzzy numbers. Under these settings, the KKT optimality conditions are elicited naturally by introducing the Lagrange function multipliers.     

On a new naturally indexed quick clustering method with a global objective function

A new clustering method is presented which proposes a class of objective functions and an algorithm which sub-optimizes the objective functions over the whole space of partitions. The objective functions have a global nature, encompassing both the cluster contents and the cluster number. However, the accompanying suboptimization algorithm works according to a simple progressive merger scheme. The algorithmic scheme produces in a quite natural way an indexed hierarchy. The hierarchy index is not just tacked on to the method—see Diday and Moreau¹—on the contrary, the algorithm refers directly to its values which measure, depending upon the particular formulation, either the relative affinity or the relative difference of the two clusters merged at a given level of hierarchy. In this way, the scale of hierarchy and hierarchy-wise validity of clusters can easily be established, which is of great importance in analysing unstructured data sets whose generating process is unknown and can only be hypothesized after an initial structure had been established, e.g. owing to clustering, as is the case in pattern recognition—see Kaminuma².     

A cut-peak function method for global optimization

A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods.     

A filled function method for global optimization

A novel filled function with one parameter is suggested in this paper for finding a global minimizer for a general class of nonlinear programming problems with a closed bounded box. A new algorithm is presented according to the theoretical analysis. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.