A Bilinear Algorithm for Optimizing a Linear Function over the Efficient Set of a Multiple Objective Linear Programming Problem

The problem Q of optimizing a linear function over the efficient set of a multiple objective linear program serves several useful purposes in multiple criteria decision making. However, Q is in itself a difficult global optimization problem, whose local optima, frequently large in number, need not be globally optimal. Indeed, this is due to the fact that the feasible region of Q is, in general, a nonconvex set. In this paper we present a monotonically increasing algorithm that finds an exact, globally-optimal solution for Q. Our approach does not require any hypothesis on the boundedness of neither the efficient set EP nor the optimal objective value. The proposed algorithm relies on a simplified disjoint bilinear program that can be solved through the use of well-known specifically designed methods within nonconvex optimization. The algorithm has been implemented in C and preliminary numerical results are reported.     

Nonsmooth nonconvex optimization approach to clusterwise linear regression problems

Clusterwise regression consists of finding a number of regression functions each approximating a subset of the data. In this paper, a new approach for solving the clusterwise linear regression problems is proposed based on a nonsmooth nonconvex formulation. We present an algorithm for minimizing this nonsmooth nonconvex function. This algorithm incrementally divides the whole data set into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate a good starting point for solving global optimization problems at each iteration of the incremental algorithm. Such an approach allows one to find global or near global solution to the problem when the data sets are sufficiently dense. The algorithm is compared with the multistart Späth algorithm on several publicly available data sets for regression analysis.     

Infinite end-devouring sets of rays with prescribed start vertices

We prove that every end of a graph contains either uncountably many disjoint rays or a set of disjoint rays that meet all rays of the end and start at any prescribed feasible set of start vertices. This confirms a conjecture of Georgakopoulos.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

A finite,nonadjacent extreme-point search algorithm for optimization over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.The author owes thanks to two anonymous referees for their helpful comments.     

Maximally diverse grouping: an iterated tabu search approach

The maximally diverse grouping problem (MDGP) consists of finding a partition of a set of elements into a given number of mutually disjoint groups, while respecting the requirements of group size constraints and diversity. In this paper, we propose an iterated tabu search (ITS) algorithm for solving this problem. We report computational results on three sets of benchmark MDGP instances of size up to 960 elements and provide comparisons of ITS to five state-of-the-art heuristic methods from the literature. The results demonstrate the superiority of the ITS algorithm over alternative approaches. The source code of the algorithm is available for free download via the internet.     

Global Optimization Versus Integer Programming in Portfolio Optimization under Nonconvex Transaction Costs

This paper is concerned with a portfolio optimization problem under concave and piecewise constant transaction cost. We formulate the problem as nonconcave maximization problem under linear constraints using absolute deviation as a measure of risk and solve it by a branch and bound algorithm developed in the field of global optimization. Also, we compare it with a more standard 0–1 integer programming approach. We will show that a branch and bound method elaborating the special structure of the problem can solve the problem much faster than the state-of-the integer programming code.     

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

Multiplicative programming problems (MPPs) are global optimization problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programmes (MOLPs) to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration, instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLPs, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our algorithms to a recent global optimization algorithm for linear MPPs from the literature as well as two general global optimization solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus, we demonstrate that the use of multi-objective optimization techniques can be beneficial to solve difficult single objective global optimization problems.     

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided.     

Density of the circular chromatic numbers of series‐parallel graphs

In this paper we show that every simple cubic graph on n vertices has a set of at least ? n/4 ? disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003     

Fully gated graphs: Recognition and convex operations

A graph is fully gated when every convex set of vertices is gated. Doignon posed the problem of characterizing fully gated graphs and in particular of deciding whether there is an efficient algorithm for their recognition. While the number of convex sets can be exponential, we establish that it suffices to examine only the convex hulls of pairs of vertices. This yields an elementary polynomial time algorithm for the recognition of fully gated graphs; however, it does not appear to lead to a simple structural characterization. In this direction, we establish that fully gated graphs are closed under a set of ‘convex’ operations, including a new operation which duplicates the vertices of a convex set (under some well-defined restrictions). This in turn establishes that every bipartite graph is an isometric subgraph of a fully gated graph, thereby severely limiting the potential for a characterization based on subgraphs. Finally, a large class of fully gated graphs is obtained using the presence of bipartite dominators, which suggests that simple convex operations cannot suffice to produce all fully gated graphs.     

Monotonic optimization based decoding for linear codes

New efficient methods are developed for the optimal maximum-likelihood (ML) decoding of an arbitrary binary linear code based on data received from any discrete Gaussian channel. The decoding algorithm is based on monotonic optimization that is minimizing a difference of monotonic (d.m.) objective functions subject to the 0–1 constraints of bit variables. The iterative process converges to the global optimal ML solution after finitely many steps. The proposed algorithm’s computational complexity depends on input sequence length k which is much less than the codeword length n, especially for a codes with small code rate. The viability of the developed is verified through simulations on different coding schemes.     

The optimal representation of disjoint iso-oriented rectangles in two-dimensional trees

Partitions of the plane are often used to design an efficient data structure for configurations in the plane. In this publication we will use recursive iso-oriented partitions in order to design a search tree data structure for a set S of mutually disjoint iso-oriented rectangles. We will consider two optimization criteria for the choice of the partitions: minimization of the size of the tree and minization of the search time. We will present polynomial time algorithms to find recursive iso-oriented partitions for both optimization criteria separately. We will show that for some arbitrarily large sets S there is a trade-off between the size of the tree and the height of the tree. However, we will prove that for each set S of rectangles logarithmic search time can be obtained with a tree of almost linear size. Such a tree can be found in time almost quadratic in the size of S.     

Fractional set systems with few disjoint pairs

Ahlswede (1980) [1] and Frankl (1977) [5] independently found a result about the structure of set systems with few disjoint pairs. Bollobás and Leader (2003) [3] gave an alternate proof by generalizing to fractional set systems and noting that the optimal fractional set systems are {0,1}-valued. In this paper we show that this technique does not extend to t-intersecting families. We find optimal fractional set systems for some infinite classes of parameters, and we point out that they are strictly better than the corresponding {0,1}-valued fractional set systems. We prove some results about the structure of an optimal fractional set system, which we use to produce an algorithm for finding such systems. The run time of the algorithm is polynomial in the size of the ground set.     

Some Variants of the Controlled Random Search Algorithm for Global Optimization

We suggested some modifications to the controlled random search (CRS) algorithm for global optimization. We introduce new trial point generation schemes in CRS, in particular, point generation schemes using linear interpolation and mutation. Central to our modifications is the probabilistic adaptation of point generation schemes within the CRS algorithm.A numerical study is carried out using a set of 50 test problems many of which are inspired by practical applications. Numerical experiments indicate that the resulting algorithms are considerably better than the previous versions. Thus, they offer a reasonable alternative to many currently available stochastic algorithms, especially for problems requiring direct search type methods.     

A Newton-type univariate optimization algorithm for locating the nearest extremum

This paper introduces an algorithm for univariate optimization using linear lower bounding functions (LLBF's). An LLBF over an interval is a linear function which lies below the given function over an interval and matches the given function at one end point of the interval. We first present an algorithm using LLBF's for finding the nearest root of a function in a search direction. When the root-finding method is applied to the derivative of an objective function, it is an optimization algorithm which guarantees to locate the nearest extremum along a search direction. For univariate optimization, we show that this approach is a Newton-type method, which is globally convergent with superlinear convergence rate. The applications of this algorithm to global optimization and other optimization problems are also discussed.     

A global supply chain model with transfer pricing and transportation cost allocation

We present a model for the optimization of a global supply that maximizes the after tax profits of a multinational corporation and that includes transfer prices and the allocation of transportation costs as explicit decision variables. The resulting mathematical formulation is a non-convex optimization problem with a linear objective function, a set of linear constraints, and a set of bilinear constraints. We develop a heuristic solution algorithm that applies successive linear programming based on the reformulation and the relaxation of the original problem. Our computational experiments investigate the impact of using different starting points. The algorithm produces feasible solutions with very small gaps between the solutions and their upper bound (UB).     

Hybrid evolutionary algorithm for solving general variational inequality problems

This paper considers the problem of finding as many as possible, hopefully all, solutions of the general (i.e., not necessarily monotone) variational inequality problem (VIP). Based on global optimization reformulation of VIP, we propose a hybrid evolutionary algorithm that incorporates local search in promising regions. In order to prevent searching process from returning to the already detected global or local solutions, we employ the tunneling and hump-tunneling function techniques. The proposed algorithm is tested on a set of test problems in the MCPLIB library and numerical results indicate that it works well in practice.     

A simulated annealing driven multi-start algorithm for bound constrained global optimization

A derivative-free simulated annealing driven multi-start algorithm for continuous global optimization is presented. We first propose a trial point generation scheme in continuous simulated annealing which eliminates the need for the gradient-based trial point generation. We then suitably embed the multi-start procedure within the simulated annealing algorithm. We modify the derivative-free pattern search method and use it as the local search in the multi-start procedure. We study the convergence properties of the algorithm and test its performance on a set of 50 problems. Numerical results are presented which show the robustness of the algorithm. Numerical comparisons with a gradient-based simulated annealing algorithm and three population-based global optimization algorithms show that the new algorithm could offer a reasonable alternative to many currently available global optimization algorithms, specially for problems requiring ‘direct search’ type algorithm.