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 21 to 40 of 101     1 2 3 4 5 6     Vehicle routing problems with multiple trips: using specific local search operatorsArda, Yasemin ; Crama, Yves ; François, Véronique et alConference (2014, June 25)In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem make use of existing ... [more ▼]In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem make use of existing VRP heuristics to create trips, together with bin packing methods aimed at assigning these trips to the available vehicles. The first contribution of this work is to propose specific local search operators for the VRPM. The operators directly integrate the multi-trip structure of the problem within well-known VRP operators. As a second contribution, heuristics using these operators are compared with classical solution techniques mentioned above. The comparison is performed by using the adaptive large neighborhood search metaheuristic as a common basis for both methods. The most classical version of the problem is studied as well as a variant involving time windows [less ▲]Detailed reference viewed: 87 (8 ULg) Service Start Time Optimization in Elementary Shortest Path Problems with Resource ConstraintsArda, Yasemin ; Kucukaydin, Hande; Crama, Yves Scientific conference (2014, June 12)Besides their real-life applications, elementary shortest path problems with resource constraints are faced as the pricing sub-problem when more complex problems are solved through column generation and ... [more ▼]Besides their real-life applications, elementary shortest path problems with resource constraints are faced as the pricing sub-problem when more complex problems are solved through column generation and branch-and-price. We consider an elementary shortest path problem with resource constraints, where there is a capacitated single vehicle at the depot for serving a set of customers by respecting their associated time windows. The vehicle can start serving the customers at any desired time and can be used for a fixed amount of time. The total transportation cost is defined as a function of the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. Every time the vehicle visits a customer, it delivers the required load and collects a revenue in return for the delivery. The objective is to determine the trip to be performed and the service start time from the depot so as to minimize the total loss, which is calculated as the total transportation cost minus the collected revenues. In this study, we develop two exact dynamic programming algorithms which can deal with an infinite number of Pareto-optimal states arising from the fact that the vehicle can depart from the depot at any point in time and charges depending on the amount of time it spends for serving customers. Apart from reporting computational results for our elementary shortest path problem, we also embed it into a column generation framework for the corresponding capacitated vehicle routing problem with time windows. Recent results for the developed branch-and-price algorithm are also reported. [less ▲]Detailed reference viewed: 13 (0 ULg) About almost periodic sequences of integers and related conceptsCrama, Yves Scientific conference (2014, May 07)Detailed reference viewed: 17 (4 ULg) Compact quadratizations of nonlinear binary optimization problemsCrama, Yves ; Rodriguez Heck, Elisabeth Conference (2014, March 25)Detailed reference viewed: 48 (18 ULg) An exact bi-directional dynamic programming algorithm for an elementary shortest path problem with variable service start timeArda, Yasemin ; Crama, Yves ; Kucukaydin, Hande Conference (2014, January 31)We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves customers by respecting their associated time windows. The vehicle can start ... [more ▼]We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves customers by respecting their associated time windows. The vehicle can start servicing the customers at any desired time, but it can be used for a fixed amount of time. The total transportation cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. On the other hand, each served customer yields a revenue. Thus, the aim is to identify the path to be followed and the start time of the vehicle from the depot that minimize the total transportation cost minus the gained revenues. This kind of a problem can be encountered as a pricing subproblem when a branch-and-price algorithm is applied to solve vehicle routing problems with additional constraints. In such a case, the revenues correspond to the dual prices of the visited vertices. It is known that the classical ESPPRC can be solved to optimality by implementing a dynamic programming (DP) algorithm. However, our problem has to take an infinite number of Pareto-optimal states into consideration, since the vehicle can leave the depot at any point in time and charges depending on the total traveling and waiting time. We propose an exact DP algorithm which can deal with an infinite number of Pareto-optimal states by representing total traveling and waiting time as a piecewise linear function of the service start time at the depot and develop suitable dominance rules. Furthermore, a column generation algorithm is devised for solving the relaxed set covering formulation of the related vehicle routing problem where new columns are determined by the proposed DP algorithm. Finally, computational results are presented. [less ▲]Detailed reference viewed: 122 (1 ULg) Quadratic reformulations of nonlinear binary optimization problemsCrama, Yves Conference (2014, January 30)Detailed reference viewed: 28 (1 ULg) Quadratic reformulations of nonlinear binary optimization problemsCrama, Yves Conference (2014, January 06)Detailed reference viewed: 21 (2 ULg) Multi-Dimensional Vector Assignment ProblemsDokka, Trivikram; Crama, Yves ; Spieksma, Frits C.R.in Discrete Optimization (2014), 14We 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 ... [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 n m-tuples so that no two vectors from the same set are in the same m-tuple and so that the sum of the costs of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed m. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function 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: 30 (6 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: 69 (7 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: 66 (7 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: 76 (14 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: 44 (16 ULg) Approximation Algorithms for Multi-Dimensional Vector Assignment ProblemsCrama, Yves Conference (2013, July 04)Detailed reference viewed: 12 (0 ULg) A global optimization method for naval structure op- timizationBay, Maud ; Crama, Yves ; Rigo, Philippe Conference (2013, July 01)The paper proposes a global optimization method for the preliminary structural design of large vessels in shipbuilding industry. We face a combinatorial problem of large size, with constraints modeled as ... [more ▼]The paper proposes a global optimization method for the preliminary structural design of large vessels in shipbuilding industry. We face a combinatorial problem of large size, with constraints modeled as implicit functions with nonlinear behavior. We present a heuristic method that performs a global search over the feasible solution space, combining a large neighborhood search and a heuristic local search. Experiments on actual structural optimization problems show that the heuristic converges towards discrete feasible solutions of good quality. [less ▲]Detailed reference viewed: 14 (1 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: 76 (2 ULg) Quadratization of pseudo-Boolean functionsCrama, Yves Scientific conference (2013, June 20)Detailed reference viewed: 11 (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: 116 (10 ULg) An elementary shortest path problem with variable service start timeKucukaydin, Hande ; Arda, Yasemin ; Crama, Yves Conference (2013, May 02)We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves a set of delivery and backhaul customers with a revenue and a time window. On ... [more ▼]We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves a set of delivery and backhaul customers with a revenue and a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where a customer is either a delivery or a backhaul customer, but not both. Split deliveries and pick-ups are not allowed. In this problem, multiple trips are allowed so that the vehicle can 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. In other words, 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 aim 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 routing 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, we present computational results. [less ▲]Detailed reference viewed: 46 (1 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: 28 (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: 193 (8 ULg)