We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in management and machine scheduling, and also appears as a subproblem in decomposition techniques for network design and other related problems. We present a new approach for determining facets of … Read more
We study a pricing problem where buyers with non-uniform demand purchase one of many items. Each buyer has a known benefit for each item and purchases the item that gives the largest utility, which is defined to be the difference between the benefit and the price of the item. The optimization problem is to decide … Read more
The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional … Read more
We identify the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling by sorting through various options that involve the primal simplex, dual simplex, and barrier methods for linear programming, the network simplex method for network flow problems, and Dantzig-Wolfe decomposition and column generation. CitationSubmitted for publication.ArticleDownload View PDF
The paper describes various combinatorial and algorithmic applications of hyperbolic (multivariate) polynomials . Section 2.2 introduces a new class of polynomials , which include as hyperbolic polynomials as well volume polynomials $Vol(x_1C_1+…+x_nC_n)$ , where $C_i$ are convex compact subsets of $R^n$. This extension leads to randomized poly-time algorithm to approximate $M(C_1,…,C_n)$ (the mixed volume) within … Read more
Local optimizations introduced to obtain improved tours for Traveling Salesman Problem have a great impact on the final solution. That is way we introduce a new ant system algorithm with a new local updating pheromone rule, and the tours are improved using k-opt techniques. The tests use different parameters, in order to obtain solutions close … Read more
The metric polytope m(n) is the polyhedron associated with all semimetrics on n nodes. In 1992 Monique Laurent and Svatopluk Poljak conjectured that every fractional vertex of the metric polytope is adjacent to some integral vertex. The conjecture holds for n
We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an … Read more
Given a set of clients and a set of potential sites for facilities, several location problems consist of opening a set of sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem … Read more
We consider two (0,1)-linear programming formulations of the graph (vertex-)coloring problem, in which variables are associated to stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in … Read more