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 71 1 2 3 4     Multi-period vehicle loading with stochastic release datesArda, Yasemin ; Crama, Yves ; Kronus, David et alin EURO Journal on Transportation and Logistics (in press)This paper investigates a multi-period vehicle loading problem with stochastic information regarding the release dates of items to be transported. The deterministic version of the problem can be ... [more ▼]This paper investigates a multi-period vehicle loading problem with stochastic information regarding the release dates of items to be transported. The deterministic version of the problem can be formulated as a large-scale set covering problem. Several heuristic algorithms are proposed to generate decision policies for the stochastic optimization model over a long rolling horizon. The resulting policies have been extensively tested on instances which display the main characteristics of the industrial case-study that motivated the research. The tests demonstrate the benefits of the multi-period stochastic model over simple myopic strategies. A simple and efficient heuristic is shown to deliver good policies and to be robust against errors in the estimation of the probability distribution of the release dates. [less ▲]Detailed reference viewed: 50 (18 ULg) Quadratization of symmetric pseudo-Boolean functionsAnthony, Martin; Boros, Endre; Crama, Yves et alE-print/Working paper (2013)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: 11 (1 ULg) Multi-period load assignment problem with stochastic load availabilityCrama, Yves ; Pironet, Thierry E-print/Working paper (2013)In this research, we want to investigate optimization techniques for a generic load assignment problem including a limited fleet of vehicles within a full-truck-load (FTL) multi-period setting including ... [more ▼]In this research, we want to investigate optimization techniques for a generic load assignment problem including a limited fleet of vehicles within a full-truck-load (FTL) multi-period setting including forecasts on load availability. Several policies are generated from simple heuristics through state of the art approaches such as consensus and restricted expectation algorithms up to the optimization of a subtree of scenarios. Moreover, myopic and a-posteriori deterministic optimizations (including no or fully revealed information) set bounds for policies performance comparisons. Tests are performed for different graphs sizes and sparsity, several distribution laws and number of loads. Performances are compared statistically over paired samples. The robustness of performing policies against a false valuation of the probability distribution is also analyzed. [less ▲]Detailed reference viewed: 13 (5 ULg) Revealed preference tests of collectively rational consumption behavior: formulations and algorithmsTalla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves et alE-print/Working paper (2013)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: 22 (4 ULg) Neighborhood Search Approaches for a Vehicle Routing Problem with Multiple Trips and Driver ShiftsArda, Yasemin ; Crama, Yves ; François, Véronique Conference (2013, July 08)Detailed reference viewed: 31 (15 ULg) Optimization of Service Start Time for an Elementary Shortest Path ProblemKucukaydin, Hande ; Arda, Yasemin ; Crama, Yves Conference (2013, July 08)We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers ... [more ▼]We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers with a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where the delivery and backhaul customers are considered to be two disjoint sets. Split deliveries and pick-ups are not allowed. In this problem, the vehicle may be assigned to several routes. In addition, the vehicle can begin servicing the customers at any desired time and can be used for at most a fixed amount of time that depends on the shift duration of the assigned driver. Distance and time based variable costs are incurred by serving the customers. Namely, the total cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned multiple trips. On the other hand, serving a customer yields also a revenue. Therefore, the objective is to determine the optimal service start time of the vehicle from the depot along with the trips to be performed in order to minimize the total of the distance and time costs minus the collected revenues. Such a problem can be faced as the pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints, where the revenues are equivalent to the dual prizes of the visited vertices. In general, ESPPRC can be solved to optimality by using a dynamic programming algorithm. However, since the vehicle can start the service at any point in time and is paid based on the total time during which it has been used, our ESPPRC has to take an infinite number of Pareto-optimal states into account. Therefore, we adapt the well-known dynamic programming algorithm according to this feature and develop piecewise linear time functions that represent total traveling and waiting time depending on a variable start time at the depot. Consequently, we propose appropriate dominance rules to discard feasible paths that cannot lead to the optimal solution. Finally, computational results are presented. [less ▲]Detailed reference viewed: 34 (9 ULg) Approximation Algorithms for Multi-Dimensional Vector Assignment ProblemsCrama, Yves Conference (2013, July 04)Detailed reference viewed: 6 (0 ULg) Quadratic reformulations of nonlinear binary optimization problemsCrama, Yves Conference (2013, July 01)We consider the problem of minimizing a pseudo-Boolean function f(x), i.e., a real-valued function of 0-1 variables. Several authors have recently proposed to reduce this problem to the quadratic case by ... [more ▼]We consider the problem of minimizing a pseudo-Boolean function f(x), i.e., a real-valued function of 0-1 variables. Several authors have recently proposed to reduce this problem to the quadratic case by expressing f(x) as min{g(x,y): y in {0,1}}, where g is a quadratic function of x and of additional binary variables y. We establish lower and upper bounds on the number of additional y-variables needed in such a reformulation, both for the general case and for the special case of symmetricfunctions like positive or negative monomials, k-out-of-n majority functions, or parity functions. [less ▲]Detailed reference viewed: 10 (1 ULg) Quadratization of pseudo-Boolean functionsCrama, Yves Scientific conference (2013, June 20)Detailed reference viewed: 3 (0 ULg) Approximation Algorithms for Multi-Dimensional Vector Assignment ProblemsDokka, Trivikram; Crama, Yves ; Spieksma, Frits C.R.E-print/Working paper (2013)We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by$m$disjoint sets, each ... [more ▼]We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by$m$disjoint sets, each of which contains the same number$n$of$p$-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an$m$-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the$m$sets of vectors into$nm$-tuples so that no two vectors from the same set are in the same$m$-tuple and so that the total cost of the$m$-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider two classes of polynomial-time heuristics for MVA, namely, hub heuristics and sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, hub heuristics, as well as sequential heuristics, have finite approximation ratio for every fixed$m$. Moreover, we establish better approximation ratios for certain variants of hub heuristics and sequential heuristics when the cost function is monotone and submodular, or when it is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case$m=3$and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension$p\$. [less ▲]Detailed reference viewed: 43 (5 ULg) Quadratization of symmetric pseudo-Boolean functionsCrama, Yves Conference (2013, April)We consider the problem of minimizing an arbitrary pseudo-Boolean function f(x), that is, a real-valued function of 0-1 variables. In recent years, several authors have proposed to reduce this problem to ... [more ▼]We consider the problem of minimizing an arbitrary pseudo-Boolean function f(x), that is, a real-valued function of 0-1 variables. In recent years, several authors have proposed to reduce this problem to the quadratic case by expressing f(x) as min{g(x,y):y∈{0,1}^m}, where g(x,y) is a quadratic pseudo-Boolean function of x and of additional binary variables y. We say that g(x,y) is a quadratization of f. In this talk, we investigate the number of additional variables needed in a quadratization when f is a symmetric function of the x-variables. The cases where f is either a positive or a negative monomial are of particular interest, but some of our techniques also extend to more complex functions, like k-out-of-n or parity functions. Joint work with Martin Anthony, Endre Boros and Aritanan Gruber [less ▲]Detailed reference viewed: 10 (0 ULg) An adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shiftsArda, Yasemin ; Crama, Yves ; François, Véronique Conference (2013, February 13)This study analyzes a rich vehicle routing problem with multiple trips and driver shifts. The considered problem features are inspired from the practical case of a Belgian distribution company. Along with ... [more ▼]This study analyzes a rich vehicle routing problem with multiple trips and driver shifts. The considered problem features are inspired from the practical case of a Belgian distribution company. Along with the multi-trip component, characteristics of this particular problem include time windows, pickup and delivery customers, and site-vehicle dependencies. Internal and external fleets are considered with different cost structures and driver shifts constraints. An adpative large neighborhood search is used to treat the problem. [less ▲]Detailed reference viewed: 130 (6 ULg) An adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shiftsArda, Yasemin ; Crama, Yves ; François, Véronique Conference (2013, February 07)Detailed reference viewed: 26 (9 ULg) Méthodes Booléennes en recherche opérationnelleCrama, Yves Conference (2013, February)Le titre de cette conférence est celui d'une monographie cosignée par Peter L. Hammer et Sergiu Rudeanu, et dont la publication en 1968 a inspiré un nombre important de travaux de recherche. Très ... [more ▼]Le titre de cette conférence est celui d'une monographie cosignée par Peter L. Hammer et Sergiu Rudeanu, et dont la publication en 1968 a inspiré un nombre important de travaux de recherche. Très récemment, le regretté Peter Hammer et moi-même avons publié deux lointaines mises à jour de cet ouvrage classique: une monographie intitulée Boolean Functions: Theory, Algorithms, and Applications (700 pages, Cambridge University Press, 2011) et une collection de surveys sur le thème Boolean Models and Methods in Mathematics, Computer Science and Engineering (780 pages, Cambridge University Press, 2010). La taille de ces deux volumes et de leurs sections bibliographiques sont les témoins de la vitalité de ce domaine de recherche et de son développement impressionnant. Les fonctions booléennes comptent en effet parmi les objets les plus fondamentaux étudiés en mathématiques. Elles interviennent dans de nombreux modèles utilisés en recherche opérationnelle, informatique, intelligence artificielle, économie, ingénierie, cryptographie, biologie et autres domaines d'application. Dans cet exposé, nous proposons un bref aperçu de quelques modèles booléens fondamentaux et de leurs applications. [less ▲]Detailed reference viewed: 26 (0 ULg) Algorithmes d'approximation pour les problèmes d'affectation multidimensionnelsCrama, Yves Scientific conference (2013, January)Le problème d'affectation multidimensionnel (PAM) consiste à partitionner les sommets d'un graphe m-parti en m-cliques disjointes de façon à minimiser la somme des coûts des cliques utilisées, où le coût ... [more ▼]Le problème d'affectation multidimensionnel (PAM) consiste à partitionner les sommets d'un graphe m-parti en m-cliques disjointes de façon à minimiser la somme des coûts des cliques utilisées, où le coût des cliques peut être défini de différentes façons. PAM généralise le problème d'affectation ou de couplage biparti classique qui correspond au cas m=2. Nous présentons plusieurs résultats, anciens et nouveaux, relatifs à des cas particuliers de PAM obtenus en spécifiant les propriétés du coût des cliques. Pour ces cas particuliers, nous décrivons des algorithmes d'approximation, nous examinons leurs garanties de performance, et nous mentionnons quelques questions ouvertes. [less ▲]Detailed reference viewed: 75 (0 ULg) Algorithms for testing the collective consumption modelTalla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves et alConference (2012, November 09)In this talk, we discuss an extension of the strong axiom of revealed preferences to collective households. The question that we address is whether a set of observed consumption baskets can be decomposed ... [more ▼]In this talk, we discuss an extension of the strong axiom of revealed preferences to collective households. The question that we address is whether a set of observed consumption baskets can be decomposed in such a way that each of the derived data sets reflects the choices of a “rational” (i.e., utility-maximizing) individual member of the household. Although testing revealed preference axioms on data generated by a single decisionmaker can be done in polynomial time, the extension to two-member households is NP-complete. We propose two algorithms for testing the collective consumption model on large data sets. The first one is an exact algorithm based on a new mixed-integer programming formulation, whereas the second one is a heuristic based on a simulated annealing procedure that solves a global optimization formulation of the problem. Computational experiments are performed on real-life data. [less ▲]Detailed reference viewed: 13 (0 ULg) Boolean Methods and Logical Analysis of DataCrama, Yves Conference (2012, June 09)About 20 years ago, we proposed an innovative approach to data mining based on a blend of Boolean techniques and combinatorial optimization. The basic tenets of this approach were presented in a joint ... [more ▼]About 20 years ago, we proposed an innovative approach to data mining based on a blend of Boolean techniques and combinatorial optimization. The basic tenets of this approach were presented in a joint paper co-authored with Toshihide Ibaraki and myself. It was subsequently developed by Peter Hammer and his coworkers into a new broad area of research, dubbed Logical Analysis of Data, or LAD for short. The effectiveness of the LAD methodology has been validated by many successful applications to real-life data analysis problems. In a first part of this lecture, I will propose a brief overview of some fundamental Boolean models and of illustrative applications arising in computer science, in optimization and in game theory. I will next turn to a presentation of the basic principles of LAD and of some of the theoretical questions that have been investigated in connection with this methodology. This part of the lecture should allow the audience to place the development of LAD in a historical perspective. [less ▲]Detailed reference viewed: 15 (0 ULg) Multiperiod vehicle loading with stochastic release datesArda, Yasemin ; Crama, Yves ; Kronus, David et alConference (2012, May 24)Production scheduling and vehicle routing problems are well-known topics in operations management. Although these tasks are consecutive in the supply chain, few optimization models tackle the associated ... [more ▼]Production scheduling and vehicle routing problems are well-known topics in operations management. Although these tasks are consecutive in the supply chain, few optimization models tackle the associated issues. A most common situation, in practice, is actually that transportation management is disconnected from production planning: when production items or batches have been completely processed by the manufacturing plant, they become available for shipping, and they are consequently handled by the transportation managers. From a global managerial perspective, and with a view towards coordination of the product flows and customer satisfaction, this is not an ideal process. It is by far preferable, indeed, to set up an integrated production-transportation plan taking into account, among other constraints, the capacity of the plants and the customer due-dates. The present research proposes a methodology to investigate a multi-period vehicle loading problem with deterministic or stochastic information concerning items arrivals from production. Results from related optimization techniques are statistically compared and the benefits of the multi-period and stochastic modeling is demonstrated. Finally, an efficient heuristic is highlighted and is shown to be robust to the deviation from item arrival forecasts. [less ▲]Detailed reference viewed: 4 (3 ULg) A Rich Vehicle Routing Problem with Multiple Trips and Driver ShiftsArda, Yasemin ; Crama, Yves ; Kucukaydin, Hande et alConference (2012)This study is concerned with a rich vehicle routing problem (RVRP) encountered at a Belgian transportation company in charge of servicing supermarkets and hypermarkets belonging to a franchise. The ... [more ▼]This study is concerned with a rich vehicle routing problem (RVRP) encountered at a Belgian transportation company in charge of servicing supermarkets and hypermarkets belonging to a franchise. The studied problem can be classified as a one-to-many-to-one pick-up and delivery problem, where there is a single depot from which all delivery customers are served and to which every pick-up demand must be carried back (Gutiérrez-Jarpa et al., 2010). The delivery and backhaul customers are considered to be two disjoint sets, where on a given route backhaul customers can be visited only after all delivery customers are served. Split deliveries and pick-ups are not allowed. The service at a customer must start within the given time window of the customer. However, it is not possible to serve a customer with every available vehicle, since the vehicles at the company’s disposal are of different types according to which the capacity changes. Therefore, our problem can be classified also as a heterogeneous fleet vehicle routing problem with customer-vehicle incompatibilities (Ceselli et al., 2009). The problem at hand requires that the same vehicle may be assigned to several routes, which leads to a multiple-trip RVRP. Furthermore, driver shifts are taken into account so that each vehicle of the fleet starts servicing the customers when the shift of the assigned driver starts. The shift duration is the same for all drivers. If the service of the vehicle exceeds SH, an overtime cost incurs to the transportation company. In such a case, a vehicle can be used during at most a fixed length of time. In addition to the vehicles of the company’s own fleet (i.e. internal vehicles), there is a possibility to request external vehicles for servicing some customers. External vehicles can be used for a fixed maximum amount of time and can start servicing customers at any desired time. A fixed reservation cost and distance and time based variable costs are incurred in the case of an external vehicle, while only distance based variable costs are incurred in the case of an internal vehicle. We employ a binary integer linear programming formulation in order to model our problem. The first constraint set ensures that each customer is visited at least once by either an internal or external vehicle. With the second constraint set, it is guaranteed that each internal vehicle is assigned to at most one tour. The last two constraint sets are the binary restrictions on the assignment variables. In order to solve the problem, we first relax the binary restrictions on the assignment variables and develop a column generation procedure, where we obtain two pricing problems, one for internal vehicles and the other one for external vehicles. The pricing problem of each internal vehicle can be formulated as an elementary shortest path problem with resource constraints, which can be solved using a dynamic programming algorithm based on a bounded bi-directional search (Righini and Salani, 2008). However, since an external vehicle can start the service at any point in time and is paid based on its total travel time, the second pricing algorithm has to take into account an infinite number of Pareto-optimal states (Liberatore et al., 2011). We discuss the efficient solution of the pricing subproblems and present preliminary computational results. [less ▲]Detailed reference viewed: 153 (4 ULg) Boolean methods in operations research and related areasCrama, Yves Conference (2011, November)These are the slides of the "IFORS Distinguished Lecture" that I delivered at the INFORMS Annual meeting in November 2011. The title of the lecture is the title of a monograph co-authored by Peter L ... [more ▼]These are the slides of the "IFORS Distinguished Lecture" that I delivered at the INFORMS Annual meeting in November 2011. The title of the lecture is the title of a monograph co-authored by Peter L. Hammer and Sergiu Rudeanu, which appeared in 1968. Their pioneering work has stimulated a large amount of research and has been very frequently cited. Over the last year, the late Peter Hammer and myself have published two distant follow-ups to this classical book: a monograph entitled Boolean Functions: Theory, Algorithms, and Applications (700 pages, Cambridge University Press, 2011), and a collection of survey papers on Boolean Models and Methods in Mathematics, Computer Science and Engineering (780 pages, Cambridge University Press, 2010). The size of these two volumes and of their bibliographic sections are witnesses of the vitality of the field and of its impressive development. Boolean functions are actually among the most fundamental objects investigated in mathematics, and provide the basic building blocks for many models arising in operations research, computer science, artificial intelligence, economics, engineering, cryptography, biology, and other fields of application. In this lecture, I propose a brief overview of some fundamental Boolean models, I discuss applications in corporate governance (modeling of shareholders’ power) and in classification (Logical Analysis of Data), and I mention a few challenging research problems. [less ▲]Detailed reference viewed: 44 (2 ULg) 1 2 3 4