Optimization
Building value-chain resilience with AI
Across industries, value chains are facing increasing uncertainty from climatic anomalies, market volatility, and the COVID-19 pandemic, among other factors. Industries as diverse as agriculture, oil and gas, and mining face essentially the same problem: they need the ability to both run with increased efficiency and recover quickly from unforeseen or unexpected challenges. But these two goals often conflict. If companies simply increase production levels, they'll inevitably run into bottlenecks--and if failures occur that worsen those bottlenecks, the entire network can slow down and become less resilient. For more on how COVID-19 has affected supply chains, see Knut Alicke, Richa Gupta, and Vera Trautwein, "Resetting supply chains for the next normal," July 21, 2020. Resolving this conflict presents several challenges.
Bayesian Optimization for Cascade-type Multi-stage Processes
Kusakawa, Shunya, Takeno, Shion, Inatsu, Yu, Kutsukake, Kentaro, Iwazaki, Shogo, Nakano, Takashi, Ujihara, Toru, Karasuyama, Masayuki, Takeuchi, Ichiro
Complex processes in science and engineering are often formulated as multi-stage decision-making problems. In this paper, we consider a type of multi-stage decision-making process called a cascade process. A cascade process is a multi-stage process in which the output of one stage is used as an input for the next stage. When the cost of each stage is expensive, it is difficult to search for the optimal controllable parameters for each stage exhaustively. To address this problem, we formulate the optimization of the cascade process as an extension of Bayesian optimization framework and propose two types of acquisition functions (AFs) based on credible intervals and expected improvement. We investigate the theoretical properties of the proposed AFs and demonstrate their effectiveness through numerical experiments. In addition, we consider an extension called suspension setting in which we are allowed to suspend the cascade process at the middle of the multi-stage decision-making process that often arises in practical problems. We apply the proposed method in the optimization problem of the solar cell simulator, which was the motivation for this study.
Enforcing and Discovering Structure in Machine Learning
The world is structured in countless ways. It may be prudent to enforce corresponding structural properties to a learning algorithm's solution, such as incorporating prior beliefs, natural constraints, or causal structures. Doing so may translate to faster, more accurate, and more flexible models, which may directly relate to real-world impact. In this dissertation, we consider two different research areas that concern structuring a learning algorithm's solution: when the structure is known and when it has to be discovered.
A Novel Machine Learning Approach to Data Inconsistency with respect to a Fuzzy Relation
Palangetić, Marko, Cornelis, Chris, Greco, Salvatore, Słowiński, Roman
Inconsistency in prediction problems occurs when instances that relate in a certain way on condition attributes, do not follow the same relation on the decision attribute. For example, in ordinal classification with monotonicity constraints, it occurs when an instance dominating another instance on condition attributes has been assigned to a worse decision class. It typically appears as a result of perturbation in data caused by incomplete knowledge (missing attributes) or by random effects that occur during data generation (instability in the assessment of decision attribute values). Inconsistencies with respect to a crisp preorder relation (expressing either dominance or indiscernibility between instances) can be handled using symbolic approaches like rough set theory and by using statistical/machine learning approaches that involve optimization methods. Fuzzy rough sets can also be seen as a symbolic approach to inconsistency handling with respect to a fuzzy relation. In this article, we introduce a new machine learning method for inconsistency handling with respect to a fuzzy preorder relation. The novel approach is motivated by the existing machine learning approach used for crisp relations. We provide statistical foundations for it and develop optimization procedures that can be used to eliminate inconsistencies. The article also proves important properties and contains didactic examples of those procedures.
Evacuation Shelter Scheduling Problem
Shimizu, Hitoshi, Suwa, Hirohiko, Iwata, Tomoharu, Fujino, Akinori, Sawada, Hiroshi, Yasumoto, Keiichi
Evacuation shelters, which are urgently required during natural disasters, are designed to minimize the burden of evacuation on human survivors. However, the larger the scale of the disaster, the more costly it becomes to operate shelters. When the number of evacuees decreases, the operation costs can be reduced by moving the remaining evacuees to other shelters and closing shelters as quickly as possible. On the other hand, relocation between shelters imposes a huge emotional burden on evacuees. In this study, we formulate the "Evacuation Shelter Scheduling Problem," which allocates evacuees to shelters in such a way to minimize the movement costs of the evacuees and the operation costs of the shelters. Since it is difficult to solve this quadratic programming problem directly, we show its transformation into a 0-1 integer programming problem. In addition, such a formulation struggles to calculate the burden of relocating them from historical data because no payments are actually made. To solve this issue, we propose a method that estimates movement costs based on the numbers of evacuees and shelters during an actual disaster. Simulation experiments with records from the Kobe earthquake (Great Hanshin-Awaji Earthquake) showed that our proposed method reduced operation costs by 33.7 million dollars: 32%.
Learn Zero-Constraint-Violation Policy in Model-Free Constrained Reinforcement Learning
Ma, Haitong, Liu, Changliu, Li, Shengbo Eben, Zheng, Sifa, Sun, Wenchao, Chen, Jianyu
--In the trial-and-error mechanism of reinforcement learning (RL), a notorious contradiction arises when we expect to learn a safe policy: how to learn a safe policy without enough data and prior model about the dangerous region? Existing methods mostly use the posterior penalty for dangerous actions, which means that the agent is not penalized until experiencing danger . This fact causes that the agent cannot learn a zero-violation policy even after convergence . Otherwise, it would not receive any penalty and lose the knowledge about danger . In this paper, we propose the safe set actor-critic (SSAC) algorithm, which confines the policy update using safety-oriented energy functions, or the safety indexes . The safety index is designed to increase rapidly for potentially dangerous actions, which allow us to locate the safe set on the action space, or the control safe set . Therefore, we can identify the dangerous actions prior to taking them, and further obtain a zero constraint-violation policy after convergence. We claim that we can learn the energy function in a model-free manner similar to learning a value function. By using the energy function transition as the constraint objective, we formulate a constrained RL problem. We prove that our Lagrangian-based solutions make sure that the learned policy will converge to the constrained optimum under some assumptions. The proposed algorithm is evaluated on both the complex simulation environments and a hardware-in-loop (HIL) experiment with a real controller from the autonomous vehicle. Experimental results suggest that the converged policy in all environments achieve zero constraint violation and comparable performance with model-based baseline. EINFORCEMENT learning has drawn rapidly growing attention for its superhuman learning capabilities in many sequential decision making problems like Go [1], Atari Games [2], and Starcraft [3].
Quality and Computation Time in Optimization Problems
Optimization problems are crucial in artificial intelligence. Optimization algorithms are generally used to adjust the performance of artificial intelligence models to minimize the error of mapping inputs to outputs. Current evaluation methods on optimization algorithms generally consider the performance in terms of quality. However, not all optimization algorithms for all test cases are evaluated equal from quality, the computation time should be also considered for optimization tasks. In this paper, we investigate the quality and computation time of optimization algorithms in optimization problems, instead of the one-for-all evaluation of quality. We select the well-known optimization algorithms (Bayesian optimization and evolutionary algorithms) and evaluate them on the benchmark test functions in terms of quality and computation time.
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
Letaief, Khaled B., Shi, Yuanming, Lu, Jianmin, Lu, Jianhua
The thriving of artificial intelligence (AI) applications is driving the further evolution of wireless networks. It has been envisioned that 6G will be transformative and will revolutionize the evolution of wireless from "connected things" to "connected intelligence". However, state-of-the-art deep learning and big data analytics based AI systems require tremendous computation and communication resources, causing significant latency, energy consumption, network congestion, and privacy leakage in both of the training and inference processes. By embedding model training and inference capabilities into the network edge, edge AI stands out as a disruptive technology for 6G to seamlessly integrate sensing, communication, computation, and intelligence, thereby improving the efficiency, effectiveness, privacy, and security of 6G networks. In this paper, we shall provide our vision for scalable and trustworthy edge AI systems with integrated design of wireless communication strategies and decentralized machine learning models. New design principles of wireless networks, service-driven resource allocation optimization methods, as well as a holistic end-to-end system architecture to support edge AI will be described. Standardization, software and hardware platforms, and application scenarios are also discussed to facilitate the industrialization and commercialization of edge AI systems.
TSO-DSOs Stable Cost Allocation for the Joint Procurement of Flexibility: A Cooperative Game Approach
Sanjab, Anibal, Cadre, Hélène Le, Mou, Yuting
--In this paper, a transmission-distribution systems flexibility market is introduced, in which system operators (SOs) jointly procure flexibility from different systems to meet their needs (balancing and congestion management) using a common market. This common market is, then, formulated as a cooperative game aiming at identifying a stable and efficient split of costs of the jointly procured flexibility among the participating SOs to incentivize their cooperation. The non-emptiness of the core of this game is then mathematically proven, implying the stability of the game and the naturally-arising incentive for cooperation among the SOs. Several cost allocation mechanisms are then introduced, while characterizing their mathematical properties. Numerical results focusing on an interconnected system (composed of the IEEE 14-bus transmission system and the Matpower 18-bus, 69-bus, and 141-bus distributions systems) showcase the cooperation-induced reduction in system-wide flexibility procurement costs, and identifies the varying costs borne by different SOs under various cost allocations methods. The increasing integration of distributed energy resources (DERs) and electrification of the consumer energy space (e.g., transportation and heating) pose challenges for grid operation, due to the induced uncertainty and changing load patterns. In this respect, the introduction of market mechanisms for the procurement of flexibility from flexibility services provides (FSPs) has been increasingly recommended in policies [1], and has been the center of several recent works in the literature [2]-[7] and demonstration projects [8]. As FSPs could provide their flexibility as a service to different system operators (SOs), a major branch of the literature has focused on the SOs' joint procurement (i.e. In particular, a key focus has been shed on the need for coordination between SOs to achieve joint procurement, not only for optimization of economic efficiency but also to ensure that the activated flexibility meets grid operational constraints of all the grids involved [2]-[5], [9], [10]. The authors are with the Flemish Institute for Technological Research VITO/EnergyVille, Thor Park 8310, 3600 Genk, Belgium. The authors have equally contributed to this work. This work is supported by the EU's Horizon 2020 research and innovation programme under grant agreement No 824414 - CoordiNet project. Flexibility is the ability to dynamically modify consumption and generation patterns providing, as a result, a service to system operators. Towards this end, we first introduce a novel flexibility market model including a TSO and multiple DSOs for jointly procuring congestion management and balancing services while explicitly accounting for grid constraints. This framework is developed by first introducing disjoint TSO and DSO level markets and joining them in a common market setting.
Dictionary-based Low-Rank Approximations and the Mixed Sparse Coding problem
Constrained tensor and matrix factorization models allow to extract interpretable patterns from multiway data. Therefore identifiability properties and efficient algorithms for constrained low-rank approximations are nowadays important research topics. This work deals with columns of factor matrices of a low-rank approximation being sparse in a known and possibly overcomplete basis, a model coined as Dictionary-based Low-Rank Approximation (DLRA). While earlier contributions focused on finding factor columns inside a dictionary of candidate columns, i.e. one-sparse approximations, this work is the first to tackle DLRA with sparsity larger than one. I propose to focus on the sparse-coding subproblem coined Mixed Sparse-Coding (MSC) that emerges when solving DLRA with an alternating optimization strategy. Several algorithms based on sparse-coding heuristics (greedy methods, convex relaxations) are provided to solve MSC. The performance of these heuristics is evaluated on simulated data. Then, I show how to adapt an efficient MSC solver based on the LASSO to compute Dictionary-based Matrix Factorization and Canonical Polyadic Decomposition in the context of hyperspectral image processing and chemometrics. These experiments suggest that DLRA extends the modeling capabilities of low-rank approximations, helps reducing estimation variance and enhances the identifiability and interpretability of estimated factors.