This paper addresses a constrained two-dimensional (2D) non-guillotine cutting problem, where a fixed set of small rectangles has to be cut from a larger stock rectangle so as to maximize the value of the rectangles cut. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose … Read more
This paper is the first of a series of two devoted to the polyhedral study of a strongly NP-hard resource-constrained scheduling problem, referred to as the process move programming problem. This problem arises in relation to the operability of certain high-availability real time distributed systems. After a brief introduction to the problem as well as … Read more
This paper is the second of a series of two devoted to the polyhedral study of a strongly NP-hard resource-constrained scheduling problem, referred to as the process move programming problem. In the present paper, we put back into the picture the capacity constraints which were ignored in the first paper. In doing so, we introduce … Read more
We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta’-numbers of the graphs that result when the loop edges are removed. We show that the theta-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets. … Read more
Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2006). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In … Read more
The aim of this paper is to study how efficiently we evaluate a system of multivariate polynomials and their partial derivatives in homotopy continuation methods. Our major tool is an extension of the Hornor scheme, which is popular in evaluating a univariate polynomial, to a multivariate polynomial. But the extension is not unique, and there … Read more
A $k$-bit Hamming prefix code is a binary code with the following property: for any codeword $x$ and any prefix $y$ of another codeword, both $x$ and $y$ having the same length, the Hamming distance between $x$ and $y$ is at least $k$. Given an alphabet $A = [a_1,\ldots,a_n]$ with corresponding probabilities $[p_1,\ldots,p_n]$, the $k$-bit … Read more
This paper is devoted to the study of the reroute sequence planning problem in multi-protocol label switching networks from the polyhedral viewpoint. The reroute sequence plan polytope, defined as the convex hull of the incidence vectors of the reroute sequences which do not violate the network link capacities, is introduced and some of its properties … Read more
In this paper we show that for discrete concave functions, a local maximum need not be a global maximum. We also provide examples of discrete concave functions where this coincidence holds. As a direct consequence of this, we can establish the equivalence of local and global profit maximizers for an equivalent well-behaved production function that … Read more
Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases n = 3, 4, 8, … Read more