BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Guillaume Sagnol

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.OCmath.COmath.STStatistics TheoryData Structures and AlgorithmsDiscrete MathematicsMethodology

Catalog footprint

Research overview

5works
7topics
2close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

5 publications

preprint2022arXiv

Stochastic Extensible Bin Packing

We consider the stochastic extensible bin packing problem (SEBP) in which nn items of stochastic size are packed into mm bins of unit capacity. In contrast to the classical bin packing problem, the number of bins is fixed and they can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of 22. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of (1+e−1)≈1.368(1+e^{-1}) \approx 1.368. Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for. We also provide a lower bound on the performance of this policy comparing against an optimal fixed assignment policy. Finally, we obtain improved bounds for the case where the processing times are drawn from a particular family of distributions, with either a bounded Pietra index or when the familly is stochastically dominated at the second order.

Open access
preprint2015arXiv

Computing exact DD-optimal designs by mixed integer second-order cone programming

Let the design of an experiment be represented by an ss-dimensional vector w\mathbf {w} of weights with nonnegative components. Let the quality of w\mathbf {w} for the estimation of the parameters of the statistical model be measured by the criterion of DD-optimality, defined as the mmth root of the determinant of the information matrix M(w)=∑i=1swiAiAiTM(\mathbf {w})=\sum_{i=1}^sw_iA_iA_i^T, where Ai,i=1,…,sA_i,i=1,\ldots,s are known matrices with mm rows. In this paper, we show that the criterion of DD-optimality is second-order cone representable. As a result, the method of second-order cone programming can be used to compute an approximate DD-optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an exact DD-optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second-order cone programming problems. Our results extend to the case of the criterion of DKD_K-optimality, which measures the quality of w\mathbf {w} for the estimation of a linear parameter subsystem defined by a full-rank coefficient matrix KK. We prove that some other widely used criteria are also second-order cone representable, for instance, the criteria of AA-, AKA_K-, GG- and II-optimality. We present several numerical examples demonstrating the efficiency and general applicability of the proposed method. We show that in many cases the mixed integer second-order cone programming approach allows us to find a provably optimal exact design, while the standard heuristics systematically miss the optimum.

Open access
preprint2011arXiv

Approximation of a Maximum-Submodular-Coverage problem involving spectral functions, with application to Experimental Design

We study a family of combinatorial optimization problems defined by a parameter p∈[0,1]p\in[0,1], which involves spectral functions applied to positive semidefinite matrices, and has some application in the theory of optimal experimental design. This family of problems tends to a generalization of the classical maximum coverage problem as pp goes to 0, and to a trivial instance of the knapsack problem as pp goes to 1. In this article, we establish a matrix inequality which shows that the objective function is submodular for all p∈[0,1]p\in[0,1], from which it follows that the greedy approach, which has often been used for this problem, always gives a design within 1−1/e1-1/e of the optimum. We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors. We prove an inequality which generalizes a classical result from the theory of optimal designs, and allows us to give a rounding procedure with an approximation factor which tends to 1 as pp goes to 1.

Open access
preprint2010arXiv

A Class of Semidefinite Programs with rank-one solutions

We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite matrix of rank at most rr, where rr is the rank of the matrix involved in the objective function of the SDP. The optimization problems of this class are semidefinite packing problems, which are the SDP analogs to vector packing problems. Of particular interest is the case in which our result guarantees the existence of a solution of rank one: we show that the computation of this solution actually reduces to a Second Order Cone Program (SOCP). We point out an application in statistics, in the optimal design of experiments.

Open access
preprint2010arXiv

Computing Optimal Designs of multiresponse Experiments reduces to Second-Order Cone Programming

Elfving's Theorem is a major result in the theory of optimal experimental design, which gives a geometrical characterization of c−c-optimality. In this paper, we extend this theorem to the case of multiresponse experiments, and we show that when the number of experiments is finite, c−,A−,T−c-,A-,T- and D−D-optimal design of multiresponse experiments can be computed by Second-Order Cone Programming (SOCP). Moreover, our SOCP approach can deal with design problems in which the variable is subject to several linear constraints. We give two proofs of this generalization of Elfving's theorem. One is based on Lagrangian dualization techniques and relies on the fact that the semidefinite programming (SDP) formulation of the multiresponse c−c-optimal design always has a solution which is a matrix of rank 11. Therefore, the complexity of this problem fades. We also investigate a \emph{model robust} generalization of c−c-optimality, for which an Elfving-type theorem was established by Dette (1993). We show with the same Lagrangian approach that these model robust designs can be computed efficiently by minimizing a geometric mean under some norm constraints. Moreover, we show that the optimality conditions of this geometric programming problem yield an extension of Dette's theorem to the case of multiresponse experiments. When the number of unknown parameters is small, or when the number of linear functions of the parameters to be estimated is small, we show by numerical examples that our approach can be between 10 and 1000 times faster than the classic, state-of-the-art algorithms.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.