Efficient Evaluation of Polynomials and Their Partial Derivatives in Homotopy Continuation Methods

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 polyhedral approach to reroute sequence planning in MPLS networks

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

A branch-and-cut algorithm for a resource-constrained scheduling problem

This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process … Read more

Dynamic Enumeration of All Mixed Cells

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

Set covering and packing formulations of graph coloring: algorithms and first polyhedral results

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

The multi-item capacitated lot-sizing problem with setup times and shortage costs

We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities … Read more

Finding optimal realignments in sports leagues using a branch-and-cut-and-price approach

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

A branch and cut algorithm for solving the linear and quadratic integer programming problems

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

Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem

The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed … Read more