Experiments with a new selection criterion in a fast interval optimization algorithm

Usually, interval global optimization algorithms use local search methods to obtain a good upper (lower) bound of the solution. These local methods are based on point evaluations. This paper investigates a new local search method based on interval analysis information and on a new selection criterion to direct the search. When this new method is used alone, the guarantee to obtain a global solution is lost. To maintain this guarantee, the new local search method can be incorporated to a standard interval GO algorithm, not only to find a good upper bound of the solution, but also to simultaneously carry out part of the work of the interval B&B algorithm. Moreover, the new method permits improvement of the guaranteed upper bound of the solution with the memory requirements established by the user. Thus, the user can avoid the possible memory problems arising in interval GO algorithms, mainly when derivative information is not used. The chance of reaching the global solution with this algorithm may depend on the established memory limitations. The algorithm has been evaluated numerically using a wide set of test functions which includes easy and hard problems. The numerical results show that it is possible to obtain accurate solutions for all the easy functions and also for the investigated hard problems.     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

A branch and bound algorithm for the matrix bandwidth minimization

In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the proposed algorithm compares favourably to previous methods.     

A honey-bee mating optimization algorithm for educational timetabling problems

In this work, we propose a variant of the honey-bee mating optimization algorithm for solving educational timetabling problems. The honey-bee algorithm is a nature inspired algorithm which simulates the process of real honey-bees mating. The performance of the proposed algorithm is tested over two benchmark problems; exam (Carter’s un-capacitated datasets) and course (Socha datasets) timetabling problems. We chose these two datasets as they have been widely studied in the literature and we would also like to evaluate our algorithm across two different, yet related, domains. Results demonstrate that the performance of the honey-bee mating optimization algorithm is comparable with the results of other approaches in the scientific literature. Indeed, the proposed approach obtains best results compared with other approaches on some instances, indicating that the honey-bee mating optimization algorithm is a promising approach in solving educational timetabling problems.     

Strategies of node selection in search procedures for solving combinatorial optimization problems: A survey and a general formalization

Currently, most combinatorial optimization problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. The objective of this work is to propose a survey and a general formalization of the selection strategy of the next node to explore, a feature that is common to all these optimization procedures. This research has been partially supported by TAP98-0494 project     

The application of automated reasoning to formal models of combinatorial optimization

Many formalisms have been proposed over the years to capture combinatorial optimization algorithms such as dynamic programming, branch and bound, and greedy. In 1989 Helman [9] presented a common formalism that captures dynamic programming and branch and bound type algorithms. The formalism was later extended to include greedy algorithms. In this paper, we describe the application of automated reasoning techniques to the domain of our model, in particular considering some representational issues and demonstrating that proofs about the model can be obtained by an automated reasoning program. The long-term objective of this research is to develop a methodology for using automated reasoning to establish new results within the theory, including the derivation of new lower bounds and the discovery (and verification) of new combinatorial search strategies.     

一类全局优化问题的线性化方法

本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解.     

A self-adaptive global best harmony search algorithm for continuous optimization problems

This paper presents a self-adaptive global best harmony search (SGHS) algorithm for solving continuous optimization problems. In the proposed SGHS algorithm, a new improvisation scheme is developed so that the good information captured in the current global best solution can be well utilized to generate new harmonies. The harmony memory consideration rate (HMCR) and pitch adjustment rate (PAR) are dynamically adapted by the learning mechanisms proposed. The distance bandwidth (BW) is dynamically adjusted to favor exploration in the early stages and exploitation during the final stages of the search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from literature. The computational results show that the proposed SGHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants.     

SOME COMBINATORIAL OPTIMIZATION PROBLEMS ARISING FROM VLSI CIRCUIT DESIGN

This paper is basically a survey to show a number of combinatorlal optimization problems arising from VLSI clrcult design.Some of them including the existence problem,minimax problem,net representation,bend minimization,area minimization,placement problem,routing problem,etc,are especially discussed with new results and theoretical ideas for treating them.Finally,a number of problems for further research are mentioned.     

On the complexity of a class of combinatorial optimization problems with uncertainty

We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})² m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty but is polynomially solvable in the case of the interval representation of uncertainty. Received: July 1998 / Accepted: May 2000?Published online March 22, 2001     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.     

Metaheuristic algorithms for combinatorial optimization problems

We present the main results in the author’s Ph.D. thesis (Iori 2004), defended at the University of Bologna in April 2004 and supervised by S. Martello. The thesis is written in English and is available from the author upon request. It proposes exact and metaheuristic algorithms for solving some relevant combinatorial optimization problems, with particular emphasis on scheduling, two-dimensional cutting and packing and capacitated vehicle routing. The performance of each algorithm is tested through extensive computational experiments and comparison with other approaches in the literature.Received: 21 September 2004, AMS classification: 90-08, 90C27, 90C59     

A global optimization using linear relaxation for generalized geometric programming

Many local optimal solution methods have been developed for solving generalized geometric programming (GGP). But up to now, less work has been devoted to solving global optimization of (GGP) problem due to the inherent difficulty. This paper considers the global minimum of (GGP) problems. By utilizing an exponential variable transformation and the inherent property of the exponential function and some other techniques the initial nonlinear and nonconvex (GGP) problem is reduced to a sequence of linear programming problems. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (GGP) on a microcomputer.     

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield-optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543.     

Exact algorithms for procurement problems under a total quantity discount structure

In this paper, we study the procurement problem faced by a buyer who needs to purchase a variety of goods from suppliers applying a so-called total quantity discount policy. This policy implies that every supplier announces a number of volume intervals and that the volume interval in which the total amount ordered lies determines the discount. Moreover, the discounted prices apply to all goods bought from the supplier, not only to those goods exceeding the volume threshold. We refer to this cost-minimization problem as the total quantity discount (TQD) problem. We give a mathematical formulation for this problem and argue that not only it is NP-hard, but also that there exists no polynomial-time approximation algorithm with a constant ratio (unless P = NP). Apart from the basic form of the TQD problem, we describe four variants. In a first variant, the market share that one or more suppliers can obtain is constrained. Another variant allows the buyer to procure more goods than strictly needed, in order to reach a lower total cost. We also consider a setting where the buyer needs to pay a disposal cost for the extra goods bought. In a third variant, the number of winning suppliers is limited, both in general and per product. Finally, we investigate a multi-period variant, where the buyer not only needs to decide what goods to buy from what supplier, but also when to do this, while considering the inventory costs. We show that the TQD problem and its variants can be solved by solving a series of min-cost flow problems. Finally, we investigate the performance of three exact algorithms (min-cost flow based branch-and-bound, linear programming based branch-and-bound, and branch-and-cut) on randomly generated instances involving 50 suppliers and 100 goods. It turns out that even the large instances of the basic problem are solved to optimality within a limited amount of time. However, we find that different algorithms perform best in terms of computation time for different variants.     

Exponential irreducible neighborhoods for combinatorial optimization problems

This paper deals with irreducible augmentation vectors associated with three combinatorial optimization problems: the TSP, the ATSP, and the SOP. We study families of irreducible vectors of exponential size, derived from alternating cycles, where optimizing a linear function over each of these families can be done in polynomial time. A family of irreducible vectors induces an irreducible neighborhood; an algorithm for optimizing over this family is known as a local search heuristic. Irreducible neighborhoods do not only serve as a tool to improve feasible solutions, but do play an important role in an exact primal algorithm; such families are the primal counterpart of a families of facet inducing inequalities.     

Berge-type theorems for vector optimization problems

In the present paper we investigate continuity properties of the minimal point multivalued mapping associated with parametric vector optimization problems in topological vector spaces. This mapping can be viewed as a counterpart of the optimal value function in scalar optimization. We prove sufficient conditions for several types of continuities of minimal points and discuss their relationship to the existing results as well to the classical Berge Maximum Theorems in the case of scalar optimization problems     

A hybrid quantum-inspired immune algorithm for multiobjective optimization

This study suggests a novel quantum immune algorithm for finding Pareto-optimal solutions to multiobjective optimization problems based on quantum computing and immune system. In the proposed algorithm, there are distinct characteristics as follows. First, the encoding method is based on Q-bit representation, and thus a chaos-based approach is suggested to initialize the population. Second, a new chaos-based rotation gate and Q-gates are presented to perform mutation and improve the quality of the population, respectively. Finally, especially, a new truncation algorithm with similar individuals (TASI) is utilized to preserve the diversity of the population. Also, a new selection operator is proposed to create the new population based on TASI. Simulation results on six standard problems (ZDT6, CP, SP, VNT, OSY and KIT) show the proposed algorithm is able to find a much better spread of solutions and has better convergence near the true Pareto-optimal front compared to the vector immune algorithm (VIS) and the elitist non-dominated sorting genetic system (NSGA-II).     

A hybrid ODE-based method for unconstrained optimization problems

This paper presents a hybrid ODE-based method for unconstrained optimization problems, which combines the idea of IMPBOT with the subspace technique and a fixed step-length. The main characteristic of this method is that at each iteration, a lower dimensional system of linear equations is solved only once to obtain a trial step. Another is that when a trial step is not accepted, this proposed method uses minimization of a convex overestimation, thus avoiding performing a line search to compute a step-length. Under some reasonable assumptions, the method is proven to be globally convergent. Numerical results show the efficiency of this proposed method in practical computations, especially for solving small scale unconstrained optimization problems.     

Ideal polytopes and face structures of some combinatorial optimization problems

Given a finite setX and a family of feasible subsetsF ofX, the 0–1 polytope P (F is defined as the convex hull of all the characteristic vectors of members ofF We show that under a certain assumption a special type of face ofP(F) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, we propose a new heuristic for such problems and give results of our preliminary computational experiments for the maximum stable set problem.Supported by a JSPS Fellowship for Young Scientists.Supported by Grant-in-Aids for Co-operative Research (06740147) of the Ministry of Education, Science and Culture.