Search

The problems of Lasso regression and optimal design of experiments share a critical property: their optimal solutions are typically \emph{sparse}, i.e., only a small fraction of the optimal variables are non-zero. Therefore, the identification of the support of an optimal solution reduces the dimensionality of the problem and can yield a substantial simplification of the calculations. It has recently been shown that linear regression with a \emph{squared} $\ell_1$-norm sparsity-inducing penalty is equivalent to an optimal experimental design problem. In this work, we use this equivalence to derive safe screening rules that can be used to discard inessential samples. Compared to previously existing rules, the new tests are much faster to compute, especially for problems involving a parameter space of high dimension, and can be used dynamically within any iterative solver, with negligible computational overhead. Moreover, we show how an existing homotopy algorithm to compute the regularization path of the lasso method can be reparametrized with respect to the squared $\ell_1$-penalty. This allows the computation of a Bayes $c$-optimal design in a finite number of steps and can be several orders of magnitude faster than standard first-order algorithms. The efficiency of the new screening rules and of the homotopy algorithm are demonstrated on different examples based on real data.

We study the elective surgery planning problem in a hospital with operation rooms shared by elective and emergency patients. This problem can be split in two distinct phases. First, a subset of patients to be operated in the next planning period has to be selected, and the selected patients have to be assigned to a block and a tentative starting time. Then, in the online phase of the problem, a policy decides how to insert the emergency patients in the schedule and may cancel planned surgeries. The overall goal is to minimize the expectation of a cost function representing the assignment of patient to blocks, case cancellations, overtime, waiting time and idle time. We model the offline problem by a two-stage stochastic program, and show that the second-stage costs can be replaced by a convex piecewise linear surrogate model that can be computed in a preprocessing step. This results in a mixed integer program which can be solved in a short amount of time, even for very large instances of the problem. We also describe a greedy policy for the online phase of the problem, and analyze the performance of our approach by comparing it to either heuristic methods or approaches relying on sampling average approximation (SAA) on a large set of benchmarking instances. Our simulations indicate that our approach can reduce the expected costs by as much as 30% compared to heuristic methods and is able to solve problems with $1000$ patients in about one minute, while SAA-approaches fail to obtain near-optimal solutions within 30 minutes, already for $100$ patients.

We study the Min-Weighted Sum Bin Packing problem, a variant of the classical Bin Packing problem in which items have a weight, and each item induces a cost equal to its weight multiplied by the index of the bin in which it is packed. This is in fact equivalent to a batch scheduling problem that arises in many fields of applications such as appointment scheduling or warehouse logistics. We give improved lower and upper bounds on the approximation ratio of two simple algorithms for this problem. In particular, we show that the knapsack-batching algorithm, which iteratively solves knapsack problems over the set of remaining items to pack the maximal weight in the current bin, has an approximation ratio of at most 17/10.

We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of~$3$ for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any $b > 1$ a tight analysis for the natural $b$-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of $(1+3\sqrt{3})\approx 6.197$ for the deterministic and of $\approx 3.032$ for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is $2$-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than $10$ for adaptions of the $b$-scaling strategy to online release dates and unweighted jobs on identical parallel machines., Comment: An extended abstract occurred in the Proceedings of the 24th International Conference on Integer Programming and Combinatorial Optimization

We consider the stochastic scheduling problem of minimizing the expected makespan on $m$ parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of $2$, any (non-adaptive) fixed assignment policy has performance guarantee $\Omega\left(\frac{\log m}{\log \log m}\right)$. Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of $\delta$-delay and $\tau$-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an $\mathcal{O}(\log \log m)$-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any $\delta$-delay and $\tau$-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.

We consider the stochastic extensible bin packing problem (SEBP) in which $n$ items of stochastic size are packed into $m$ 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 $2$. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of $(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.

We show that the $A$-optimal design optimization problem over $m$ design points in $\mathbb{R}^n$ is equivalent to minimizing a quadratic function plus a group lasso sparsity inducing term over $n\times m$ real matrices. This observation allows to describe several new algorithms for $A$-optimal design based on splitting and block coordinate decomposition. These techniques are well known and proved powerful to treat large scale problems in machine learning and signal processing communities. The proposed algorithms come with rigorous convergence guaranties and convergence rate estimate stemming from the optimization literature. Performances are illustrated on synthetic benchmarks and compared to existing methods for solving the optimal design problem.

Let the design of an experiment be represented by an $s$-dimensional vector $\mathbf {w}$ of weights with nonnegative components. Let the quality of $\mathbf {w}$ for the estimation of the parameters of the statistical model be measured by the criterion of $D$-optimality, defined as the $m$th root of the determinant of the information matrix $M(\mathbf {w})=\sum_{i=1}^sw_iA_iA_i^T$, where $A_i,i=1,\ldots,s$ are known matrices with $m$ rows. In this paper, we show that the criterion of $D$-optimality is second-order cone representable. As a result, the method of second-order cone programming can be used to compute an approximate $D$-optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an exact $D$-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 $D_K$-optimality, which measures the quality of $\mathbf {w}$ for the estimation of a linear parameter subsystem defined by a full-rank coefficient matrix $K$. We prove that some other widely used criteria are also second-order cone representable, for instance, the criteria of $A$-, $A_K$-, $G$- and $I$-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., Comment: Published at http://dx.doi.org/10.1214/15-AOS1339 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We study a family of combinatorial optimization problems defined by a parameter $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 $p$ goes to 0, and to a trivial instance of the knapsack problem as $p$ goes to 1. In this article, we establish a matrix inequality which shows that the objective function is submodular for all $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/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 $p$ goes to 1.

Elfving's Theorem is a major result in the theory of optimal experimental design, which gives a geometrical characterization of $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-$ and $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-$optimal design always has a solution which is a matrix of rank $1$. Therefore, the complexity of this problem fades. We also investigate a \emph{model robust} generalization of $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.

We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite matrix of rank at most $r$, where $r$ 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., Comment: 16 pages