http://hdl.handle.net/2268/71 Search this channel search http://orbi.ulg.ac.be/simple-search http://hdl.handle.net/2268/147977 Title: Approximation Algorithms for Multi-Dimensional Vector Assignment Problems <br/> <br/>Author, co-author: Dokka, Trivikram; Crama, Yves; Spieksma, Frits C.R. <br/> <br/>Abstract: 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$. Mon, 06 May 2013 20:37:16 GMT http://hdl.handle.net/2268/147868 Title: New issues for the Goodness-of-fit test of the error distribution : a comparison between Sinh-arcsinh and Generalized Hyperbolic distributions <br/> <br/>Author, co-author: Hambuckers, julien; Heuchenne, Cédric <br/> <br/>Abstract: In this article, we consider a multiplicative heteroskedastic structure of financial returns and propose a methodology to study the goodness-of-fit of the error distribution. We use non-conventional estimation and model selection procedures (Berk-Jones (1978) tests, Sarno and Valente (2004) hypothesis testing, Diks et al. (2011) weighting method), based on the local volatility estimator of Mercurio and Spokoiny (2004) and the bootstrap methodology to compare the fit performances of candidate density functions. In particular, we introduce the sinh-arcsinh distributions (Jones and Pewsey, 2009) and we show that this family of density functions provides better bootstrap IMSE and better weighted Kullback-Leibler distances. Fri, 03 May 2013 10:03:02 GMT http://hdl.handle.net/2268/146971 Title: Automatic Aircraft Cargo Load Planning with Pick-up and Delivery <br/> <br/>Author, co-author: Lurkin, Virginie; Schyns, Michael <br/> <br/>Abstract: This research aims to develop a new mixed integer linear program to solve the containers assignment problem when pickup and deliveries are considered. Given a pool of ULDs and an aircraft with multiple destinations, we want to obtain a loading plan determining at which positions the ULDs must be assigned in order to minimize simultaneous the quantity of fuel consumed and the number of re-handles. The loading plan should also ensure a number of structural, safety and manoeuvrability constraints. The model has been tested on real instances and provides encouraging results. Wed, 17 Apr 2013 07:10:04 GMT http://hdl.handle.net/2268/146903 Title: Quadratization of symmetric pseudo-Boolean functions <br/> <br/>Author, co-author: Crama, Yves <br/> <br/>Abstract: 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 Tue, 16 Apr 2013 09:16:50 GMT http://hdl.handle.net/2268/146040 Title: Error distribution estimation in nonparametric regression with right censored selection biased data <br/> <br/>Author, co-author: Laurent, Géraldine; Heuchenne, Cédric <br/> <br/>Abstract: In this presentation, we study the nonparametric regression model Y = m(X) +sigma(X) * epsilon where the error epsilon, with unknown distribution, is independent of the covariate X, and m(X) = E[Y|X] and sigma²(X) =Var[Y|X] are unknown smooth functions. The problem is to estimate the cumulative distribution function of the error in a nonparametric way when the couple (X;Y) is subject to generalized bias selection while the positive response Y can be right-censored. We propose a new estimator for the error distribution function. Asymptotic properties of the proposed estimator are established, namely the rate of convergence and the limiting distribution. A bootstrap procedure is developed to solve the critical problem of the smoothing parameter choice. The performance of the proposed estimator is investigated through simulations. Finally, a data set based on the mortality of diabetics is analyzed. Wed, 03 Apr 2013 08:35:18 GMT http://hdl.handle.net/2268/143896 Title: Objectivation des besoins fonciers et immobiliers des entreprises en Wallonie. Discussion méthodologique <br/> <br/>Author, co-author: Vandermeer, Marie-Caroline Wed, 27 Feb 2013 11:37:02 GMT http://hdl.handle.net/2268/143758 Title: Modal share of intermodal freight transportation in Belgium <br/> <br/>Author, co-author: Mostert, Martine; Limbourg, Sabine <br/> <br/>Commentary: Abstract submitted to the Transport Research Day 2013 conference. Tue, 26 Feb 2013 10:52:31 GMT http://hdl.handle.net/2268/143747 Title: Intermodal network design for freight transportation in Belgium - location of rail/road and road/inland waterway terminals <br/> <br/>Author, co-author: Mostert, Martine; Limbourg, Sabine <br/> <br/>Abstract: In the recent years, growing concerns about environmental, societal and economic issues have emerged in the society. The improvement and the expansion of the multimodal network is one way of solving those kinds of problems. The objective of this work is therefore the integration of inland waterway, rail and road transport into the linear modeling of intermodal terminal location problems, based on transportation costs functions which are nonlinear with the distance traveled. The model should also take into account the capacity constraints linked to the different modes of transport. Tue, 26 Feb 2013 09:04:09 GMT http://hdl.handle.net/2268/143615 Title: Automatic Aircraft Cargo Load Planning with Pick-up and Delivery <br/> <br/>Author, co-author: Lurkin, Virginie; Schyns, Michael <br/> <br/>Abstract: This research aims to develop a new mixed integer linear program to solve the containers assignment problem when pickup and deliveries are considered. Given a pool of ULDs and an aircraft with multiple destinations, we want to obtain a loading plan determining at which positions the ULDs must be assigned in order to minimize simultaneous the quantity of fuel consumed and the number of re-handles. The loading plan should also ensure a number of structural, safety and manoeuvrability constraints. The model has been tested on real instances and provides encouraging results. Fri, 22 Feb 2013 14:50:25 GMT http://hdl.handle.net/2268/143000 Title: Algorithmes d'approximation pour les problèmes d'affectation multidimensionnels <br/> <br/>Author, co-author: Crama, Yves <br/> <br/>Abstract: 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. Sat, 16 Feb 2013 09:36:24 GMT http://hdl.handle.net/2268/142999 Title: Méthodes Booléennes en recherche opérationnelle <br/> <br/>Author, co-author: Crama, Yves <br/> <br/>Abstract: 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. <br/> <br/>Commentary: Session plénière Sat, 16 Feb 2013 09:30:28 GMT http://hdl.handle.net/2268/140359 Title: The evaluation of Fair Trade as a Development Project– Methodological Considerations <br/> <br/>Author, co-author: Paul, Elisabeth <br/> <br/>Abstract: This article identifies the need for an appropriate methodology for evaluating Fair Trade, given that most evaluations to date have been in-house or commissioned reviews and hence have not followed a consistent approach. Focusing on the development aspects of Fair Trade, the article reviews a range of impact evaluation methods and presents a detailed methodology for analyzing Fair Trade. This methodology incorporates standard project evaluation criteria and is based on a wide range of proven methods for collecting and analysing data, principally qualitative but also quantitative. This framework is a modular package from which practitioners may select according to their needs and means, while still retaining an overarching logic. The article illustrates its use by reference to evaluations undertaken in Costa Rica, Ghana, Nicaragua, and Tanzania. The approach allows for a comprehensive understanding of Fair Trade programmes and enables these to be compared with conventional development projects. Wed, 23 Jan 2013 18:16:12 GMT http://hdl.handle.net/2268/138872 Title: Cause-effect relationships and partially defined Boolean functions <br/> <br/>Author, co-author: Crama, Yves; Ibaraki, Toshihide <br/> <br/>Abstract: This paper investigates the use of Boolean techniques in a systematic study of cause-effect relationships. The model uses partially defined Boolean functions. Procedures are provided to extrapolate from limited observations, concise and meaningful theories to explain the effect under study, and to prevent (or provoke) its occurrence Tue, 15 Jan 2013 14:32:36 GMT http://hdl.handle.net/2268/138861 Title: The complexity of scheduling short tasks with few starting times <br/> <br/>Author, co-author: Crama, Yves; Spieksma, Frits C.R. <br/> <br/>Abstract: The following problem is proved to be NP-complete: given n tasks, such that each task has processing time \tau=2, and has no more than k=3 possible starting times, does there exist a feasible schedule for these tasks on a single processor? This result establishes a sharp borderline between NP-complete and polynomially solvable versions of this problem with respect to the parameters \tau and k. Tue, 15 Jan 2013 14:14:02 GMT http://hdl.handle.net/2268/134476 Title: Overview of smallholders’ local rice post-harvest activities in Benin: Gender, practices, commercialization and rice processors livelihoods <br/> <br/>Author, co-author: Zossou, Enangnon; Vodouhe, Davo Simplice; Diagne, Aliou; Lebailly, Philippe <br/> <br/>Abstract: Rice is a primary food source, vital vehicle in dealing with food security and eradicating poverty. In Benin rice is becoming increasingly important and its production and processing tasks are divided on the basis of gender, with women being responsible for much of the drudgery involved in processing. To have an overview of gender and socio-economic dimensions of local rice processing in Benin, a study was conducted in the north and south of Benin with 240 smallholder rice processors randomly selected. In addition to structured interviews and weekly report sheets, the participatory assessment on sustainable livelihood approach was used to appreciate the different states of their financial, social, human, natural and physical capitals assets. Rice processors are mostly women (67% in the whole sample). Men are more representative in white rice processing while women are more representative in parboiled rice processing. Women rice processors have less acces to formal learning source and have bad practices during white rice processing. The traditional rice parboiling methods that don’t lead to good quality rice is prevalence. The main actors of local rice commercialization are the rice producers; the bodies of the Ministry of Agriculture; Famers Organisation and smallholder local rice processors who are generally young women. During local rice commercialization, women are more representative in the sale without contract in the processing village while men are more representative in the sale under a contract. The overall state of capitals is low with better scores in human, physical and natural capitals stocks for men and in social capital for women. Tue, 20 Nov 2012 16:51:58 GMT http://hdl.handle.net/2268/134402 Title: Multi-period vehicle loading with stochastic release dates <br/> <br/>Author, co-author: Arda, Yasemin; Crama, Yves; Kronus, David; Pironet, Thierry; Van Hentenryck, Pascal <br/> <br/>Abstract: 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. Sun, 18 Nov 2012 23:12:52 GMT http://hdl.handle.net/2268/134299 Title: Boolean Methods and Logical Analysis of Data <br/> <br/>Author, co-author: Crama, Yves <br/> <br/>Abstract: 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. Fri, 16 Nov 2012 12:43:02 GMT http://hdl.handle.net/2268/134298 Title: Algorithms for testing the collective consumption model <br/> <br/>Author, co-author: Talla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves; Demuynck, Thomas; De Rock, Bram; Spieksma, Frits <br/> <br/>Abstract: 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. Fri, 16 Nov 2012 12:32:34 GMT http://hdl.handle.net/2268/133740 Title: Estimation under left parametric truncation and right censoring <br/> <br/>Author, co-author: Heuchenne, Cédric; Laurent, Géraldine Fri, 09 Nov 2012 10:57:35 GMT http://hdl.handle.net/2268/133739 Title: Estimation under left parametric truncation and right censoring <br/> <br/>Author, co-author: Heuchenne, Cédric; Laurent, Géraldine Fri, 09 Nov 2012 10:50:49 GMT