References of "Crama, Yves"
     in
Bookmark and Share    
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: 98 (10 ULg)
Peer Reviewed
See detailAn elementary shortest path problem with variable service start time
Kucukaydin, Hande ULg; Arda, Yasemin ULg; Crama, Yves ULg

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: 15 (1 ULg)
Full Text
See detailQuadratization of symmetric pseudo-Boolean functions
Crama, Yves ULg

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: 22 (0 ULg)
Full Text
See detailAn adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shifts
Arda, Yasemin ULg; Crama, Yves ULg; François, Véronique ULg

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: 179 (8 ULg)
See detailMéthodes Booléennes en recherche opérationnelle
Crama, Yves ULg

Conference (2013, February)

Le titre de cette conférence est celui d'une monographie cosignée par Peter L. Hammer et Sergiu Rudeanu, et dont la publication en 1968 a inspiré un nombre important de travaux de recherche. Très ... [more ▼]

Le titre de cette conférence est celui d'une monographie cosignée par Peter L. Hammer et Sergiu Rudeanu, et dont la publication en 1968 a inspiré un nombre important de travaux de recherche. Très récemment, le regretté Peter Hammer et moi-même avons publié deux lointaines mises à jour de cet ouvrage classique: une monographie intitulée Boolean Functions: Theory, Algorithms, and Applications (700 pages, Cambridge University Press, 2011) et une collection de surveys sur le thème Boolean Models and Methods in Mathematics, Computer Science and Engineering (780 pages, Cambridge University Press, 2010). La taille de ces deux volumes et de leurs sections bibliographiques sont les témoins de la vitalité de ce domaine de recherche et de son développement impressionnant. Les fonctions booléennes comptent en effet parmi les objets les plus fondamentaux étudiés en mathématiques. Elles interviennent dans de nombreux modèles utilisés en recherche opérationnelle, informatique, intelligence artificielle, économie, ingénierie, cryptographie, biologie et autres domaines d'application. Dans cet exposé, nous proposons un bref aperçu de quelques modèles booléens fondamentaux et de leurs applications. [less ▲]

Detailed reference viewed: 37 (0 ULg)
See detailAlgorithmes d'approximation pour les problèmes d'affectation multidimensionnels
Crama, Yves ULg

Scientific conference (2013, January)

Le problème d'affectation multidimensionnel (PAM) consiste à partitionner les sommets d'un graphe m-parti en m-cliques disjointes de façon à minimiser la somme des coûts des cliques utilisées, où le coût ... [more ▼]

Le problème d'affectation multidimensionnel (PAM) consiste à partitionner les sommets d'un graphe m-parti en m-cliques disjointes de façon à minimiser la somme des coûts des cliques utilisées, où le coût des cliques peut être défini de différentes façons. PAM généralise le problème d'affectation ou de couplage biparti classique qui correspond au cas m=2. Nous présentons plusieurs résultats, anciens et nouveaux, relatifs à des cas particuliers de PAM obtenus en spécifiant les propriétés du coût des cliques. Pour ces cas particuliers, nous décrivons des algorithmes d'approximation, nous examinons leurs garanties de performance, et nous mentionnons quelques questions ouvertes. [less ▲]

Detailed reference viewed: 109 (2 ULg)
See detailAlgorithms for testing the collective consumption model
Talla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves ULg et al

Conference (2012, November 09)

In this talk, we discuss an extension of the strong axiom of revealed preferences to collective households. The question that we address is whether a set of observed consumption baskets can be decomposed ... [more ▼]

In this talk, we discuss an extension of the strong axiom of revealed preferences to collective households. The question that we address is whether a set of observed consumption baskets can be decomposed in such a way that each of the derived data sets reflects the choices of a “rational” (i.e., utility-maximizing) individual member of the household. Although testing revealed preference axioms on data generated by a single decisionmaker can be done in polynomial time, the extension to two-member households is NP-complete. We propose two algorithms for testing the collective consumption model on large data sets. The first one is an exact algorithm based on a new mixed-integer programming formulation, whereas the second one is a heuristic based on a simulated annealing procedure that solves a global optimization formulation of the problem. Computational experiments are performed on real-life data. [less ▲]

Detailed reference viewed: 16 (0 ULg)
See detailBoolean Methods and Logical Analysis of Data
Crama, Yves ULg

Conference (2012, June 09)

About 20 years ago, we proposed an innovative approach to data mining based on a blend of Boolean techniques and combinatorial optimization. The basic tenets of this approach were presented in a joint ... [more ▼]

About 20 years ago, we proposed an innovative approach to data mining based on a blend of Boolean techniques and combinatorial optimization. The basic tenets of this approach were presented in a joint paper co-authored with Toshihide Ibaraki and myself. It was subsequently developed by Peter Hammer and his coworkers into a new broad area of research, dubbed Logical Analysis of Data, or LAD for short. The effectiveness of the LAD methodology has been validated by many successful applications to real-life data analysis problems. In a first part of this lecture, I will propose a brief overview of some fundamental Boolean models and of illustrative applications arising in computer science, in optimization and in game theory. I will next turn to a presentation of the basic principles of LAD and of some of the theoretical questions that have been investigated in connection with this methodology. This part of the lecture should allow the audience to place the development of LAD in a historical perspective. [less ▲]

Detailed reference viewed: 26 (0 ULg)
Full Text
Peer Reviewed
See detailMultiperiod vehicle loading with stochastic release dates
Arda, Yasemin ULg; Crama, Yves ULg; Kronus, David ULg et al

Conference (2012, May 24)

Production scheduling and vehicle routing problems are well-known topics in operations management. Although these tasks are consecutive in the supply chain, few optimization models tackle the associated ... [more ▼]

Production scheduling and vehicle routing problems are well-known topics in operations management. Although these tasks are consecutive in the supply chain, few optimization models tackle the associated issues. A most common situation, in practice, is actually that transportation management is disconnected from production planning: when production items or batches have been completely processed by the manufacturing plant, they become available for shipping, and they are consequently handled by the transportation managers. From a global managerial perspective, and with a view towards coordination of the product flows and customer satisfaction, this is not an ideal process. It is by far preferable, indeed, to set up an integrated production-transportation plan taking into account, among other constraints, the capacity of the plants and the customer due-dates. The present research proposes a methodology to investigate a multi-period vehicle loading problem with deterministic or stochastic information concerning items arrivals from production. Results from related optimization techniques are statistically compared and the benefits of the multi-period and stochastic modeling is demonstrated. Finally, an efficient heuristic is highlighted and is shown to be robust to the deviation from item arrival forecasts. [less ▲]

Detailed reference viewed: 8 (3 ULg)
Full Text
Peer Reviewed
See detailA Rich Vehicle Routing Problem with Multiple Trips and Driver Shifts
Arda, Yasemin ULg; Crama, Yves ULg; Kucukaydin, Hande ULg et al

Conference (2012)

This study is concerned with a rich vehicle routing problem (RVRP) encountered at a Belgian transportation company in charge of servicing supermarkets and hypermarkets belonging to a franchise. The ... [more ▼]

This study is concerned with a rich vehicle routing problem (RVRP) encountered at a Belgian transportation company in charge of servicing supermarkets and hypermarkets belonging to a franchise. The studied problem can be classified as a one-to-many-to-one pick-up and delivery problem, where there is a single depot from which all delivery customers are served and to which every pick-up demand must be carried back (Gutiérrez-Jarpa et al., 2010). The delivery and backhaul customers are considered to be two disjoint sets, where on a given route backhaul customers can be visited only after all delivery customers are served. Split deliveries and pick-ups are not allowed. The service at a customer must start within the given time window of the customer. However, it is not possible to serve a customer with every available vehicle, since the vehicles at the company’s disposal are of different types according to which the capacity changes. Therefore, our problem can be classified also as a heterogeneous fleet vehicle routing problem with customer-vehicle incompatibilities (Ceselli et al., 2009). The problem at hand requires that the same vehicle may be assigned to several routes, which leads to a multiple-trip RVRP. Furthermore, driver shifts are taken into account so that each vehicle of the fleet starts servicing the customers when the shift of the assigned driver starts. The shift duration is the same for all drivers. If the service of the vehicle exceeds SH, an overtime cost incurs to the transportation company. In such a case, a vehicle can be used during at most a fixed length of time. In addition to the vehicles of the company’s own fleet (i.e. internal vehicles), there is a possibility to request external vehicles for servicing some customers. External vehicles can be used for a fixed maximum amount of time and can start servicing customers at any desired time. A fixed reservation cost and distance and time based variable costs are incurred in the case of an external vehicle, while only distance based variable costs are incurred in the case of an internal vehicle. We employ a binary integer linear programming formulation in order to model our problem. The first constraint set ensures that each customer is visited at least once by either an internal or external vehicle. With the second constraint set, it is guaranteed that each internal vehicle is assigned to at most one tour. The last two constraint sets are the binary restrictions on the assignment variables. In order to solve the problem, we first relax the binary restrictions on the assignment variables and develop a column generation procedure, where we obtain two pricing problems, one for internal vehicles and the other one for external vehicles. The pricing problem of each internal vehicle can be formulated as an elementary shortest path problem with resource constraints, which can be solved using a dynamic programming algorithm based on a bounded bi-directional search (Righini and Salani, 2008). However, since an external vehicle can start the service at any point in time and is paid based on its total travel time, the second pricing algorithm has to take into account an infinite number of Pareto-optimal states (Liberatore et al., 2011). We discuss the efficient solution of the pricing subproblems and present preliminary computational results. [less ▲]

Detailed reference viewed: 186 (5 ULg)
Full Text
See detailBoolean methods in operations research and related areas
Crama, Yves ULg

Conference (2011, November)

These are the slides of the "IFORS Distinguished Lecture" that I delivered at the INFORMS Annual meeting in November 2011. The title of the lecture is the title of a monograph co-authored by Peter L ... [more ▼]

These are the slides of the "IFORS Distinguished Lecture" that I delivered at the INFORMS Annual meeting in November 2011. The title of the lecture is the title of a monograph co-authored by Peter L. Hammer and Sergiu Rudeanu, which appeared in 1968. Their pioneering work has stimulated a large amount of research and has been very frequently cited. Over the last year, the late Peter Hammer and myself have published two distant follow-ups to this classical book: a monograph entitled Boolean Functions: Theory, Algorithms, and Applications (700 pages, Cambridge University Press, 2011), and a collection of survey papers on Boolean Models and Methods in Mathematics, Computer Science and Engineering (780 pages, Cambridge University Press, 2010). The size of these two volumes and of their bibliographic sections are witnesses of the vitality of the field and of its impressive development. Boolean functions are actually among the most fundamental objects investigated in mathematics, and provide the basic building blocks for many models arising in operations research, computer science, artificial intelligence, economics, engineering, cryptography, biology, and other fields of application. In this lecture, I propose a brief overview of some fundamental Boolean models, I discuss applications in corporate governance (modeling of shareholders’ power) and in classification (Logical Analysis of Data), and I mention a few challenging research problems. [less ▲]

Detailed reference viewed: 62 (2 ULg)
Full Text
See detailPower indices and the measurement of control in corporate structures
Crama, Yves ULg; Leruth, Luc ULg

E-print/Working paper (2011)

This paper proposes a review of the use of power indices in the corporate governance literature. It places the emphasis on the game-theoretic aspects of this research, but it also addresses some of the ... [more ▼]

This paper proposes a review of the use of power indices in the corporate governance literature. It places the emphasis on the game-theoretic aspects of this research, but it also addresses some of the key issues linked to the specific field of application. [less ▲]

Detailed reference viewed: 91 (1 ULg)
See detailControl and Voting Power in Complex Shareholding Networks
Crama, Yves ULg; Leruth, Luc ULg; Su Wang

Conference (2011, June)

Detailed reference viewed: 34 (3 ULg)
Full Text
See detailMultiperiod vehicle loading optimization with stochastic supply
Amand, Guillaume ULg; Arda, Yasemin ULg; Crama, Yves ULg et al

Scientific conference (2011, April 07)

Detailed reference viewed: 16 (6 ULg)
Full Text
See detailThe Mathematics of Peter L. Hammer (1936-2006): Graphs, Optimization, and Boolean Models
Boros, Endre; Crama, Yves ULg; De Werra, Dominique et al

in Boros, Endre; Crama, Yves; De Werra, Dominique (Eds.) et al The Mathematics of Peter L. Hammer (1936-2006): Graphs, Optimization, and Boolean Models (2011)

This volume of the Annals of Operations Research, contains a collection of papers published in memory of Peter L. Hammer. As we recall further down, Peter made substantial contributions to several areas ... [more ▼]

This volume of the Annals of Operations Research, contains a collection of papers published in memory of Peter L. Hammer. As we recall further down, Peter made substantial contributions to several areas of operations research and discretemathematics, including, in particular, mathematical programming (linear and quadratic 0–1 programming, pseudo-Boolean optimization, knapsack problems, etc.), combinatorial optimization (transportation problems, network flows, MAXSAT, simple plant location, etc.), graph theory (special classes of graphs, stability problems, and their applications), data mining and classification (Logical Analysis of Data), and, last but not least, Boolean theory (satisfiability, duality, Horn functions, threshold functions, and their applications). [less ▲]

Detailed reference viewed: 25 (1 ULg)
Full Text
Peer Reviewed
See detailThe Mathematics of Peter L. Hammer (1936-2006): Graphs, Optimization, and Boolean Models
Boros, Endre; Crama, Yves ULg; de Werra, Dominique et al

in Annals of Operations Research (2011), 188

This volume contains a collection of papers published in memory of Peter L. Hammer (1936-2006). Peter Hammer made substantial contributions to several areas of operations research and discrete mathematics ... [more ▼]

This volume contains a collection of papers published in memory of Peter L. Hammer (1936-2006). Peter Hammer made substantial contributions to several areas of operations research and discrete mathematics, including, in particular, mathematical programming (linear and quadratic 0--1 programming, pseudo-Boolean optimization, knapsack problems, etc.), combinatorial optimization (transportation problems, network flows, MAXSAT, simple plant location, etc.), graph theory (special classes of graphs, stability problems, and their applications), data mining and classification (Logical Analysis of Data), and, last but not least, Boolean theory (satisfiability, duality, Horn functions, threshold functions, and their applications). The volume contains 23 contributed papers along these lines. [less ▲]

Detailed reference viewed: 52 (9 ULg)
Full Text
Peer Reviewed
See detailLogical Analysis of Data: Classification with justification
Boros, Endre; Crama, Yves ULg; Hammer, Peter L. et al

in Annals of Operations Research (2011), 188

Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of ... [more ▼]

Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of such algorithms is frequently carried out ex post, on an experimental basis: their performance is measured either by cross validation on benchmark data sets, or by clinical trials. Few of these approaches evaluate the learning process ex ante, on its own merits. In this paper, we dis- cuss a property of rule-based classifiers which we call "justifiability", and which focuses on the type of information extracted from the given training set in order to classify new observations. We investigate some interesting mathematical properties of justifiable classifiers. In partic- ular, we establish the existence of justifiable classifiers, and we show that several well-known learning approaches, such as decision trees or nearest neighbor based methods, automatically provide justifiable clas- sifiers. We also identify maximal subsets of observations which must be classified in the same way by every justifiable classifier. Finally, we illustrate by a numerical example that using classifiers based on "most justifiable" rules does not seem to lead to over fitting, even though it involves an element of optimization. [less ▲]

Detailed reference viewed: 48 (5 ULg)
Full Text
See detailBoolean Functions: Theory, Algorithms, and Applications
Crama, Yves ULg; Hammer, Peter L.

Book published by Cambridge University Press (2011)

This monograph provides the first comprehensive presentation of the theoretical, algorithmic and applied aspects of Boolean functions, i.e., {0,1}-valued functions of a finite number of {0,1}-valued ... [more ▼]

This monograph provides the first comprehensive presentation of the theoretical, algorithmic and applied aspects of Boolean functions, i.e., {0,1}-valued functions of a finite number of {0,1}-valued variables. The book focuses on algebraic representations of Boolean functions, especially normal form representations. It presents the fundamental elements of the theory (Boolean equations and satisfiability problems, prime implicants and associated representations, dualization, etc.), an in-depth study of special classes of Boolean functions (quadratic, Horn, shellable, regular, threshold, read-once, etc.), and two fruitful generalizations of the concept of Boolean functions (partially defined and pseudo-Boolean functions). It features a rich bibliography of about one thousand items. Prominent among the disciplines in which Boolean methods play a significant role are propositional logic, combinatorics, graph and hypergraph theory, complexity theory, integer programming, combinatorial optimization, game theory, reliability theory, electrical and computer engineering, artificial intelligence, etc. The book contains applications of Boolean functions in all these areas. [less ▲]

Detailed reference viewed: 454 (11 ULg)