Browse ORBi by ORBi project

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

Quadratic reformulations of nonlinear binary optimization problems ; ; Crama, Yves 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: 95 (7 ULg)Revealed preference tests of collectively rational consumption behavior: formulations and algorithms ; ; Crama, Yves et al in Operations Research (in press) This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np ... [more ▼] This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np}-complete. This makes the application of these tests problematic for (increasingly available) large(r) scale data sets. We then present two approaches to overcome this negative result. First, we introduce exact algorithms based on mixed-integer programming ({\sc mip}) formulations of the collective rationality tests, which can be usefully applied to medium sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model in the case of large data sets. We illustrate our methods by a number of computational experiments based on Dutch labor supply data. [less ▲] Detailed reference viewed: 86 (10 ULg)A class of valid inequalities for multilinear 0-1 optimization problems Crama, Yves ; Rodriguez Heck, Elisabeth E-print/Working paper (2016) This paper investigates the polytope associated with the classical standard linearization technique for the unconstrained optimization of multilinear polynomials in 0-1 variables. A new class of valid ... [more ▼] This paper investigates the polytope associated with the classical standard linearization technique for the unconstrained optimization of multilinear polynomials in 0-1 variables. A new class of valid inequalities, called 2-links, is introduced to strengthen the LP relaxation of the standard linearization. The addition of the 2-links to the standard linearization inequalities provides a complete description of the convex hull of integer solutions for the case of functions consisting of at most two nonlinear monomials. For the general case, various computational experiments show that the 2- links improve both the standard linearization bound and the computational performance of exact branch & cut methods. The improvements are especially significant for a class of instances inspired from the image restoration problem in computer vision. The magnitude of this effect is rather surprising in that the 2-links are in relatively small number (quadratic in the number of terms of the objective function). [less ▲] Detailed reference viewed: 53 (3 ULg)Recherche à voisinage large pour le problème de tournées de véhicules à voyages multiples François, Véronique ; Arda, Yasemin ; Crama, Yves et al Conference (2016, February 10) Detailed reference viewed: 24 (1 ULg)Tightening linearizations of non-linear binary optimization problems Rodriguez Heck, Elisabeth ; Crama, Yves Conference (2016, January 28) Detailed reference viewed: 20 (3 ULg)Quadratization of symmetric pseudo-Boolean functions ; ; Crama, Yves et al in Discrete Applied Mathematics (2016), 203 A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1 ... [more ▼] A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say that $g(x,y)$ is a quadratization of $f$ if $g(x,y)$ is a Quadratic polynomial depending on $x$ and on $m$ auxiliary binary variables $y_1,y_2,\ldots,y_m$ such that $f(x)= \min \{ g(x,y) : y \in \{0,1\}^m \} $ for all $x \in \{0,1\}^n$. By means of quadratizations, minimization of $f$ is reduced to minimization (over its extended set of variables) of the quadratic function $g(x,y)$. This is of some practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper initiated a systematic study of the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function $f$ (a natural question, since the complexity of minimizing the quadratic function $g(x,y)$ depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of \emph{symmetric} pseudo-Boolean functions $f(x)$, those functions whose value depends only on the Hamming weight of the input $x$ (the number of variables equal to 1). [less ▲] Detailed reference viewed: 83 (12 ULg)Large neighborhood search for multi-trip vehicle routing François, Véronique ; Arda, Yasemin ; Crama, Yves et al E-print/Working paper (2015) We consider two large neighborhood search approaches for the multi-trip vehicle routing problem, where each vehicle can perform several routes during the working shift to serve a set of customers. The ... [more ▼] We consider two large neighborhood search approaches for the multi-trip vehicle routing problem, where each vehicle can perform several routes during the working shift to serve a set of customers. The problem specifically arises when customers are close to each other and/or when the demands are large. A common approach in the literature consists in solving this problem by mixing vehicle routing heuristics with bin packing routines to assign routes to vehicles. We compare this approach with the use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. We provide several best known solutions for benchmark instances. At the end of the work, we give insights about the proposed algorithm configurations by analyzing the behavior of several method components. [less ▲] Detailed reference viewed: 125 (17 ULg)Revealed preference tests of collectively rational consumption behavior Crama, Yves Scientific conference (2015, October 29) To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests did can be applied to real-world data. These tests check whether the observed ... [more ▼] To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests did can be applied to real-world data. These tests check whether the observed household behavior is "rational" in the sense that it is consistent with the predictions of the model. In this talk, we present different approaches based on revealed preferences to test collective models of household consumption. Testing collective rationality is computationally difficult (NP-hard). In order to overcome this negative result, we introduce mixed-integer programming formulations which can be used for medium-sized datasets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model on large datasets. We present the results of computational experiments with our approaches. Joint work with: Fabrice Talla Nobibon, Laurens Cherchye, Thomas Demuynck, Bram De Rock and Frits CR Spieksma. [less ▲] Detailed reference viewed: 26 (0 ULg)Multi-period vehicle allocation with uncertain transportation requests Crama, Yves ; Pironet, Thierry E-print/Working paper (2015) This work investigates optimization techniques for a multi-period vehicle allocation problem with uncertain requests. A company owning a limited fleet of trucks attempts to maximize its operational profit ... [more ▼] This work investigates optimization techniques for a multi-period vehicle allocation problem with uncertain requests. A company owning a limited fleet of trucks attempts to maximize its operational profit over an infinite horizon by optimally assigning transportation orders to the vehicles. Its profit stems from profits collected when transporting full truckloads, minus costs incurred when waiting or when moving unladen. The stochastic component of the problem arises from the uncertainty on the realization of each transportation order. The methodology is based on optimizing decisions for deterministic scenarios. Several policies are generated in this way, either by simple heuristics, or by more complex approaches, such as consensus and restricted expectation algorithms, or from network flow formulations over subtrees of scenarios. Myopic and a-posteriori deterministic optimization models are used to compute bounds allowing for performance evaluation. Numerical experiments are performed on various instances featuring different numbers of orders, graph sizes, sparsity, and probability distributions, and the performance of the algorithms is assessed by statistical tests. The robustness of various policies with respect to erroneous evaluations of the probability distributions is also analyzed. [less ▲] Detailed reference viewed: 129 (15 ULg)Quadratizations of pseudo-Boolean functions Crama, Yves Conference (2015, October 23) A pseudo-Boolean function is a real-valued function of 0-1 variables. Every pseudo-Boolean function can be represented by various analytical expressions, e.g., as a polynomial in its variables, or as a ... [more ▼] A pseudo-Boolean function is a real-valued function of 0-1 variables. Every pseudo-Boolean function can be represented by various analytical expressions, e.g., as a polynomial in its variables, or as a polynomial in its variables and in their Boolean complements, or as a disjunctive form, or as pointwise minimum of a family of affine functions, and so forth. Motivated by the problem of minimizing pseudo-Boolean functions, we consider yet another class of representations. Namely, we say that g(x,y) is a quadratization of the pseudo-Boolean function f(x) if g(x,y) is a quadratic pseudo-Boolean function of x and of m auxiliary binary variables y such that, for all x, f(x) = min g(x,y), where the minimum is taken over all possible values of the y-variables. It can be shown that every pseudo-Boolean function has at least one, and usually, many quadratizations. In recent years, several authors have proposed to reduce the problem of minimizing an arbitrary function f(x) (say, expressed as a high-degree polynomial) to the (presumably easier) problem of minimizing one of its quadratizations. In this talk, we discuss the size of ``small'' quadratizations, that is, the number of auxiliary variables required in any quadratization. We provide lower and upper bounds on the number of auxiliary variables for the case of an arbitrary function f(x), as well as for the special case where f(x) is a symmetric function of its variables. [less ▲] Detailed reference viewed: 28 (2 ULg)Branch-and-Price Based Matheuristics for a Vehicle Routing Problem with Time Windows and Variable Service Start Time ; Arda, Yasemin ; Crama, Yves et al Conference (2015, July 15) We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In ... [more ▼] We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In order to solve the problem to optimality, a branch-and-price (BP) algorithm is implemented recognizing the pertinent pricing subproblem as an elementary shortest path problem with resource constraints (ESPPRC) which can handle an infinite number of labels and employs effective dominance rules. We present the past, present, and future implementations of the BP procedure based on bounded bi-directional search, decremental state space relaxation, and ng-route relaxation. We further discuss the design of BP-based matheuristics which make use of metaheuristics in pricing subproblem resolution, upper bound improvement, and column generation. [less ▲] Detailed reference viewed: 33 (2 ULg)Strengthening linear reformulations of pseudo-Boolean optimization problems Rodriguez Heck, Elisabeth ; Crama, Yves Conference (2015, July 13) Detailed reference viewed: 48 (14 ULg)Quadratization of pseudo-Boolean functions Crama, Yves ; ; et al Conference (2015, July) Detailed reference viewed: 21 (1 ULg)Linearization and quadratization approaches for non-linear 0-1 optimization Rodriguez Heck, Elisabeth ; Crama, Yves Scientific conference (2015, June 23) Detailed reference viewed: 16 (6 ULg)Exact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time Michelini, Stefano ; Arda, Yasemin ; Crama, Yves et al Conference (2015, June 10) We consider a VRP with time windows in which the total cost of a solu- tion depends on the total duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first ... [more ▼] We consider a VRP with time windows in which the total cost of a solu- tion depends on the total duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch- and-Price (BP) algorithm considering the related pricing subproblem, an elementary shortest path problem with resource constraints (ESP- PRC). We discuss past, present and planned research on this exact so- lution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic. [less ▲] Detailed reference viewed: 24 (5 ULg)Multi-period vehicle assignment problem with stochastic transportation order availability Pironet, Thierry ; Crama, Yves Conference (2015, June 01) This work investigates optimization techniques for a vehicle-load assignment problem. A company owning a limited fleet of vehicles wants to maximize its operational profit over an infinite horizon divided ... [more ▼] This work investigates optimization techniques for a vehicle-load assignment problem. A company owning a limited fleet of vehicles wants to maximize its operational profit over an infinite horizon divided into periods. The profit stems from revenues for transporting full truckloads and costs derived from waiting idle and moving unladen. The stochastic component of the problem arises from projections on the realization of each transportation order, i.e. load. The methodology is based on optimizing decisions for deterministic scenarios. Several policies are generated in this way, from simple heuristics to more complex approaches, such as consensus and restricted expectation algorithms, up to policies derived from network flow models formulated over subtrees of scenarios. Myopic and a-posteriori deterministic optimizations models are used to compute bounds allowing for performance evaluation. Tests are performed on various instances featuring different number of loads, graph sizes, sparsity, and probability distributions. Performances are compared statistically over paired samples. The robustness of various policies with respect to erroneous évaluations of the probability distributions is also analyzed. [less ▲] Detailed reference viewed: 85 (1 ULg)Proceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems ; Crama, Yves ; et al Book published by KU Leuven (2015) This volume contains abstracts of talks presented at the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), held from June 8 to June 12, 2015, in La Roche-en-Ardenne ... [more ▼] This volume contains abstracts of talks presented at the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), held from June 8 to June 12, 2015, in La Roche-en-Ardenne, Belgium. MAPSP is a biennial workshop dedicated to all theoretical and practical aspects of scheduling, planning, and timetabling. The abstracts in this volume include 5 invited talks by Onno Boxma, Michel Goemans, Willem-Jan van Hoeve, Rolf Niedermeier, and Stephan Westphal, plus 88 contributed talks. [less ▲] Detailed reference viewed: 103 (8 ULg)Functions of binary variables Crama, Yves Conference (2015, April 29) Detailed reference viewed: 18 (0 ULg)Quand les maths nous transportent... Crama, Yves Conference given outside the academic context (2015) Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter ... [more ▼] Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter deux fois le même pont. Leonhard Euler apporta en 1736 une démonstration élégante de cette affirmation. Il produisit ainsi l’une des premières applications des mathématiques à la construction d’itinéraires optimisés. Aujourd’hui, la modélisation mathématique est devenue un outil indispensable pour les décideurs dans le monde du transport et, plus généralement, pour la gestion et la planification des activités logistiques. Qu’il s’agisse de calculer l’itinéraire le plus rapide de Liège à Marbella, d’optimiser les tournées de livraison d’une chaîne de grande distribution, de charger des navires ou des avions en assurant leur stabilité, de réduire les stocks excédentaires d’une entreprise pharmaceutique, de fixer le prix de billets de TGV en fonction des places disponibles, dans chaque cas, les mathématiques, alliées à l’informatique, permettent de formuler de façon précise le problème rencontré et d’y apporter des réponses pertinentes. Cet exposé présentera quelques applications typiques des mathématiques dans le domaine de la logistique et fournira un aperçu des méthodes qui y sont mises en œuvre. [less ▲] Detailed reference viewed: 30 (3 ULg)Exact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time Michelini, Stefano ; Arda, Yasemin ; Crama, Yves et al Conference (2015, February 05) We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a ... [more ▼] We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch-and-Price algorithm considering the pricing subproblem, an elementary shortest path problem with resource constraints (ESPPRC). We discuss research on this exact solution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic. [less ▲] Detailed reference viewed: 73 (22 ULg) |
||