References of "Crama, Yves"
     in
Bookmark and Share    
See detailQuadratic reformulations of nonlinear binary optimization problems
Crama, Yves ULg

Conference (2014, January 06)

Detailed reference viewed: 21 (2 ULg)
Full Text
Peer Reviewed
See detailMulti-Dimensional Vector Assignment Problems
Dokka, Trivikram; Crama, Yves ULg; Spieksma, Frits C.R.

in Discrete Optimization (2014), 14

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 ... [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 sum of the costs of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed m. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function 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: 24 (6 ULg)
Full Text
See detailQuadratization of symmetric pseudo-Boolean functions
Anthony, Martin; Boros, Endre; Crama, Yves ULg et al

E-print/Working paper (2013)

A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1 ... [more ▼]

A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say that $g(x,y)$ is a quadratization of $f$ if $g(x,y)$ is a quadratic polynomial depending on $x$ and on $m$ auxiliary binary variables $y_1,y_2,\ldots,y_m$ such that $f(x)= \min \{ g(x,y) : y \in \{0,1\}^m \} $ for all $x \in \{0,1\}^n$. By means of quadratizations, minimization of $f$ is reduced to minimization (over its extended set of variables) of the quadratic function $g(x,y)$. This is of some practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper initiated a systematic study of the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function $f$ (a natural question, since the complexity of minimizing the quadratic function $g(x,y)$ depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of \emph{symmetric} pseudo-Boolean functions $f(x)$, those functions whose value depends only on the Hamming weight of the input $x$ (the number of variables equal to 1). [less ▲]

Detailed reference viewed: 63 (4 ULg)
Full Text
See detailRevealed preference tests of collectively rational consumption behavior: formulations and algorithms
Talla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves ULg et al

E-print/Working paper (2013)

This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np ... [more ▼]

This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np}-complete. This makes the application of these tests problematic for (increasingly available) large(r) scale data sets. We then present two approaches to overcome this negative result. First, we introduce exact algorithms based on mixed-integer programming ({\sc mip}) formulations of the collective rationality tests, which can be usefully applied to medium sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model in the case of large data sets. We illustrate our methods by a number of computational experiments based on Dutch labor supply data. [less ▲]

Detailed reference viewed: 59 (7 ULg)
Peer Reviewed
See detailOptimization of Service Start Time for an Elementary Shortest Path Problem
Kucukaydin, Hande ULg; Arda, Yasemin ULg; Crama, Yves ULg

Conference (2013, July 08)

We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers ... [more ▼]

We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers with a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where the delivery and backhaul customers are considered to be two disjoint sets. Split deliveries and pick-ups are not allowed. In this problem, the vehicle may 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. Namely, 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 objective 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 total of the distance and time 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, computational results are presented. [less ▲]

Detailed reference viewed: 70 (12 ULg)
See detailApproximation Algorithms for Multi-Dimensional Vector Assignment Problems
Crama, Yves ULg

Conference (2013, July 04)

Detailed reference viewed: 12 (0 ULg)
Full Text
Peer Reviewed
See detailA global optimization method for naval structure op- timization
Bay, Maud ULg; Crama, Yves ULg; Rigo, Philippe ULg

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: 8 (1 ULg)
See detailQuadratic reformulations of nonlinear binary optimization problems
Crama, Yves ULg

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: 43 (2 ULg)
See detailQuadratization of pseudo-Boolean functions
Crama, Yves ULg

Scientific conference (2013, June 20)

Detailed reference viewed: 11 (0 ULg)
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: 108 (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: 40 (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: 26 (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: 185 (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: 50 (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: 125 (2 ULg)
Full Text
Peer Reviewed
See detailPower indices and the measurement of control in corporate structures
Crama, Yves ULg; Leruth, Luc ULg

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: 96 (3 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: 17 (0 ULg)