SPARSE HIGH-DIMENSIONAL REGRESSION Bertsimas, Dimitris; Van Parys, Bart
Annals of statistics,
02/2020, Volume:
48, Issue:
1
Journal Article
Peer reviewed
Open access
We present a novel binary convex reformulation of the sparse regression problem that constitutes a new duality perspective. We devise a new cutting plane method and provide evidence that it can solve ...to provable optimality the sparse regression problem for sample sizes n and number of regressors p in the 100,000s, that is, two orders of magnitude better than the current state of the art, in seconds. The ability to solve the problem for very high dimensions allows us to observe new phase transition phenomena. Contrary to traditional complexity theory which suggests that the difficulty of a problem increases with problem size, the sparse regression problem has the property that as the number of samples n increases the problem becomes easier in that the solution recovers 100% of the true signal, and our approach solves the problem extremely fast (in fact faster than Lasso), while for small number of samples n, our approach takes a larger amount of time to solve the problem, but importantly the optimal solution provides a statistically more relevant regressor. We argue that our exact sparse regression approach presents a superior alternative over heuristic methods available at present.
Optimal classification trees Bertsimas, Dimitris; Dunn, Jack
Machine learning,
07/2017, Volume:
106, Issue:
7
Journal Article
Peer reviewed
Open access
State-of-the-art decision tree methods apply heuristics recursively to create each split in isolation, which may not capture well the underlying characteristics of the dataset. The optimal decision ...tree problem attempts to resolve this by creating the entire decision tree at once to achieve global optimality. In the last 25 years, algorithmic advances in integer optimization coupled with hardware improvements have resulted in an astonishing 800 billion factor speedup in mixed-integer optimization (MIO). Motivated by this speedup, we present
optimal classification trees
, a novel formulation of the decision tree problem using modern MIO techniques that yields the optimal decision tree for axes-aligned splits. We also show the richness of this MIO formulation by adapting it to give
optimal classification trees with hyperplanes
that generates optimal decision trees with multivariate splits. Synthetic tests demonstrate that these methods recover the true decision tree more closely than heuristics, refuting the notion that optimal methods overfit the training data. We comprehensively benchmark these methods on a sample of 53 datasets from the UCI machine learning repository. We establish that these MIO methods are practically solvable on real-world datasets with sizes in the 1000s, and give average absolute improvements in out-of-sample accuracy over CART of 1–2 and 3–5% for the univariate and multivariate cases, respectively. Furthermore, we identify that optimal classification trees are likely to outperform CART by 1.2–1.3% in situations where the CART accuracy is high and we have sufficient training data, while the multivariate version outperforms CART by 4–7% when the CART accuracy or dimension of the dataset is low.
This paper considers the problem of integrating cross-docks (CDs) into a given retail supply network with the aim of minimizing related logistics costs. These comprise transportation costs, costs for ...setting up and operating CDs, inventory holding and purchasing costs. We present a novel mixed integer program (MIP) for optimizing the number and locations of CDs within the supply network as well as the selection of flow type (cross-docking or direct-to-warehouse shipping) and the associated delivery pattern tailored to a specific supplier. A numerical study shows that the original problem is difficult to solve for real-sized instances using a standard MIP solver. We therefore develop a hierarchical decomposition approach that achieves cost-efficient results compared to heuristic approaches, which assume linear transportation costs. In order to demonstrate the model’s applicability to real-life instances and to gain further practical insights we conducted a case study using data from a major European retail company. In this study we found that more than 6% of related logistics costs can be saved by setting up CDs within the supply network. We also show that existing approaches in literature may lead to unfavorable results in certain settings due to an overestimation of transportation bundling effects. Extensive numerical experiments and scenario analyses provide further managerial insights into the problem characteristics.
•Cross-dock facilities improve the efficiency of the supply network in retailing.•Considering the dependency between cross-dock location and operational planning.•Operational planning decides on delivery frequency and the delivery day.•Developing a hierarchical decomposition approach that solves real-sized instances.•A case study shows the benefits of the modeling and solution approach in retail.
•Mixed-integer linear programming model for optimizing renewable energy storage.•A clustering algorithm to approximate the optimal levelized cost of electricity.•Case study on providing power under ...different demand profiles in New York City.•Motivation for including backup storage options in addition to battery.
Intermittent solar and wind availabilities pose design and operational challenges for renewable power systems because they are asynchronous with consumer demand. To align this supply-demand mismatch, optimization-based design and scheduling models have been developed to minimize the capital and operational costs associated with power production and energy storage. However, hourly time discretization and large time horizons used to describe short- and long-term solar and wind dynamics, demand fluctuations, & price changes significantly increase the computational burden of solving these models. A decomposition algorithm based on agglomerative hierarchical clustering (AHC) is developed to alleviate the model complexity and optimize the system over representative time periods, instead of every hour. An advantage for AHC compared to other clustering methods is the preservation of time chronology, which is important for energy storage applications. The algorithm is applied to investigate a renewable power system with battery storage in New York City. Results show that a few representative time periods (5–15 days) sufficiently capture the system performance within 5% of the true optimal solution. The decomposition algorithm is suitable for investigating any optimization problem with time series data.
In this paper, we investigate dynamic traffic optimization in railway systems, i.e., the behavior of these systems through time when their movements are dictated by solutions to optimization models ...with finite horizons. As interactions between trains are not considered beyond the limits of finite horizons, the danger of leading the system into a deadlock arises. In this paper we present new procedures to establish finite prediction horizons that are formally guaranteed to operate the system in a way that is compatible with the physical constraints of the network while avoiding deadlocking and minimizing computations. The key to this result is the notion of recursive feasibility . This paper introduces conditions sufficient to attain it. We then discuss several important ramifications of recursive feasibility that enable efficient computations. We examine the possibility of decomposing the underlying optimization models into smaller models with shorter horizons, or into models that only consider subsets of all trains. We also discuss warm starting and anytime approaches. We finally perform numerical experiments verifying these results on models that include a real-world railway system used for freight transport. On harder instances, some of our approaches outperform solving the same models as monolithic MILPs by more than two order of magnitude in terms of median computation times, while also achieving better worst-case optimality gaps.
Unit commitment, one of the most critical tasks in electric power system operations, faces new challenges as the supply and demand uncertainty increases dramatically due to the integration of ...variable generation resources such as wind power and price responsive demand. To meet these challenges, we propose a two-stage adaptive robust unit commitment model for the security constrained unit commitment problem in the presence of nodal net injection uncertainty. Compared to the conventional stochastic programming approach, the proposed model is more practical in that it only requires a deterministic uncertainty set, rather than a hard-to-obtain probability distribution on the uncertain data. The unit commitment solutions of the proposed model are robust against all possible realizations of the modeled uncertainty. We develop a practical solution methodology based on a combination of Benders decomposition type algorithm and the outer approximation technique. We present an extensive numerical study on the real-world large scale power system operated by the ISO New England. Computational results demonstrate the economic and operational advantages of our model over the traditional reserve adjustment approach.
The ALAMO approach to machine learning Wilson, Zachary T.; Sahinidis, Nikolaos V.
Computers & chemical engineering,
11/2017, Volume:
106
Journal Article
Peer reviewed
Open access
•The ALAMO framework for building models is reviewed.•A review of the machine learning literature on model-building is presented.•ALAMO is illustrated through its application to learning problems in ...kinetics.
ALAMO is a computational methodology for learning algebraic functions from data. Given a data set, the approach begins by building a low-complexity, linear model composed of explicit non-linear transformations of the independent variables. Linear combinations of these non-linear transformations allow a linear model to better approximate complex behavior observed in real processes. The model is refined, as additional data are obtained in an adaptive fashion through error maximization sampling using derivative-free optimization. Models built using ALAMO can enforce constraints on the response variables to incorporate first-principles knowledge. The ability of ALAMO to generate simple and accurate models for a number of reaction problems is demonstrated. The error maximization sampling is compared with Latin hypercube designs to demonstrate its sampling efficiency. ALAMO's constrained regression methodology is used to further refine concentration models, resulting in models that perform better on validation data and satisfy upper and lower bounds placed on model outputs.
•We quantify the potential of EVs to utilize fluctuating RES through optimized charging.•We use empirical driving data to model the behavior of key sociodemographic groups.•Optimized charging can ...double the utilization of RES compared to simple charging.•Trip information is more relevant than charger availability to utilize EV flexibility.
Electric vehicles (EVs) are a new load type with considerable temporal flexibility. This work evaluates to what extent EV fleets (based on empirical driving profiles from two distinct sociodemographic groups) can cover their charging requirements by means of variable renewable generation (wind or solar-PV). For this purpose we formulate a mixed-integer optimization problem minimizing the amount of conventional generation employed. The results indicate that the usage of variable renewable generation can be more than doubled as compared to uncoordinated charging. Furthermore, we analyze how the utilization of renewable generation by EV fleets is affected through different portfolios of renewable generation sources, charging infrastructure specifications as well as a reduced optimization horizon.
•We study single or bilevel models, respectively, for flexible electricity tariffs to appropriately capture the incentives of retailers and consumers.•We consider the following flexible electricity ...tariffs: fixed-price, time-of-use, real-time-pricing, and critical-peak-pricing tariffs.•The tariffs are analyzed in a detailed computational study.•Real-time-pricing increases retailer profits, however, shifts all price risk to the prosumer.•Time-of-use and critical-peak-pricing only yield mild additional retailer profits.
We compare various flexible tariffs that have been proposed to cost-effectively govern a prosumer’s electricity management—in particular time-of-use (TOU), critical-peak-pricing (CPP), and a real-time-pricing tariff (RTP). As the outside option, we consider a fixed-price tariff (FP) that restricts the specific characteristics of TOU, CPP, and RTP, so that the flexible tariffs are at least as profitable for the prosumer as the FP tariff. We propose bilevel models to determine the optimal interplay between the retailer’s tariff design and the prosumer’s decisions on using the storage, on consumption, and on electricity purchases from as well as electricity sales to the grid. The single-level reformulations of the considered bilevel models are computationally highly challenging optimization problems since they combine bilinearities and mixed-integer aspects for modeling certain tariff structures. Based on a computational study using real-world data, we find that RTP increases retailer profits, however, leads to the largest price volatility for the prosumer. TOU and CPP only yield mild additional retailer profits and, due to the multiplicity of optimal plans on the part of the prosumer, imply uncertain revenues for the retailer.
This article presents a two-timescale duplex neurodynamic approach to mixed-integer optimization, based on a biconvex optimization problem reformulation with additional bilinear equality or ...inequality constraints. The proposed approach employs two recurrent neural networks operating concurrently at two timescales. In addition, particle swarm optimization is used to update the initial neuronal states iteratively to escape from local minima toward better initial states. In spite of its minimal system complexity, the approach is proven to be almost surely convergent to optimal solutions. Its superior performance is substantiated via solving five benchmark problems.
PDF
