References of "Crama, Yves"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailDo balanced words have a short period?
Brauner, Nadia; Crama, Yves ULiege; Delaporte, Etienne et al

in Theoretical Computer Science (in press)

We conjecture that each balanced word on N letters - either arises from a balanced word on two letters by expanding both letters with a congruence word, - or is D-periodic with D <= 2^N-1. Our conjecture ... [more ▼]

We conjecture that each balanced word on N letters - either arises from a balanced word on two letters by expanding both letters with a congruence word, - or is D-periodic with D <= 2^N-1. Our conjecture arises from extensive numerical experiments. It implies, for any fixed N, the finiteness of the number of balanced words on N letters which do not arise from expanding a balanced word on two letters. It refines a theorem of Graham and Hubert, which states that non-periodic balanced words are congruence expansions of balanced words on two letters. It also relates to Fraenkel's conjecture, which states that for N > 2, every balanced word with distinct densities d_1 > d_2 > ... > d_N satisfies d_i = 2^{N-i} / (2^N-1), since this implies that the word is D-periodic with D= 2^N-1. For N < 7, we provide a tentative list of the density vectors of balanced words which do not arise from expanding a balanced word with fewer letters. We prove that the list is complete for N=4 letters. We also prove that deleting a letter in a congruence word always produces a balanced word and this construction allows us to further reduce the list of density vectors that remains unexplained. Moreover, we prove that deleting a letter in an m-balanced word produces an (m+1)-balanced word, thus extending and simplifying a result of Sano et al. (2004). [less ▲]

Detailed reference viewed: 23 (2 ULiège)
Full Text
Peer Reviewed
See detailAdaptive large neighborhood search for multi-trip vehicle routing with time windows
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege

in Transportation Science (in press)

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW), in which each vehicle can perform several trips during its working shift. This problem is especially relevant in the context ... [more ▼]

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW), in which each vehicle can perform several trips during its working shift. This problem is especially relevant in the context of city logistics. Heuristic solution methods for multi-trip vehicle routing problems often separate routing and assignment phases in order to create trips and then assign them to the available vehicles. We show that this approach is outperformed by an integrated solution method in the presence of time windows. We use an automatic configuration tool to obtain efficient and contextualized implementations of our solution methods. We provide suitable instances for the MTVRPTW as well as an instance generator. Also, we discuss the relevance of two objective functions: the total duration and the total travel time. When minimizing the travel time, large increases of waiting time are incurred, which is not realistic in practice. [less ▲]

Detailed reference viewed: 28 (6 ULiège)
Full Text
Peer Reviewed
See detailTenth International Colloquium on Graphs and Optimization (GO X), 2016
Crama, Yves ULiege; Gendron, B.; Ries, B.

in Discrete Applied Mathematics (2019), 261

The Tenth International Colloquium on Graphs and Optimization (GO X) took place from July 10 to July 14, 2016, in Rigi Kaltbad, Switzerland. The meeting featured more than 50 contributed talks and ... [more ▼]

The Tenth International Colloquium on Graphs and Optimization (GO X) took place from July 10 to July 14, 2016, in Rigi Kaltbad, Switzerland. The meeting featured more than 50 contributed talks and attracted some 100 participants from 15 different countries. This special issue of Discrete Applied Mathematics contains 27 papers that have been submitted by participants in the colloquium. [less ▲]

Detailed reference viewed: 22 (2 ULiège)
Full Text
Peer Reviewed
See detailVehicle allocation problem with uncertain transportation requests over a multi-period rolling horizon
Crama, Yves ULiege; Pironet, Thierry ULiege

in Logistics Research (2019), 12(1), 1-22

Abstract This work investigates optimization techniques for a multi-period vehicle allocation problem with uncertain transportation requests revealed sequentially over a rolling horizon. Policies derived ... [more ▼]

Abstract This work investigates optimization techniques for a multi-period vehicle allocation problem with uncertain transportation requests revealed sequentially over a rolling horizon. Policies derived from deterministic scenarios are compared: they are generated either by simple heuristics, or by more complex approaches, such as consensus and restricted expectation algorithms, or by network flow formulations over subtrees of scenarios. Myopic and a posteriori deterministic optimization models are used to compute bounds allowing for performance evaluation and for estimating the value of information. The economic benefit of the stochastic model is highlighted: our results show that the the information about future, uncertain orders contained in the stochastic part of the horizon can be used to generate improved profits. Robustness against misspecified probability distributions is examined. Subtree formulations produce the best results, are robust and can be solved efficiently, which makes them appropriate for industrial implementations. [less ▲]

Detailed reference viewed: 200 (23 ULiège)
Full Text
See detailRecovery management for a dial-a-ride system with real-time disruptions
Paquay, Célia ULiege; Crama, Yves ULiege; Pironet, Thierry ULiege

E-print/Working paper (2019)

The problem considered in this work stems from a non-profit organization in charge of door-to-door passenger transportation for medical appointments. Patients are picked up at home by a driver and are ... [more ▼]

The problem considered in this work stems from a non-profit organization in charge of door-to-door passenger transportation for medical appointments. Patients are picked up at home by a driver and are then dropped at their appointment location. They may also be driven back home at the end of their appointment. Some patients have specific requirements, e.g., they may require an accompanying person or a wheelchair. Planning such activities gives rise to a so-called dial-a-ride problem. In the present work, it is assumed that the requests assigned to the drivers have been selected, and the transportation plan has been established for the next day. However, in practice, appointment durations may vary due to unforeseen circumstances, and some transportation requests may be modified, delayed or canceled during the day. The aim of this work is to propose a reactive algorithm which can adapt the initial plan in order to manage the disruptions and to take care of as many patients as possible in real-time. The plan should be modified quickly when a perturbation is observed, without resorting to major changes which may confuse the drivers and the patients. Several recourse procedures are defined for this purpose. They allow the dispatcher to temporarily delete a request, to insert a previously deleted request, or to permanently cancel a request. Simulation techniques are used to test the approach on randomly generated scenarios. Several key performance indicators are introduced in order to measure the impact of the disruptions and the quality of the solutions. [less ▲]

Detailed reference viewed: 15 (0 ULiège)
Full Text
See detailRecourse in Kidney Exchange Programs
Bartier, Valentin; Smeulders, Bart ULiege; Crama, Yves ULiege et al

E-print/Working paper (2019)

The problem to decide which patient-donor pairs in a kidney exchange program should undergo a cross-match test is modelled as a two-stage stochastic optimization problem. We give an integer programming ... [more ▼]

The problem to decide which patient-donor pairs in a kidney exchange program should undergo a cross-match test is modelled as a two-stage stochastic optimization problem. We give an integer programming formulation of this so-called selection problem, and describe a solution method based on Benders decomposition. We extensively test various solution methods, and observe that the solutions, when compared to solutions found by recourse models, lead to an improvement in the expected number of transplants. We also investigate the computational efficiency of our approach as a function of different parameters, such as maximum cycle length and the presence of altruists. [less ▲]

Detailed reference viewed: 32 (5 ULiège)
Full Text
Peer Reviewed
See detailBerge-acyclic multilinear 0-1 optimization problems
Buchheim, Christoph; Crama, Yves ULiege; Rodriguez Heck, Elisabeth ULiege

in European Journal of Operational Research (2019), 273

The problem of optimizing a multilinear polynomial f in 0–1 variables arises in applications from many different areas. We are interested in resolution methods based on reformulating the polynomial ... [more ▼]

The problem of optimizing a multilinear polynomial f in 0–1 variables arises in applications from many different areas. We are interested in resolution methods based on reformulating the polynomial problem into an equivalent linear one, an approach that attempts to draw benefit from the extensive literature in integer linear programming. More precisely, we characterize instances for which the classical standard linearization procedure guarantees integer optimal solutions. We show that the standard linearization polytope P_H is integer if and only if the hypergraph H defined by the higher-degree monomials of f is Berge-acyclic, or equivalently, when the matrix defining P_H is balanced. This characterization follows from more general conditions that guarantee integral optimal vertices for a relaxed formulation depending on the sign pattern of the monomials of f. [less ▲]

Detailed reference viewed: 64 (13 ULiège)
Full Text
Peer Reviewed
See detailRevealed preference theory: An algorithmic outlook
Smeulders, Bart ULiege; Crama, Yves ULiege; Spieksma, Frits C.R.

in European Journal of Operational Research (2019), 272

Revealed preference theory is a domain within economics that studies rationalizability of behavior by (certain types of) utility functions. Given observed behavior in the form of choice data, testing ... [more ▼]

Revealed preference theory is a domain within economics that studies rationalizability of behavior by (certain types of) utility functions. Given observed behavior in the form of choice data, testing whether certain conditions are satisfied gives rise to a variety of computational problems that can be analyzed using operations research techniques. In this survey, we provide an overview of these problems, their theoretical complexity, and available algorithms for tackling them. We focus on consumer choice settings, in particular individual choice, collective choice and stochastic choice settings. [less ▲]

Detailed reference viewed: 85 (19 ULiège)
Full Text
Peer Reviewed
See detailSeven Surveys in Operations Research
Crama, Yves ULiege; Grabisch, Michel; Martello, Silvano

in Annals of Operations Research (2018), 271(1),

The present issue collects seven surveys that appeared in the triennium 2015–2017 of 4OR: A Quarterly Journal of Operations Research. The authors of the surveys were given the opportunity to correct ... [more ▼]

The present issue collects seven surveys that appeared in the triennium 2015–2017 of 4OR: A Quarterly Journal of Operations Research. The authors of the surveys were given the opportunity to correct, revise, update and sometimes substantially improve their past work. [less ▲]

Detailed reference viewed: 29 (2 ULiège)
See detailLarge neighborhood search approaches for multi-trip vehicle routing with time windows and driver shifts
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege

Conference (2018, July)

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW) and we assume that the working time of each vehicle may not exceed a maximum duration smaller than the planning horizon. We ... [more ▼]

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW) and we assume that the working time of each vehicle may not exceed a maximum duration smaller than the planning horizon. We seek to minimize the total working time, implying that vehicle start times are explicit decision variables. We develop two adaptive large neighborhood search approaches based on different solution representations. The first method treats each vehicle journey as a giant tour that includes trip delimiters. The second one works on separate trips before assigning them to the available vehicles and scheduling them. We configure both methods using an automatic algorithm configuration package and show that the first one is more efficient in the presence of time windows, especially when these are tight. We obtain high quality results on MTVRPTW benchmark instances. We propose a generator to produce instances which characteristics naturally favor the creation of multi-trips. We also show that minimizing the total working time of the vehicles instead of the total distance is suitable in the presence of time windows since accepting a small deterioration in terms of traveled distance has a large positive impact on the working time. This effect increases as the size of time windows decreases. [less ▲]

Detailed reference viewed: 20 (4 ULiège)
See detailReformulations of nonlinear binary optimization problems
Crama, Yves ULiege

Conference (2018, June 16)

Detailed reference viewed: 19 (3 ULiège)
See detailQuadratizations in nonlinear binary optimization: new results
Crama, Yves ULiege

Scientific conference (2018, May 14)

Detailed reference viewed: 18 (2 ULiège)
See detailOptimiser la logistique: Slogan ou réalité?
Crama, Yves ULiege

Conference given outside the academic context (2018)

Detailed reference viewed: 48 (1 ULiège)
See detailAuthor spotlight
Crama, Yves ULiege

Article for general public (2018)

An interview published by INFORMS following the publication of the paper: Y. Crama, M. Rezaei, M. Savelsbergh and T. Van Woensel, Stochastic inventory routing for perishable products, Transportation ... [more ▼]

An interview published by INFORMS following the publication of the paper: Y. Crama, M. Rezaei, M. Savelsbergh and T. Van Woensel, Stochastic inventory routing for perishable products, Transportation Science 52 (2018) 526-546. https://doi.org/10.1287/trsc.2017.0799 and http://hdl.handle.net/2268/213243 [less ▲]

Detailed reference viewed: 12 (2 ULiège)
Full Text
See detailEditorial: Sweet sixteen
Crama, Yves ULiege; Grabisch, Michel; Martello, Silvano

in 4OR: A Quarterly Journal of Operations Research (2018)

This is the traditional triennial note used by the editors to give the readers of 4OR information on the state of the journal and its future. In the 3years that have passed since the last editorial note ... [more ▼]

This is the traditional triennial note used by the editors to give the readers of 4OR information on the state of the journal and its future. In the 3years that have passed since the last editorial note (Liberti et al. in Q J Oper 13:1–13, 2015), three volumes (each containing four issues) of the journal have been published: vol. 13 (2015), vol. 14 (2016), and vol. 15 (2017). [less ▲]

Detailed reference viewed: 18 (4 ULiège)
See detailReformulations of nonlinear binary optimization problems
Crama, Yves ULiege

Scientific conference (2018, March)

Detailed reference viewed: 17 (2 ULiège)
Full Text
See detailCompact quadratizations for pseudo-Boolean functions
Boros, Endre; Crama, Yves ULiege; Rodriguez Heck, Elisabeth ULiege

E-print/Working paper (2018)

The problem of minimizing a pseudo-Boolean function, that is, a real-valued function of 0-1 variables, arises in many applications. A quadratization is a reformulation of this nonlinear problem into a ... [more ▼]

The problem of minimizing a pseudo-Boolean function, that is, a real-valued function of 0-1 variables, arises in many applications. A quadratization is a reformulation of this nonlinear problem into a quadratic one, obtained by introducing a set of auxiliary binary variables. A desirable property for a quadratization is to introduce a small number of auxiliary variables. We present upper and lower bounds on the number of auxiliary variables required to define a quadratization for several classes of specially structured functions, such as functions with many zeros, symmetric, exact k-out-of-n, at least k-out-of-n and parity functions, and monomials with a positive coefficient, also called positive monomials. Most of these bounds are logarithmic in the number of original variables, and we prove that they are best possible for several of the classes under consideration. For positive monomials and for some other symmetric functions, a logarithmic bound represents a significant improvement with respect to the best bounds previously published, which are linear in the number of original variables. Moreover, the case of positive monomials is particularly interesting: indeed, when a pseudo-Boolean function is represented by its unique multilinear polynomial expression, a quadratization can be obtained by separately quadratizing its monomials. [less ▲]

Detailed reference viewed: 117 (9 ULiège)