The sports team realignment problem can be modelled as $k$-way equipartition: given a complete graph $K_{n}=(V,E)$, with edge weight $c_{e}$ on each edge, partition the vertices $V$ into $k$ divisions that have exactly $S$ vertices, so as to minimize the total weight of the edges that have both endpoints in the same division. In this … Read more
We give a hierarchy of semidefinite upper bounds for the maximum size $A(n,d)$ of a binary code of word length $n$ and minimum distance at least $d$. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in $n$; this is based on a result of … Read more
We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more
In the DIMACS benchmark suite for the maximum clique problem, the best known solution for test C2000.9 is a 78 nodes clique; optimality is not proved. We present a 79 nodes clique emerged during the testing of a heuristic algorithm. ArticleDownload View PDF
This paper first presents an improve cutting plane method for solving the linear programming problems, based on the primal simplex method with the current equivalent facet technique, in which the increment of objection function is allowed as a pivot variable to decide the search step size. We obtain a strong valid inequality from the objective … Read more
A GRASP with path-relinking for finding good-quality solutions of the weighted maximum satisfiability problem (MAX-SAT) is described in this paper. GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multi-start metaheuristic, where at each iteration locally optimal solutions are constructed, each independent of the others. Previous experimental results indicate its effectiveness for solving weighted … Read more
In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of … Read more
Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. We formulate this as a combinatorial linear program and give … Read more
We introduce a new extension of Punnen’s exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen’s neighborhood by De Franceschi, Fischetti and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including … Read more
In power law graphs, cut quality varies inversely with cut balance. Using some million node social graphs as a test bed, we empirically investigate this property and its implications for graph partitioning. We use six algorithms, including Metis and MQI (state of the art methods for finding bisections and quotient cuts) and four relaxation/rounding methods. … Read more