Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

On low order moments of the homodyned-K distribution

Fractional low order moments have been reported as beneficial for sampling computations using the K distribution. However, it has been recently pointed out that this it not the case for the homodyned-K distribution for a tissue discrimination problem. In this paper we show that such an statement is not fully justified. To that end, we follow a standard pattern recognition procedure both to determine class separability measures and to classify data with several classifiers. We conclude that the optimum order of the moments is intimately linked to the specific statistical properties of the tissues to be discriminated. Some ideas on how to choose the optimum order are discussed.     

Conformational analysis of methylphenidate: comparison of molecular orbital and molecular mechanics methods

Summary Methylphenidate (MP) binds to the cocaine binding site on the dopamine transporter and inhibits reuptake of dopamine, but does not appear to have the same abuse potential as cocaine. This study, part of a comprehensive effort to identify a drug treatment for cocaine abuse, investigates the effect of choice of calculation technique and of solvent model on the conformational potential energy surface (PES) of MP and a rigid methylphenidate (RMP) analogue which exhibits the same dopamine transporter binding affinity as MP. Conformational analysis was carried out by the AM1 and AM1/SM5.4 semiempirical molecular orbital methods, a molecular mechanics method (Tripos force field with the dielectric set equal to that of vacuum or water) and the HF/6-31G* molecular orbital method in vacuum phase. Although all three methods differ somewhat in the local details of the PES, the general trends are the same for neutral and protonated MP. In vacuum phase, protonation has a distinctive effect in decreasing the regions of space available to the local conformational minima. Solvent has little effect on the PES of the neutral molecule and tends to stabilize the protonated species. The random search (RS) conformational analysis technique using the Tripos force field was found to be capable of locating the minima found by the molecular orbital methods using systematic grid search. This suggests that the RS/Tripos force field/vacuum phase protocol is a reasonable choice for locating the local minima of MP. However, the Tripos force field gave significantly larger phenyl ring rotational barriers than the molecular orbital methods for MP and RMP. For both the neutral and protonated cases, all three methods found the phenyl ring rotational barriers for the RMP conformers/invertamers (denoted as cte, tte, and cta) to be: cte, tte> MP > cta. Solvation has negligible effect on the phenyl ring rotational barrier of RMP. The B3LYP/6-31G* density functional method was used to calculate the phenyl ring rotational barrier for neutral MP and gave results very similar to those of the HF/6-31G* method.     

Non-classical preference models in combinatorial problems: Models and algorithms for graphs

This is a summary of the most important results presented in the authors PhD thesis (Spanjaard 2003). This thesis, written in French, was defended on 16 December 2003 and supervised by Patrice Perny. A copy is available from the author upon request. This thesis deals with the search for preferred solutions in combinatorial optimization problems (and more particularly graph problems). It aims at conciliating preference modelling and algorithmic concerns for decision aiding.Received: March 2004, MSC classification: 91B06, 90C27, 90B40, 16Y60     

The Attribute Based Hill Climber

In this paper we introduce the Attribute Based Hill Climber, a parameter-free algorithm that provides a concrete, stand-alone implementation of a little used technique from the Tabu Search literature known as regional aspiration. Results of applying the algorithm to two classical optimisation problems, the Travelling Salesman Problem and the Quadratic Assignment Problem, show it to be competitive with existing general purpose heuristics in these areas.     

Selecting distances in arrangements of hyperplanes spanned by points

In this paper we consider a problem of distance selection in the arrangement of hyperplanes induced by n given points. Given a set of n points in d-dimensional space and a number k, , determine the hyperplane that is spanned by d points and at distance ranked by k from the origin. For the planar case we present an O(nlog²n) runtime algorithm using parametric search partly different from the usual approach [N. Megiddo, J. ACM 30 (1983) 852]. We establish a connection between this problem in 3-d and the well-known 3SUM problem using an auxiliary problem of counting the number of vertices in the arrangement of n planes that lie between two sheets of a hyperboloid. We show that the 3-d problem is almost 3SUM-hard and solve it by an O(n²log²n) runtime algorithm. We generalize these results to the d-dimensional (d4) space and consider also a problem of enumerating distances.     

Local branching

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box ``tactical' tool to explore effectively suitable solution subspaces defined and controlled at a ``strategic' level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. Mathematics Subject Classification (2000):90C06, 90C10, 90C11, 90C27, 90C59     

Small Solutions of Quadratic Diophantine Equations

We consider quadratic diophantine equations of the shape for a polynomial Q(X₁, ..., X_s) Z[X₁, ..., X_s] of degree 2.Let H be an upper bound for the absolute values of the coefficientsof Q, and assume that the homogeneous quadratic part of Q isnon-singular. We prove, for all s 3, the existence of a polynomialbound _s(H) with the following property: if equation (1) hasa solution x Z^s at all, then it has one satisfying For s = 3 and s = 4 no polynomial bounds _s(H) were previouslyknown, and for s 5 we have been able to improve existing boundsquite significantly. 2000 Mathematics Subject Classification11D09, 11E20, 11H06, 11P55.     

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.