A column generation approach to exact experimental design Selin Ahipasaoglu, Stefano Cipolla, Jacek Gondzio Abstract In this work, we address the exact D-optimal experimental design problem by proposing an efficient algorithm that rapidly identifies the support of its continuous relaxation. Our method leverages a column generation framework to solve such a continuous relaxation, where each restricted master problem is tackled using a Primal-Dual Interior-Point-based Semidefinite Programming solver. This enables fast and reliable detection of the design’s support. The identified support is subsequently used to construct a feasible exact design that is provably close to optimal. We show that, for large-scale instances in which the number of regression points exceeds by far the number of experiments, our approach achieves superior performance compared to existing branch-and-bound-based algorithms in both computational efficiency and solution quality. MSC Classification]35A01, 65L10, 65L12, 65L20, 65L70 keywords Experimental Design pacs [ 1 Introduction The optimal experimental design problem is fundamental in robust statistics. The simplest version of the problem assumes a framework in which a researcher designs a set of experiments by selecting a finite number of regression vectors from a given candidate set with an objective function that maximizes the expected information gain from the experiments. The experiments can be repeated several times on selected points, while some points in the candidate set might be unused. The total number of experiments (counting repetitions) is determined before the design of the experiments. Optimal experimental design has been an integral and critical element of clinical research in which experiments are costly and statistical robustness is highly desired. In this application area, the candidate set is determined by fixing a few factor levels for each control such as the dose of the medication. Often, the results of the experiments are used to train simple supervised models such as polynomial or logistic regression. In these applications, the size of the problem (number of candidate points in the set, number of parameters to be estimated, and number of experiments to be conducted) is relatively small. Therefore, optimal experimental designs (under the D-optimality criterion for linear regression models) can be calculated in a short amount of time, for example, by modeling the problem as a mixed-integer nonlinear problem, which in turn can be solved by existing off-the-shelf solvers (e.g. Sagnol and Harman 2015 ), customized branch-and-bound algorithms (e.g., Ahipaşaoğlu 2021 ), or using more sophisticated mixed-integer programming techniques (e.g., Hendrych et al. 2024 ). Despite these advances, certain instances of the problem remain challenging to solve exactly. These typically arise in machine learning applications and differ from the classical setting in terms of the ratios of the number of parameters to be estimated, the cardinality of the candidate set, and the number of experiments to be conducted. One such example is subsampling: the selection of smaller subsets of data points from a large dataset as part of the model training process. Applying optimal design principles in the selection of subsamples, referred to as optimal subsampling (see ( Yao and Wang 2021 ) and references therein for a review), improves the robustness of the learning model while simultaneously decreasing the computational time spent on the training phase. Extracting a small set of relevant points, tailored for the regression model, also allows for a focused analysis, reduces noise, and minimizes spurious correlations compared to random sampling. In this paper, we propose an algorithm to solve large-scale instances of the exact optimal experimental design problem where the number of candidate points is very large, while the number of parameters of the regression model is moderate. We demonstrate that the problem is particularly challenging when the number of experiments is close to the number of parameters to be estimated, in other words, when an exact design with a relatively small support is desired. This is typically the case for optimal subsampling and other machine learning applications. The most important feature of our work is the control of the size of the problems that need to be solved in each iteration of the algorithm. Each problem remains small enough to be tackled by second-order methods in a short amount of time, allowing high accuracy solutions even for large scale problems. 1.1 Problem formulation Given a finite number of regression points x_{1},...,x_{m}\in\mathbb{R}^{n} that span \mathbb{R}^{n} , an exact experimental design (EED) of size N can be defined as a set of non-negative integers n_{1},\dots,n_{m} such that \sum_{i=1}^{m}n_{i}=N . For each i\in\{1,2,\dots,m\} , the integer n_{i} corresponds to the number of experiments to be carried out with the vector x_{i} as the input and N is the total number of experiments. The support of an experimental design is the set of regression points on which at least one experiment is carried out, that is, x_{i} is in support if n_{i}>0 . Under the assumption that errors in experiments are identically distributed random variables with mean zero and standard deviation \sigma and a generalized linear model is used in regression, the Fisher information matrix of an EED is independent of the parameters to be estimated and is equal to \frac{N}{\sigma^{2}}\sum_{i=1}^{m}\frac{n_{i}}{N}x_{i}x_{i}^{T} . A D-optimal exact experimental design maximizes the determinant of this matrix and can be calculated by solving the following nonlinear integer program ( Ahipaşaoğlu 2021 ) : \displaystyle\max \displaystyle g_{0}(u):=\ln\det(XUX^{T}) (1) \displaystyle s.t. \displaystyle\sum_{i=1}^{m}u_{i}=1, \displaystyle u_{i}\geq 0 \displaystyle\hbox{ for }i=1,\dots,m, \displaystyle u_{i}N\in\mathbb{Z} \displaystyle\hbox{ for }i=1,\dots,m, where [u_{i}]_{i=1}^{m}:=[\frac{n_{i}}{N}]_{i=1}^{m}\in\mathbb{R}^{m} , X:=\begin{bmatrix}x_{1}|\cdots|x_{m}\end{bmatrix} , and U:=diag(u) . In the following, we will refer to the continuous relaxation of problem ( 1 ) as the limit problem . This is also known as the approximate D-optimal experimental design problem in the literature. We prefer the first nomenclature, as the continuous version of the problem can be viewed as the limit of problem ( 1 ) when the number of experiments N goes to infinity. The limit problem is a convex program (note that the objective function to be maximized is a concave function and the feasible region is the unit simplex) and can be solved by any of the known methods for constrained convex programming. Solving the limit problem efficiently is important in tackling problem ( 1 ) regardless of the global optimization techniques used for the integer version. We will provide a brief literature review for the limit problem in Section 2 and present an efficient method for large-scale instances where m\gg n in Section 3 . We have previously mentioned that when problem ( 1 ) is tackled directly as a mixed-integer nonlinear program, computational limitations are encountered relatively quickly. This is demonstrated in Figure 1 . This figure presents the boxplots relative to the computational time required to solve 10 randomly generated instances of ( 1 ) with n=30 , and for each of m\in\{100,\dots 500\} and N\in\{n,n+5,n+10\} using the method proposed in Hendrych et al. 2024 (and relative software). To the best of our knowledge, this is the state of the art of mixed-integer solvers for exact D-optimal experimental design. The results clearly indicate that instances with N=n are significantly more challenging to solve and that the computational time quickly increases even for moderate m . Moreover, the figure clearly shows how the solver performance appears to be highly sensitive to the specific instance considered, although this variability tends to decrease as N increases. This suggests that the problem is particularly challenging when N , the number of experiments, is close to n , the number of parameters to be estimated. The current state-of-the-art might not be sufficient to address these instances. Figure 1: Computational times for random instances generated and solved using the software from Hendrych et al. 2024 . In this work, we address the limitations of mixed-integer solvers in the regime N\approx n by proposing a hybrid approach. To be precise, we will consider n,m,N s.t. the following Assumption 1 holds. Assumption 1 . n is in general a small integer ( n\leq 50 ), m\gg n , e.g., m\in O(n^{c}) for c\in\mathbb{N} , and N\in\{n,\dots,n+10\} . 2 Literature review and contribution It is known that the minimum-volume enclosing ellipsoid problem is dual to the limit problem and strong duality holds. The duality of these two problems leads to an interesting geometric interpretation of the optimality conditions for both problems. In particular, when a regression vector is in the support of the D-optimal experimental design, it must also be on the surface of the minimum-volume ellipsoid that encloses all the regression vectors in the candidate set. An early but excellent investigation of the duality of the two problems is provided in Pukelsheim 2006 , while Ahipasaoglu et al. 2008 provides a modern view in which the geometric interpretation is extended to approximate optimal solutions. The limit problem and its dual can be solved by a variety of numerical methods to any desired accuracy and the performance of the algorithms change significantly with respect to the size and properties of the dataset. Most of the widely used and analyzed first-order methods for the limit problem are variants of the Frank-Wolfe algorithm. In these, the next iterate is chosen by solving a one-dimensional maximization problem over the unit simplex, where the objective function corresponds to the linearization of the objective function at the current iterate. The maximum is attained by either increasing the weight of the solution at a regression point that is not covered by the dual ellipsoid (an ordinary Frank-Wolfe step) or decreasing the weight of one of the points that is in the current support (Wolfe’s away step). In both cases, the FW method can be viewed as a coordinate descent algorithm, the best step size can be calculated in closed-form, and the objective function value and the gradient at the next iterate can be calculated efficiently due to the fact that the Fisher information matrix at the new iterate is a rank-one update over the current one, see, e.g., Ahipasaoglu et al. 2008 for more details. These algorithms are terminated when a primal-dual pair with a small optimality gap is obtained and have desirable convergence properties especially when the algorithm is started with an iterate with a small support following the initialization strategy suggested in Kumar and Yildirim 2005 and Wolfe’s away steps are used as in Todd and Yıldı rım 2007 ; Ahipasaoglu et al. 2008 . In particular, Ahipasaoglu et al. 2008 ; Kumar and Yildirim 2005 show that an \epsilon -approximate solution to the limit problem can be obtained in \mathcal{O}(n\ln n+\frac{n}{\epsilon}) steps. This is also the size of the support of the output of the algorithm. Furthermore, this global convergence result, which holds for any starting point, provides a pessimistic view. It is proven in ( Ahipasaoglu et al. 2008 ) that there exist data-dependent constants P and Q such that the number of steps is only \mathcal{O}(P+Q{\ln(\epsilon^{-1})}) . I.e., this method is locally linearly convergent and the number of iterations does not depend on the number of data points in the neighborhood of the optimal set. Furthermore, the gradient evaluated at a feasible solution provides critical information on identifying regression vectors that can not be in the support of an optimal solution following the discussion in Harman and Ponzato 2007 . Including regular checkpoints to eliminate such points from the dataset greatly improves the efficiency of first-order methods and makes solving large-scale instances of the problem possible, as demonstrated in Ahipa¸saoğlu 2009 . This is important since each iteration of the algorithm takes \mathcal{O}(mn) operations where m is the number of regression vectors in the candidate set and reducing its size leads to significant gains in computational time. To tackle the challenges posed by “tall” datasets - those too large to fit into working memory - Rosa and Harman 2022 introduced the Big Index Batching (BIB) algorithm, which iteratively optimizes over a small subset of points, uses the elimination rule from Harman and Ponzato 2007 to delete points, and then adapts the subset by adding new points from the larger dataset. The BIB algorithm emphasises minimizing data reads and is coupled with a first-order method to find the optimal solution for each batch. Although the authors do not mention this, the BIB algorithm can be viewed as a column generation or active-set method as discussed in Section 3 . Alternatively, the limit problem can also be tackled using higher-order methods, e.g., Sun and Freund 2004 uses the dual reduced Newton method together with active set strategies, which works well for moderate problem sizes. In addition, Sagnol and Harman 2015 formulates the problem as a second-order cone program and utilizes MOSEK, and in Boyd and Vandenberghe 2004 an SDP formulation is given which can be solved directly using CVX. The choice between first-order and higher-order methods remains a relevant research question. A comparative analysis of several first and second methods is provided in Bowman and Heath 2023 together with a classification of the difficulty of the data sets using kurtosis as the relevant metric. Their work also includes an implementation of an active-set method, drawing inspiration from the general strategy outlined in Murtagh and Saunders 1978 - a seminal paper published in 1978. The availability of their Python codes facilitates further research and benchmarking. While second-order methods demonstrate potential, as highlighted by Bowman and Heath 2023 ; Sagnol and Harman 2015 , their scalability often presents a significant bottleneck for very large-scale problems. Similarly, solving the limit problem using semidefinite programming (SDPs) or second-order cone programming (SOCPs) techniques, is only possible when the problem size is small due to their high computational complexity. Here, we provide an algorithm that uses column generation and elimination methods to reduce the size of the problem to a scale that is tractable by SDP solvers. In particular, we solve the smaller subproblems using a barrier method for the Linear Matrix Inequality Representation of the problem. This enables us to use a higher-order method for the subproblems, while using first-order information to generate the subproblems in each step of the column generation algorithm. Although the problem formulation ( 1 ) is an integer program that is known to be NP-hard, the use of greedy methods for its solution has been widespread with good performance in practice. Early approaches are mostly variants of the two-exchange heuristic that iteratively swaps pairs of points until a 2-optimal solution is reached. A well-established version is provided in Atkinson et al. 2007 , with even earlier origins in Federov’s work Fedorov 1972 . While computationally efficient, these heuristics do not guarantee global optimality. Also, when they are applied to the full dataset, they take considerable amount of time for large scale instances of the problem. The first attempts at exact solutions include a simple branch-and-bound algorithm provided by Welch 1982 , nevertheless, this method can handle only very small instances of the problem. Modern research into exact D-optimal design can broadly be categorized into three main lines: (i) customized or generic branch-and-bound (BaB) implementations, (ii) methods based on quadratic programming (QP) approximations, and (iii) Mixed-Integer Second-Order Cone Programming (MISOCP) reformulations that leverage off-the-shelf solvers. There appears to be a growing recent interest in this area, potentially driven by advancements in solver technology and algorithmic frameworks for mixed-integer nonlinear programming. A customized BaB algorithm is provided by Ahipaşaoğlu 2021 , where subproblems correspond to bounded versions of the limit problem and its dual. The subproblems are solved using a customized Frank-Wolfe (FW) algorithm with Wolfe’s away steps, where the algorithm is initiated using solutions of the parent node, and the bounds on the variables are respected in each iteration of the FW algorithm. More recently, Hendrych et al. 2024 have used Boscia.jl, a contemporary algorithmic framework to solve nonlinear integer programs using BaB. This framework also employs FW algorithms for solving node relaxations to approximate optimality, sharing similarities with Ahipasaoglu’s approach but potentially benefiting from more efficient solver components or step-size rules. Similarly, Ponte et al. 2023 presented a BaB algorithm that features variable tightening techniques derived from the dual of bounded subproblems, similar to those in Ahipaşaoğlu 2021 . Additionally, the BaB given in Ponte et al. 2023 incorporates spectral and Hadamard bounds with promising results. The relevance of these as cutting planes for related problems such as the Minimum Volume Enclosing Ellipsoid (MVEE) problem could be further investigated. They also employ several local search methods, including a 2-exchange algorithm and a randomized SVD-based approach, to improve lower bounds within their Julia-based implementation, which solves subproblems with Knitro within the Juniper BaB solver, tackling problems with around 100 candidate points. In the domain of QP-based approximations, Filová and Harman 2020 proposed a method that constructs a quadratic approximation of the D-optimality objective function in the neighborhood of an optimal solution of the limit problem. This leads to a quadratic integer program (IQP) which is solved using Gurobi. Later, Filová and Harman 2020 introduced the AQuA (Ascent with Quadratic Assistance) algorithm, which employs IQP or MIQP-based approximations. While AQuA can handle a large number of candidate points in low-dimensional settings, it lacks theoretical guarantees and has reportedly shown variable performance. MISOCP reformulations offer another avenue for exact solutions. The first MISOCP formulation for the exact D-optimal design was provided in Sagnol and Harman 2015 , which was solved utilizing CPLEX via PICOS. Their work highlighted a graph-theoretic interpretation related to maximum spanning trees and noted that the inclusion of linear constraints significantly accelerates the solution process. They provided computational comparisons against the 2-exchange heuristic mentioned above on block-design and chemical kinetics datasets. The collective efforts indicate a drive towards scalable and provably optimal methods, leveraging both problem-specific insights and general advancements in mathematical optimization solvers and frameworks. However, very large instances of the problem are beyond the reach of any of the exact methods discussed above. Therefore, development of approximation algorithms with provable optimality guarantees is a recent area of interest. In this regard, Madan et al. 2019 has shown that the 2-exchange algorithm and other greedy heuristics are asymptotically optimal when N\gg n , which is different than the assumptions we have in this work. It is also worth noting a related work on other optimality criteria. For instance, Ahipaşaoğlu 2021 studies the BaB algorithm for Kiefer’s optimality criteria in general and provides the necessary details for the exact A-optimal design, where the objective function is (trace(XUX^{T})^{-1})^{-1} . The MISOCP formulations by Sagnol and Harman 2015 also include A-optimality. In addition, Harman and Rosa 2025 recently formulates the exact A-optimal design problem as a Mixed-Integer Linear Program (MILP) with McCormick relaxations, demonstrating the broader applicability of mixed-integer programming to optimal design problems beyond D-optimality. 2.1 Contribution and organization Our contribution focuses on the efficient computation of exact D-optimal designs in settings where the dimension n is moderate, but the number of candidate design points m is much bigger. In such a regime a naive enumeration, e.g., any technique which involves Branch-and-Bound, is computationally infeasible. Broadly speaking, exploiting the fact that the cardinality of the support of D-optimal designs remains moderate independently from the number of datapoints, i.e., exploiting the sparsity of the continuous relaxation, our method combines rapid support identification - implemented via a column generation strategy integrated with an Interior-Point-based SDP solver - with a local search algorithm restricted to the identified support. On the one hand, this approach is theoretically justified, as it produces solutions with the same quality guarantees for the objective function as applying the local search algorithm to the entire dataset. On the other hand, our numerical experiments demonstrate that the framework proposed here can compute high-quality approximate solutions for the exact D-optimal design at scales never achieved before. More in detail, our contribution is organised as follows: • In Section 3 , we frame and reinterpret the approach proposed in Rosa and Harman 2022 for computing the minimum-volume ellipsoids in the context of Column Generation. In our formulation, the master problem maintains a restricted set of design points, while the pricing subproblem identifies the most informative point to be added. This perspective elucidates the algorithmic framework and related convergence properties presented in Rosa and Harman 2022 , anchoring the method within the established Linear Programming literature while still acknowledging and recognising the unique challenges and peculiarities brought by the MVEE problem. Moreover, to solve the restricted master problems at each iteration, we propose and justify the use of an Interior-Point-based method, namely SDPT3 Tütüncü et al. 2003 , for computing high-accuracy solutions. This feature enables the rapid identification of the optimal support. It is interesting to note that, when coupled with the column generation approach described above, our proposal extends the applicability of SDP-based solvers for the computation of minimum volume ellipsoids for datasets with a high number of data points. • In Section 3.3 , we seek for provable approximation guarantees for local search algorithms when the pairs to be considered for exchange are restricted to the support of the solution of the continuous relaxation. In particular, we prove that a local search approach for the computation of exact D-optimal design solutions, when applied solely to the identified support set, achieves the same error bounds as when applied to the entire dataset. This significantly reduces computational cost while preserving theoretical guarantees on the worst-case estimate. • In Section 5 , we demonstrate the practical advantages of our approach, proposing a broad spectrum of numerical results. The considered large-scale Synthetic and Real World datasets are suitably modified to represent challenging instances of the exact D-optimal design problem. And indeed, the results presented there confirm the efficiency and robustness of our approach, showcasing how our proposed computational framework is able to consistently outperform state-of-the-art first-order methods Ahipasaoglu et al. 2008 ; Todd 2016 for the solution of the MVEE and state-of-the-art mixed-integer based solvers Ahipaşaoğlu 2021 ; Hendrych et al. 2024 for the exact D-optimal design problem in terms of computational time and quality of computed solutions. In the exact D-optimal design setting, our numerical results show that our method reliably produces solutions whose objective values match those from a mixed-integer programming approach, while running orders of magnitude faster, thereby enabling high-quality exact D-optimal designs at scales previously considered unattainable, cfr. Figures 1 and 2 . Figure 2: Computational times for the same random instances of Figure 1 solved using our proposal. 3 Column generation In this section, always under Assumption 1 , we neglect the integrality constraints u_{i}N\in\mathbb{Z} and study possible approaches to solve the limit problem. We start by briefly reviewing the related duality theory. 3.1 Duality We refer the interested reader to ( Todd 2016 , Ch. 2) from where this session is borrowed. Let us consider the following convex problem: \displaystyle\min \displaystyle f_{0}(H):=\ln\det H^{-1} (DMP) \displaystyle s.t. \displaystyle x_{i}^{T}Hx_{i}\leq n, \displaystyle\hbox{ for }i=1,\dots,m, which is known as the Minimum Volume Enclosing Ellipsoid problem (MVEE) in the literature. For u\geq 0 , consider the Lagrangian function: L_{0}(H,u):=\ln\det H^{-1}+\sum_{i=1}^{m}u_{i}(x_{i}^{T}Hx_{i}-n), (2) where u_{i} corresponds to the multiplier of the i^{th} constraint. Using the Lagrangian in ( 2 ), the KKT conditions of problem ( DMP ) can be stated as \displaystyle x_{i}^{T}Hx_{i} \displaystyle\leq n, \displaystyle\hbox{ for }i=1,\dots,m, (PF) \displaystyle u_{i} \displaystyle\geq 0, \displaystyle\hbox{ for }i=1,\dots,m, (DF) \displaystyle u_{i}(x_{i}^{T}Hx_{i}-n) \displaystyle=0, \displaystyle\hbox{ for }i=1,\dots,m, (Comp) \displaystyle\nabla_{H}L_{0}(H,u)=-H^{-1}+XUX^{T} \displaystyle=0. (Stat) Lemma 1 . We have that \min_{H}L_{0}(H,u)=\ln\det(XUX^{T})+n(1-\sum_{i=1}^{m}u_{i}). (3) Proof. We have -\ln\det H=\ln\det H^{-1} and hence, using ( Stat ), i.e., XUX^{T}=H^{-1} , we have that -\ln\det H=\ln\det(XUX^{T}). Moreover, always using ( Stat ) in second part of ( 2 ), we have trace(HXUX^{T})=n , which proves hence ( 3 ). ∎ Using Lemma 1 , we have hence that the dual problem of ( DMP ) is exactly the continuous relaxation of ( 1 ) (limit problem), i.e., \displaystyle\max \displaystyle g_{0}(u) (MP) \displaystyle s.t. \displaystyle\sum_{i=1}^{m}u_{i}=1, \displaystyle u_{i}\geq 0 \displaystyle\hbox{ for }i=1,\dots,m. Remark 1 . It is important to note that, in the derivation above, for the sake of simplicity, we derived ( MP ) as dual of ( DMP ). On the other hand, in the following, we refer to and interpret ( MP ) as the Primal Master Problem and ( DMP ) as the Dual Master Problem. This is fully justified by the fact that strong duality holds, see also Theorem 1 below. Remark 2 . For any primal dual feasible points (u,H) , weak duality follows also observing that \begin{split}&-\ln\det H-\ln\det(XUX^{T})=\\ &-\ln\det(HXUX^{T})=\\ &-\ln(\prod_{i=1}^{n}\lambda_{i})\geq-n\ln(\sum_{i=1}^{n}\lambda_{i}/n)=-n\ln(n/n)=0,\end{split} where we used the arithmetic-geometric mean inequality and the fact that \sum_{i=1}^{n}\lambda_{i}=\rm{trace}(HXUX^{T})=n . We are now ready to state the main theorem of this section that clarifies the existence and uniqueness of ( MP )-( DMP ), see ( Todd 2016 , Th. 2.2) . Theorem 1 . If X has full rank, then ( DMP ) has a unique optimal solution H^{*} , ( MP ) has an optimal solution u^{*} with XU^{*}X^{T} , and f_{0}(H^{*})=g_{0}(u^{*}) . Definition 1 . Throughout this work, ({u}^{*},{{H}}^{*}) will denote a primal-dual solution of ( MP ) - ( DMP ), i.e., it will satisfy ( PF )-( Stat ). 3.2 Column generation for the limit problem We start the description of the column generation approach for solving the limit problem and its dual by introducing the Restricted Master Primal-Dual problems. The Primal Restricted Master Problem (RMP) is obtained as the restriction of ( MP ) to a subset \bar{M}\subset\{1,\dots,m\}=:M , i.e., \displaystyle\max \displaystyle\ln\det(X\bar{U}X^{T}) (RMP) \displaystyle s.t. \displaystyle\sum_{i\in\bar{M}}\bar{u}_{i}=1, \displaystyle\bar{u}_{i}\geq 0 \displaystyle\hbox{ for }i\in\bar{M}. It is important to note that \bar{u}\in\mathbb{R}^{|\bar{M}|} and, hence, that the dimension and complexity of the solution of ( RMP ) depends on |\bar{M}| . For this reason, to fix ideas, we can assume |\bar{M}|\in O(n) and |\bar{M}|\geq(n+1) . Using the discussion carried out in the previous section, we can see that the dual of ( RMP ) has again the form \displaystyle\min \displaystyle-\ln\det(\bar{H}) (DRMP) \displaystyle s.t. \displaystyle tr(\bar{H}x_{i}x_{i}^{T})\leq n, \displaystyle\hbox{ for }i\in\bar{M}. We will use, what is common in the column generation scheme, a pricing procedure Gondzio et al. 2013 to identify all (or a subset of) violated dual constraints. Such constraints will be appended to the set \bar{M} . Let us assume that primal-dual solution (\bar{u}^{*},\bar{{H}}^{*}) of ( RMP )-( DRMP ) has been computed, and find z(\bar{H}^{*}):=\max_{i\in M}\{0,x_{i}^{T}\bar{H}^{*}x_{i}-n\}. (4) Following on the discussion on the geometric interpretation of optimality conditions above, \bar{{H}}^{*} determines the current approximation of the MVEE which contains all points in the index set \bar{M} , while the points x_{i} such that x_{i}^{T}\bar{H}^{*}x_{i}-n>0 lie outside this ellipsoid, and therefore, correspond to constraints of (DMP) which are violated. Moreover, z(\bar{H}^{*})>0 implies the existence of an index \bar{i} such that the point x_{\bar{i}} lies outside of the ellipsoid defined by \bar{H}^{*} . We also observe that every optimal solution \bar{u}^{*} of the problem ( RMP ) corresponds to a feasible solution u of problem ( MP ), where u_{i}=\bar{u}^{*}_{i} for i\in\bar{M} , and u_{i}=0 for i\in M\setminus\bar{M} . Hence \ln\det(\bar{X}\bar{U}^{*}\bar{X}^{T})=\ln det(XUX^{T})\leq\ln\det(X{U}^{*}X^{T}), where \bar{X} is the submatrix of X built of columns i\in\bar{M} only. Moreover, since \bar{u}_{i}(n-x_{i}^{T}\bar{H}^{*}x_{i})=0 for all i\in\bar{M} , using the definition above, we have u_{i}(n-x_{i}^{T}\bar{H}^{*}x_{i})=0 for all i\in M . Hence \bar{H}^{*} is an optimal solution of (MP) iff z(\bar{H}^{*})~=~0 . Using the ideas introduced until now, we are finally ready to present the full details of a column generation approach for the solution of problems ( MP )-( DMP ), see Algorithm 1 . Such a framework, generalises the column generation approach usually used in linear programming, see e.g. Gondzio et al. 2013 , to the nonlinear problem in ( MP ). Algorithm 1 Column Generation for ( MP ) 1: procedure ColumnGeneration 2: Initialize u using the technique proposed in Kumar and Yildirim 2005 ; 3: Initialize \bar{M}:=\{i\in M\hbox{ s.t. }u_{i}>0\} ; 4: Solve ( RMP )-( DRMP ) restricted to \bar{M} to produce initial (\bar{u}^{*},\bar{{H}}^{*}) ; 5: while z(\bar{H}^{*}):=\max_{i\in M}\{0,x_{i}^{T}\bar{H}^{*}x_{i}-n\}>0 do ; 6: Find \bar{i} s.t. \bar{i}\;{\in}\;\arg\max_{i\in M}x_{i}^{T}\bar{H}^{*}x_{i}-n ; 7: Define \bar{M}=\bar{M}\cup\{\bar{i}\} ; 8: Solve ( RMP )-( DRMP ) restricted to \bar{M} to produce a new (\bar{u}^{*},\bar{{H}}^{*}) ; 9: end while 10: For i\in\bar{M} define u_{i}=\bar{u}_{i}^{*} and u_{i}=0 , otherwise; 11: end procedure The convergence of Algorithm 1 is analyzed in Theorem 2 . Theorem 2 . Algorithm 1 converges to a Primal-Dual optimal solution in m iterations. Proof. Let us define g^{*} as the optimal value of ( MP ). Let us denote with (\bar{u}^{*},\bar{{H}}^{*}) the solution of ( RMP )-( DRMP ) obtained at Line ( 8 ) of Algorithm 1 . Two situations may occur: • If z(\bar{H}^{*})>0 , then there exists \bar{i}\in\{1,\dots,m\}\hbox{ s.t. }x_{\bar{i}}^{T}\bar{H}^{*}x_{\bar{i}}-n>0 . Since \bar{i} is added to \bar{M} , the corresponding dual constraints will not be violated in the next iterations. Therefore, it guarantees the progress of the algorithm. Also, this case can only happen at most m times. • If z(\bar{H}^{*})=0 , then Algorithm 1 stops. In this case, consider (\bar{u}^{*},\bar{{H}}^{*}) to be a solution of the Primal-Dual pair ( RMP )-( DRMP ). An optimal solution ({u}^{*},{{H}}^{*}) of ( MP )-( DMP ) is obtained by defining u_{i}^{*}=\bar{u}_{i}^{*} for i\in\bar{M} and u_{i}^{*}=0 for i\in M\setminus\bar{M} and {{H}}^{*}=\bar{{H}}^{*} . ∎ Remark 3 . A similar proof to the one proposed for Theorem 2 holds when n_{0}>1 points violating the dual constraints are added to the set \bar{M} . In that case, Algorithm 1 converges in at most \lceil m/n_{0}\rceil iterations. Moreover, it is easy to see that the convergence proof still holds if at Line 6 of Algorithm 1 the \arg\max is substituted by any \bar{i} s.t. x_{i}^{T}\bar{H}^{*}x_{i}-n>0 , i.e., any point that violates the dual-constraints. It is important to note, at this stage, that since the cardinality of \bar{M} increases at every step of Algorithm 1 , the dimension of the problems ( RMP )-( DRMP ) to be solved, increases at every step. This issue represents one of the main computational bottlenecks and, in the next section, we will show how such drawback can be overcome for the particular case of D-optimal design thanks to the use of the Harman-Ponzato constant Harman and Ponzato 2007 that identifies which points in set M can be dropped from the data set fully since these cannot be in the support of the optimal solution of (MP). 3.3 On the use of Harman-Ponzato constant Harman and Ponzato 2007 Let us define the constant h_{n}(\varepsilon):=n\left(1+\frac{\varepsilon}{2}-\frac{\sqrt{\varepsilon(4+\varepsilon-4/n)}}{2}\right), where \varepsilon:=\max_{i=1,\dots,m}x_{i}^{T}Hx_{i}-n and H=(XUX^{T})^{-1} for any given primal feasible u\geq 0 . In ( Harman and Ponzato 2007 , Th. 2) it is proven that a point x_{j} that satisfies x_{j}^{T}Hx_{j}0 . Definition 2 . In the following, given H , we will say that a point x satisfies the Harman-Ponzato condition, in short HP-condition, if x^{T}Hx0 , see Harman and Ponzato 2007 , we have that x^{T}Hx-n\leq x^{T}Hx-h_{n}(\varepsilon). Hence \begin{split}&x^{T}Hx-n>0\Rightarrow x^{T}Hx-h_{n}(\varepsilon)>0,\\ &x^{T}Hx-h_{n}(\varepsilon)<0\Rightarrow x^{T}Hx-n<0.\end{split} The above implications show that all points x that are not covered by the current estimated MVEE defined by H , i.e., x^{T}Hx-n>0 will fail the condition. Whereas all points that satisfy the HP-condition, i.e., x^{T}Hxh_{n}(\varepsilon) x^{T}Hxn Figure 3 : Pictorial representation the regions identified by HP-condition, see Remark 4 In light of Remark 4 , it is natural to modify Line 7 of Algorithm 1 using the information provided by the HP-condition, i.e., substituting such line with \bar{M}=(\bar{M}\cup\{\bar{i}\})\cap\bar{J}, where \bar{J}:=\{i\in M\hbox{ s.t. }x_{i}^{T}\bar{H}^{*}x_{i}\geq h_{n}(\varepsilon)\} . Indeed, points s.t. x^{T}Hx-h_{n}(\varepsilon)<0 can be safely discarded from \bar{M} , reducing hence the dimension of the ( RMP )-( DRMP ) to be solved. On the other hand, as per the discussion in Remark 4 , \bar{M} defined as above could still contain points s.t. x^{T}Hx-n<0 (especially in the initial phases of the algorithm). This might still represent a computational issue/bottleneck and could lead to sets \bar{M} having unnecessarily high number of points. To prevent this and guarantee an efficient solution of problems ( MP )-( DMP ), we consider the following Algorithm 2 , a reformulation of the Big Index Batching Algorithm, see ( Harman and Ponzato 2007 , Alg. 1) , where the dimensions of the ( MP )-( DMP ) to be solved – the batch size – is not upper bounded. In this framework, the points which are detected as non-support for the currently estimated MVEE defined by \bar{H}^{*}=(X\bar{U^{*}}X^{T})^{-1} , i.e., points x_{i} such that \bar{u}_{i}^{*}=0 , are eliminated from \bar{M} reducing hence the dimension of the problem ( RMP )-( DRMP ) to be solved in the next iteration. In particular, given \bar{M} and the corresponding (\bar{u}^{*},\bar{{H}}^{*}) , we define the next \bar{M} as follows: 1. Define \bar{A}:=\{i\in\bar{M}\hbox{ s.t. }\bar{u}^{*}_{i}>0\}; 2. Define the new \bar{M} as \bar{M}=(\bar{I}\cup\bar{A}) where \bar{I} is the set of the n_{0} most violated dual constraints (we assume that there are at least n_{0} of such constraints). Moreover, defining \bar{J}:=\{i\in M\hbox{ s.t. }x_{i}^{T}\bar{H}^{*}x_{i}\geq h_{n}(\varepsilon)\} , we know that the points in \bar{J}^{C} can be safely eliminated from the dataset, see Remark 4 . Moreover, always using Remark 4 , we note that at Line 9 of Algorithm 2 , it holds x_{i}^{T}\bar{H}^{*}x_{i}-n>0\Rightarrow x_{i}^{T}\bar{H}^{*}x_{i}-h_{n}(z(\bar{H}^{*}))>0, which implies that the indexes i corresponding to violated dual constraints belong indeed to \bar{J} . Algorithm 2 Column Generation for ( MP ) 1: procedure ColumnGeneration 2: Initialise M_{P}=M 3: Choose n_{0}\in\mathbb{N} ; 4: Choose an initial \bar{M}\subset M_{P} using Kumar and Yildirim 2005 ; 5: Initialize z(\bar{H}^{*})=+\infty ; 6: while z(\bar{H}^{*})>0 do 7: Solve ( RMP )-( DRMP ) restricted to \bar{M} to produce (\bar{u}^{*},\bar{{H}}^{*}) 8: Define \bar{A}:=\{i\in\bar{M}\hbox{ s.t. }\bar{u}^{*}_{i}>0\} 9: Define \bar{I}:=\{i\in M_{P}\hbox{ s.t. }n_{0}\hbox{ largest elements }x_{i}^{T}\bar{H}^{*}x_{i}-n>0\} 10: Define \bar{M}=(\bar{I}\cup\bar{A}) 11: Compute z(\bar{H}^{*})=\max_{i\in M_{P}}\{0,x_{i}^{T}\bar{H}^{*}x_{i}-n\} 12: Define h_{n}(z(\bar{H}^{*})) as in ( Harman and Ponzato 2007 , Th. 2) 13: Define \bar{J}:=\{i\in M_{P}\hbox{ s.t. }x_{i}^{T}\bar{H}^{*}x_{i}\geq h_{n}(z(\bar{H}^{*}))\} 14: Define M_{P}:=M_{P}\setminus\bar{J}^{C} 15: end while 16: For i\in\bar{M} define u^{*}_{i}=\bar{u}_{i}^{*} and u^{*}_{i}=0 otherwise. 17: end procedure We are finally able to prove the finite convergence of Algorithm 2 . The proof of finite convergence is partially borrowed from Harman and Ponzato 2007 . Theorem 3 . Algorithm 2 terminates in finite number of iterations. Proof. The first important observation is that Line 14 of Algorithm 2 does not discard any point of the support at optimality, hence, it can be ignored. We consider then the version of Algorithm 2 where M_{P} is always equal to M and where the lines connected to the use of the Harman-Ponzato constant are ignored (Lines 12 - 14 ). To show that Algorithm 2 terminates in a finite number of iterations, let us argue by contradiction. Suppose that Algorithm 2 as just described, does not terminate in a finite number of steps. Then there exists an infinite sequence \{\bar{A}_{i}\}_{i\in\mathbb{N}} of computed supports (see Line 8 ). Let us denote by \{\bar{g}_{i}\}_{i\in\mathbb{N}} the corresponding function values of the function g_{0}(u) . As at every iteration we are adding at least one point outside the current estimated ellipsoid, see Line 9 , we have that \bar{g}_{i+1}>\bar{g}_{i} , i.e., \bar{g}_{i} is a strictly increasing sequence. The absurd follows from observing that there exists only a finite number of possible subsets of the given dataset. ∎ 4 Local search algorithms for exact D-optimal design In this section, we present the local search approach considered to produce an approximate integer solution exploiting a computed primal-dual solution (u^{*},H^{*}) of ( DMP )-( MP ), i.e., the limit problem. Let us define the support of u^{*} as S:=\{i\in 1,\dots,m\,:u_{i}^{*}>0\} and \phi_{Rel}:=g_{0}(u^{*})=f_{0}(H^{*}) . By definition of support S and using the fact that (u^{*},H^{*}) is primal-dual solution of ( DMP )-( MP ), the optimal objective function values of the following two problems are equal \begin{aligned} \max&\;g_{0}(u)\\ s.t.&\;\sum_{i\in S}u_{i}=1,\\ &\;u_{i}\geq 0\;\;\hbox{ for }i\in S,\\ \end{aligned}\quad\quad{\mbox{ and }}\quad\quad\begin{aligned} \min&\;f_{0}(H)\\ s.t.&\;{\rm trace}(Hx_{i}x_{i}^{T})\leq n,&\hbox{ for }i\in S.\\ \\ \end{aligned} (5) and are, in turn, equal to g_{0}(u^{*})=f_{0}(H^{*}) . Problem ( 4 ) coincides, indeed, with ( DMP )-( MP ) where the original set M has been substituted by the support S . We will exploit the equality in ( 5 ) to apply a local search algorithm for the solution of the exact D-optimal design problem, where the original set M is substituted by the possibly much smaller set S in order to produce an approximate integer solution. Before we present and analyse the local search algorithm considered here, we recall that there may exist a vector \hat{u}^{*}\neq u^{*} such that \Bigl(\sum_{i}\hat{u}^{*}_{i}\,x_{i}x_{i}^{T}\Bigr)^{-1}=H^{*}, i.e., the support S of the minimisers is not uniquely determined. In fact, this ambiguity depends heavily on the particular algorithm used to compute a solution. For example, if the limit problem is solved using the FW algorithm without Wolfe’s away steps initialised with a uniform distribution, i.e., with all identical u_{i} , then the algorithm will fail in identifying an optimal solution with sparse support in finitely many steps. In contrast, if the algorithm is initialised with a sparse vector and Wolfe’s away steps are employed, then the resulting solution may indeed exhibit a sparse support. Indeed, in general, the cardinality of the support depends on the problem dimension, the used algorithmic framework and the target accuracy of the solution, while remaining independent of the total number of points. As discussed in Section 2 , Kumar and Yildirim 2005 shows that an optimal solution with a small support can be obtained with a careful initialization. At first glance, this ambiguity might seems to be quite problematic when applying a local search approach to exploit the support of a computed primal solution u^{*} . A first clarifying observation in this regard is that, even though there might be multiple optimal solutions to the primal problem, they correspond to the same (unique) dual solution H^{*} . Therefore, we can use any of such primal solutions to determine a support set S . Interestingly enough, exploiting the uniqueness of H^{*} , we will prove that the local exchange phase that will be described next, see Algorithm 3 , produces an approximate integer solution having worst-case guarantees not depending on the particular primal optimal solution used – and its corresponding support –. 4.1 Bounds Based on a local search algorithm In this section, we show that, when applying the local search algorithm (see Algorithm 3 ) to the exact D-optimal design problem, it is sufficient to restrict the search to the support S of an optimal solution to the limit problem. In particular, we show that the approximation guarantee obtained by running the algorithm on S is identical to that achieved when the algorithm is executed over the full data set M . Given the combinatorial nature of the local search procedure, this reduction is expected to yield significant computational savings in cases where |M|\gg|S| . The proof of this result follows easily from the analysis in Madan et al. 2019 ; for completeness, we briefly outline the main steps in the following. To this aim, consider the local search procedure described in Algorithm 3 , which iteratively replaces elements in the current multi-subset I with elements from the set S , provided such exchanges lead to an increase in the determinant of the current candidate solution (see Line 2 ). The use of multi-set notation permits repeated inclusion of indices i\in S , and we denote by n_{i} the multiplicity of each index i\in I . The initialisation of I is based on an optimal solution u^{*} of the limit problem. Specifically, I is constructed by including n_{i} copies of each index i\in S , where n_{i} is a suitable integer approximation of Nu_{i} satisfying the condition \sum_{i\in S}n_{i}=N . Algorithm 3 Local search algorithm for D -optimal experimental design 1: Input: S , I any multi-subset of S of size N such that G\;=\;\sum_{i\in I}x_{i}\,x_{i}^{T} is a non-singular matrix. 2: while there exist i\in I and j\in S such that \det\bigl(G-x_{i}\,x_{i}^{T}+x_{j}\,x_{j}^{T}\bigr)\;>\;\det(G) do 3: G\leftarrow G-x_{i}\,x_{i}^{T}+x_{j}\,x_{j}^{T} 4: I\leftarrow\bigl(I\setminus\{i\}\bigr)\cup\{j\} 5: end while 6: Output: (G,I) Definition 3 . For any G\;=\;\sum_{i\in I}x_{i}\,x_{i}^{T} and for all i,j\in\{1,\dots,m\} , let us define \tau_{i}:=x_{i}^{T}G^{-1}x_{i}\hbox{ and }\tau_{ij}:=x_{i}^{T}G^{-1}x_{j}. In the following Lemma 2 , we state an important property satisfied by \tau_{i} and \tau_{ij} defined above. Lemma 2 (see Claim 1 in Madan et al. 2019 ) . Let (G,I) denote the output of Algorithm 3 . Then for all i\in I and j\in S it holds \tau_{j}-\tau_{i}\tau_{j}+\tau_{ij}\tau_{ji}\leq\tau_{i}. We are now ready to state the worst-case approximation bound for approximate integer solutions computed using Algorithm 3 . Lemma 3 . Let us denote by \phi_{D}:=\log\det(XU_{I}^{*}X^{T}) where u_{I}^{*} is an optimal solution of ( 1 ) and (G,I) denote the output of Algorithm 3 . Then \log\det(\frac{1}{N}G)\geq-h(N,n)+\phi_{Rel}\geq-h(N,n)+\phi_{D}, (6) where h(n,N) is a constant that depends only on n,N . Proof. Given G , the strategy of the proof is based on exhibiting a feasible solution of the dual problem in ( 5 ) that will be used to obtain the desired result. Let us consider Y=\frac{\alpha}{N}G . We have Y^{-1}=\frac{N}{\alpha}G^{-1} and suppose that we want to find a constant \alpha s.t. x_{j}^{T}Y^{-1}x_{j}=\frac{N}{\alpha}x_{j}^{T}G^{-1}x_{j}\leq n for all j\in S . In that case, we would have indeed, \phi_{Rel}\leq f_{0}(\frac{N}{\alpha}G^{-1})=-\log\det(\frac{N}{\alpha}G^{-1})=\log\det(\frac{\alpha}{N}G)=n\log({\alpha})+\log\det(\frac{1}{N}G). Therefore, calculating an upper bound on \tau_{j} would be useful when finding an \alpha which satisfies the desired condition, i.e., we would like to bound \max_{j\in S}x_{j}^{T}G^{-1}x_{j} . Such a bound is provided in Lemma 9 of Madan et al. 2019 : \tau_{j}\leq\frac{n}{N-n+1}. Since we want \alpha s.t. \frac{N}{\alpha}\frac{n}{N-n+1}\leq n , i.e., \alpha\geq\frac{N}{N-n+1}\geq 1 , we can set h(N,n):=n\log(\frac{N}{N-n+1}) and observe that \phi_{Rel}\geq\phi_{D} to complete the proof. ∎ Remark 5 . It is easy to see that if Algorithm 3 uses the whole dataset M rather than S , as proved in Madan et al. 2019 , one can obtain exactly the same approximation bound as stated in ( 6 ). Moreover, ( 6 ) confirms the very well-known fact that the exact D-optimal design problem is more difficult to solve when N\approx n and easier when N\gg n as, in this case, the local search algorithm would indeed produce solutions having very good approximation bounds since \lim_{N\to\infty}\frac{N}{N-n+1}=1 . Corollary 1 . If (G,I) is the output of Algorithm 3 and u_{I}^{*} is an optimal solution of ( 1 ), then \det(G)\geq(\frac{N-n+1}{N})^{n}\det(XNU_{I}^{*}X^{T}). 5 Numerical Results In this section, we present a series of numerical results to support the efficiency and robustness of our proposal when compared to the state of the art methods. We will start showcasing the strength of our proposal in the fast identification of support for challenging datasets for the MVEE problem, see Section 5.2 , and then we will present numerical results concerning the computational performance of the approach proposed in this paper for the the solution of large exact D-optimal design problems, see Section 5.3 . Our implementation is written in Matlab 2024b and all the numerical results are obtained using Iridis X equipped with 2.35 GHz AMD 7452 Processor . All the software is publicly available at https://github.com/StefanoCipolla/D_Optimal_Desing_Matlab . In the remainder of this section we discuss the details about the datasets and our implementation. 5.0.1 Solution of the Restricted Problems and Stopping Criteria In Algorithm 2 we use the following experimental setting. Given \bar{M} , every ( RMP )-( DRMP ) pair of problems is solved with SDPT3 Tütüncü et al. 2003 using OPTIONS.gaptol =1e-9 . Despite this being quite a strict tolerance, we noticed that such a parameter is mainly responsible for the fast identification of the support of the limit MVEE problem and largely justifies the use of a second-order method. Concerning the stopping criterion, we stop Algorithm 2 when z(\bar{H}^{*})\det(G) do 3: Choose (i^{\ast},j^{\ast}) that maximizes \det\bigl(G-x_{i}\,x_{i}^{T}+x_{j}\,x_{j}^{T}\bigr)-\det(G) 4: G\leftarrow G-x_{i^{\ast}}\,x_{i^{\ast}}^{T}+x_{j^{\ast}}\,x_{j^{\ast}}^{T} 5: I\leftarrow\bigl(I\setminus\{i^{\ast}\}\bigr)\cup\{j^{\ast}\} 6: end while 7: Output: (G,I) The purpose of the first presented series of experiments is to evaluate the goodness of our proposal by comparing the execution time and the primal objective function obtained by using the software from Hendrych et al. 2024 (denoted in the following by Boscia ) on medium-sized problems. For Boscia, we use the default parameters. In Figures 6 and 7 , we report the results of numerical experiments obtained on synthetic problems created using the generator provided in the solver Boscia using the option ‘‘correlated’’ when (n,m)\in\{10,20,30,40,50\}\times\{100,200,300,400,500\} and when for every (m,n) 10 instances are generated. Broadly speaking, such a generator produces instances by sampling one Gaussian distribution with a randomly generated mean and covariance matrix. As highlighted by the upper panels of the aforementioned figures and as already observed in Section 1.1 , the computational time for the solver Boscia (in black), in the case N=n , roughly increases by two orders of magnitude when m goes from 100 to 500 . It is also interesting to note how such a trend still remains true when N>n and n\in\{30,40,50\} , suggesting that the problems become more and more difficult for the solver when the possible size of the support increases. For n=40,50 we capped the maximum allowed time to 1800 seconds, and such a wall-time is usually hit by Boscia before producing a solution satisfying the required accuracy. On the other hand, our proposal (in red) is able to solve all the instances in less than 10 seconds. Moreover, in general, our proposal produces better or comparable objective functions, especially when N=n , see the lower panels of Figures 6 and 7 . It is also important to note that the worst-case complexity reported in Corollary 1 is systematically shown to be an over-pessimistic bound as the function values obtained by ColGen are comparable with the function values computed using Boscia, which is, theoretically, an enumerative method and should return the true optimizer. Figure 6: Top to bottom: n=10,20 . Synthetic problems using generator from Hendrych et al. 2024 with ‘‘correlated’’ option. Figure 7: Top to bottom: n=30,40,50 . Synthetic problems using generator from Hendrych et al. 2024 with ‘‘correlated’’ option. In the second experiment, see Figures 8 and 9 , we compare FW and ColGen when used to generate the initial support S in Algorithm 4 on Synthetic and Real World datasets. In particular, in order to offer an alternative measure for evaluating the quality of the computed integer solution, we will use the following gap measure, an analogue of the relative MIP gap for Mixed Integer Programming, i.e., given G output of Algorithm 4 and u^{*} solution of ( MP ), we define gap:=\frac{\log(\det(XU^{*}X^{T}))-\log(\det(G))}{|\log(\det(XU^{*}X^{T}))|}. Given u_{I}^{*} solution of ( 1 ), it is easy to see that gap\geq 0 and that gap\geq\frac{\log(\det(XU^{*}X^{T}))-\log(\det(XNU_{I}^{*}X^{T}))}{|\log(\det(XU^{*}X^{T}))|}, where the right-hand side is the best achievable relative gap for an integer solution. The figures present the computational time (upper panel) and the optimality gap (lower panel) relative to Column Generation (ColGen) and the Frank–Wolfe (FW) method. As shown by these results, our proposed approach solves all instances within 150 seconds, whereas FW remains consistently slower. Regarding the quality of the integer solutions, both frameworks typically exhibit a gap on the order of 1e-1 . Intriguingly, although FW generally identifies sparser supports than ColGen (cf. the discussion in Section 5.2 ), it still produces integer solutions whose gap is comparable to that delivered by ColGen. This finding is somewhat counterintuitive, since one would expect that applying the local search Algorithm 4 on a larger set S would, in general, yield to superior quality solutions. On the other hand, this is perfectly in line with the theory developed in Section 4 , basically postulating that the worst case bounds only depend on the objective value. Figure 8: Synthetic dataset m=10M . Running time and gap values of Algorithm 4 with Algorithm 2 (in red) and FW (in black). Upper panel: \sinh-\arcsinh transformation. Lower Panel: original dataset . Figure 9: Real World : Running time and gap for FW and ColGen for \sinh-\arcsinh transformed datase. In the last experiment, we compare our proposal with Algorithm 4 when the input S is the full dataset, i.e., without the preliminary support identification performed using Algorithm 2 , and when the I is randomly initialised. In this experiment, we restrict our analysis to the case N=n , as the experiments conducted and presented until this moment have shown that this regime includes the most challenging cases for the computation of exact D-optimal design solutions. As highlighted in Figure 10 , our proposal outperforms Algorithm 2 , as described above, by two orders of magnitude in terms of computational time for the Synthetic dataset with m=1M (cfr., first and second rows subplots) while obtaining equal or better objective function values (cfr., third and fourth rows subplots). Moreover, the comparison of the reported computational times for m=100K and m=1M highlights how ColGen exhibits a limited dependence on m . Figure 10: Synthetic : Running time and objective function values of Algorithm 4 with (in red) or without (in black) Algorithm 2 . 6 Conclusions In this work, we have addressed the longstanding challenge of computing exact D-optimal experimental designs in the regime where the number of candidate points far exceeds the dimensionality of the regression model and the total number of allowed experiments is close to the number of parameters to be estimated, i.e., N\approx n . Building on the duality between the D-optimal design problem and the minimum-volume enclosing ellipsoid (MVEE) problem, we have introduced a hybrid column-generation framework that integrates the following key elements: • Rapid Support Identification via Column Generation and Interior-Point SDP . This is achieved by formulating the continuous relaxation, the limit problem , as a primal–dual pair and by deploying a column-generation strategy – Algorithm 2 – to identify, in an iterative fashion, the small support set that carries all of the mass of the continuous optimum. At each iteration, we solve a restricted master problem over a modest-sized subset of candidate points using a high-accuracy, primal–dual Interior-Point SDP solver (SDPT3). • Restricted Local Search with Provable Bounds . Once the support S of the limit problem has been determined, we invoke a greedy local‐search algorithm – Algorithm 3 – that operates only on those points in S . By leveraging the bound provided by the optimiser of the limit problem , we prove that restricting the local search to S yields an exact design whose worst‐case approximation factor to the optimum is identical to that obtained when running the same local‐search procedure on the entire dataset. Crucially, this means that no theoretical guarantee is sacrificed: performing a local search restricted to the support of the limit problem yields the same worst-case bound in N and n as in recently proposed analyses, but at a fraction of the computational cost. • Extensive Numerical Validation on Synthetic and Real-World Data . We benchmark our proposal for the solution of MVEE against a state-of-the-art Frank–Wolfe‐type algorithm on very large synthetic datasets and on large UCI real-world datasets (up to m=10^{7} ). Across all instances, including those modified to be more challenging, our proposal identifies the continuous support tens to hundreds of times faster than FW, attains smaller duality gaps, and exhibits far fewer iterations, thereby demonstrating both superior convergence and robustness. Moreover, we compare our full pipeline – support identification followed by restricted local search – against a state-of-the-art nonlinear-mixed-integer solver – Boscia – on medium-scale synthetic instances (up to m=500 , n=50 ). Even for the most challenging cases, i.e., when N=n , our method consistently produces exact designs of equal or better objective value in under 30 seconds, whereas Boscia often fails to reach optimality within the 1800 second time limit. Finally, we evaluated the impact of preliminary support identification on the efficiency of the local‐search procedure by conducting experiments on large‐scale synthetic datasets with m=10^{5} and m=10^{6} candidate points. In these experiments, our column‐generation–driven approach delivered up to a two‐order‐of‐magnitude reduction in runtime compared to a naive local‐search algorithm applied directly to the full dataset. Moreover, when applied to the UCI real-world dataset, our method consistently produced exact designs with a negligible mixed‐integer programming (MIP) optimality gap, demonstrating that the restricted local search confined to the support of the limit problem guarantees the quality of the solution while drastically reducing computational overhead. In summary, by combining a column-generation viewpoint with second-order optimization techniques and a tailored local-search, we have demonstrated that exact D-optimal designs for large datasets with small to moderate features can be computed efficiently, reliably and accurately, also at scales several orders of magnitude larger than previously possible.