Publications

The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions to systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer k, we prove that there exists a constant c(n,k), depending only on the dimension n and on the number k, such that if a bounded polyhedron {x in R^n : Ax <= b} contains exactly k integer points, then there exists a subset of the rows, of cardinality no more than c(n,k), defining a polyhedron that contains exactly the same k integer points. In this case c(n,0)=2^n as in the original case of Doignon-Bell-Scarf for infeasible systems of inequalities. We work on both upper and lower bounds for the constant c(n,k) and discuss some consequences, including a Clarkson-style algorithm to find the l-th best solution of an integer program with respect to the ordering induced by the objective function.

The well-studied semigroup Sg(A) = {b : b = Ax; x in Z^n; x >= 0} can be stratified by the sizes of the polyhedral fibers IPA(b) = {x : Ax = b; x >= 0; x in Z^n}. The key theme of this paper is a structure theory that characterizes precisely the set Sg_k(A) of all vectors b in Sg(A) such that their fiber IPA(b) has at least k-solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors b for which IPA(b) has exactly k solutions or fewer than k solutions. We also show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of Sg_k(A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have at least k solutions. Using this tool we prove that for fixed n; k the k-Frobenius number can be computed in polynomial time, generalizing a well-known result of R. Kannan.

We consider a mixed integer set which generalizes two well-known sets: the single node fixed- charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general mixed integer problems such as lot-sizing and network design problems. We derive several families of valid inequalities that, in particular, generalize the arc resid- ual capacity inequalities and the flow cover inequalities. For the constant capacitated case we provide an extended compact formulation and give a partial description of the convex hull in the original space which is exact under a certain condition. By lifting some basic inequalities we provide some insight on the difficulty of obtaining such a full polyhedral description for the constant capacitated case. Preliminary computational results are presented.

We develop a method for computing facet-defining valid inequalities for any mixed-integer set PJ. Our practical implementation does not return only facet- defining inequalities, but it is able to find a separating cut whenever one exists. The separator is not comparable in speed with the specific cutting-plane generators used in branch-and-cut solvers, but it is general-purpose. We can thus use it to compute cuts derived from any reasonably small relaxation PJ of a general mixed- integer problem, even when there exists no specific implementation for computing cuts with PJ. Exploiting this, we evaluate, from a computational perspective, the usefulness of cuts derived from several types of multi-row relaxations. In particular, we present results with four different strengthenings of the two-row intersection cut model, and multi-row models with up to fifteen rows. We conclude that only fully-strengthened two-row cuts seem to offer a significant advantage over two-row intersection cuts. Our results also indicate that the improvement obtained by going from models with very few rows to models with up to fifteen rows may not be worth the increased computing cost.

We consider a price signal with two settings: off-peak tariff and on-peak tariff. Some loads are connected to specific electricity meters which allow the consumption of power only in off-peak periods. Historically, off-peak periods were located during the night and on-peak periods during the day. Changing the assignment of off-peak periods is an easy method for distribution system operators to access to the flexibility of small consumers. This solution can be implemented quickly as the infrastructure needed already exists in some countries. We propose a mixed-integer linear model to assign optimally the off-peak hours so as to minimize a societal cost. This cost gathers together the cost of electricity, the financial losses due to energy curtailments of photovoltaic installations and the loads' wellbeing. Our model considers automatic tripping of inverters and constraints of the electrical distribution networks. Simulation results show that the new disposition of off-peak hours could reduce significantly the photovoltaic energy curtailed in the summer.

We consider a class of optimal power flow (OPF) applications where some loads offer a modulation service in exchange for an activation fee. These applications can be modeled as multi-period formulations of the OPF with discrete variables that define mixed-integer non-convex mathematical programs. We propose two types of relaxations to tackle these problems. One is based on a Lagrangian relaxation and the other is based on a network flow relaxation. Both relaxations are tested on several benchmarks and, although they provide a comparable dual bound, it appears that the constraints in the solutions derived from the network flow relaxation are significantly less violated.

We propose and analyze a day-ahead reserve market model that handles bids from flexible loads. This pool market model takes into account the fact that a load modulation in one direction must usually be compensated later by a modulation of the same magnitude in the opposite direction. Our analysis takes into account the gaming possibilities of producers and retailers, controlling load flexibility, in the day-ahead energy and reserve markets, and in imbalance settlement. This analysis is carried out by an agent-based approach where, for every round, each actor uses linear programs to maximize its profit according to forecasts of the prices. The procurement of a reserve is assumed to be determined, for each period, as a fixed percentage of the total consumption cleared in the energy market for the same period. The results show that the provision of reserves by flexible loads has a negligible impact on the energy market prices but markedly decreases the cost of reserve procurement. However, as the rate of flexible loads increases, the system operator has to rely more and more on non-contracted reserves, which may cancel out the benefits made in the procurement of reserves.

A large number of problems can be formalized as finding the best symbolic expression to maximize a given numerical objective. Most approaches to approximately solve such problems rely on random exploration of the search space. This paper focuses on how this random exploration should be performed to take into account expressions redundancy and invalid expressions. We propose a learning algorithm that, given the set of available constants, variables and operators and given the target finite number of trials, computes a probability distribution to maximize the expected number of semantically different, valid, generated expressions. We illustrate the use of our approach on both medium-scale and large-scale expression spaces, and empirically show that such optimized distributions significantly outperform the uniform distribution in terms of the diversity of generated expressions. We further test the method in combination with the recently proposed nested Monte-Carlo algorithm on a set of benchmark symbolic regression problems and demonstrate its interest in terms of reduction of the number of required calls to the objective function.

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.

In this paper we study a generalization of the classical fesibility problem in integer linear programming, where an ILP needs to have a prescribed number of solutions to be considered solved. We first provide a generalization of the famous Doignon-Bell-Scarf theorem: Given an integer k, we prove that there exists a constant c(k, n), depending only on the dimension n and k, such that if a polyhedron {x : Ax = b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. The second contribution of the article presents a structure theory that characterizes precisely the set Sg=k (A) of all vectors b such that the problem Ax = b, x = 0, x ? Zn , has at least k-solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computation. Similar results can be derived for those right-hand-side vectors that have exactly k solutions or fewer than k solutions. Finally we show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of Sg=k(A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have exactly k solutions (similarly for at least k or less than k solutions). Under the same assumptions we prove that the k-Frobenius number can be computed in polynomial time.

We study the minmax optimization problem introduced in [Fonteneau et al. (2011), ``Towards min max reinforcement learning'', Springer CCIS, vol. 129, pp. 61-77] for computing control policies for batch mode reinforcement learning in a deterministic setting with fixed, finite optimization horizon. First, we state that the $\min$ part of this problem is NP-hard. We then provide two relaxation schemes. The first relaxation scheme works by dropping some constraints in order to obtain a problem that is solvable in polynomial time. The second relaxation scheme, based on a Lagrangian relaxation where all constraints are dualized, can also be solved in polynomial time. We theoretically show that both relaxation schemes provide better results than those given in [Fonteneau et al. (2011)]

Considering a set of points in a multi-dimensional space with an associated real value for each point, we want to find the box with the maximum sum of the values of the included points. This problem has applications in data mining and can be formulated as a mixed-integer linear program. We propose a branch-and-bound algorithm where the bounding is obtained by combinatorial arguments instead of the traditional linear relaxation. Computational experiments show that this approach competes with current state of the art mixed-integer solvers. The algorithm proposed in this paper may be seen as a simple and dependence-free method to solve the box search problem.

This article studies a decision making problem faced by an aggregator willing to offer a load modulation service to a Transmission System Operator. This service is contracted one day ahead and consists in a load modulation option, which can be called once per day. The option specifies the range of a potential modification on the demand of the loads within a certain time interval. The specific case where the loads can be modeled by a generic tank model is considered. Under this assumption, the problem of maximizing the range of the load modulation service can be formulated as a mixed integer linear programming problem. A novel heuristic-method is proposed to solve this problem in a computationally efficient manner. This method is tested on a set of problems. The results show that this approach can be orders of magnitude faster than CPLEX without significantly degrading the solution accuracy.

Cet article aborde le problème de généralisation minmax dans le cadre de l'apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par [Fonteneau, 2011], et il a déjà été montré qu'il est NP-dur. Deux schémas de relaxation pour le cas deux étapes ont été présentés aux JFPDA'12, et ce papier présente une généralisation de ces schémas au cas T étapes. Le premier schéma fonctionne en éliminant des contraintes afin d'obtenir un problème soluble en temps polynomial. Le deuxième schéma est une relaxation lagrangienne conduisant également à un problème soluble en temps polynomial. On montre théoriquement que ces deux schémas permettent d'obtenir de meilleurs résultats que ceux proposés par [Fonteneau, 2011].

We study the min max optimization problem introduced in Fonteneau et al. [Towards min max reinforcement learning, ICAART 2010, Springer, Heidelberg, 2011, pp. 61–77] for computing policies for batch mode reinforcement learning in a deterministic setting with ?xed, ?nite time horizon. First, we show that the min part of this problem is NP-hard. We then provide two relaxation schemes. The ?rst relaxation scheme works by dropping some constraints in order to obtain a problem that is solvable in polynomial time. The second relaxation scheme, based on a Lagrangian relaxation where all constraints are dualized, can also be solved in polynomial time. We also theoretically prove and empirically illustrate that both relaxation schemes provide better results than those given in [Fonteneau et al., 2011, as cited above].

On s’intéresse au problème de généralisation min max dans le cadre de l’apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par Fonteneau et al. (2011). Dans un premier temps, on montre que le problème est NP-dur. Dans le cas où l’horizon d’optimisation vaut 2, on développe deux schémas de relaxation. Le premier schéma fonctionne en éliminant des contraintes de telle sorte qu’on obtienne un problème soluble en temps polynomial. Le deuxième schéma est une relaxation Lagrangienne conduisant à un problème conique-quadratique. On montre théoriquement et empiriquement que ces deux schémas permettent d’obtenir de meilleurs résultats que ceux proposés par Fonteneau et al. (2011).

We study the min max optimization problem introduced in [Fonteneau, 2011] for computing policies for batch mode reinforcement learning in a deterministic setting. This problem is NP-hard. We focus on the two-stage case for which we provide two relaxation schemes. The first relaxation scheme works by dropping some constraints in order to obtain a problem that is solvable in polynomial time. The second relaxation scheme, based on a Lagrangian relaxation where all constraints are dualized, leads to a conic quadratic programming problem. Both relaxation schemes are shown to provide better results than those given in [Fonteneau, 2011].

A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. and Cornuéjols and Margot showed that the facet-de?ning inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. Through a result by Cook et al., it is known that one particular class of facet- de?ning triangle inequality does not have a ?nite split rank. In this paper, we show that all other facet-de?ning triangle and quadrilateral inequalities have ?nite split rank. The proof is constructive and given a facet-de?ning triangle or quadrilateral inequality we present an explicit sequence of split inequalities that can be used to generate it.

Finding an approximation of a Nash equilibria in matrix games is an important topic that reaches beyond the strict application to matrix games. A bandit algorithm commonly used to approximate a Nash equilibrium is EXP3. However, the solution to many problems is often sparse, yet EXP3 inherently fails to exploit this property. To the knowledge of the authors, there exist only an offline truncation to tackle such issue. In this paper, we propose a variation of EXP3 to exploit the fact that solution is sparse by dynamically removing arms; the resulting algorithm empirically performs better than previous versions. We apply the resulting algorithm to a MCTS program for the Urban Rivals card game.

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 ?ndings 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. Speci?cally, 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.

The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the w th split closure. We show the w th split closure is a polyhedron. This generalizes a previous result showing this to be true when w = 1. We also consider the design of ?nite cutting plane proofs for the validity of an inequality. Given a measure of “size” of a maximal lattice free polyhedron, a natural question is how large a size s of a maximal lattice free polyhedron is required to design a ?nite cutting plane proof for the validity of an inequality. We characterize s based on the faces of the linear relaxation of the mixed integer linear set.

We derive a certificate of integral infeasibility for linear systems with equations and inequalities by generating algebraically an outer description of a lattice point free polyhedron that contains the given integer infeasible system. The extension to the mixed integer setting is also derived.

We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formu- lation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet descrip- tion decomposes into one “linking polyhedron” per block and the “aggre- gated polyhedron”. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coeffi- cients, this theorem provides a complete description in an extended space with a polynomial number of variables. Based on this theory, we propose a new branching scheme that analyzes the problem structure. It is designed to be applied in those subproblems of hard integer programs where LP-based techniques do not provide good branching decisions. Preliminary computational experiments show that it is successful for some benchmark problems of multi-knapsack type.

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.

In this paper we explore the geometry of the integer points in a cone rooted at a rational point. This basic geometric object allows us to establish some links between lattice point free bodies and the derivation of inequalities for mixed integer linear programs by considering two rows of a simplex tableau simultaneously.

In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure com- bining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive lifting which allows one to lift simultane- ously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer rounding inequality, and superaddilifting. It is applied to several generalizations of the 0-1 single node flow set.

We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation.

In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, empha- sizing superadditive lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construc- tion of a mixed integer rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0-1 single node flow set.

We consider a hard integer programming problem that is difficult for the standard branch-and-bound approach even for small instances. A reformulation based on lattice basis reduction is known to be more effective. However the step to compute the reduced basis, even if it is found in polynomial time, becomes a bottleneck for small to medium instances. By using the structure of the problem, we show that we can decompose the problem and obtain the basis by taking the kronecker product of two smaller bases easier to compute. Furthermore, if the two small bases are reduced, the kronecker product is also reduced up to a reordering of the vectors. Computational results show the gain from such an approach.