References of "Crama, Yves"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailQuadratic reformulations of nonlinear binary optimization problems
Anthony, Martin; Boros, Endre; Crama, Yves ULg et al

in Mathematical Programming (in press)

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these ... [more ▼]

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all ``minimal'' quadratizations of negative monomials. [less ▲]

Detailed reference viewed: 122 (11 ULg)
Full Text
See detailBerge-acyclic multilinear 0-1 optimization problems
Buchheim, Christoph; Crama, Yves ULg; Rodriguez Heck, Elisabeth ULg

E-print/Working paper (2016)

Detailed reference viewed: 12 (3 ULg)
Full Text
Peer Reviewed
See detailLarge neighborhood search for multi-trip vehicle routing
François, Véronique ULg; Arda, Yasemin ULg; Crama, Yves ULg et al

in European Journal of Operational Research (2016), 255(2), 422-441

We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close ... [more ▼]

We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances. [less ▲]

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

in Operations Research (2016), 64(6), 11971216

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: 108 (12 ULg)
Full Text
See detailBalanced words and related concepts: applications and complexity issues
Crama, Yves ULg

Conference (2016, September 05)

In this talk, I present a few results and several questions about "regular" sequences of integers and related concepts, such as balanced words, partitions and covers of the integers by arithmetic ... [more ▼]

In this talk, I present a few results and several questions about "regular" sequences of integers and related concepts, such as balanced words, partitions and covers of the integers by arithmetic sequences. Such concepts have been investigated in pure mathematics, but also naturally arise in a variety of application fields such as production planning, political science, or queueing theory. I briefly present some of these applications and explain how they motivate seemingly new questions relating, for instance, to the algorithmic complexity of regular partitions, or to the structure of balanced words. The presentation is based on joint work with Nadia Brauner and Vincent Jost (Grenoble). [less ▲]

Detailed reference viewed: 17 (3 ULg)
See detailReformulations of nonlinear binary optimization problems
Crama, Yves ULg

Scientific conference (2016, August 17)

Detailed reference viewed: 16 (0 ULg)
See detailNeighborhood search approaches for multi-trip vehicle routing problems
François, Véronique ULg; Arda, Yasemin ULg; Crama, Yves ULg

Conference (2016, July 06)

We introduce two large neighborhood search approaches for solving the multi-trip vehicle routing problem (MTVRP), where each vehicle can perform several routes to serve a set of customers. The problem ... [more ▼]

We introduce two large neighborhood search approaches for solving the multi-trip vehicle routing problem (MTVRP), where each vehicle can perform several routes to serve a set of customers. The problem specifically arises when travel times between customers are short and/or when demands are large. It has been commonly solved in the literature by mixing vehicle routing heuristics and bin packing techniques aimed at assigning routes to vehicles. As an alternative, we propose specific operators that tackle the routing and the assignment aspects of the problem simultaneously. The introduced methods are compared both for the MTVRP and the version with time windows, in which the assignment part of the problem becomes more challenging. In the latter, besides considering a time window at the depot, the working time of each vehicle may not exceed a maximum duration, while its start time is a decision variable. Beyond providing several best known solutions for benchmark instances of the MTVRP, we focus on understanding the behavior of the algorithms. An automatic configuration tool is used, not only to improve the quality of the results, but also as a mean to gain knowledge about algorithm design options and their interactions. We question the impact of several heuristic components and in particular those of the roulette wheel mechanism and of the adaptive memory of routes. [less ▲]

Detailed reference viewed: 22 (6 ULg)
See detailQuadratic reformulations of nonlinear binary optimization problems
Crama, Yves ULg

Conference (2016, July)

A {\em 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 $\mathbf R$. \emph{Nonlinear binary optimization ... [more ▼]

A {\em 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 $\mathbf R$. \emph{Nonlinear binary optimization problems} of the form \begin{equation}\label{eq:PBO} \min \{ f(x) : x \in \{0,1\}^n \}, \end{equation}, where $f$ is a pseudo-Boolean function expressed as a multilinear polynomial in its variables, are notoriously difficult. For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say that $g(x,y)$ is a \emph{quadratization} of $f$ if $g(x,y)$ is a quadratic polynomial depending on $x$ and on $m$ \emph{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 the extended set of variables) of the quadratic function $g(x,y)$. This is of 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. This talk addresses two main types of questions. First, we want to determine the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function~$f$. This question is rather natural since the complexity of minimizing the quadratic function $g(x,y)$ heavily depends (among other factors) on the number of binary variables~$(x,y)$. We establish tight lower and upper bounds on the number of auxiliary variables needed in such a reformulation. Next, we determine more precisely the number of auxiliary variables required by quadratizations of \emph{symmetric} pseudo-Boolean functions $f(x)$, i.e., functions whose value only depends on the number of variables equal to~$1$. [less ▲]

Detailed reference viewed: 15 (1 ULg)
Full Text
See detailA class of valid inequalities for multilinear 0-1 optimization problems
Crama, Yves ULg; Rodriguez Heck, Elisabeth ULg

E-print/Working paper (2016)

This paper investigates the polytope associated with the classical standard linearization technique for the unconstrained optimization of multilinear polynomials in 0-1 variables. A new class of valid ... [more ▼]

This paper investigates the polytope associated with the classical standard linearization technique for the unconstrained optimization of multilinear polynomials in 0-1 variables. A new class of valid inequalities, called 2-links, is introduced to strengthen the LP relaxation of the standard linearization. The addition of the 2-links to the standard linearization inequalities provides a complete description of the convex hull of integer solutions for the case of functions consisting of at most two nonlinear monomials. For the general case, various computational experiments show that the 2- links improve both the standard linearization bound and the computational performance of exact branch & cut methods. The improvements are especially significant for a class of instances inspired from the image restoration problem in computer vision. The magnitude of this effect is rather surprising in that the 2-links are in relatively small number (quadratic in the number of terms of the objective function). [less ▲]

Detailed reference viewed: 98 (16 ULg)
Full Text
See detailTightening linearizations of non-linear binary optimization problems
Rodriguez Heck, Elisabeth ULg; Crama, Yves ULg

Conference (2016, January 28)

Detailed reference viewed: 36 (3 ULg)
Full Text
Peer Reviewed
See detailQuadratization of symmetric pseudo-Boolean functions
Anthony, Martin; Boros, Endre; Crama, Yves ULg et al

in Discrete Applied Mathematics (2016), 203

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: 89 (13 ULg)
Full Text
See detailLarge neighborhood search for multi-trip vehicle routing
François, Véronique ULg; Arda, Yasemin ULg; Crama, Yves ULg et al

E-print/Working paper (2015)

We consider two large neighborhood search approaches for the multi-trip vehicle routing problem, where each vehicle can perform several routes during the working shift to serve a set of customers. The ... [more ▼]

We consider two large neighborhood search approaches for the multi-trip vehicle routing problem, where each vehicle can perform several routes during the working shift to serve a set of customers. The problem specifically arises when customers are close to each other and/or when the demands are large. A common approach in the literature consists in solving this problem by mixing vehicle routing heuristics with bin packing routines to assign routes to vehicles. We compare this approach with the use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. We provide several best known solutions for benchmark instances. At the end of the work, we give insights about the proposed algorithm configurations by analyzing the behavior of several method components. [less ▲]

Detailed reference viewed: 140 (18 ULg)
See detailRevealed preference tests of collectively rational consumption behavior
Crama, Yves ULg

Scientific conference (2015, October 29)

To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests did can be applied to real-world data. These tests check whether the observed ... [more ▼]

To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests did can be applied to real-world data. These tests check whether the observed household behavior is "rational" in the sense that it is consistent with the predictions of the model. In this talk, we present different approaches based on revealed preferences to test collective models of household consumption. Testing collective rationality is computationally difficult (NP-hard). In order to overcome this negative result, we introduce mixed-integer programming formulations which can be used for medium-sized datasets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model on large datasets. We present the results of computational experiments with our approaches. Joint work with: Fabrice Talla Nobibon, Laurens Cherchye, Thomas Demuynck, Bram De Rock and Frits CR Spieksma. [less ▲]

Detailed reference viewed: 32 (0 ULg)
Full Text
See detailMulti-period vehicle allocation with uncertain transportation requests
Crama, Yves ULg; Pironet, Thierry ULg

E-print/Working paper (2015)

This work investigates optimization techniques for a multi-period vehicle allocation problem with uncertain requests. A company owning a limited fleet of trucks attempts to maximize its operational profit ... [more ▼]

This work investigates optimization techniques for a multi-period vehicle allocation problem with uncertain requests. A company owning a limited fleet of trucks attempts to maximize its operational profit over an infinite horizon by optimally assigning transportation orders to the vehicles. Its profit stems from profits collected when transporting full truckloads, minus costs incurred when waiting or when moving unladen. The stochastic component of the problem arises from the uncertainty on the realization of each transportation order. The methodology is based on optimizing decisions for deterministic scenarios. Several policies are generated in this way, either by simple heuristics, or by more complex approaches, such as consensus and restricted expectation algorithms, or from network flow formulations over subtrees of scenarios. Myopic and a-posteriori deterministic optimization models are used to compute bounds allowing for performance evaluation. Numerical experiments are performed on various instances featuring different numbers of orders, graph sizes, sparsity, and probability distributions, and the performance of the algorithms is assessed by statistical tests. The robustness of various policies with respect to erroneous evaluations of the probability distributions is also analyzed. [less ▲]

Detailed reference viewed: 177 (15 ULg)
See detailQuadratizations of pseudo-Boolean functions
Crama, Yves ULg

Conference (2015, October 23)

A pseudo-Boolean function is a real-valued function of 0-1 variables. Every pseudo-Boolean function can be represented by various analytical expressions, e.g., as a polynomial in its variables, or as a ... [more ▼]

A pseudo-Boolean function is a real-valued function of 0-1 variables. Every pseudo-Boolean function can be represented by various analytical expressions, e.g., as a polynomial in its variables, or as a polynomial in its variables and in their Boolean complements, or as a disjunctive form, or as pointwise minimum of a family of affine functions, and so forth. Motivated by the problem of minimizing pseudo-Boolean functions, we consider yet another class of representations. Namely, we say that g(x,y) is a quadratization of the pseudo-Boolean function f(x) if g(x,y) is a quadratic pseudo-Boolean function of x and of m auxiliary binary variables y such that, for all x, f(x) = min g(x,y), where the minimum is taken over all possible values of the y-variables. It can be shown that every pseudo-Boolean function has at least one, and usually, many quadratizations. In recent years, several authors have proposed to reduce the problem of minimizing an arbitrary function f(x) (say, expressed as a high-degree polynomial) to the (presumably easier) problem of minimizing one of its quadratizations. In this talk, we discuss the size of ``small'' quadratizations, that is, the number of auxiliary variables required in any quadratization. We provide lower and upper bounds on the number of auxiliary variables for the case of an arbitrary function f(x), as well as for the special case where f(x) is a symmetric function of its variables. [less ▲]

Detailed reference viewed: 35 (3 ULg)
Peer Reviewed
See detailBranch-and-Price Based Matheuristics for a Vehicle Routing Problem with Time Windows and Variable Service Start Time
Küçükaydın, Hande; Arda, Yasemin ULg; Crama, Yves ULg et al

Conference (2015, July 15)

We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In ... [more ▼]

We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In order to solve the problem to optimality, a branch-and-price (BP) algorithm is implemented recognizing the pertinent pricing subproblem as an elementary shortest path problem with resource constraints (ESPPRC) which can handle an infinite number of labels and employs effective dominance rules. We present the past, present, and future implementations of the BP procedure based on bounded bi-directional search, decremental state space relaxation, and ng-route relaxation. We further discuss the design of BP-based matheuristics which make use of metaheuristics in pricing subproblem resolution, upper bound improvement, and column generation. [less ▲]

Detailed reference viewed: 90 (4 ULg)
See detailQuadratization of pseudo-Boolean functions
Crama, Yves ULg; Anthony, Martin; Boros, Endre et al

Conference (2015, July)

Detailed reference viewed: 27 (1 ULg)