Search

Given the abundance of images related to operations that are being captured and stored, it behooves firms to innovate systems using image processing to improve operational performance that refers to any activity that can save labor cost. In this paper, we use deep learning techniques, combined with classic image/signal processing methods, to propose a pipeline to solve certain types of object counting and layer characterization problems in firm operations. Using data obtained by us through a collaborative effort with real manufacturers, we demonstrate that the proposed pipeline method is able to achieve higher than 93% accuracy in layer and log counting. Theoretically, our study conceives, constructs, and evaluates proof of concept of a novel pipeline method in characterizing and quantifying the number of defined items with images, which overcomes the limitations of methods based only on deep learning or signal processing. Practically, our proposed method can help firms significantly reduce labor costs and/or improve quality and inventory control by recording the number of products in real time, more accurately and with minimal up-front technological investment. The codes and data are made publicly available online through the INFORMS Journal on Computing GitHub site. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0260) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0260). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0019) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0019). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We apply supervised learning to a general problem in queueing theory: using a neural net, we develop a fast and accurate predictor of the stationary system-length distribution of a GI/GI/1 queue—a fundamental queueing model for which no analytical solutions are available. To this end, we must overcome three main challenges: (i) generating a large library of training instances that cover a wide range of arbitrary interarrival and service time distributions, (ii) labeling the training instances, and (iii) providing continuous arrival and service distributions as inputs to the neural net. To overcome (i), we develop an algorithm to sample phase-type interarrival and service time distributions with complex transition structures. We demonstrate that our distribution-generating algorithm indeed covers a wide range of possible positive-valued distributions. For (ii), we label our training instances via quasi-birth-and-death(QBD) that was used to approximate PH/PH/1 (with phase-type arrival and service process) as labels for the training data. For (iii), we find that using only the first five moments of both the interarrival and service times distribution as inputs is sufficient to train the neural net. Our empirical results show that our neural model can estimate the stationary behavior of the GI/GI/1—far exceeding other available methods in terms of both accuracy and runtimes. History: Ram Ramesh, Area Editor for Data Science and Machine Learning. Funding: O. Baron received financial support from the Natural Sciences and Engineering Research Council of Canada (NERC) [Grant 458051]. D. Krass received financial support from the NERC [Grant 458395]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0263) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0263). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. When incorporated inside branch-and-bound, the cutting planes obtained from CGLPs help to tighten relaxations and improve dual bounds. However, running the CGLPs at the nodes of the branch-and-bound tree is computationally cumbersome due to the large number of node candidates and the lack of a priori knowledge on which nodes admit useful cutting planes. As a result, CGLPs are often avoided at default settings of branch-and-cut algorithms despite their potential impact on improving dual bounds. In this paper, we propose a novel framework based on machine learning to approximate the optimal value of a CGLP class that determines whether a cutting plane can be generated at a node of the branch-and-bound tree. Translating the CGLP as an indicator function of the objective function vector, we show that it can be approximated through conventional data classification techniques. We provide a systematic procedure to efficiently generate training data sets for the corresponding classification problem based on the CGLP structure. We conduct computational experiments on benchmark instances using classification methods such as logistic regression. These results suggest that the approximate CGLP obtained from classification can improve the solution time compared with that of conventional cutting plane methods. Our proposed framework can be efficiently applied to a large number of nodes in the branch-and-bound tree to identify the best candidates for adding a cut. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0241. [ABSTRACT FROM AUTHOR]

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0384. [ABSTRACT FROM AUTHOR]

We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programs. We aim at solving problems where the second stage is demanding. Our core idea is to gain large reductions in online solution time, while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate, supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time—for example, in transport planning related to fleet management, routing, and container yard management. Our numerical results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and stochastic multi-knapsack (SMKP) problems available in the literature. The proposed method can solve the hardest instances of SSLP in less than 9% of the time it takes the state-of-the-art exact method, and in the case of SMKP, the same figure is 20%. Average optimality gaps are, in most cases, less than 0.1%. History: Accepted by Alice Smith, Area Editor (for this paper) for Design and Analysis of Algorithms–Discrete. Funding: Financial support from the Institut de Valorisation des Données (IVADO) Fundamental Research Project Grants [project entitled "Machine Learning for (Discrete) Optimization"]; Canada Research Chairs; the Natural Sciences and Engineering Research Council of Canada [Collaborative Research and Development Grant CRD-477938-14]; and the Canadian National Railway Company Chair in Optimization of Railway Operations at Université de Montréal is gratefully acknowledged. E. Frejinger holds a Canada Research Chair. Computations were made on the supercomputer Béluga, managed by Calcul Québec and Digital Research Alliance of Canada. The operation of this supercomputer is funded by the Canada Foundation for Innovation; the Ministère de l'Économie, de la Science et de l'Innovation du Québec; and the Fonds de Recherche du Québec – Nature et Technologies. [ABSTRACT FROM AUTHOR]

Federated learning is a new distributed machine learning framework, where numerous heterogeneous clients collaboratively train a model without sharing training data. In this work, we consider a practical and ubiquitous issue when deploying federated learning in mobile environments: intermittent client availability, where the set of eligible clients may change during the training process. Such intermittent client availability would seriously deteriorate the performance of the classical federated averaging algorithm (FedAvg). Thus, we propose a simple distributed nonconvex optimization algorithm, called federated latest averaging (FedLaAvg), which leverages the latest gradients of all clients, even when the clients are not available, to jointly update the global model in each iteration. Our theoretical analysis shows that FedLaAvg achieves guaranteed convergence and a sublinear speedup with respect to the total number of clients. We implement FedLaAvg along with several baselines and evaluate them over the benchmarking MNIST and Sentiment140 data sets. The evaluation results demonstrate that FedLaAvg achieves more stable training than FedAvg in both convex and nonconvex settings and reaches a sublinear speedup. Source code and online supplement are available at the IJOC GitHub site (http://dx.doi.org/10.1287/ijoc.2022.0057.cd, https://github.com/INFORMSJoC/2022.0057). History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Leaning. Funding: This work was supported by the National Key R&D Program of China [Grant 2022ZD0119100], the National Natural Science Foundation of China (NSFC) [Grants 61972252, 61972254, 62072303, 62025204, 62132018, 62202296, and 62202297], the Alibaba Innovation Research (AIR) Program, and the Tencent Rhino Bird Key Research Project. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0057) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0057). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]