ORBi Collection: Mathematics
http://hdl.handle.net/2268/153
The Collection's search engineSearch this channelsearch
http://orbi.ulg.ac.be/simple-search
Production Planning in Automated Manufacturing
http://hdl.handle.net/2268/202760
Title: Production Planning in Automated Manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.; Spieksma, Frits C.R.Fri, 21 Oct 2016 08:17:53 GMTThe polytope of block diagonal matrices and complete bipartite partitionings
http://hdl.handle.net/2268/202758
Title: The polytope of block diagonal matrices and complete bipartite partitionings
<br/>
<br/>Author, co-author: Crama, Yves; Oosten, Maarten
<br/>
<br/>Abstract: Motivated by a fundamental clustering problem arising in several areas (production management, marketing, numerical analysis, etc.), we investigate the facial structure of the polytope whose extreme points are all 0–1 block diagonal matrices. For this polytope, general properties of facet-defining inequalities are investigated and specific families of facets are identified. Various techniques for lifting or combining facet-defining inequalities into new ones are also presented. Throughout the paper, a block diagonal matrix is regarded as the adjacency matrix of a disjoint union of complete bipartite graphs. The presentation and the derivation of the results heavily rely on this graph-theoretic interpretation.Fri, 21 Oct 2016 07:51:33 GMTRobust discriminant analysis based on the joint graphcial lasso estimator
http://hdl.handle.net/2268/202654
Title: Robust discriminant analysis based on the joint graphcial lasso estimator
<br/>
<br/>Author, co-author: Aerts, Stéphanie; Croux, Christophe; Wilms, Ines
<br/>
<br/>Abstract: Linear and Quadratic Discriminant Analysis (LDA/QDA) are the most often applied classification rules under the normality assumption. When there is not enough data, the quadratic rule, which requires the estimation of one precision matrix in each class, is often replaced by the linear one, based on the homoscedasticity assumption. This strong assumption is however rarely verified in practice and ignores the intrinsic différences between groups that may be of particular interest in the classification context. In this aper, alternatives to the usual maximum likelihood estimates for the precision matrices are proposed that borrow strength across classes while allowing for heterogeneity at the same time. This results in a classifier that is intermediate between QDA and LDA. Moreover, our estimator is sparse: the undesirable effect of uninformative variables is reduced. The performance of the method is illustrated through simulated and real dataset
examples.Tue, 18 Oct 2016 07:31:16 GMTA full inference toolbox to measure multivariate relative dispersion
http://hdl.handle.net/2268/202653
Title: A full inference toolbox to measure multivariate relative dispersion
<br/>
<br/>Author, co-author: Aerts, Stéphanie; Haesbroeck, Gentiane
<br/>
<br/>Abstract: In the univariate context, coefficients of variation (CV) are widely used to compare the dispersion of a variable in several populations. When the comparison is based on p characteristics however, side-by-side comparison of marginal CV’s may lead to contradictions. In this talk, we present a multivariate coefficient of variation (MCV), defined as the inverse of the Mahalanobis distance between the mean and the origin, whose usefulness is demonstrated in some applications in finance and analytical chemistry. A full inference toolbox is provided for practitioners: several parametric and non-parametric bias-correction methods are suggested and compared, and some exact and approximate confidence intervals are built and analyzed in a simulation study. Finally, in order to meet the practical need to compare MCV’s in K populations, some asymptotic statistical testing procedures are derived, whose finite-sample performance is empirically assessed.
Throughout the talk, the robustness of the techniques will be discussed. As a by-product, a test statistic allowing to reliably compare K univariate CV’s even in presence of outliers will be outlined.Tue, 18 Oct 2016 07:22:07 GMTHitting or avoiding balls in Euclidean space
http://hdl.handle.net/2268/202636
Title: Hitting or avoiding balls in Euclidean space
<br/>
<br/>Author, co-author: Crama, Yves; Ibaraki, Toshihide
<br/>
<br/>Abstract: We investigate the algorithmic complexity of several geometric problems of the following type: given a "feasible" box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. We establish that all these problems are NP-hard in their most general version. We derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, we show that all these problems can be solved in polynomial time when the dimension of the space is fixed.Mon, 17 Oct 2016 14:23:38 GMTVariable and term removal from Boolean formulae
http://hdl.handle.net/2268/202634
Title: Variable and term removal from Boolean formulae
<br/>
<br/>Author, co-author: Crama, Yves; Ekin, Oya; Hammer, Peter L.
<br/>
<br/>Abstract: Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfying some prescribed property. Similar problems can be defined with respect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broad class of DNF properties.Mon, 17 Oct 2016 13:54:35 GMTUne construction des nombres hyperréels
http://hdl.handle.net/2268/202578
Title: Une construction des nombres hyperréels
<br/>
<br/>Author, co-author: Nicolay, Samuel
<br/>
<br/>Abstract: Nous proposons ici une brève construction classique des nombres hyperréels à partir des nombres réels. Dans un soucis de pédagogie, nous omettons les détails les plus techniques. La présentation est divisée en deux parties. La première fait presqu' exclusivement appel à l'intuition, tandis que la seconde reprend les mêmes linéaments mais se veut plus rigoureuse.Fri, 14 Oct 2016 09:18:38 GMTAbelian borders and periodicity
http://hdl.handle.net/2268/202438
Title: Abelian borders and periodicity
<br/>
<br/>Author, co-author: Charlier, EmilieSun, 09 Oct 2016 09:00:51 GMTPseudo-Boolean optimization
http://hdl.handle.net/2268/202427
Title: Pseudo-Boolean optimization
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.
<br/>
<br/>Abstract: This article briefly surveys some fundamental results regarding pseudo-Boolean functions.Fri, 07 Oct 2016 15:47:46 GMTBoolean normal forms, shellability and reliability computations
http://hdl.handle.net/2268/202426
Title: Boolean normal forms, shellability and reliability computations
<br/>
<br/>Author, co-author: Boros, Endre; Crama, Yves; Ekin, Oya; Hammer, Peter L.; Ibaraki, Toshihide; Kogan, Alex
<br/>
<br/>Abstract: Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.Fri, 07 Oct 2016 15:35:41 GMTInference in a stochastic SEIR model using Sequential Monte Carlo methods
http://hdl.handle.net/2268/202086
Title: Inference in a stochastic SEIR model using Sequential Monte Carlo methods
<br/>
<br/>Author, co-author: Bonou, Wilfried; LAMBERT, Philippe
<br/>
<br/>Abstract: Many biological, physical, chemical, economic, and social phenomena are dynamic and are modeled using (systems of) Ordinary Differential Equations (ODEs). But a more realistic way to describe these dynamics relies on Discrete Time Markov Chains (DTMC). There is a growing interest in the development of Bayesian statistical methods to infer on the parameters in such dynamic models, particularly those defining epidemic spread, by combining prior information with experimental or observational data. Our proposal aims to explore the merits of the Bayesian Optimal Filtering technique in the estimation of the parameters of a stochastic SEIR (S = Susceptible, E = Exposed, I = Infectious, R = Removed) epidemic model. State Space Models (SSMs) are used to describe the epidemic dynamic. The unknown static parameters are estimated using a combination of Sequential Monte Carlo techniques with a Markov Chain Monte Carlo algorithm, . . .Wed, 28 Sep 2016 12:28:04 GMTIT formulae for gamma target: mutual information and relative entropy
http://hdl.handle.net/2268/201799
Title: IT formulae for gamma target: mutual information and relative entropy
<br/>
<br/>Author, co-author: Arras, Benjamin; Swan, YvikThu, 15 Sep 2016 08:33:40 GMTCoefficients binomiaux de mots
http://hdl.handle.net/2268/201779
Title: Coefficients binomiaux de mots
<br/>
<br/>Author, co-author: Rigo, Michel
<br/>
<br/>Abstract: Le coefficient binomial (u,v) de deux mots u et v est défini comme le nombre de fois que v
apparaît comme sous-suite du mot u. Par exemple, (abbab,ab)=4. Il étend de manière naturelle le coefficient binomial de deux entiers. Ce concept a été largement étudié depuis plus d'une trentaine d'années (cf. par exemple, Simon et Sakarovitch). Dans cet exposé, je passerai tout d'abord en revue quelques résultats combinatoires classiques pour ensuite m'attarder sur l'équivalence k-binomiale. A l'instar de l'équivalence k-abélienne étudiée par Karhumäki et al., deux mots x et y sont k-binomialement équivalents si leurs coefficients binomiaux (x,v) et (y,v) coïncident pour les mots v de longueur au plus k. En fin d'exposé, j'évoquerai l'extension récente des triangles de Pascal et de Sierpinski à ces coefficients.Wed, 14 Sep 2016 13:20:56 GMTAdvanced graph theory and combinatorics
http://hdl.handle.net/2268/201753
Title: Advanced graph theory and combinatorics
<br/>
<br/>Author, co-author: Rigo, Michel
<br/>
<br/>Abstract: This book focuses on some of the main notions arising in graph theory, with an emphasis throughout on the possible applications of the theory and the fruitful links that exist with linear algebra. Commencing with basic notions such as connectedness, Eulerian, Hamiltonian and planar graphs, opens the way for a variety of applications. A short chapter is devoted to complexity theory, and after a presentation of the chromatic polynomial and Ramsey numbers, the book highlights the important interplay between graph theory and linear algebra. Perron-Frobenius theory is then presented. With rational generating functions and powers of the adjacency matrix, counting walks in a directed multigraph is a recurrent topic of the book and is studied in great detail. Google’s PageRank is then covered in the final chapter of the book.
Every application of the theory is accompanied by fully worked examples and proofs, and supplemented by over 100 exercises throughout the book. This allows the student to gain a full and thorough understanding of advanced graph theory and its potential applications.Tue, 13 Sep 2016 18:22:48 GMTGeneralized Pascal triangle for binomial coefficients of words : an overview
http://hdl.handle.net/2268/201502
Title: Generalized Pascal triangle for binomial coefficients of words : an overview
<br/>
<br/>Author, co-author: Stipulanti, Manon
<br/>
<br/>Abstract: We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. Then we create a new sequence from this extended Pascal triangle that counts, on each row of this triangle, the number of positive binomial coefficients. We study some properties of this sequences. To be precise, we investigate some properties regarding the regularity of the sequence. To extend our work, we construct a Pascal triangle using the Fibonacci representations of all the nonnegative integers and we define the corresponding sequence of which we study the regularity. This regularity is an extension of the classical k-regularity of sequences.
<br/>
<br/>Commentary: Work in collaboration with Julien Leroy (ULg, j.leroy@ulg.ac.be) and Michel Rigo (ULg, m.rigo@ulg.ac.be). // Travail en collaboration avec Julien Leroy (ULg, j.leroy@ulg.ac.be) et Michel Rigo (ULg, m.rigo@ulg.ac.be).Wed, 07 Sep 2016 12:30:05 GMTBalanced words and related concepts: applications and complexity issues
http://hdl.handle.net/2268/201448
Title: Balanced words and related concepts: applications and complexity issues
<br/>
<br/>Author, co-author: Crama, Yves
<br/>
<br/>Abstract: 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).Mon, 05 Sep 2016 16:25:42 GMTDobble, analyse d'un jeu de cartes
http://hdl.handle.net/2268/201176
Title: Dobble, analyse d'un jeu de cartes
<br/>
<br/>Author, co-author: Rigo, MichelThu, 25 Aug 2016 05:02:59 GMTKöppen–Geiger Climate Classification for Europe Recaptured via the Hölder Regularity of Air Temperature Data
http://hdl.handle.net/2268/200984
Title: Köppen–Geiger Climate Classification for Europe Recaptured via the Hölder Regularity of Air Temperature Data
<br/>
<br/>Author, co-author: Deliège, Adrien; Nicolay, Samuel
<br/>
<br/>Abstract: In this paper, we make use of the monoHölder nature of surface air temperature data to recapture the Köppen–Geiger climate classification in Europe. Using data from the European climate Assessment and Dataset (ECA&D), we first show that the Ho ̈lder exponents of surface air temperature data are statistically related to pressure anomalies. Then, we establish a climate classification based on these Hölder exponents in such a way that it allows to recover the Ko ̈ppen–Geiger climate classification. We show that the two classifications match for a vast majority of stations, and we corroborate these observations with a confirmation test. We compare these results with those obtained with another dataset (NCEP-NCAR Reanalysis Project) to show that the new classification is still well-adapted, before eventually discussing these findings.Wed, 17 Aug 2016 12:42:47 GMTQuadratic reformulations of nonlinear binary optimization problems
http://hdl.handle.net/2268/200379
Title: Quadratic reformulations of nonlinear binary optimization problems
<br/>
<br/>Author, co-author: Crama, Yves
<br/>
<br/>Abstract: 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$.Thu, 14 Jul 2016 20:12:36 GMTFeasibility-oriented Branching Strategies for Global Optimization
http://hdl.handle.net/2268/200219
Title: Feasibility-oriented Branching Strategies for Global Optimization
<br/>
<br/>Author, co-author: Gerard, Damien; Köppe, Matthias; Louveaux, Quentin
<br/>
<br/>Abstract: We study the spatial Brand-and-Bound algorithm for the global optimization of nonlinear problems. In particular we are interested in a method to find quickly good feasible solutions. Most spatial Branch-and-Bound-based solvers use a non global solver at a few nodes to try to find better incumbents. We show that it is possible to improve the branching rules and the node priority by exploiting the solutions from the non global solver. We also propose several smart adaptive strategies to choose when to run the non global solver. We show that despite the time spent in solving many more NLP problems in the nodes, the new strategies enable the algorithm to find the first good incumbents faster and to prove the global optimality faster. Numerous easy, medium size as well as hard NLP instances from the Coconut library are benchmarked. All experiments are run using the open source solver Couenne.Mon, 11 Jul 2016 15:22:39 GMT