Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

Minimizing multi-homogeneous Bézout numbers by a local search method

Consider the multi-homogeneous homotopy continuation method for solving a system of polynomial equations. For any partition of variables, the multi-homogeneous Bézout number bounds the number of isolated solution curves one has to follow in the method. This paper presents a local search method for finding a partition of variables with minimal multi-homogeneous Bézout number. As with any other local search method, it may give a local minimum rather than the minimum over all possible homogenizations. Numerical examples show the efficiency of this local search method.

     

Improved Bounds for Ternary Linear Codes of Dimension 8 Using Tabu Search

In this paper, new codes of dimension 8 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Twenty three codes are given which improve or establish the bounds for ternary codes. In addition, a table of upper and lower bounds for d ₃(n, 8) is presented for n 200.     

The rollon–rolloff waste collection vehicle routing problem with time windows

This study introduces a rollon–rolloff waste collection vehicle routing problem involving large containers that accumulate huge amounts of garbage at construction sites and shopping districts. In this problem, tractors move one container at a time between customer locations, a depot, disposal facilities, and container storage yards. The complicated constraints discussed in this study arise from having multiple disposal facilities, multiple container storage yards, seven service types of customer demands, different time windows for customer demands and facilities, various types and sizes of containers, and the lunch break of tractor drivers. In addition, real-world issues, such as changing service types, multiple demands at a customer’s location, and tractors with different work schedules, are dealt with. This study proposes a large neighborhood search based iterative heuristic approach consisting of several algorithms for the problem. The effectiveness of the proposed methods is demonstrated by computational experiments using benchmark data, some instances of which are derived from real-world problems.     

Parameter-setting-free harmony search algorithm

Various phenomenon-mimicking algorithms, such as genetic algorithm, simulated annealing, tabu search, ant colony optimization, and particle swarm optimization, have their own algorithm parameters. These parameters need to be skillfully assigned in order to obtain good results. It is burdensome, especially to novice users, to assign these parameters. The same is true for the harmony search algorithm which was inspired by music performance. Thus, this study proposes a novel technique to eliminate tedious and experience-requiring parameter assigning efforts. The new parameter-setting-free (PSF) technique which this study suggests contains one additional matrix which contains an operation type (random selection, memory consideration, or pitch adjustment) for every variable in harmony memory. Three examples illustrate that the PSF technique can find good solutions robustly.     

Schemata, Distributions and Graphical Models in Evolutionary Optimization

In this paper the optimization of additively decomposed discrete functions is investigated. For these functions genetic algorithms have exhibited a poor performance. First the schema theory of genetic algorithms is reformulated in probability theory terms. A schema defines the structure of a marginal distribution. Then the conceptual algorithm BEDA is introduced. BEDA uses a Boltzmann distribution to generate search points. From BEDA a new algorithm, FDA, is derived. FDA uses a factorization of the distribution. The factorization captures the structure of the given function. The factorization problem is closely connected to the theory of conditional independence graphs. For the test functions considered, the performance of FDA—in number of generations till convergence—is similar to that of a genetic algorithm for the OneMax function. This result is theoretically explained.     

A memetic algorithm for multi-objective dynamic location problems

This paper describes a new multiobjective interactive memetic algorithm applied to dynamic location problems. The memetic algorithm integrates genetic procedures and local search. It is able to solve capacitated and uncapacitated multi-objective single or multi-level dynamic location problems. These problems are characterized by explicitly considering the possibility of a facility being open, closed and reopen more than once during the planning horizon. It is possible to distinguish the opening and reopening periods, assigning them different coefficient values in the objective functions. The algorithm is part of an interactive procedure that asks the decision maker to define interesting search areas by establishing limits to the objective function values or by indicating reference points. The procedure will be applied to some illustrative location problems.     

Multi-step nonlinear conjugate gradient methods for unconstrained minimization

Conjugate gradient methods are appealing for large scale nonlinear optimization problems, because they avoid the storage of matrices. Recently, seeking fast convergence of these methods, Dai and Liao (Appl. Math. Optim. 43:87–101, 2001) proposed a conjugate gradient method based on the secant condition of quasi-Newton methods, and later Yabe and Takano (Comput. Optim. Appl. 28:203–225, 2004) proposed another conjugate gradient method based on the modified secant condition. In this paper, we make use of a multi-step secant condition given by Ford and Moghrabi (Optim. Methods Softw. 2:357–370, 1993; J. Comput. Appl. Math. 50:305–323, 1994) and propose two new conjugate gradient methods based on this condition. The methods are shown to be globally convergent under certain assumptions. Numerical results are reported.     

An Interactive Method for 0-1 Multiobjective Problems Using Simulated Annealing and Tabu Search

This paper presents an interactive method for solving general 0-1 multiobjective linear programs using Simulated Annealing and Tabu Search. The interactive protocol with the decision maker is based on the specification of reservation levels for the objective function values. These reservation levels narrow the scope of the search in each interaction in order to identify regions of major interest to the decision maker. Metaheuristic approaches are used to generate potentially nondominated solutions in the computational phases. Generic versions of Simulated Annealing and Tabu Search for 0-1 single objective linear problems were developed which include a general routine for repairing unfeasible solutions. This routine improves significantly the results of single objective problems and, consequently, the quality of the potentially nondominated solutions generated for the multiobjective problems. Computational results and examples are presented.     

Subspace Barzilai-Borwein Gradient Method for Large-Scale Bound Constrained Optimization

An active set subspace Barzilai-Borwein gradient algorithm for large-scale bound constrained optimization is proposed. The active sets are estimated by an identification technique. The search direction consists of two parts: some of the components are simply defined; the other components are determined by the Barzilai-Borwein gradient method. In this work, a nonmonotone line search strategy that guarantees global convergence is used. Preliminary numerical results show that the proposed method is promising, and competitive with the well-known method SPG on a subset of bound constrained problems from CUTEr collection. This work was supported by the 973 project granted 2004CB719402 and the NSF project of China granted 10471036.