Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Approximation Algorithms for Multi-Dimensional Vector Assignment Problems Crama, Yves Conference (2013, July 04) Detailed reference viewed: 14 (0 ULg)A global optimization method for naval structure op- timization Bay, Maud ; Crama, Yves ; Rigo, Philippe Conference (2013, July 01) The paper proposes a global optimization method for the preliminary structural design of large vessels in shipbuilding industry. We face a combinatorial problem of large size, with constraints modeled as ... [more ▼] The paper proposes a global optimization method for the preliminary structural design of large vessels in shipbuilding industry. We face a combinatorial problem of large size, with constraints modeled as implicit functions with nonlinear behavior. We present a heuristic method that performs a global search over the feasible solution space, combining a large neighborhood search and a heuristic local search. Experiments on actual structural optimization problems show that the heuristic converges towards discrete feasible solutions of good quality. [less ▲] Detailed reference viewed: 21 (1 ULg)Quadratic reformulations of nonlinear binary optimization problems Crama, Yves 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: 85 (2 ULg)Quadratization of pseudo-Boolean functions Crama, Yves Scientific conference (2013, June 20) Detailed reference viewed: 11 (0 ULg)Approximation Algorithms for Multi-Dimensional Vector Assignment Problems ; Crama, Yves ; 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: 135 (11 ULg)An elementary shortest path problem with variable service start time Kucukaydin, Hande ; Arda, Yasemin ; Crama, Yves 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: 58 (1 ULg)Quadratization of symmetric pseudo-Boolean functions Crama, Yves 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: 31 (0 ULg)An adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shifts Arda, Yasemin ; Crama, Yves ; François, Véronique 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: 202 (8 ULg)Elementary shortest path problems for a multiple-trip vehicle routing problem Arda, Yasemin ; Crama, Yves ; Kucukaydin, Hande Conference (2013, February 08) Detailed reference viewed: 12 (0 ULg)An adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shifts Arda, Yasemin ; Crama, Yves ; François, Véronique Conference (2013, February 07) Detailed reference viewed: 59 (9 ULg)Méthodes Booléennes en recherche opérationnelle Crama, Yves 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: 62 (1 ULg)Algorithmes d'approximation pour les problèmes d'affectation multidimensionnels Crama, Yves 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: 137 (2 ULg)Power indices and the measurement of control in corporate structures Crama, Yves ; Leruth, Luc in International Game Theory Review (2013), 15 This paper proposes a brief review of the use of power indices in the corporate governance literature. Without losing sight of the field of application, it places the emphasis on the game-theoretic ... [more ▼] This paper proposes a brief review of the use of power indices in the corporate governance literature. Without losing sight of the field of application, it places the emphasis on the game-theoretic aspects of this research and on the issues that arise in this framework. [less ▲] Detailed reference viewed: 114 (4 ULg)Algorithms for testing the collective consumption model ; ; Crama, Yves 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: 19 (0 ULg)Boolean Methods and Logical Analysis of Data Crama, Yves 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: 35 (0 ULg)Multiperiod vehicle loading with stochastic release dates Arda, Yasemin ; Crama, Yves ; Kronus, David 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: 12 (4 ULg)A Rich Vehicle Routing Problem with Multiple Trips and Driver Shifts Arda, Yasemin ; Crama, Yves ; Kucukaydin, Hande 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: 227 (6 ULg)Boolean methods in operations research and related areas Crama, Yves 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: 109 (2 ULg)Control and Voting Power in Complex Shareholding Networks Crama, Yves ; Leruth, Luc ; Conference (2011, June) Detailed reference viewed: 53 (3 ULg)Multiperiod vehicle loading optimization with stochastic supply Amand, Guillaume ; Arda, Yasemin ; Crama, Yves et al Scientific conference (2011, April 07) Detailed reference viewed: 24 (6 ULg) |
||