Search

Sparse estimation for Gaussian graphical models is a crucial technique for making the relationships among numerous observed variables more interpretable and quantifiable. Various methods have been proposed, including graphical lasso, which utilizes the $\ell_1$ norm as a regularization term, as well as methods employing non-convex regularization terms. However, most of these methods approximate the $\ell_0$ norm with convex functions. To estimate more accurate solutions, it is desirable to treat the $\ell_0$ norm directly as a regularization term. In this study, we formulate the sparse estimation problem for Gaussian graphical models using the $\ell_0$ norm and propose a method to solve this problem using the Difference of Convex functions Algorithm (DCA). Specifically, we convert the $\ell_0$ norm constraint into an equivalent largest-$K$ norm constraint, reformulate the constrained problem into a penalized form, and solve it using the DC algorithm (DCA). Furthermore, we designed an algorithm that efficiently computes using graphical lasso. Experimental results with synthetic data show that our method yields results that are equivalent to or better than existing methods. Comparisons of model learning through cross-validation confirm that our method is particularly advantageous in selecting true edges.

This paper is concerned with personalized pricing models aimed at maximizing the expected revenues or profits for a single item. While it is essential for personalized pricing to predict the purchase probabilities for each consumer, these predicted values are inherently subject to unavoidable errors that can negatively impact the realized revenues and profits. To address this issue, we focus on robust optimization techniques that yield reliable solutions to optimization problems under uncertainty. Specifically, we propose a robust optimization model for personalized pricing that accounts for the uncertainty of predicted purchase probabilities. This model can be formulated as a mixed-integer linear optimization problem, which can be solved exactly using mathematical optimization solvers. We also develop a Lagrangian decomposition algorithm combined with line search to efficiently find high-quality solutions for large-scale optimization problems. Experimental results demonstrate the effectiveness of our robust optimization model and highlight the utility of our Lagrangian decomposition algorithm in terms of both computational efficiency and solution quality.

In a two-sided marketplace, network effects are crucial for competitiveness, and platforms need to retain users through advanced customer relationship management as much as possible. Maintaining numerous providers' stable and active presence on the platform is highly important to enhance the marketplace's scale and diversity. The strongest motivation for providers to continue using the platform is to realize actual profits through sales. Then, we propose a personalized promotion to increase the number of successful providers with sales experiences on the platform. The main contributions of our research are twofold. First, we introduce a new perspective in provider management with the distribution of successful sales experiences. Second, we propose a personalized promotion optimization method to maximize the number of providers' sales experiences. By utilizing this approach, we ensure equal opportunities for providers to experience sales without being monopolized by a few providers. Through experiments using actual data on coupon distribution, we confirm that our method enables the implementation of coupon allocation strategies that significantly increase the total number of providers having sales experiences., Comment: 8 pages, 10 figures, KDD 2024 Workshop on Two-sided Marketplace Optimization: Search, Pricing, Matching & Growth

In two-sided marketplaces such as online flea markets, recommender systems for providing consumers with personalized item rankings play a key role in promoting transactions between providers and consumers. Meanwhile, two-sided marketplaces face the problem of balancing consumer satisfaction and fairness among items to stimulate activity of item providers. Saito and Joachims (2022) devised an impact-based fair ranking method for maximizing the Nash social welfare based on fair division; however, this method, which requires solving a large-scale constrained nonlinear optimization problem, is very difficult to apply to practical-scale recommender systems. We thus propose a fast solution to the impact-based fair ranking problem. We first transform the fair ranking problem into an unconstrained optimization problem and then design a gradient ascent method that repeatedly executes the Sinkhorn algorithm. Experimental results demonstrate that our algorithm provides fair rankings of high quality and is about 1000 times faster than application of commercial optimization software.

This paper is concerned with portfolio optimization models for creating high-quality lists of recommended items to balance the accuracy and diversity of recommendations. However, the statistics (i.e., expectation and covariance of ratings) required for mean--variance portfolio optimization are subject to inevitable estimation errors. To remedy this situation, we focus on robust optimization techniques that derive reliable solutions to uncertain optimization problems. Specifically, we propose a robust portfolio optimization model that copes with the uncertainty of estimated statistics based on the cardinality-based uncertainty sets. This robust portfolio optimization model can be reduced to a mixed-integer linear optimization problem, which can be solved exactly using mathematical optimization solvers. Experimental results using two publicly available rating datasets demonstrate that our method can improve not only the recommendation accuracy but also the diversity of recommendations compared with conventional mean--variance portfolio optimization models. Notably, our method has the potential to improve the recommendation quality of various rating prediction algorithms.

This paper is concerned with the container pre-marshalling problem, which involves relocating containers in the storage area so that they can be efficiently loaded onto ships without reshuffles. In reality, however, ship arrival times are affected by various external factors, which can cause the order of container retrieval to be different from the initial plan. To represent such uncertainty, we generate multiple scenarios from a multivariate probability distribution of ship arrival times. We derive a mixed-integer linear optimization model to find an optimal container layout such that the conditional value-at-risk is minimized for the number of misplaced containers responsible for reshuffles. Moreover, we devise an exact algorithm based on the cutting-plane method to handle large-scale problems. Numerical experiments using synthetic datasets demonstrate that our method can produce high-quality container layouts compared with the conventional robust optimization model. Additionally, our algorithm can speed up the computation of solving large-scale problems.

In order to provide high-quality recommendations for users, it is desirable to share and integrate multiple datasets held by different parties. However, when sharing such distributed datasets, we need to protect personal and confidential information contained in the datasets. To this end, we establish a framework for privacy-preserving recommender systems using the data collaboration analysis of distributed datasets. Numerical experiments with two public rating datasets demonstrate that our privacy-preserving method for rating prediction can improve the prediction accuracy for distributed datasets. This study opens up new possibilities for privacy-preserving techniques in recommender systems.

Currently, many e-commerce websites issue online/electronic coupons as an effective tool for promoting sales of various products and services. We focus on the problem of optimally allocating coupons to customers subject to a budget constraint on an e-commerce website. We apply a robust portfolio optimization model based on customer segmentation to the coupon allocation problem. We also validate the efficacy of our method through numerical experiments using actual data from randomly distributed coupons. Main contributions of our research are twofold. First, we handle six types of coupons, thereby making it extremely difficult to accurately estimate the difference in the effects of various coupons. Second, we demonstrate from detailed numerical results that the robust optimization model achieved larger uplifts of sales than did the commonly-used multiple-choice knapsack model and the conventional mean-variance optimization model. Our results open up great potential for robust portfolio optimization as an effective tool for practical coupon allocation., Comment: 9 pages, 17 figures, AAAI-2024 Workshop on Artificial Intelligence for Operations Research

In recent years, the accumulation of data across various institutions has garnered attention for the technology of confidential data analysis, which improves analytical accuracy by sharing data between multiple institutions while protecting sensitive information. Among these methods, Data Collaboration Analysis (DCA) is noted for its efficiency in terms of computational cost and communication load, facilitating data sharing and analysis across different institutions while safeguarding confidential information. However, existing optimization problems for determining the necessary collaborative functions have faced challenges, such as the optimal solution for the collaborative representation often being a zero matrix and the difficulty in understanding the process of deriving solutions. This research addresses these issues by formulating the optimization problem through the segmentation of matrices into column vectors and proposing a solution method based on the generalized eigenvalue problem. Additionally, we demonstrate methods for constructing collaborative functions more effectively through weighting and the selection of efficient algorithms suited to specific situations. Experiments using real-world datasets have shown that our proposed formulation and solution for the collaborative function optimization problem achieve superior predictive accuracy compared to existing methods., Comment: 16 pages, 9 figures, preprint

We study the mixed-integer optimization (MIO) approach to feature subset selection in nonlinear kernel support vector machines (SVMs) for binary classification. First proposed for linear regression in the 1970s, this approach has recently moved into the spotlight with advances in optimization algorithms and computer hardware. The goal of this paper is to establish an MIO approach for selecting the best subset of features for kernel SVM classification. To measure the performance of subset selection, we use the kernel-target alignment, which is the distance between the centroids of two response classes in a high-dimensional feature space. We propose a mixed-integer linear optimization (MILO) formulation based on the kernel-target alignment for feature subset selection, and this MILO problem can be solved to optimality using optimization software. We also derive a reduced version of the MILO problem to accelerate our MILO computations. Experimental results show good computational efficiency for our MILO formulation with the reduced problem. Moreover, our method can often outperform the linear-SVM-based MILO formulation and recursive feature elimination in prediction performance, especially when there are relatively few data instances.

This paper studies a distributionally robust portfolio optimization model with a cardinality constraint for limiting the number of invested assets. We formulate this model as a mixed-integer semidefinite optimization (MISDO) problem by means of the moment-based ambiguity set of probability distributions of asset returns. To exactly solve large-scale problems, we propose a specialized cutting-plane algorithm that is based on bilevel optimization reformulation. We prove the finite convergence of the algorithm. We also apply a matrix completion technique to lower-level SDO problems to make their problem sizes much smaller. Numerical experiments demonstrate that our cutting-plane algorithm is significantly faster than the state-of-the-art MISDO solver SCIP-SDP. We also show that our portfolio optimization model can achieve good investment performance compared with the conventional robust optimization model based on the ellipsoidal uncertainty set.

This paper discusses the prediction of hierarchical time series, where each upper-level time series is calculated by summing appropriate lower-level time series. Forecasts for such hierarchical time series should be coherent, meaning that the forecast for an upper-level time series equals the sum of forecasts for corresponding lower-level time series. Previous methods for making coherent forecasts consist of two phases: first computing base (incoherent) forecasts and then reconciling those forecasts based on their inherent hierarchical structure. With the aim of improving time series predictions, we propose a structured regularization method for completing both phases simultaneously. The proposed method is based on a prediction model for bottom-level time series and uses a structured regularization term to incorporate upper-level forecasts into the prediction model. We also develop a backpropagation algorithm specialized for application of our method to artificial neural networks for time series prediction. Experimental results using synthetic and real-world datasets demonstrate the superiority of our method in terms of prediction accuracy and computational efficiency.

This paper studies mean-risk portfolio optimization models using the conditional value-at-risk (CVaR) as a risk measure. We also employ a cardinality constraint for limiting the number of invested assets. Solving such a cardinality-constrained mean-CVaR model is computationally challenging for two main reasons. First, this model is formulated as a mixed-integer optimization (MIO) problem because of the cardinality constraint, so solving it exactly is very hard when the number of investable assets is large. Second, the problem size depends on the number of asset return scenarios, and the computational efficiency decreases when the number of scenarios is large. To overcome these challenges, we propose a high-performance algorithm named the \emph{bilevel cutting-plane algorithm} for exactly solving the cardinality-constrained mean-CVaR portfolio optimization problem. We begin by reformulating the problem as a bilevel optimization problem and then develop a cutting-plane algorithm for solving the upper-level problem. To speed up computations for cut generation, we apply to the lower-level problem another cutting-plane algorithm for efficiently minimizing CVaR with a large number of scenarios. Moreover, we prove the convergence properties of our bilevel cutting-plane algorithm. Numerical experiments demonstrate that, compared with other MIO approaches, our algorithm can provide optimal solutions to large problem instances faster.

This paper examines the relationship between user pageview (PV) histories and their item-choice behavior on an e-commerce website. We focus on PV sequences, which represent time series of the number of PVs for each user--item pair. We propose a shape-restricted optimization model that accurately estimates item-choice probabilities for all possible PV sequences. This model imposes monotonicity constraints on item-choice probabilities by exploiting partial orders for PV sequences, according to the recency and frequency of a user's previous PVs. To improve the computational efficiency of our optimization model, we devise efficient algorithms for eliminating all redundant constraints according to the transitivity of the partial orders. Experimental results using real-world clickstream data demonstrate that our method achieves higher prediction performance than that of a state-of-the-art optimization model and common machine learning methods.

This paper is concerned with the nonparametric item response theory (NIRT) for estimating item characteristic curves (ICCs) and latent abilities of examinees on educational and psychological tests. In contrast to parametric models, NIRT models can estimate various forms of ICCs under mild shape restrictions, such as the constraints of monotone homogeneity and double monotonicity. However, NIRT models frequently suffer from estimation instability because of the great flexibility of nonparametric ICCs, especially when there is only a small amount of item-response data. To improve the estimation accuracy, we propose a novel NIRT model constrained by monotone homogeneity and smoothness based on ordered latent classes. Our smoothness constraints avoid overfitting of nonparametric ICCs by keeping them close to logistic curves. We also implement a tailored expectation--maximization algorithm to calibrate our smoothness-constrained NIRT model efficiently. We conducted computational experiments to assess the effectiveness of our smoothness-constrained model in comparison with the common two-parameter logistic model and the monotone-homogeneity model. The computational results demonstrate that our model obtained more accurate estimation results than did the two-parameter logistic model when the latent abilities of examinees for some test items followed bimodal distributions. Moreover, our model outperformed the monotone-homogeneity model because of the effect of the smoothness constraints.

This paper is concerned with a store-choice model for investigating consumers' store-choice behavior based on scanner panel data. Our store-choice model enables us to evaluate the effects of the consumer/product attributes not only on the consumer's store choice but also on his/her purchase quantity. Moreover, we adopt a mixed-integer optimization (MIO) approach to selecting the best set of explanatory variables with which to construct a store-choice model. We devise two MIO models for hierarchical variable selection in which the hierarchical structure of product categories is used to enhance the reliability and computational efficiency of the variable selection. We assess the effectiveness of our MIO models through computational experiments on actual scanner panel data. These experiments are focused on the consumer's choice among three types of stores in Japan: convenience stores, drugstores, and grocery supermarkets. The computational results demonstrate that our method has several advantages over the common methods for variable selection, namely, the stepwise method and $L_1$-regularized regression. Furthermore, our analysis reveals that convenience stores tend to be chosen because of accessibility, drugstores are chosen for the purchase of specific products at low prices, and grocery supermarkets are chosen for health food products by women with families.

This paper analyzes customer product-choice behavior based on the recency and frequency of each customer's page views on e-commerce sites. Recently, we devised an optimization model for estimating product-choice probabilities that satisfy monotonicity, convexity, and concavity constraints with respect to recency and frequency. This shape-restricted model delivered high predictive performance even when there were few training samples. However, typical e-commerce sites deal in many different varieties of products, so the predictive performance of the model can be further improved by integration of such product heterogeneity. For this purpose, we develop a novel latent-class shape-restricted model for estimating product-choice probabilities for each latent class of products. We also give a tailored expectation-maximization algorithm for parameter estimation. Computational results demonstrate that higher predictive performance is achieved with our latent-class model than with the previous shape-restricted model and common latent-class logistic regression.

This paper concerns a method of selecting a subset of features for a sequential logit model. Tanaka and Nakagawa (2014) proposed a mixed integer quadratic optimization formulation for solving the problem based on a quadratic approximation of the logistic loss function. However, since there is a significant gap between the logistic loss function and its quadratic approximation, their formulation may fail to find a good subset of features. To overcome this drawback, we apply a piecewise-linear approximation to the logistic loss function. Accordingly, we frame the feature subset selection problem of minimizing an information criterion as a mixed integer linear optimization problem. The computational results demonstrate that our piecewise-linear approximation approach found a better subset of features than the quadratic approximation approach.