Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

A Quantitative Doignon-Bell-Scarf theorem ; ; et al in Combinatorica (in press) 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 45 (8 ULg)Parametric Polyhedra with at least k Lattice Points: Their Semigroup Structure and the k-Frobenius Problem ; ; Louveaux, Quentin in Beveridge, Andrew; Griggs, Jerold; Hogben, Leslie (Eds.) et al Recent trends in Combinatorics (in press) 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 33 (4 ULg)Direct control service from residential heat pump aggregation with specified payback Georges, Emeline ; Cornélusse, Bertrand ; Ernst, Damien et al in Proceedings of the 19th Power Systems Computation Conference (PSCC) (2016, June) This paper addresses the problem of an aggregator controlling residential heat pumps to offer a direct control flexibility service. The service is defined by a 15 minute power modulation, upward or ... [more ▼] This paper addresses the problem of an aggregator controlling residential heat pumps to offer a direct control flexibility service. The service is defined by a 15 minute power modulation, upward or downward, followed by a payback of one hour and 15 minutes. The service modulation is relative to an optimized baseline that minimizes the energy costs. The potential amount of modulable power and the payback effect are computed by solving mixed integer linear problems. Within these problems, the building thermal behavior is modeled by an equivalent thermal network made of resistances and lumped capacitances whose parameters are identified from validated models. Simulations are performed on 100 freestanding houses. For an average 4.3 kW heat pump, results show a potential of 1.2 kW upward modulation with a payback of 600 Wh and 150 Wh of overconsumption. A downward modulation of 500 W per house can be achieved with a payback of 420 Wh and 120 Wh of overconsumption. [less ▲] Detailed reference viewed: 36 (9 ULg)Online Learning for Strong Branching Approximation in Branch-and-Bound Marcos Alvarez, Alejandro ; Wehenkel, Louis ; Louveaux, Quentin E-print/Working paper (2016) We present an online learning approach to variable branching in branch-and-bound for mixed-integer linear problems. Our approach consists in learning strong branching scores in an online fashion and in ... [more ▼] We present an online learning approach to variable branching in branch-and-bound for mixed-integer linear problems. Our approach consists in learning strong branching scores in an online fashion and in using them to take branching decisions. More specifically, numerical scores are used to rank the branching candidates. If, for a given variable, the learned approximation is deemed reliable, then the score for that variable is computed thanks to the learned function. If the approximation is not reliable yet, the real strong branching score is used instead. The scores that are computed through the real strong branching procedure are fed to the online learning algorithm in order to improve the approximated function. The experiments show promising results. [less ▲] Detailed reference viewed: 40 (4 ULg)DSIMA: A testbed for the quantitative analysis of interaction models within distribution networks Mathieu, Sébastien ; Louveaux, Quentin ; Ernst, Damien et al in Sustainable Energy, Grids and Networks (2016), 5 This article proposes an open-source testbed to simulate interaction models governing the exchange of flexibility services located within a distribution network. The testbed is an agent-based system in ... [more ▼] This article proposes an open-source testbed to simulate interaction models governing the exchange of flexibility services located within a distribution network. The testbed is an agent-based system in which the distribution system operator, the transmission system operator, producers and retailers make their decisions based on mixed-integer linear programs. This testbed helps to highlight the characteristics of an interaction model, the benefits for the agents and eases the detection of unwanted or abusive behaviors which decreases the welfare. The testbed is implemented in Python and the optimization problems are encoded in the modeling language ZIMPL. A web interface is coupled with an instance generator using macroscopic parameters of the system such as the total power production. This testbed is, therefore, well suited to test the implemented interaction models on various scenarios and to extend the implementation to other models. Five interaction models developed with industrial partners are simulated over a year on a 75-bus test system. Simulations show that interaction models relying on active network management, as they have been developed, lead to substantial welfare even though they suffer from a lack of coordination between the DSO and the TSO. A conservative interaction model restricting grid users to an access range that is computed ahead of time to prevent any congestion, avoids shedding distributed generation but considerably restrains the amount of distributed production. [less ▲] Detailed reference viewed: 420 (37 ULg)Feasibility-oriented Branching Strategies for Global Optimization Gerard, Damien ; ; Louveaux, Quentin Conference (2015, July 13) We study the spatial Brand-and-Bound algorithm for the global optimization of nonlinear problems. In particular we are interested in a method to find quickly good feasible solutions. Most spatial Branch ... [more ▼] We study the spatial Brand-and-Bound algorithm for the global optimization of nonlinear problems. In particular we are interested in a method to find quickly good feasible solutions. Most spatial Branch-and-Bound-based solvers use a non global solver at a few nodes to try to find better incumbents. We show that it is possible to improve the branching rules and the nodes priority by exploiting the solutions from the non global solver. We also propose several smart adaptive strategies to choose when to run the non global solver. We show that despite the time spent in solving many more NLP problems in the nodes, the new strategies enable the algorithm to find the first good incumbents much faster and to prove the global optimality faster. NLP instances from the COCONUT library are benchmarked. All experiments are run using the open source solver Couenne. [less ▲] Detailed reference viewed: 21 (4 ULg)The strength of multi-row models Louveaux, Quentin ; ; in Mathematical Programming Computation (2015), 7(2), 113-148 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 67 (8 ULg)Valid inequalities for the single arc design problem with set-ups ; ; Louveaux, Quentin in Discrete Optimization (2015), 16 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 48 (11 ULg)Machine Learning to Balance the Load in Parallel Branch-and-Bound Marcos Alvarez, Alejandro ; Wehenkel, Louis ; Louveaux, Quentin E-print/Working paper (2015) We describe in this paper a new approach to parallelize branch-and-bound on a certain number of processors. We propose to split the optimization of the original problem into the optimization of several ... [more ▼] We describe in this paper a new approach to parallelize branch-and-bound on a certain number of processors. We propose to split the optimization of the original problem into the optimization of several subproblems that can be optimized separately with the goal that the amount of work that each processor carries out is balanced between the processors, while achieving interesting speedups. The main innovation of our approach consists in the use of machine learning to create a function able to estimate the difficulty (number of nodes) of a subproblem of the original problem. We also present a set of features that we developed in order to characterize the encountered subproblems. These features are used as input of the function learned with machine learning in order to estimate the difficulty of a subproblem. The estimates of the numbers of nodes are then used to decide how to partition the original optimization tree into a given number of subproblems, and to decide how to distribute them among the available processors. The experiments that we carry out show that our approach succeeds in balancing the amount of work between the processors, and that interesting speedups can be achieved with little effort. [less ▲] Detailed reference viewed: 75 (9 ULg)Optimal Assignment of Off-Peak Hours to Lower Curtailments in the Distribution Network Merciadri, Luca ; Mathieu, Sébastien ; Ernst, Damien et al in Proceedings of the 5th European Innovative Smart Grid Technologies (ISGT) (2014, October) 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 118 (26 ULg)A quantitative analysis of the effect of flexible loads on reserve markets Mathieu, Sébastien ; Louveaux, Quentin ; Ernst, Damien et al in Proceedings of the 18th Power Systems Computation Conference (PSCC) (2014, August) 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 253 (39 ULg)Relaxations for multi-period optimal power flow problems with discrete decision variables Gemine, Quentin ; Ernst, Damien ; Louveaux, Quentin et al in Proceedings of the 18th Power Systems Computation Conference (PSCC'14) (2014, August) 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 194 (39 ULg)A learning procedure for sampling semantically different valid expressions ; ; Ernst, Damien et al in International Journal of Artificial Intelligence (2014), 12(1), 18-35 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 43 (5 ULg)An algorithm for the separation of two-row cuts Louveaux, Quentin ; Poirrier, Laurent 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: 132 (19 ULg)Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem ; ; Louveaux, Quentin in Lee, Jon; Vygen, Jens (Eds.) Proceedings of the 17th IPCO (2014) 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 45 (1 ULg)Lipschitz robust control from off-policy trajectories Fonteneau, Raphaël ; Ernst, Damien ; Boigelot, Bernard et al in Proceedings of the 53rd IEEE Conference on Decision and Control (IEEE CDC 2014) (2014) 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 ... [more ▼] 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)] [less ▲] Detailed reference viewed: 58 (10 ULg)A combinatorial branch-and-bound algorithm for box search Mathieu, Sébastien ; Louveaux, Quentin in Discrete Optimization (2014), 13 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 81 (26 ULg)A Supervised Machine Learning Approach to Variable Branching in Branch-And-Bound Marcos Alvarez, Alejandro ; Louveaux, Quentin ; Wehenkel, Louis E-print/Working paper (2014) We present in this paper a new approach that uses supervised machine learning techniques to improve the performances of optimization algorithms in the context of mixed-integer programming (MIP). We focus ... [more ▼] We present in this paper a new approach that uses supervised machine learning techniques to improve the performances of optimization algorithms in the context of mixed-integer programming (MIP). We focus on the branch-and-bound (B&B) algorithm, which is the traditional algorithm used to solve MIP problems. In B&B, variable branching is the key component that most conditions the efficiency of the optimization. Good branching strategies exist but are computationally expensive and usually hinder the optimization rather than improving it. Our approach consists in imitating the decisions taken by a supposedly good branching strategy, strong branching in our case, with a fast approximation. To this end, we develop a set of features describing the state of the ongoing optimization and show how supervised machine learning can be used to approximate the desired branching strategy. The approximated function is created by a supervised machine learning algorithm from a set of observed branching decisions taken by the target strategy. The experiments performed on randomly generated and standard benchmark (MIPLIB) problems show promising results. [less ▲] Detailed reference viewed: 179 (3 ULg)An efficient algorithm for the provision of a day-ahead modulation service by a load aggregator Mathieu, Sébastien ; Ernst, Damien ; Louveaux, Quentin in Proceedings of the 4th European Innovative Smart Grid Technologies (ISGT) (2013, October) 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 157 (37 ULg)Généralisation Min Max pour l'Apprentissage par Renforcement Batch et Déterministe : Relaxations pour le Cas Général T Etapes Fonteneau, Raphaël ; Ernst, Damien ; Boigelot, Bernard et al in 8èmes Journées Francophones de Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA'13) (2013) 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 ... [more ▼] 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]. [less ▲] Detailed reference viewed: 45 (7 ULg) |
||