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

E-print/Working paper (2014)

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: 35 (6 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: 157 (35 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: 29 (12 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: 74 (6 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: 46 (6 ULg)
See detailAbout almost periodic sequences of integers and related concepts
Crama, Yves ULg

Scientific conference (2014, May 07)

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

Conference (2014, March 25)

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

Conference (2014, January 30)

Detailed reference viewed: 21 (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: 53 (3 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: 40 (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: 58 (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: 37 (1 ULg)
See detailQuadratization of pseudo-Boolean functions
Crama, Yves ULg

Scientific conference (2013, June 20)

Detailed reference viewed: 9 (0 ULg)
Full Text
See detailApproximation Algorithms for Multi-Dimensional Vector Assignment Problems
Dokka, Trivikram; Crama, Yves ULg; 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 $n$ $m$-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: 90 (10 ULg)