Search

The advancement of autonomous capabilities in maritime navigation has gained significant attention, with a trajectory moving from decision support systems to full autonomy. This push towards autonomy has led to extensive research focusing on collision avoidance, a critical aspect of safe navigation. Among the various possible approaches, dynamic programming is a promising tool for optimizing collision avoidance maneuvers. This paper presents a DP formulation for the collision avoidance of autonomous vessels. We set up the problem framework, formulate it as a multi-stage decision process, define cost functions and constraints focusing on the actual requirements a marine maneuver must comply with, and propose a solution algorithm leveraging parallel computing. Additionally, we present a greedy approximation to reduce algorithm complexity. We put the proposed algorithms to the test in realistic navigation scenarios and also develop an extensive test on a large set of randomly generated scenarios, comparing them with the RRT* algorithm using performance metrics proposed in the literature. The results show the potential benefits of an autonomous navigation or decision support framework. [ABSTRACT FROM AUTHOR]

Problem definition: We investigate the effects of waiting time, mainly due to production in a make-to-batch-order (MTBO) system, on consumer choice behavior, pricing, assortment, and model estimation. In an MTBO system, the seller/manufacturer first collects orders placed within a certain period of time into a batch and then starts the production process. After the production of all orders in a batch are complete, the products are then shipped and delivered to individual consumers. Because of batch production and shipping, the disutility of the waiting time exhibits negative externality. Methodology/results: We adopt the widely used multinomial logit (MNL) model as a starting point and incorporate the anticipated wait into consumers' decision making. The derived model, referred to as the MNL with wait model, is a solution of the rational expectation equilibrium and is capable of capturing the effects of negative externality induced by anticipated wait that may change the substitution patterns dramatically. We characterize the multiproduct price optimization problem under the MNL with wait model by establishing a one-to-one mapping between the price vector and the choice probability vector. We find that firms tend to charge higher prices for time-consuming items and charge lower prices for time-saving items compared with the optimal prices under the standard MNL model. In addition to price competition, we also study the Cournot-type competition, in which the decision is the choice probability for each firm and establish the existence of a Nash equilibrium. For assortment optimization, we identify mild conditions under which the optimality of revenue-ordered assortments still holds. However, the assortment problem under the MNL with wait model is generally NP-hard, so we develop approximation algorithms with performance guarantees and provide an easy-to-compute tight upper bound. Moreover, we develop an efficient maximum likelihood-based algorithm for model calibration and further conduct numerical studies to showcase the importance of incorporating disutility due to wait in estimation, pricing, and assortment planning problems. Managerial implications: The MNL with wait model can increase prediction accuracy for consumers' choice behavior especially when they are aware of the potential wait. Failure to take into account the effects of anticipated wait in firms' decision making may lead to substantial losses. Funding: The research of C. Ke is supported in part by the National Natural Science Foundation of China [Grant 72101113]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2020.0346. [ABSTRACT FROM AUTHOR]

Multiobjective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multiobjective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multiobjective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multiobjective shortest-path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA)—the go-to approach for tackling optimization problems on near-term quantum computers—we examine the Pareto plot that results from the scheme and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA and identify key challenges associated with this approach. Finally, through Amazon Braket, we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.

In this paper we analyze the links between the agent's reservation utility, bargaining power, and risk aversion in terms of their simultaneous effects on the structure of optimal static contracts. We compare the following principal-agent models in the symmetric and asymmetric information environments: the standard approach, which includes a participation constraint, and a multi-objective (MO) optimization approach in which the objective function is a convex combination of the expected utilities of the principal and the agent. The MO model does not include a participation constraint, but it includes a parameter for the agent's bargaining power. We also study an Evolutionary Algorithm implementation of the static principal-agent model to support and extend our analytical results. We show that the numerical solution approximated by our implementation of an evolutionary algorithm is in line with the analytical solutions mentioned before. That is, for every admissible value of the agent's reservation utility, there is a corresponding admissible value of the agent's bargaining parameter, both in the MO approach and the EA implementation. [ABSTRACT FROM AUTHOR]

In "Sequential Competitive Facility Location: Exact and Approximate Algorithms," Qi et al. consider a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets and maximize their market shares of demand following a probabilistic choice model. They derive an equivalent, single-level mixed-integer nonlinear program (MINLP) reformulation of the bilevel MINLP and exploit the problem structures to derive valid inequalities based on submodularity and concave overestimation. They also develop an approximation algorithm with a constant approximation guarantee. They further study several extensions of CFLP that have general facility-opening costs, outside competitors, and diverse facility-planning decisions. Their approaches significantly accelerate the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods. We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation and exploit the problem structures to derive two valid inequalities based on submodularity and concave overestimation, respectively. We use the two valid inequalities in a branch-and-cut algorithm to find globally optimal solutions. Then, we propose an approximation algorithm to find good-quality solutions with a constant approximation guarantee. We develop several extensions by considering general facility-opening costs and outside competitors as well as diverse facility-planning decisions, and we discuss solution approaches for each extension. We conduct numerical studies to demonstrate that the exact algorithm significantly accelerates the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods, and the approximation algorithm can quickly find high-quality solutions. We derive managerial insights based on sensitivity analysis of different settings that affect customers' probabilistic choices and the ensuing demand. Funding: M. Qi was partially supported by the National Natural Science Foundation of China [Grant 71772100] to work on this project. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2339. [ABSTRACT FROM AUTHOR]

The integrated industrial control systems require a reliable communication among each part of control systems. The limitation of network topology comprises the low latency of data transmission. The network algorithm topologies are sometimes failed to ensure the faulttolerant network design even if they offer it. Therefore, this works investigates a Node Insertion Algorithm (NIA) and Ant Colony Optimization (ACO) in order to solve the Travelling Salesman Problem (TSP) for network topologies in a communication network. The NP Non deterministic (polynomial time)-hardness based of TSP leads to the impossibility of polynomial time algorithm to solve an exponentially increasing amount of communication addresses. TSP itself is a well-known solution method known in the graph theory which is based on approximation algorithm. Therefore, this work also presents a comparison between the NIA and ACO for 200 nodes of network topologies. The results show that NIA is superior than ACO in terms of resulting ring's cost and computation duration. Three topologies are tested and it is observable that NIA requires only 14.88 seconds to finish the computation in which the resulting ring's length reaches 164019 units. Therefore, the achievement of the NIA can be applied for logical and physical nodes for a reliable connection in an industrial topology network. [ABSTRACT FROM AUTHOR]

Cybersecurity planning supports the selection of and implementation of security controls in resource-constrained settings to manage risk. Doing so requires considering adaptive adversaries with different levels of strategic sophistication in modeling efforts to support risk management. However, most models in the literature only consider rational or nonstrategic adversaries. Therefore, we study how to inform defensive decision making to mitigate the risk from boundedly rational players, with a particular focus on making integrated, interdependent planning decisions. To achieve this goal, we introduce a modeling framework for selecting a portfolio of security mitigations that interdict adversarial attack plans that uses a structured approach for risk analysis. Our approach adapts adversarial risk analysis and cognitive hierarchy theory to consider a maximum-reliability path interdiction problem with a single defender and multiple attackers who have different goals and levels of strategic sophistication. Instead of enumerating all possible attacks and defenses, we introduce a solution technique based on integer programming and approximation algorithms to iteratively solve the defender's and attackers' problems. A case study illustrates the proposed models and provides insights into defensive planning. Funding: A. Peper and L. A. Albert were supported in part by the National Science Foundation [Grant 2000986]. [ABSTRACT FROM AUTHOR]

Problem definition: On-demand delivery has become increasingly popular around the world. Motivated by a large grocery chain store who offers fast on-demand delivery services, we model and solve a stochastic dynamic driver dispatching and routing problem for last-mile delivery systems where on-time performance is the main target. The system operator needs to dispatch a set of drivers and specify their delivery routes facing random demand that arrives over a fixed number of periods. The resulting stochastic dynamic program is challenging to solve because of the curse of dimensionality. Methodology/results: We propose a novel structured approximation framework to approximate the value function via a parametrized dispatching and routing policy. We analyze the structural properties of the approximation framework and establish its performance guarantee under large-demand scenarios. We then develop efficient exact algorithms for the approximation problem based on Benders decomposition and column generation, which deliver verifiably optimal solutions within minutes. Managerial implications: The evaluation results on a real-world data set show that our framework outperforms the current policy of the company by 36.53% on average in terms of delivery time. We also perform several policy experiments to understand the value of dynamic dispatching and routing with varying fleet sizes and dispatch frequencies. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72222011 and 72171112], China Association for Science and Technology [Grant 2019QNRC001], and the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2022-04950]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/msom.2022.1171. [ABSTRACT FROM AUTHOR]

How can we efficiently find very large numbers of clusters C in very large datasets N of potentially high dimensionality D? Here we address the question by using a novel variational approach to optimize Gaussian mixture models (GMMs) with diagonal covariance matrices. The variational method approximates expectation maximization (EM) by applying truncated posteriors as variational distributions and partial E-steps in combination with coresets. Run time complexity to optimize the clustering objective then reduces from O(NCD) per conventional EM iteration to O(N′G2D) for a variational EM iteration on coresets (with coreset size N ′ ≤ N and truncation parameter G ≪ C). Based on the strongly reduced run time complexity per iteration, which scales sublinearly with NC, we then provide a concrete, practically applicable, parallelized and highly efficient clustering algorithm. In numerical experiments on standard large-scale benchmarks we (A) show that also overall clustering times scale sublinearly with NC, and (B) observe substantial wall-clock speedups compared to already highly efficient recently reported results. The algorithm’s sublinear scaling allows for applications at scales where alternative methods cease to be applicable. We demonstrate such very large-scale applicability using the YFCC100M benchmark, for which we realize with a GMM of up to 50.000 clusters an optimization of a data density model with up to 150 M parameters. [ABSTRACT FROM AUTHOR]

Adversarial attacks have been extensively studied in recent years since they can identify the vulnerability of deep learning models before deployed. In this paper, we consider the black-box adversarial setting, where the adversary needs to craft adversarial examples without access to the gradients of a target model. Previous methods attempted to approximate the true gradient either by using the transfer gradient of a surrogate white-box model or based on the feedback of model queries. However, the existing methods inevitably suffer from low attack success rates or poor query efficiency since it is difficult to estimate the gradient in a high-dimensional input space with limited information. To address these problems and improve black-box attacks, we propose two prior-guided random gradient-free (PRGF) algorithms based on biased sampling and gradient averaging, respectively. Our methods can take the advantage of a transfer-based prior given by the gradient of a surrogate model and the query information simultaneously. Through theoretical analyses, the transfer-based prior is appropriately integrated with model queries by an optimal coefficient in each method. Extensive experiments demonstrate that, in comparison with the alternative state-of-the-arts, both of our methods require much fewer queries to attack black-box models with higher success rates. [ABSTRACT FROM AUTHOR]

This article presents a rough-to-fine evolutionary multiobjective optimization algorithm based on the decomposition for solving problems in which the solutions are initially far from the Pareto-optimal set. Subsequently, a tree is constructed by a modified $k$ -means algorithm on $N$ uniform weight vectors, and each node of the tree contains a weight vector. Each node is associated with a subproblem with the help of its weight vector. Consequently, a subproblem tree can be established. It is easy to find that the descendant subproblems are refinements of their ancestor subproblems. The proposed algorithm approaches the Pareto front (PF) by solving a few subproblems in the first few levels to obtain a rough PF and gradually refining the PF by involving the subproblems level-by-level. This strategy is highly favorable for solving problems in which the solutions are initially far from the Pareto set. Moreover, the proposed algorithm has lower time complexity. Theoretical analysis shows the complexity of dealing with a new candidate solution is $\mathcal {O}(M \log N)$ , where $M$ is the number of objectives. Empirical studies demonstrate the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper revisits the temporal difference (TD) learning algorithm for the policy evaluation tasks in reinforcement learning. Typically, the performance of TD(0) and TD($\lambda$ λ ) is very sensitive to the choice of stepsizes. Oftentimes, TD(0) suffers from slow convergence. Motivated by the tight link between the TD(0) learning algorithm and the stochastic gradient methods, we develop a provably convergent adaptive projected variant of the TD(0) learning algorithm with linear function approximation that we term AdaTD(0). In contrast to the TD(0), AdaTD(0) is robust or less sensitive to the choice of stepsizes. Analytically, we establish that to reach an $\epsilon$ ε accuracy, the number of iterations needed is $\tilde{O}(\epsilon ^{-2}\ln ^4\frac{1}{\epsilon }/\ln ^4\frac{1}{\rho })$ O ˜ (ε - 2 ln 4 1 ε / ln 4 1 ρ) in the general case, where $\rho$ ρ represents the speed of the underlying Markov chain converges to the stationary distribution. This implies that the iteration complexity of AdaTD(0) is no worse than that of TD(0) in the worst case. When the stochastic semi-gradients are sparse, we provide theoretical acceleration of AdaTD(0). Going beyond TD(0), we develop an adaptive variant of TD($\lambda$ λ ), which is referred to as AdaTD($\lambda$ λ ). Empirically, we evaluate the performance of AdaTD(0) and AdaTD($\lambda$ λ ) on several standard reinforcement learning tasks, which demonstrate the effectiveness of our new approaches. [ABSTRACT FROM AUTHOR]

Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and the scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy-tensor estimating error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy. [ABSTRACT FROM AUTHOR]

One of the most extensively studied combinatorial optimization problems is the Travelling Salesman Problem (TSP). Considerable research efforts in the past have resulted in exact solvers. However, the runtime of such hand-crafted solutions increases exponentially with problem size. Ising model based solvers have also gained prominence due to their abilities to find fast and approximate solutions for combinatorial optimization problems. However, such Ising based heuristics also suffer from scalability as the solution quality becomes increasingly sub-optimal with increase in problem size. In this work, we propose Neuro-Ising – a machine learning framework which uses Ising models to find clusters of near-optimal partial solutions of large scale TSPs and combines those solutions by employing a supervised data driven mechanism, which we model as a Graph Neural Network (GNN). The GNN is trained from solution instances obtained through exact solvers and hence, the proposed approach generalizes to unseen problems while avoiding the run-time complexity otherwise required, if the solution is built from scratch. Using standard computing resources, our proposed framework rapidly converges to near-optimal solutions for 15 TSPs (upto $\sim 5k$ cities) from the TSPLib benchmark suite. We report $\sim 10.66\times $ speedup over Tabu Search for 8 problems. Furthermore, compared to two state-of-the-art clustering-based TSP solvers, Neuro-Ising achieves $\sim 38 \times $ faster convergence along with $\sim 8.9\%$ better quality of solution, on average. [ABSTRACT FROM AUTHOR]

Owing to its good compression ability, discrete cosine transform (DCT) is widely used in signal processing, including high-efficiency video coding (HEVC). For efficient implementation, approximate DCTs and integer DCTs were proposed, but the challenge in the tradeoff between coding performance and implementation cost always exists. To solve this problem, this article proposes a new algorithm to derive Int-DCT with good coding performance and low hardware cost. To address the multiobjective optimization problem, we extract information from the initially shortlisted transform matrices to derive the weighting factors for the different matrices properties. Those properties having a higher impact to the performance are assigned with higher weights and vice versa. Subsequently, an efficient search algorithm is proposed to shortlist those candidates which can lead to better coding performance evaluated by the proposed measure. Last but not the least, a splitting method is proposed to search the efficient extended double-base number system (EDBNS) representation of the coefficients for hardware implementation and select the solution which encounters the lowest cost. The experimental results in ASIC demonstrate that the implementation area and power cost of designs by the new algorithm are reduced by at least 11.1% and 17.5% for 32-point transform, respectively, over other competing algorithms. Meanwhile, the transforms generated by the proposed algorithm causes negligible impact to coding performance compared to the original transforms in HEVC. [ABSTRACT FROM AUTHOR]

This article deals with nonconvex stochastic optimization problems in deep learning. Appropriate learning rates, based on theory, for adaptive-learning-rate optimization algorithms (e.g., Adam and AMSGrad) to approximate the stationary points of such problems are provided. These rates are shown to allow faster convergence than previously reported for these algorithms. Specifically, the algorithms are examined in numerical experiments on text and image classification and are shown in experiments to perform better with constant learning rates than algorithms using diminishing learning rates. [ABSTRACT FROM AUTHOR]

This article introduces a new deep learning approach to approximately solve the covering salesman problem (CSP). In this approach, given the city locations of a CSP as input, a deep neural network model is designed to directly output the solution. It is trained using the deep reinforcement learning without supervision. Specifically, in the model, we apply the multihead attention (MHA) to capture the structural patterns, and design a dynamic embedding to handle the dynamic patterns of the problem. Once the model is trained, it can generalize to various types of CSP tasks (different sizes and topologies) without the need of retraining. Through controlled experiments, the proposed approach shows desirable time complexity: it runs more than 20 times faster than the traditional heuristic solvers with a tiny gap of optimality. Moreover, it significantly outperforms the current state-of-the-art deep learning approaches for combinatorial optimization in the aspect of both training and inference. In comparison with traditional solvers, this approach is highly desirable for most of the challenging tasks in practice that are usually large scale and require quick decisions. [ABSTRACT FROM AUTHOR]

We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as xq, q≥ 1, with the amount x of resources used. We define a novel linear programming relaxation for such problems and then show that the integrality gap of the relaxation is Aq, where Aq is the q-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for the Minimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. Our analysis relies on the decoupling inequality for nonnegative random variables. The inequality states that ║∑i=1nXi║q ≤ Cq║∑i=1nYi║q, where Xi are independent nonnegative random variables, Yi are possibly dependent nonnegative random variables, and each Yi has the same distribution as Xi. The inequality was proved by de la Peña in 1990. De la Peña, Ibragimov, and Sharakhmetov showed that Cq≤ 2 for q∈(1,2) and Cq≤ Aq1/q for q≥ 2. We show that the optimal constant is Cq= Aq1/q for any q≥ 1. We then prove a more general inequality: For every convex function ϕ, E[ϕ(∑i=1nXi)] ≤ E[ϕ (P∑i=1n Yi)], and, for every concave function ψ, E[ψ (∑i=1n Xi)] ≥ E[ψ(P∑i=1n Yi)], where P is a Poisson random variable with parameter 1 independent of the random variables Yi. [ABSTRACT FROM AUTHOR]

In a large cloud data center HPC system, a critical problem is how to allocate the submitted tasks to heterogeneous servers that will achieve the goal of maximizing the system’s gain defined as the value of completed tasks minus system operation costs. We consider this problem in the online setting that tasks arrive in batches and propose a novel deep reinforcement learning (DRL) enhanced greedy optimization algorithm of two-stage scheduling interacting task sequencing and task allocation. For task sequencing, we deploy a DRL module to predict the best allocation sequence for each arriving batch of tasks based on the knowledge (allocation strategies) learnt from previous batches. For task allocation, we propose a greedy strategy that allocates tasks to servers one by one online following the allocation sequence to maximize the total gain increase. We show that our greedy strategy has a performance guarantee of competitive ratio $\frac{1}{1+\kappa }$ 1 1 + κ to the optimal offline solution, which improves the existing result for the same problem, where $\kappa$ κ is upper bounded by the maximum cost-to-gain ratio of each task. While our DRL module enhances the greedy algorithm by providing the likely-optimal allocation sequence for each batch of arriving tasks, our greedy strategy bounds DRL’s prediction error within a proven worst-case performance guarantee for any allocation sequence. It enables a better solution quality than that obtainable from both DRL and greedy optimization alone. Extensive experiment evaluation results in both simulation and real application environments demonstrate the effectiveness and efficiency of our proposed algorithm. Compared with the state-of-the-art baselines, our algorithm increases the system gain by about 10% to 30%. Our algorithm provides an interesting example of combining machine learning (ML) and greedy optimization techniques to improve ML-based solutions with a worst-case performance guarantee for solving hard optimization problems. [ABSTRACT FROM AUTHOR]

This brief addresses the problem of implementing very large constant multiplications by a single variable under the shift-adds architecture using a minimum number of adders/subtractors. Due to the intrinsic complexity of the problem, we introduce an approximate algorithm, called TÕLL, which partitions the very large constants into smaller ones. To reduce the number of operations, TÕLL incorporates graph-based and common subexpression elimination methods proposed for the shift-adds design of constant multiplications. It can also consider the delay of a multiplierless design defined in terms of the maximum number of operations in series, i.e., the number of adder-steps, while reducing the number of operations. High-level experimental results show that the adder-steps of a shift-adds design can be reduced significantly with a little overhead in the number of operations. Gate-level experimental results indicate that while the shift-adds design can lead to a 36.6% reduction in gate-level area with respect to a design using a multiplier, the delay-aware optimization can yield a 48.3% reduction in minimum achievable delay of the shift-adds design when compared to the area-aware optimization. [ABSTRACT FROM AUTHOR]

Jobs in modern parallel-computing frameworks, such as Hadoop and Spark, are subject to several constraints. In these frameworks, the data are typically distributed across a cluster of machines and is processed in multiple stages. Therefore, tasks that belong to the same stage (job) have a collective completion time that is determined by the slowest task in the collection. Furthermore, a task's processing time is machine dependent, and each machine is capable of processing multiple tasks at a time subject to its capacity. In "Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints," by Mehrnoosh Shafiee and Javad Ghaderi, multiple approximation algorithms with theoretical guarantees are provided to solve the problem under preemptive and nonpreemptive scenarios. The numerical results, using a real traffic trace, demonstrate that the algorithms yield significant gains over the prior approaches. Motivated by modern parallel computing applications, we consider the problem of scheduling parallel-task jobs with heterogeneous resource requirements in a cluster of machines. Each job consists of a set of tasks that can be processed in parallel; however, the job is considered completed only when all its tasks finish their processing, which we refer to as the synchronization constraint. Furthermore, assignment of tasks to machines is subject to placement constraints, that is, each task can be processed only on a subset of machines, and processing times can also be machine dependent. Once a task is scheduled on a machine, it requires a certain amount of resource from that machine for the duration of its processing. A machine can process (pack) multiple tasks at the same time; however, the cumulative resource requirement of the tasks should not exceed the machine's capacity. Our objective is to minimize the weighted average of the jobs' completion times. The problem, subject to synchronization, packing, and placement constraints, is NP-hard, and prior theoretical results only concern much simpler models. For the case that migration of tasks among the placement-feasible machines is allowed, we propose a preemptive algorithm with an approximation ratio of (6 + ϵ). In the special case that only one machine can process each task, we design an algorithm with an improved approximation ratio of four. Finally, in the case that migrations (and preemptions) are not allowed, we design an algorithm with an approximation ratio of 24. Our algorithms use a combination of linear program relaxation and greedy packing techniques. We present extensive simulation results, using a real traffic trace, that demonstrate that our algorithms yield significant gains over the prior approaches. Funding: This work was supported by the National Science Foundation [Grants CNS-1652115 and CNS-1717867]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2021.2198. [ABSTRACT FROM AUTHOR]

Convolutional transform learning (CTL), learning filters by minimizing the data fidelity loss function in an unsupervised way, is becoming very pervasive, resulting from keeping the best of both worlds: the benefit of unsupervised learning and the success of the convolutional neural network. There have been growing interests in developing efficient CTL algorithms. However, developing a convergent and accelerated CTL algorithm with accurate representations simultaneously with proper sparsity is an open problem. This article presents a new CTL framework with a $log$ regularizer that can not only obtain accurate representations but also yield strong sparsity. To efficiently address our nonconvex composite optimization, we propose to employ the proximal difference of the convex algorithm (PDCA) which relies on decomposing the nonconvex regularizer into the difference of two convex parts and then optimizes the convex subproblems. Furthermore, we introduce the extrapolation technology to accelerate the algorithm, leading to a fast and efficient CTL algorithm. In particular, we provide a rigorous convergence analysis for the proposed algorithm under the accelerated PDCA. The experimental results demonstrate that the proposed algorithm can converge more stably to desirable solutions with lower approximation error and simultaneously with stronger sparsity and, thus, learn filters efficiently. Meanwhile, the convergence speed is faster than the existing CTL algorithms. [ABSTRACT FROM AUTHOR]

Bilevel optimization involves two levels of optimization, where one optimization problem is nested within the other. The structure of the problem often requires solving a large number of inner optimization problems that make these kinds of optimization problems expensive to solve. The reaction set mapping and the lower level optimal value function mapping are often used to reduce bilevel optimization problems to a single level; however, the mappings are not known a priori, and the need is to be estimated. Though there exist a few studies that rely on the estimation of these mappings, they are often applied to problems where one of these mappings has a known form, that is, piecewise linear, convex, etc. In this article, we utilize both these mappings together to solve general bilevel optimization problems without any assumptions on the structure of these mappings. Kriging approximations are created during the generations of an evolutionary algorithm, where the population members serve as the samples for creating the approximations. One of the important features of the proposed algorithm is the creation of an auxiliary optimization problem using the Kriging-based metamodel of the lower level optimal value function that solves an approximate relaxation of the bilevel optimization problem. The auxiliary problem when used for local search is able to accelerate the evolutionary algorithm toward the bilevel optimal solution. We perform experiments on two sets of test problems and a problem from the domain of control theory. Our experiments suggest that the approach is quite promising and can lead to substantial savings when solving bilevel optimization problems. The approach is able to outperform state-of-the-art methods that are available for solving bilevel problems, in particular, the savings in function evaluations for the lower level problem are substantial with the proposed approach. [ABSTRACT FROM AUTHOR]

By employing time-varying proximal functions, adaptive subgradient methods (ADAGRAD) have improved the regret bound and been widely used in online learning and optimization. However, ADAGRAD with full matrix proximal functions (ADA-FULL) cannot handle large-scale problems due to the impractical $O(d^3)$ O (d 3) time and $O(d^2)$ O (d 2) space complexities, though it has better performance when gradients are correlated. In this paper, we propose two efficient variants of ADA-FULL via a matrix sketching technique called frequent directions (FD). The first variant named as ADA-FD directly utilizes FD to maintain and manipulate low-rank matrices, which reduces the space and time complexities to $O(\tau d)$ O (τ d) and $O(\tau ^2d)$ O (τ 2 d) respectively, where $d$ d is the dimensionality and $\tau \ll d$ τ ≪ d is the sketching size. The second variant named as ADA-FFD further adopts a doubling trick to accelerate FD used in ADA-FD, which reduces the average time complexity to $O(\tau d)$ O (τ d) while only doubles the space complexity of ADA-FD. Theoretical analysis reveals that the regret of ADA-FD and ADA-FFD is close to that of ADA-FULL as long as the outer product matrix of gradients is approximately low-rank. Experimental results demonstrate the efficiency and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This article investigates the finite-time distributed approximate optimization problem of higher order multiagent systems, where the local cost functions are considered to be quadratic functions. This problem is solved via penalty-function-based method. First, by the penalty-function method, a global approximate cost function is constructed. Second, nonlinear distributed optimization algorithms are proposed for higher order multiagent systems by the tool of adding a power integrator technique. In the optimization algorithms design, the gradients of the approximate cost function are utilized. Under the proposed optimization algorithms, the agents approach the approximate optimal solution in finite time. Although there exist errors (they may be called approximation errors) between the approximate minimizers and the global accurate minimizer, the approximation errors can be regulated by penalty parameter and the relationship between the bound of the approximation errors and the penalty parameter is given explicitly. Furthermore, the proposed distributed approximate optimization algorithms are applied to the optimal rendezvous problem of wheeled multimobile robots, making the mobile robots achieve approximate optimization rendezvous in finite time. The effectiveness of the proposed distributed optimization algorithms and their applications to optimal rendezvous problem are validated by simulations. [ABSTRACT FROM AUTHOR]

Fog networks facilitate ultra-low latency through the use of data availability near the network edge in fog servers. Existing work in fog networks considers the objective of energy efficiency and low latency for internet-of-things (IoT) for resource allocation. These works provide solutions to energy efficiency and low latency resource allocation problem without consideration of secure communication. This article investigates the benefits of fog architecture from the perspective of three promising technologies namely device-to-device (D2D) communication, caching, and physical layer security. We propose security provisioning followed by mode selection for D2D-assisted fog networks. The secrecy rate maximization problem is formulated first, which belongs to mixed-integer nonlinear programming (MINLP) problem. It is NP-hard, that is why an exhaustive search for finding the solution is complex. Keeping in view the complexity, a nonlinear technique namely outer approximation algorithm (OAA) is applied. OAA is a traditional algorithm, whose results are compared with the proposed heuristic algorithm, namely the security heuristic algorithm (SHA). Performance of the network is observed for the different numbers of eavesdroppers, IoT nodes, and fog nodes. [ABSTRACT FROM AUTHOR]

With an increasing penetration of distributed energy resources (DERs), it has become a public interest regarding how to efficiently manage large-scale DERs into wholesale markets. The existing literature has focused on various coordination methods including iteration-based (e.g., Lagrangian relaxation) and projection-based (e.g., vertex enumeration) ones, which may not work for the cases with complicated constraints due to curse of dimensionality. In this article, we propose an efficient projection-based method that adapts to characterizing the feasible region of active distribution networks with temporal-coupled constraints. The problem of finding the temporal-coupled feasible region is formulated as a max–min optimization program, aiming to determine the largest set allowing zero-valued slack variables. Based on Duality Principle, the max–min model is transformed into a solvable mixed-integer linear programming that can be efficiently optimized by off-the-shelf solvers. In contrast to the existing methods searching for a vertex from interior points, we develop an outer progressive approximation algorithm that generates feasibility cuts for each iteration. Case studies based on a modified IEEE 33-bus feeder and Caracas 141-bus system demonstrate the effectiveness and efficiency of our proposed method in characterizing the feasible region with large-scale temporal-coupled constraints. [ABSTRACT FROM AUTHOR]

This paper explores the non-convex composition optimization consisting of inner and outer finite-sum functions with a large number of component functions. This problem arises in important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gradient descent (SGD) and stochastic variance reduced gradient (SVRG) descent can be applied to solve this problem, their query complexities tend to be high, especially when the number of inner component functions is large. Therefore, to significantly improve the query complexity of current approaches, we have devised the stochastic composition via variance reduction (SCVR). What's more, we analyze the query complexity under different numbers of inner function and outer function. Based on different kinds of estimation of inner component function, we also present the SCVRII algorithm, though the order of query complexities are the same with SCVR. Additionally, we propose an extension to handle the mini-batch cases, which improve the query complexity under the optimal mini-batch size. The experimental results validate our proposed algorithms and theoretical analyses. [ABSTRACT FROM AUTHOR]

The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining n − 1 cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are k salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances. [ABSTRACT FROM AUTHOR]

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based $(1-1/e)$ (1 - 1 / e) -approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a $(1-\rho)(1-1/e)$ (1 - ρ) (1 - 1 / e) approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a $(1-\rho)(1-1/e-\varepsilon)$ (1 - ρ) (1 - 1 / e - ɛ) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively. [ABSTRACT FROM AUTHOR]

Revenue maximization (RM) is one of the most important problems in social networks, which attempts to find a small subset of users that make the expected revenue maximized. It has been studied in depth before. However, most of the existing literature was based on nonadaptive seeding strategies and simple information diffusion models. It considered the number of influenced users as a measurement unit to quantify the revenue. Until the emergence of the collaborate game model, it considered the activity as a basic object to compute the revenue. An activity initiated by a user can only influence those users whose distances are within ${k}$ -hop from the initiator. Based on that, we adopt an adaptive seed strategy and formulate an RM under the size budget (RMSB) problem. If taking into account the product’s promotion, we extend it to an RM under the community budget problem, where the influence can be distributed over the whole network uniformly. We can prove that our objective function is adaptive monotone and not adaptive submodular, but it is adaptive submodular in some special cases. We study these two problems under both the special submodular cases and general nonsubmodular cases, and propose RMSBSolver and RMCBSolver to solve them with strong theoretical guarantees, respectively. In particular, we give a data-dependent approximation ratio by adaptive primal curvature for the RMSB in general nonsubmodular cases. Finally, we evaluate our proposed algorithms by conducting experiments on real datasets, and show the effectiveness and accuracy of our solutions. [ABSTRACT FROM AUTHOR]

We introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V +) and negative nodes (V −). We study the Maximum Bounded Dual Domination , where, given a bound k , the problem is to find a set D ⊆ V + , which maximizes the number of nodes dominated in V + , dominating at most k nodes in V −. We show that such problem is hard to approximate to a factor better than (1 − 1 / e). We give a polynomial time algorithm with approximation guaranteed (1 − e − 1 / Δ) , where Δ represents the maximum number of neighbors in V + of any node in V − , and an O (| V | k 2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O (| V |) time algorithms on trees. [ABSTRACT FROM AUTHOR]

An Exponentially Faster Algorithm for Submodular Maximization Under a Matroid Constraint This paper studies the problem of submodular maximization under a matroid constraint. It is known since the 1970s that the greedy algorithm obtains a constant-factor approximation guarantee for this problem. Twelve years ago, a breakthrough result by Vondrák obtained the optimal 1 − 1/e approximation. Previous algorithms for this fundamental problem all have linear parallel runtime, which was considered impossible to accelerate until recently. The main contribution of this paper is a novel algorithm that provides an exponential speedup in the parallel runtime of submodular maximization under a matroid constraint, without loss in the approximation guarantee. In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid k or in the worst case sublinear in the size of the ground set n. We present an algorithm that has an approximation guarantee arbitrarily close to the optimal 1 − 1 / e for monotone submodular maximization under a matroid constraint and has near-optimal adaptivity of O (log (n) log (k)). This result is obtained using a novel technique of adaptive sequencing, which departs from previous techniques for submodular maximization in the adaptive complexity model. In addition to our main result, we show how to use this technique to design other approximation algorithms with strong approximation guarantees and polylogarithmic adaptivity. [ABSTRACT FROM AUTHOR]

A subset ${\mathcal{ S}}\subseteq V$ of vertices of an undirected graph $G=(V,E)$ is a hub cover when for each edge $(u,v) \in E$ , at least one of its endpoints belongs to ${\mathcal{ S}}$ , or there exists a vertex $r \in {\mathcal{ S}}$ that is a neighbor of both $u$ and $v$ . The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes $\Psi $ -MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is $\ln \mu $ , where $\mu $ is upper bounded by $\min \left\{{\frac {1}{2}(\Delta +1)^{2}, \vert E\vert }\right\}$ and $\Delta $ is the degree of $G$ . The execution time of $\Psi $ -MHC is $O((\Delta + 1) \vert E \vert + \vert {\mathcal{ S}} \vert \vert V \vert)$ . Experimental results show that $\Psi $ -MHC far outperforms the theoretical approximation ratio for the input graph instances.

Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithm (QAOA) constitutes a promising candidate for demonstrating tangible quantum advantages based on NISQ devices. In this paper, we consider the maximum likelihood (ML) detection problem of binary symbols transmitted over a multiple-input and multiple-output (MIMO) channel, where finding the optimal solution is exponentially hard using classical computers. Here, we apply the QAOA for the ML detection by encoding the problem of interest into a level- $p$ QAOA circuit having $2p$ variational parameters, which can be optimized by classical optimizers. This level- $p$ QAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately in $p$ consecutive rounds. More explicitly, we first encode the optimal solution of the ML detection problem into the ground state of a problem Hamiltonian. Using the quantum adiabatic evolution technique, we provide both analytical and numerical results for characterizing the evolution of the eigenvalues of the quantum system used for ML detection. Then, for level-1 QAOA circuits, we derive the analytical expressions of the expectation values of the QAOA and discuss the complexity of the QAOA based ML detector. Explicitly, we evaluate the computational complexity of the classical optimizer used and the storage requirement of simulating the QAOA. Finally, we evaluate the bit error rate (BER) of the QAOA based ML detector and compare it both to the classical ML detector and to the classical minimum mean squared error (MMSE) detector, demonstrating that the QAOA based ML detector is capable of approaching the performance of the classical ML detector. [ABSTRACT FROM AUTHOR]

Toward better approximation for the minimum-weighted vertex cover (MWVC) problem in multiagent systems, we present a distributed algorithm from the perspective of learning in games. For self-organized coordination and optimization, we see each vertex as a potential game player who makes decisions using local information of its own and the immediate neighbors. The resulting Nash equilibrium is classified into two categories, i.e., the inferior Nash equilibrium (INE) and the dominant Nash equilibrium (DNE). We show that the optimal solution must be a DNE. To achieve better approximation ratios, local rules of perturbation and weighted memory are designed, with the former destroying the stability of an INE and the latter facilitating the refinement of a DNE. By showing the existence of an improvement path from any INE to a DNE, we prove that when the memory length is larger than 1, our algorithm converges in finite time to DNEs, which could not be improved by exchanging the action of a selected node with all its unselected neighbors. Moreover, additional freedom for solution efficiency refinement is provided by increasing the memory length. Finally, intensive comparison experiments demonstrate the superiority of the presented methodology to the state of the art, both in solution efficiency and computation speed. [ABSTRACT FROM AUTHOR]

We consider decentralized large-scale continuous submodular constrained optimization problems over networks, where the goal is to maximize a sum of nonconvex functions with diminishing returns property. However, the computations of the projection step and the whole gradient can become prohibitive in high-dimensional constrained optimization problems. For this reason, a decentralized randomized block-coordinate Frank-Wolfe algorithm is proposed for submoduar maximization over networks by local communication and computation, which adopts the randomized block-coordinate descent and the Frank-Wolfe technique. We also show that the proposed algorithm converges to an approximation fact $(1-e^{-p_{\max }/p_{\min }})$ of the global maximal points at a rate of $\mathcal {O}(1/T)$ by choosing a suitable stepsize, where $T$ is the number of iterations. In addition, we confirm the theoretical results by experiments. [ABSTRACT FROM AUTHOR]

The manta ray foraging optimization algorithm (MRFO) is one of the promised meta-heuristic optimization algorithms. However, it can stick to a local minimum, consuming iterations without reaching the optimum solution. So, this paper proposes a hybridization between MRFO, and the genetic algorithm (GA) based on a pseudo parameter; where the GA can help MRFO to escape from falling into the local minimum. It is called a pseudo genetic algorithm with manta-ray foraging optimization (PGA-MRFO). The proposed algorithm is not a classical hybridization between MRFO and GA, wherein the classical hybridization consumes time in the search process as each algorithm is applied to all system variables. In addition, the classical hybridization results in an extended search algorithm, especially in systems with many variables. The PGA-MRFO hybridizes the pseudo-parameter-based GA and the MRFO algorithm to produce a more efficient algorithm that combines the advantages of both algorithms without getting stuck in a local minimum or taking a long time in the calculations. The pseudo parameter enables the GA to be applied to a specific number of variables and not to all system variables leading to reduce the computation time and burden. Also, the proposed algorithm used an approximation for the gradient of the objective function, which leads to dispensing derivatives calculations. Besides, PGA-MRFO depends on the pseudo inverse of non-square matrices, which saves calculations time; where the dependence on the pseudo inverse gives the algorithm more flexibility to deal with square and non-square systems. The proposed algorithm will be tested on the test functions that the main MRFO failed to find their optimum solution to prove its capability and efficiency. In addition, it will be applied to solve the unit commitment (UC) problem as one of the vital power system problems to show the validity of the proposed algorithm in practical applications. Finally, several analyses will be applied to the proposed algorithm to illustrate its effectiveness and reliability. [ABSTRACT FROM AUTHOR]

Most existing random access schemes for machine-type communications (MTC) simply adopt a uniform preamble selection distribution, irrespective of the underlying device activity distributions. Hence, they may yield unsatisfactory access efficiency. In this paper, we model device activities for MTC as multiple Bernoulli random variables following an arbitrary multivariate Bernoulli distribution which can reflect both dependent and independent device activities. Then, we optimize preamble selection and access barring for random access in MTC according to the underlying joint device activity distribution. Specifically, we investigate three cases of the joint device activity distribution, i.e., the cases of perfect, imperfect, and unknown joint device activity distributions, and formulate the average, worst-case average, and sample average throughput maximization problems, respectively. The problems in the three cases are challenging nonconvex problems. In the case of perfect joint device activity distribution, we develop an iterative algorithm and a low-complexity iterative algorithm to obtain stationary points of the original problem and an approximate problem, respectively. In the case of imperfect joint device activity distribution, we develop an iterative algorithm and a low-complexity iterative algorithm to obtain a Karush-Kuhn-Tucker (KKT) point of an equivalent problem and a stationary point of an approximate problem, respectively. Finally, in the case of unknown joint device activity distribution, we develop an iterative algorithm to obtain a stationary point. The proposed solutions are widely applicable and outperform existing solutions for dependent and independent device activities. [ABSTRACT FROM AUTHOR]

Hammerstein model with a static nonlinearity followed by a linear filter is commonly used in numerous applications. This paper focuses on adaptive filtering techniques for parameter identification of Hammerstein systems and output prediction of nonlinear systems. By formulating the underlying filtering problem as a recursive bilinear least-squares optimization with the non-convex feasible region constraint, we develop a recursive non-convex projected least-squares (RncPLS) algorithm based on alternating direction method of multipliers (ADMM). The RncPLS algorithm alternates between implementing ridge regression and projecting on the non-convex feasible set, which successively refines the system parameters. The convergence and accuracy properties of the proposed RncPLS algorithm are theoretically investigated. Moreover, extensive simulation results in the context of system identification, nonlinear predication, and acoustic echo cancellation, are also included to demonstrate the performance characteristics of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Numerical optimization has been playing an increasingly important role in the design of contemporary antenna systems. Due to the shortage of design-ready theoretical models, optimization is mainly based on electromagnetic (EM) analysis, which tends to be costly. Numerous techniques have evolved to abate this cost, including surrogate-assisted frameworks for global optimization, or sparse sensitivity updates for speeding up local search. In the latter, CPU-heavy updates of the system response sensitivity through finite differentiation are suppressed based on, e.g., the magnitude of design variability during the optimization run. Another approach is to incorporate variable-resolution simulations. Recently, a technique exploiting a continuous spectrum of admissible model fidelity levels has been reported, thereby allowing for a considerable reduction of computational expenditures. Seeking further savings, this work introduces an accelerated gradient-based algorithm with sparse sensitivity updates and variable-resolution EM simulations. Our technique is validated using four broadband antennas, and demonstrated to offer substantial (around 80%) savings over the benchmark while maintaining acceptable design quality. [ABSTRACT FROM AUTHOR]

Generation Expansion Planning (GEP) can inform regulation, electricity market design, and regional system planning by identifying adaptive investment strategies. Relevant uncertainties include hourly variability in load and renewable generation and decadal-scale uncertainty in technology, markets, and regulation. A multi-stage and multi-scale stochastic GEP model that represents these uncertainties at sufficient resolution becomes intractable. We present an approach for representing this multi-scale uncertainty, and compare it to existing methods, applied to a two-stage stochastic GEP model with a cumulative carbon emission target. For long-term uncertainty, we compare partitioning methods, which reduce the number of decision variables but retain all scenarios, to representative scenario methods, which retain only a subset of the original scenarios. For short-term uncertainty, we compare methods that select representative weeks based on distance metrics in the parameter space to methods that use the covariance of outcomes across feasible decisions to select weeks. We find that scenario reduction methods struggle to find the appropriate investment levels for variable renewable generation and consequently produce more costly plans than scenario partitioning methods. While simple approximating methods perform well with larger models, covariance-based approximations have the best performance overall. [ABSTRACT FROM AUTHOR]

Gas-fired generators, with their ability to quickly ramp up and down their electricity production, play an important role in managing renewable energy variability. However, these changes in electricity production translate into variability in the consumption of natural gas, and propagation of uncertainty from the electric grid to the natural gas system. To ensure that both systems are operating safely, there is an increasing need for coordination and uncertainty management among the electricity and gas networks. A challenging aspect of this coordination is the consideration of natural gas dynamics, which play an important role in intra-day operation, but give rise to a set of non-linear and non-convex equations that are hard to optimize even in the deterministic case. Ideally, the problem is formulated as a stochastic problem but many conventional methods for stochastic optimization are numerically intractable because they either incorporate a large number of scenarios directly or require the underlying problem to be convex. To address these challenges, we propose using a Stochastic Hybrid Approximation algorithm to more efficiently solve these problems and investigate the efficacy of several different variants of this algorithm. Our case study demonstrates that the proposed technique is able to quickly obtain high quality solutions and outperforms existing benchmarks such as Generalized Benders Decomposition. We demonstrate that coordinated uncertainty management that accounts for the gas system can significantly reduce both electric and gas system load shed in stressed conditions. [ABSTRACT FROM AUTHOR]

Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP–hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this article, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art. [ABSTRACT FROM AUTHOR]

Despite being commonly used in big-data analytics; the outcome of dimensionality reduction remains a black-box to most of its users. Understanding the quality of a low-dimensional embedding is important as not only it enables trust in the transformed data, but it can also help to select the most appropriate dimensionality reduction algorithm in a given scenario. As existing research primarily focuses on the visual exploration of embeddings, there is still a need for enhancing interpretability of such algorithms. To bridge this gap, we propose two novel interactive explanation techniques for low-dimensional embeddings obtained from any dimensionality reduction algorithm. The first technique LAPS produces a local approximation of the neighborhood structure to generate interpretable explanations on the preserved locality for a single instance. The second method GAPS explains the retained global structure of a high-dimensional dataset in its embedding, by combining non-redundant local-approximations from a coarse discretization of the projection space. We demonstrate the applicability of the proposed techniques using 16 real-life tabular, text, image, and audio datasets. Our extensive experimental evaluation shows the utility of the proposed techniques in interpreting the quality of low-dimensional embeddings, as well as with selecting the most suitable dimensionality reduction algorithm for any given dataset. [ABSTRACT FROM AUTHOR]

Existing wideband beampattern synthesis methods usually require multiple beamformers, each corresponding to one frequency bin, which results in excessive resource consumption in engineering practice. To alleviate the resource consumption of wideband array beamforming, we propose a novel time-domain wideband digital beamformer that can control the beam shape over the whole bandwidth for interference mitigation by using only one set of amplitude–phase weights and integer time delay filters. To tackle the resultant optimization problem, two effective algorithms are introduced, and both can solve the problem within polynomial time. One is an alternating optimization algorithm that decomposes the original problem into multiple tractable subproblems iteratively. The other is the convex approximation algorithm that transforms the original problem into a series of second-order cone programming problems iteratively. The two algorithms exhibit their respective advantages in terms of convergence and computational complexity. Extensive numerical examples are presented to evaluate the proposed time-domain wideband beamforming strategy, highlighting that it can form a deep notch in any interested spatial–spectral region to suppress the strong interferences. [ABSTRACT FROM AUTHOR]