References of "Crama, Yves"
     in
Bookmark and Share    
See detailQuadratizations of pseudo-Boolean functions
Crama, Yves ULg

Conference (2015, October 23)

A pseudo-Boolean function is a real-valued function of 0-1 variables. Every pseudo-Boolean function can be represented by various analytical expressions, e.g., as a polynomial in its variables, or as a ... [more ▼]

A pseudo-Boolean function is a real-valued function of 0-1 variables. Every pseudo-Boolean function can be represented by various analytical expressions, e.g., as a polynomial in its variables, or as a polynomial in its variables and in their Boolean complements, or as a disjunctive form, or as pointwise minimum of a family of affine functions, and so forth. Motivated by the problem of minimizing pseudo-Boolean functions, we consider yet another class of representations. Namely, we say that g(x,y) is a quadratization of the pseudo-Boolean function f(x) if g(x,y) is a quadratic pseudo-Boolean function of x and of m auxiliary binary variables y such that, for all x, f(x) = min g(x,y), where the minimum is taken over all possible values of the y-variables. It can be shown that every pseudo-Boolean function has at least one, and usually, many quadratizations. In recent years, several authors have proposed to reduce the problem of minimizing an arbitrary function f(x) (say, expressed as a high-degree polynomial) to the (presumably easier) problem of minimizing one of its quadratizations. In this talk, we discuss the size of ``small'' quadratizations, that is, the number of auxiliary variables required in any quadratization. We provide lower and upper bounds on the number of auxiliary variables for the case of an arbitrary function f(x), as well as for the special case where f(x) is a symmetric function of its variables. [less ▲]

Detailed reference viewed: 37 (3 ULg)
Peer Reviewed
See detailBranch-and-Price Based Matheuristics for a Vehicle Routing Problem with Time Windows and Variable Service Start Time
Küçükaydın, Hande; Arda, Yasemin ULg; Crama, Yves ULg et al

Conference (2015, July 15)

We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In ... [more ▼]

We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In order to solve the problem to optimality, a branch-and-price (BP) algorithm is implemented recognizing the pertinent pricing subproblem as an elementary shortest path problem with resource constraints (ESPPRC) which can handle an infinite number of labels and employs effective dominance rules. We present the past, present, and future implementations of the BP procedure based on bounded bi-directional search, decremental state space relaxation, and ng-route relaxation. We further discuss the design of BP-based matheuristics which make use of metaheuristics in pricing subproblem resolution, upper bound improvement, and column generation. [less ▲]

Detailed reference viewed: 105 (4 ULg)
See detailQuadratization of pseudo-Boolean functions
Crama, Yves ULg; Anthony, Martin; Boros, Endre et al

Conference (2015, July)

Detailed reference viewed: 30 (1 ULg)
Full Text
See detailLinearization and quadratization approaches for non-linear 0-1 optimization
Rodriguez Heck, Elisabeth ULg; Crama, Yves ULg

Scientific conference (2015, June 23)

Detailed reference viewed: 20 (8 ULg)
Full Text
Peer Reviewed
See detailExact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time
Michelini, Stefano ULg; Arda, Yasemin ULg; Crama, Yves ULg et al

Conference (2015, June 10)

We consider a VRP with time windows in which the total cost of a solu- tion depends on the total duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first ... [more ▼]

We consider a VRP with time windows in which the total cost of a solu- tion depends on the total duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch- and-Price (BP) algorithm considering the related pricing subproblem, an elementary shortest path problem with resource constraints (ESP- PRC). We discuss past, present and planned research on this exact so- lution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic. [less ▲]

Detailed reference viewed: 37 (6 ULg)
Full Text
Peer Reviewed
See detailMulti-period vehicle assignment problem with stochastic transportation order availability
Pironet, Thierry ULg; Crama, Yves ULg

Conference (2015, June 01)

This work investigates optimization techniques for a vehicle-load assignment problem. A company owning a limited fleet of vehicles wants to maximize its operational profit over an infinite horizon divided ... [more ▼]

This work investigates optimization techniques for a vehicle-load assignment problem. A company owning a limited fleet of vehicles wants to maximize its operational profit over an infinite horizon divided into periods. The profit stems from revenues for transporting full truckloads and costs derived from waiting idle and moving unladen. The stochastic component of the problem arises from projections on the realization of each transportation order, i.e. load. The methodology is based on optimizing decisions for deterministic scenarios. Several policies are generated in this way, from simple heuristics to more complex approaches, such as consensus and restricted expectation algorithms, up to policies derived from network flow models formulated over subtrees of scenarios. Myopic and a-posteriori deterministic optimizations models are used to compute bounds allowing for performance evaluation. Tests are performed on various instances featuring different number of loads, graph sizes, sparsity, and probability distributions. Performances are compared statistically over paired samples. The robustness of various policies with respect to erroneous évaluations of the probability distributions is also analyzed. [less ▲]

Detailed reference viewed: 140 (1 ULg)
Full Text
See detailProceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems
Marchetti-Spaccamela, Alberto; Crama, Yves ULg; Goossens, Dries et al

Book published by KU Leuven (2015)

This volume contains abstracts of talks presented at the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), held from June 8 to June 12, 2015, in La Roche-en-Ardenne ... [more ▼]

This volume contains abstracts of talks presented at the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), held from June 8 to June 12, 2015, in La Roche-en-Ardenne, Belgium. MAPSP is a biennial workshop dedicated to all theoretical and practical aspects of scheduling, planning, and timetabling. The abstracts in this volume include 5 invited talks by Onno Boxma, Michel Goemans, Willem-Jan van Hoeve, Rolf Niedermeier, and Stephan Westphal, plus 88 contributed talks. [less ▲]

Detailed reference viewed: 157 (8 ULg)
See detailFunctions of binary variables
Crama, Yves ULg

Conference (2015, April 29)

Detailed reference viewed: 25 (0 ULg)
Full Text
See detailQuand les maths nous transportent...
Crama, Yves ULg

Conference given outside the academic context (2015)

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter ... [more ▼]

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter deux fois le même pont. Leonhard Euler apporta en 1736 une démonstration élégante de cette affirmation. Il produisit ainsi l’une des premières applications des mathématiques à la construction d’itinéraires optimisés. Aujourd’hui, la modélisation mathématique est devenue un outil indispensable pour les décideurs dans le monde du transport et, plus généralement, pour la gestion et la planification des activités logistiques. Qu’il s’agisse de calculer l’itinéraire le plus rapide de Liège à Marbella, d’optimiser les tournées de livraison d’une chaîne de grande distribution, de charger des navires ou des avions en assurant leur stabilité, de réduire les stocks excédentaires d’une entreprise pharmaceutique, de fixer le prix de billets de TGV en fonction des places disponibles, dans chaque cas, les mathématiques, alliées à l’informatique, permettent de formuler de façon précise le problème rencontré et d’y apporter des réponses pertinentes. Cet exposé présentera quelques applications typiques des mathématiques dans le domaine de la logistique et fournira un aperçu des méthodes qui y sont mises en œuvre. [less ▲]

Detailed reference viewed: 38 (3 ULg)
Full Text
Peer Reviewed
See detailExact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time
Michelini, Stefano ULg; Arda, Yasemin ULg; Crama, Yves ULg et al

Conference (2015, February 05)

We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a ... [more ▼]

We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch-and-Price algorithm considering the pricing subproblem, an elementary shortest path problem with resource constraints (ESPPRC). We discuss research on this exact solution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic. [less ▲]

Detailed reference viewed: 113 (23 ULg)
Full Text
See detailA branch-and-price algorithm for 2-period vehicle routing problems
Crama, Yves ULg; Rezaei Sadrabadi, Mahmood ULg; Van Woensel, Tom

E-print/Working paper (2015)

We consider a Vehicle Routing Problem (VRP) with deterministic orders in two periods from a set of stores. Orders in period 1 (2) can be postponed (advanced) to the other period but any diversion from the ... [more ▼]

We consider a Vehicle Routing Problem (VRP) with deterministic orders in two periods from a set of stores. Orders in period 1 (2) can be postponed (advanced) to the other period but any diversion from the initial orders incurs a penalty. From the perspective of a Logistics Service Provider (LSP), such diversions could be beneficial if savings in the routing costs outweigh the penalties. So could they be from a store's view, as the store can set a high enough penalty to compensate the diversion from its own optimal orders. In this paper, we introduce a new model where we seek a better solution for the LSP, compared to solving two independent VRPs with fixed orders, by allowing orders to be fully postponed or advanced. We apply a branch-and-price algorithm to solve this model to optimality. Many cutting-edge techniques are implemented to have an efficient branch-and-price algorithm, and two ideas to possibly improve the upper bound are tested. We draw algorithmic and managerial insights based on our test instances. [less ▲]

Detailed reference viewed: 145 (8 ULg)
Full Text
See detailQuadratizations of pseudo-Boolean functions
Rodriguez Heck, Elisabeth ULg; Crama, Yves ULg

Scientific conference (2014, December 04)

Detailed reference viewed: 32 (14 ULg)
See detailBoolean Functions for Classification: Logical Analysis of Data
Crama, Yves ULg

Conference (2014, November 20)

Detailed reference viewed: 31 (0 ULg)
Full Text
See detailQuand les maths nous transportent...
Crama, Yves ULg

Conference given outside the academic context (2014)

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter ... [more ▼]

Voici trois siècles, il se racontait dans la ville prussienne de Königsberg qu’un promeneur ne pouvait pas traverser successivement les sept ponts reliant les différentes parties de la cité sans emprunter deux fois le même pont. Leonhard Euler apporta en 1736 une démonstration élégante de cette affirmation. Il produisit ainsi l’une des premières applications des mathématiques à la construction d’itinéraires optimisés. Aujourd’hui, la modélisation mathématique est devenue un outil indispensable pour les décideurs dans le monde du transport et, plus généralement, pour la gestion et la planification des activités logistiques. Qu’il s’agisse de calculer l’itinéraire le plus rapide de Liège à Marbella, d’optimiser les tournées de livraison d’une chaîne de grande distribution, de charger des navires ou des avions en assurant leur stabilité, de réduire les stocks excédentaires d’une entreprise pharmaceutique, de fixer le prix de billets de TGV en fonction des places disponibles, dans chaque cas, les mathématiques, alliées à l’informatique, permettent de formuler de façon précise le problème rencontré et d’y apporter des réponses pertinentes. Cet exposé présentera quelques applications typiques des mathématiques dans le domaine de la logistique et fournira un aperçu des méthodes qui y sont mises en œuvre. [less ▲]

Detailed reference viewed: 69 (3 ULg)
See detailRevealed preference tests of collectively rational consumption behavior
Crama, Yves ULg

Conference (2014, October 28)

To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests that can be applied to real-world data. These tests check whether the observed ... [more ▼]

To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests that can be applied to real-world data. These tests check whether the observed household behavior is "rational", in the sense that it is consistent with the predictions of the model. In this talk, we present different approaches based on revealed preferences to test collective models of household consumption. Testing collective rationality is computationally difficult (NP-hard). In order to overcome this negative result, we introduce mixed-integer programming formulations which can be used for medium-sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model on large data sets. We present the results of computational experiments using our approaches. [less ▲]

Detailed reference viewed: 28 (1 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: 229 (56 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: 72 (28 ULg)
Full Text
Peer Reviewed
See detailSpecific Multi-trip Operators for Vehicle Routing Problems
Arda, Yasemin ULg; Crama, Yves ULg; François, Véronique ULg et al

Conference (2014, July 17)

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 use existing VRP ... [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 use existing VRP heuristics to create trips, together with bin packing methods aimed at assigning these trips to the available vehicles. In this work, specific local search operators for the VRPM are proposed. Heuristics using these operators are compared with classical solution techniques mentioned above. [less ▲]

Detailed reference viewed: 66 (4 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: 257 (14 ULg)