A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables

Geometric branch-and-bound techniques are well-known solution algorithms for non-convex continuous global optimization problems with box constraints. Several approaches can be found in the literature differing mainly in the bounds used.     

A distributed computation algorithm for solving portfolio problems with integer variables

A portfolio problem with integer variables can facilitate the use of complex models, including models containing discrete asset values, transaction costs, and logical constraints. This study proposes a distributed algorithm for solving a portfolio program to obtain a global optimum. For a portfolio problem with n integer variables, the objective function first is converted into an ellipse function containing n separated quadratic terms. Next, the problem is decomposed into m equal-size separable programming problems solvable by a distributed computation system composed of m personal computers linked via the Internet. The numerical examples illustrate that the proposed method can obtain the global optimum effectively for large scale portfolio problems involving integral variables.     

Hybrid scatter tabu search for unconstrained global optimization

The problem of finding a global optimum of an unconstrained multimodal function has been the subject of intensive study in recent years, giving rise to valuable advances in solution methods. We examine this problem within the framework of adaptive memory programming (AMP), focusing particularly on AMP strategies that derive from an integration of Scatter Search and Tabu Search. Computational comparisons involving 16 leading methods for multimodal function optimization, performed on a testbed of 64 problems widely used to calibrate the performance of such methods, disclose that our new Scatter Tabu Search (STS) procedure is competitive with the state-of-the-art methods in terms of the average optimality gap achieved.     

Implicitly and densely discrete black-box optimization problems

This paper addresses derivative-free optimization problems where the variables lie implicitly in an unknown discrete closed set. The evaluation of the objective function follows a projection onto the discrete set, which is assumed dense (and not sparse as in integer programming). Such a mathematical setting is a rough representation of what is common in many real-life applications where, despite the continuous nature of the underlying models, a number of practical issues dictate rounding of values or projection to nearby feasible figures. We discuss a definition of minimization for these implicitly discrete problems and outline a direct-search algorithm framework for its solution. The main asymptotic properties of the algorithm are analyzed and numerically illustrated.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.     

Deterministic global derivative-free optimization of black-box problems with bounded Hessian

Obtaining guaranteed lower bounds for problems with unknown algebraic form has been a major challenge in derivative-free optimization. In this work, we pre     

A breakpoint search approach for convex resource allocation problems with bounded variables

We present an efficient approach to solve resource allocation problems with a single resource, a convex separable objective function, a convex separable resource-usage constraint, and variables that are bounded below and above. Through a combination of function evaluations and median searches, information on whether or not the upper- and lowerbounds are binding is obtained. Once this information is available for all upper and lower bounds, it remains to determine the optimum of a smaller problem with unbounded variables. This can be done through a multiplier search procedure. The information gathered allows for alternative approaches for the multiplier search which can reduce the complexity of this procedure.     

A minimax search plan for constrained optimization problems

A minimax search strategy is described for locating the boundary point of a region on a line joining a feasible point to an infeasible point. Asymptotic strategies, useful when the number of experiments to be used in the search is not predetermined, are also given. These strategies are useful subroutines for many multidimensional optimization algorithms.The authors thank G. V. Reklaitis for initial discussions concerning this problem. John H. Beamer was an NSF Graduate Fellow at the time when this research was conducted.     

Integrating partial optimization with scatter search for solving bi-criteria {0, 1}-knapsack problems

This paper deals with the problem of inaccuracy of the solutions generated by metaheuristic approaches for combinatorial optimization bi-criteria {0, 1}-knapsack problems. A hybrid approach which combines systematic and heuristic searches is proposed to reduce that inaccuracy in the context of a scatter search method. The components of this method are used to determine regions in the decision space to be systematically searched.     

Cutting planes for integer programs with general integer variables

We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was partly performed when the author was affiliated with CORE, Université Catholique de Louvain.     

Error bounds for mixed integer nonlinear optimization problems

We introduce a-posteriori and a-priori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the NLP relaxation of a mixed-integer nonlinear optimization problem. Our analysis mainly bases on the construction of a tractable approximation of the so-called grid relaxation retract. Under appropriate Lipschitz assumptions on the defining functions, we thereby generalize and slightly improve results for the mixed-integer linear case from Stein (Mathematical Programming, 2015, doi: 10.1007/s10107-015-0872-7). In particular, we identify cases in which the optimality and feasibility errors tend to zero at an at least linear rate for increasingly refined meshes.     

A continuous method for computing bounds in integer quadratic optimization problems

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x ^T Q x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1} ⁿ . We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in [4]. In this paper, we extend this method by using techniques of differential geometry.     

A dual local search framework for combinatorial optimization problems with TSP application

In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart.     

Implementation of scatter search for multi-objective optimization: a comparative study

Interest in the design of efficient meta-heuristics for the application to combinatorial optimization problems is growing rapidly. The optimal design of water distribution networks is an important optimization problem which consists of finding the best way of conveying water from the sources to the users, thus satisfying their requirements. The efficient design of looped networks is a much more complex problem than the design of branched ones, but their greater reliability can compensate for the increase in cost when closing some loops. Mathematically, this is a non-linear optimization problem, constrained to a combinatorial space, since the diameters are discrete and it has a very large number of local solutions. Many works have dealt with the minimization of the cost of the network but few have considered their cost and reliability simultaneously. The aim of this paper is to evaluate the performance of an implementation of Scatter Search in a multi-objective formulation of this problem. Results obtained in three benchmark networks show that the method here proposed performs accurately well in comparison with other multi-objective approaches also implemented.     

Degeneracy in integer linear optimization problems: A selected bibliography

Annals of Operations Research -     

解线性等式约束优化问题的模式搜索过滤集方法

提出一个解线性等式约束无导数优化的模式搜索过滤集算法,该算法将过滤集技术嵌入无导数优化算法中以改善算法的效率. 建立了新算法的总体收敛性, 初步的数值试验结果表明新算法是有效的.     

Global optimization for generalized geometric programming problems with discrete variables

Generalized geometric programming (GGP) problems occur frequently in engineering design and management, but most existing methods for solving GGP actually only consider continuous variables. This article presents a new branch-and-bound algorithm for globally solving GGP problems with discrete variables. For minimizing the problem, an equivalent monotonic optimization problem (P) with discrete variables is presented by exploiting the special structure of GGP. In the algorithm, the lower bounds are computed by solving ordinary linear programming problems that are derived via a linearization technique. In contrast to pure branch-and-bound methods, the algorithm can perform a domain reduction cut per iteration by using the monotonicity of problem (P), which can suppress the rapid growth of branching tree in the branch-and-bound search so that the performance of the algorithm is further improved. Computational results for several sample examples and small randomly generated problems are reported to vindicate our conclusions.     

Ideal formulations for constrained convex optimization problems with indicator variables

Mathematical Programming - Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and...