References of "Crama, Yves"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailMulti-Dimensional Vector Assignment Problems
Dokka, Trivikram; Crama, Yves ULg; Spieksma, Frits C.R.

in Discrete Optimization (in press)

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 ... [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: 8 (2 ULg)
Full Text
Peer Reviewed
See detailMulti-period vehicle loading with stochastic release dates
Arda, Yasemin ULg; Crama, Yves ULg; Kronus, David ULg et al

in EURO Journal on Transportation and Logistics (2014), 3(2), 93-119

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: 152 (33 ULg)
Full Text
See detailShort Prime Quadratizations of Cubic Negative Monomials
Crama, Yves ULg; Rodriguez Heck, Elisabeth ULg

E-print/Working paper (2014)

Pseudo-Boolean functions naturally model problems in a number of different areas such as computer science, statistics, economics, operations research or computer vision, among others. Pseudo-Boolean ... [more ▼]

Pseudo-Boolean functions naturally model problems in a number of different areas such as computer science, statistics, economics, operations research or computer vision, among others. Pseudo-Boolean optimization (PBO) is NP-hard, even for quadratic polynomial objective functions. However, much progress has been done in finding exact and heuristic algorithms for the quadratic case. Quadratizations are techniques aimed at reducing a general PBO problem to a quadratic polynomial one. Quadratizing single monomials is particularly interesting because it allows quadratizing any pseudo-Boolean function by termwise quadratization. A characterization of short quadratizations for negative monomials has been provided. In this report we present a proof of this characterization for the case of cubic monomials, which requires a different analysis than the case of higher degree. [less ▲]

Detailed reference viewed: 22 (6 ULg)
Full Text
See detailOptimization of the service start time for an elementary shortest path problem with time windows
Arda, Yasemin ULg; Crama, Yves ULg; Kucukaydin, Hande ULg

E-print/Working paper (2014)

We investigate an elementary shortest path problem with resource constraints where a single capacitated vehicle, initially located at a depot, must serve a set of customers while respecting their ... [more ▼]

We investigate an elementary shortest path problem with resource constraints where a single capacitated vehicle, initially located at a depot, must serve a set of customers while respecting their individual time windows. When the vehicle visits a customer, it delivers the customer's demand and collects a revenue in return for the delivery. The vehicle can start its trip at any desired time. The transportation cost is a function of both the total distance traveled and the duration of the assigned trip. The objective is to determine the service start time from the depot, the subset of customers to be served, and the trip to be performed so as to minimize the total loss, which is calculated as the di erence between the transportation cost and the revenue collected from the customers. We develop two exact dynamic programming algorithms which can deal with an in nite number of Pareto-optimal states arising from the fact that the starting time and the duration of the trip act like continuous decision variables. We report computational results obtained with these algorithms and with a faster heuristic for the elementary shortest path problem. We also examine the performance of these algorithms when they are used to solve the pricing subproblem arising in the framework of a column generation algorithm for a related vehicle routing problem with time windows. [less ▲]

Detailed reference viewed: 40 (5 ULg)
See detailApproximation algorithms for multi-dimensional vector assignment problems
Crama, Yves ULg

Conference (2014, July 09)

Detailed reference viewed: 5 (0 ULg)
See detailVehicle routing problems with multiple trips: using specific local search operators
Arda, Yasemin ULg; Crama, Yves ULg; François, Véronique ULg et al

Conference (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: 35 (3 ULg)
See detailAbout almost periodic sequences of integers and related concepts
Crama, Yves ULg

Scientific conference (2014, May 07)

Detailed reference viewed: 14 (2 ULg)
See detailCompact quadratizations of nonlinear binary optimization problems
Crama, Yves ULg; Rodriguez Heck, Elisabeth ULg

Conference (2014, March 25)

Detailed reference viewed: 28 (7 ULg)
Full Text
See detailMulti-period vehicle assignment with stochastic load availability
Crama, Yves ULg; Pironet, Thierry ULg

Conference (2014, February 27)

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 evaluations of the probability distributions is also analyzed. [less ▲]

Detailed reference viewed: 1 (0 ULg)
Full Text
See detailMulti-period vehicle assignment with stochastic load availability
Crama, Yves ULg; Pironet, Thierry ULg

Conference (2014, January 31)

We investigate the following problem, which is faced by major forwarding companies active in road transportation (see [2]). A company owning a limited fl eet of vehicles wants to maximize its operational ... [more ▼]

We investigate the following problem, which is faced by major forwarding companies active in road transportation (see [2]). A company owning a limited fl eet of vehicles wants to maximize its operational pro fit over an infi nite horizon divided into equal periods (days). The pro fit stems from revenues for transporting full truckloads and from costs derived from waiting idle and moving empty. A decision leading to a set of actions is made at every period and is based on the dispatcher's information over a restricted horizon, called rolling horizon, which subsequently rolls over period per period. The data provided by the customers concern their prospective loads, or requirements for transportation: locations of departure and destination cities, and a unique pick-up period for each load. Moreover, the dispatcher has data regarding travel times between cities, current location and status (empty or loaded) of trucks. These data are known with certainty and represent the deterministic component of the problem. The stochastic component of the problem arises from the uncertainty on the eff ective materialization of each transportation order. More precisely, the availability of each order can be either con rmed, or denied, a few periods ahead of the loading period (meaning that clients con firm their order, which the transporter may still decide to ful ll, or not). For prospective orders in the remote part of the rolling horizon, the dispatcher only knows the order con firmation probability which represents the stochastic load availability. In this setting, trucking orders are provided by the dispatching center to the drivers and to the customers on the eve of the pick-up period at the latest. Typically, the loading decisions are made when all orders are con firmed for the next day. The decision problem faced by the dispatcher is to select or to reject loads, and to assign the selected loads to trucks, taking into account con firmed and expected loads as well as the availability and current location of trucks. The main objective of this research is to provide e fficient algorithmic strategies to tackle this multi-period vehicle-load assignment problem over a rolling horizon including prospective transportation orders. This problem is computationally di fficult owing to the large number of possible realizations of the random variables, and to the combinatorial nature of the decision space. The methodology is based on optimizing decisions for deterministic scenarios. By solving the assignment problem for a sample of scenarios, by mixing solutions and by evaluating them at each period, we aim at finding actions per decision period leading to pro table policies in the long run. Several policies are generated in this way, from simple myopic heuristics to more complex approaches, such as consensus and restricted expectation algorithms [3], up to policies derived from network flow models formulated over subtrees of scenarios. Similar approaches have proved eff ective for other problems; see, e.g., [1]. Myopic and a-posteriori deterministic optimization models are used to compute bounds allowing for performance evaluation. Test are performed on various instances featuring di fferent numbers of loads, graph sizes, sparsity, and probability distributions. Performances are compared statistically over paired samples to assess the signi ficance of the observed differences among algorithmic policies. The robustness of various policies with respect to erroneous evaluations of the probability distributions is also analyzed. Numerical experiments show that the best algorithms close a signi ficant fraction of the gap between the worst (myopic) and best (a posteriori) bounds for a broad range of datasets and for several probability distributions. Furthermore, the subtree algorithm remains quite robust against a variety of probability distributions when it is calibrated with a distribution re flecting maximum uncertainty . Acknowledgements. The project leading to these results was partially funded by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy O ffice (grant P7/36). References [1] Arda, Y., Crama, Y., Kronus, D., Pironet, Th., and Van Hentenryck, P. (2013), Multi-period vehicle loading with stochastic release dates, EURO Journal on Transportation and Logistics, pp. 1-27, available on-line http://dx.doi.org/10.1007/s13676-013-0035-z. [2] Powell, W. B. (1996), A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers, Transportation Science, Vol. 30, pp. 195-219. [3] Van Hentenryck, P., and Bent,R. W. (2006), Online Stochastic Combinatorial Optimization, MIT Press, Cambridge, Massachussetts. [less ▲]

Detailed reference viewed: 8 (3 ULg)
Peer Reviewed
See detailAn exact bi-directional dynamic programming algorithm for an elementary shortest path problem with variable service start time
Arda, Yasemin ULg; Crama, Yves ULg; Kucukaydin, Hande ULg

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: 36 (0 ULg)
See detailQuadratic reformulations of nonlinear binary optimization problems
Crama, Yves ULg

Conference (2014, January 30)

Detailed reference viewed: 20 (0 ULg)
See detailQuadratic reformulations of nonlinear binary optimization problems
Crama, Yves ULg

Conference (2014, January 06)

Detailed reference viewed: 17 (1 ULg)
Full Text
See detailQuadratization of symmetric pseudo-Boolean functions
Anthony, Martin; Boros, Endre; Crama, Yves ULg et al

E-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: 50 (3 ULg)
Full Text
See detailMulti-period load assignment problem with stochastic load availability
Crama, Yves ULg; Pironet, Thierry ULg

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: 32 (6 ULg)
Full Text
See detailRevealed preference tests of collectively rational consumption behavior: formulations and algorithms
Talla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves ULg et al

E-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: 36 (6 ULg)
Peer Reviewed
See detailOptimization of Service Start Time for an Elementary Shortest Path Problem
Kucukaydin, Hande ULg; Arda, Yasemin ULg; Crama, Yves ULg

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: 57 (11 ULg)
See detailApproximation Algorithms for Multi-Dimensional Vector Assignment Problems
Crama, Yves ULg

Conference (2013, July 04)

Detailed reference viewed: 11 (0 ULg)
See detailQuadratic reformulations of nonlinear binary optimization problems
Crama, Yves ULg

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: 35 (1 ULg)