References of "Crama, Yves"      in Complete repository Arts & humanities   Archaeology   Art & art history   Classical & oriental studies   History   Languages & linguistics   Literature   Performing arts   Philosophy & ethics   Religion & theology   Multidisciplinary, general & others Business & economic sciences   Accounting & auditing   Production, distribution & supply chain management   Finance   General management & organizational theory   Human resources management   Management information systems   Marketing   Strategy & innovation   Quantitative methods in economics & management   General economics & history of economic thought   International economics   Macroeconomics & monetary economics   Microeconomics   Economic systems & public economics   Social economics   Special economic topics (health, labor, transportation…)   Multidisciplinary, general & others Engineering, computing & technology   Aerospace & aeronautics engineering   Architecture   Chemical engineering   Civil engineering   Computer science   Electrical & electronics engineering   Energy   Geological, petroleum & mining engineering   Materials science & engineering   Mechanical engineering   Multidisciplinary, general & others Human health sciences   Alternative medicine   Anesthesia & intensive care   Cardiovascular & respiratory systems   Dentistry & oral medicine   Dermatology   Endocrinology, metabolism & nutrition   Forensic medicine   Gastroenterology & hepatology   General & internal medicine   Geriatrics   Hematology   Immunology & infectious disease   Laboratory medicine & medical technology   Neurology   Oncology   Ophthalmology   Orthopedics, rehabilitation & sports medicine   Otolaryngology   Pediatrics   Pharmacy, pharmacology & toxicology   Psychiatry   Public health, health care sciences & services   Radiology, nuclear medicine & imaging   Reproductive medicine (gynecology, andrology, obstetrics)   Rheumatology   Surgery   Urology & nephrology   Multidisciplinary, general & others Law, criminology & political science   Civil law   Criminal law & procedure   Criminology   Economic & commercial law   European & international law   Judicial law   Metalaw, Roman law, history of law & comparative law   Political science, public administration & international relations   Public law   Social law   Tax law   Multidisciplinary, general & others Life sciences   Agriculture & agronomy   Anatomy (cytology, histology, embryology...) & physiology   Animal production & animal husbandry   Aquatic sciences & oceanology   Biochemistry, biophysics & molecular biology   Biotechnology   Entomology & pest control   Environmental sciences & ecology   Food science   Genetics & genetic processes   Microbiology   Phytobiology (plant sciences, forestry, mycology...)   Veterinary medicine & animal health   Zoology   Multidisciplinary, general & others Physical, chemical, mathematical & earth Sciences   Chemistry   Earth sciences & physical geography   Mathematics   Physics   Space science, astronomy & astrophysics   Multidisciplinary, general & others Social & behavioral sciences, psychology   Animal psychology, ethology & psychobiology   Anthropology   Communication & mass media   Education & instruction   Human geography & demography   Library & information sciences   Neurosciences & behavior   Regional & inter-regional studies   Social work & social policy   Sociology & social sciences   Social, industrial & organizational psychology   Theoretical & cognitive psychology   Treatment & clinical psychology   Multidisciplinary, general & others     Showing results 1 to 20 of 109 1 2 3 4 5 6     Quadratic reformulations of nonlinear binary optimization problemsAnthony, Martin; Boros, Endre; Crama, Yves et alin 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: 96 (7 ULg) Revealed preference tests of collectively rational consumption behavior: formulations and algorithmsTalla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves et alin 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 problemsCrama, 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: 57 (3 ULg) Recherche à voisinage large pour le problème de tournées de véhicules à voyages multiplesFrançois, Véronique ; Arda, Yasemin ; Crama, Yves et alConference (2016, February 10)Detailed reference viewed: 25 (1 ULg) Tightening linearizations of non-linear binary optimization problemsRodriguez Heck, Elisabeth ; Crama, Yves Conference (2016, January 28)Detailed reference viewed: 20 (3 ULg) Quadratization of symmetric pseudo-Boolean functionsAnthony, Martin; Boros, Endre; Crama, Yves et alin Discrete Applied Mathematics (2016), 203A 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 routingFrançois, Véronique ; Arda, Yasemin ; Crama, Yves et alE-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: 126 (17 ULg) Revealed preference tests of collectively rational consumption behaviorCrama, 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 requestsCrama, 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: 131 (15 ULg) Quadratizations of pseudo-Boolean functionsCrama, 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 TimeKüçükaydın, Hande; Arda, Yasemin ; Crama, Yves et alConference (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: 34 (2 ULg) Strengthening linear reformulations of pseudo-Boolean optimization problemsRodriguez Heck, Elisabeth ; Crama, Yves Conference (2015, July 13)Detailed reference viewed: 48 (14 ULg) Quadratization of pseudo-Boolean functionsCrama, Yves ; Anthony, Martin; Boros, Endre et alConference (2015, July)Detailed reference viewed: 21 (1 ULg) Linearization and quadratization approaches for non-linear 0-1 optimizationRodriguez 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 TimeMichelini, Stefano ; Arda, Yasemin ; Crama, Yves et alConference (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 availabilityPironet, 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: 86 (1 ULg) Proceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling ProblemsMarchetti-Spaccamela, Alberto; Crama, Yves ; Goossens, Dries et alBook 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: 104 (8 ULg) Functions of binary variablesCrama, 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 TimeMichelini, Stefano ; Arda, Yasemin ; Crama, Yves et alConference (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: 74 (22 ULg)