References of "Mathematical Programming"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailQuadratic reformulations of nonlinear binary optimization problems
Anthony, Martin; Boros, Endre; Crama, Yves ULg et al

in Mathematical Programming (in press)

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these ... [more ▼]

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all ``minimal'' quadratizations of negative monomials. [less ▲]

Detailed reference viewed: 122 (11 ULg)
Full Text
Peer Reviewed
See detailAn algorithm for the separation of two-row cuts
Louveaux, Quentin ULg; Poirrier, Laurent ULg

in Mathematical Programming (2014), 143(1-2), 111-146

We consider the question of finding deep cuts from a model with two rows of the type PI = {(x,s) ∈ Z2 ×Rn+ : x = f +Rs}. To do that, we show how to reduce the complexity of setting up the polar of conv(PI ... [more ▼]

We consider the question of finding deep cuts from a model with two rows of the type PI = {(x,s) ∈ Z2 ×Rn+ : x = f +Rs}. To do that, we show how to reduce the complexity of setting up the polar of conv(PI ) from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice. [less ▲]

Detailed reference viewed: 136 (20 ULg)
Full Text
Peer Reviewed
See detailMixed-integer sets from two rows of two adjacent simplex bases
Andersen, Kent; Louveaux, Quentin ULg; Weismantel, Robert

in Mathematical Programming (2010), 124(1-2), 455-480

In 2007 we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with ... [more ▼]

In 2007 we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with either three or four variables. In this paper we generalize our findings and show that, when upper bounds on the non-basic variables are also considered, further classes of facets arise that cannot be obtained from triangles and quadrilaterals. Specifically, when exactly one upper bound on a non-basic variable is intro- duced, stronger inequalities that can be derived from pentagons involving up to six variables also appear. [less ▲]

Detailed reference viewed: 125 (18 ULg)
Full Text
Peer Reviewed
See detailPolyhedral properties for the intersection of two knapsacks
Louveaux, Quentin ULg; Weismantel, Robert

in Mathematical Programming (2008), 113(1), 15-37

We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out ... [more ▼]

We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out that the sign patterns of the weight vectors are responsible for the types of combinatorial valid inequalities appearing in the description of the convex hull of the intersection. In partic- ular, we introduce the notion of an incomplete set inequality which is based on a combinatorial principle for the intersection of two knapsacks. We outline schemes to compute nontrivial bounds for the strength of such inequalities w.r.t. the intersection of the convex hulls of the initial knapsacks. An extension of the inequalities to the mixed case is also given. This opens up the possibility to use the inequalities in an arbitrary simplex tableau. [less ▲]

Detailed reference viewed: 98 (13 ULg)
Peer Reviewed
See detailScheduling jobs of equal length: complexity, facets and computational results
Crama, Yves ULg; Spieksma, Frits C.R.

in Mathematical Programming (1996), 72

The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed ... [more ▼]

The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed timespan [0,T], subdivided into T unit-length subperiods. The processing time (or length) of each job equals p,p ∈ ℕ. The processing cost of each job is an arbitrary function of its start-time. The problem is to schedule all jobs so as to minimize the sum of the processing costs. This problem is proved to be NP-hard, already for p=2 and 0–1 processing costs. On the other hand, when T=np+c, with c constant, the problem can be solved in polynomial time. A partial polyhedral description of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which the separation problem is polynomially solvable. Also, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions. Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances. [less ▲]

Detailed reference viewed: 16 (3 ULg)