检索结果-内蒙古大学图书馆

Interval Abstractions for Robust Counterfactual Explanations

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jiang, Junqi Leofante, Francesco Rago, Antonio Toni, Francesca Department of Computing Imperial College London 180 Queen’s Gate LondonSW7 2AZ United Kingdom

Counterfactual Explanations (CEs) have emerged as a major paradigm in explainable AI research, providing recourse recommendations for users affected by the decisions of machine learning models. However, CEs found by existing methods often become invalid when slight changes occur in the parameters of the model they were generated for. The literature lacks a way to provide exhaustive robustness guarantees for CEs under model changes, in that existing methods to improve CEs’ robustness are mostly heuristic, and the robustness performances are evaluated empirically using only a limited number of retrained models. To bridge this gap, we propose a novel interval abstraction technique for parametric machine learning models, which allows us to obtain provable robustness guarantees for CEs under a possibly infinite set of plausible model changes ∆. Based on this idea, we formalise a robustness notion for CEs, which we call ∆-robustness, in both binary and multi-class classification settings. We present procedures to verify ∆-robustness based on mixed integer linear programming, using which we further propose algorithms to generate CEs that are ∆-robust. In an extensive empirical study involving neural networks and logistic regression models, we demonstrate the practical applicability of our approach. We discuss two strategies for determining the appropriate hyperparameters in our method, and we quantitatively benchmark CEs generated by eleven methods, highlighting the effectiveness of our algorithms in finding robust CEs. © 2024, CC BY.

关键词： mixed-integer linear programming

Long-Term Multi-Objective Optimization for Integrated Unit Commitment and Investment Planning for District Heating Networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Riedmüller, Stephanie Rivetta, Fabian Zittel, Janina Zuse Institute Berlin Berlin Germany

The need to decarbonize the energy system has intensified the focus on district heating networks in urban and suburban areas. Therefore, exploring transformation pathways with reasonable trade-offs between economic viability and environmental goals became necessary. We introduce a network-flow-based model class integrating unit commitment and long-term investment planning for multi-energy systems. While the integration of unit commitment and investment planning has been applied to multi-energy systems, a formal introduction and suitability for the application of long-term portfolio planning of an energy provider on an urban scale has yet to be met. Based on mixed integer linear programming, the model bridges the gap between overly detailed industrial modeling tools not designed for computational efficiency at scale and rather abstract academic models. The formulation is tested on Berlin’s district heating network. Hence, the challenge lies in a large number of variables and constraints and the coupling of time steps, for example, through investment decisions. A case study explores different solutions on the Pareto front defined by optimal trade-offs between minimizing costs and CO2 emissions through a lexicographic optimization approach. The resulting solution catalog can provide decision-makers valuable insights into feasible transformation pathways, highlighting distinctions between robust and target-dependent investments. © 2024, CC BY-NC-SA.

关键词： mixed-integer linear programming

Feature-Based Interpretable Optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Goerigk, Marc Hartisch, Michael Merten, Sebastian Sharma, Kartikey University of Passau Dr.-Hans-Kapfinger-Str. 30 Passau94032 Germany University of Erlangen–Nuremberg Cauerstraße 11 Erlangen91058 Germany Zuse Institute Berlin Takustr. 7 Berlin14195 Germany

For optimization models to be used in practice, it is crucial that users trust the results. A key factor in this aspect is the interpretability of the solution process. A previous framework for inherently interpretable optimization models used decision trees to map instances to solutions of the underlying optimization model. Based on this work, we investigate how we can use more general optimization rules to further increase interpretability and at the same time give more freedom to the decision maker. The proposed rules do not map to a concrete solution but to a set of solutions characterized by common features. To find such optimization rules, we present an exact methodology using mixed-integer programming formulations as well as heuristics. We also outline the challenges and opportunities that these methods present. In particular, we demonstrate the improvement in solution quality that our approach offers compared to existing frameworks for interpretable optimization and we discuss the relationship between interpretability and performance. These findings are supported by experiments using both synthetic and real-world data. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Network Design for the Traffic Assignment Problem with mixed-integer Frank-Wolfe

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sharma, Kartikey Hendrych, Deborah Besançon, Mathieu Pokutta, Sebastian Zuse Institute Berlin Takustr. 7 Berlin14195 Germany Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany Université Grenoble Alpes Inria LIG Grenoble France

We tackle the network design problem for centralized traffic assignment, which can be cast as a mixed-integer convex optimization (MICO) problem. For this task, we propose different formulations and solution methods in both a deterministic and a stochastic setting in which the demand is unknown in the design phase. We leverage the recently proposed Boscia framework, which can solve MICO problems when the main nonlinearity stems from a differentiable objective function. Boscia tackles these problems by branch-and-bound with continuous relaxations solved approximately with Frank-Wolfe algorithms. We compare different linear relaxations and the corresponding subproblems solved by Frank-Wolfe, and alternative problem formulations to identify the situations in which each performs best. Our experiments evaluate the different approaches on instances from the Transportation Networks library and highlight the suitability of the mixed-integer Frank-Wolfe algorithm for this problem. In particular, we find that the Boscia framework is particularly applicable to this problem and that a mixed-integer linear Frank-Wolfe subproblem performs well for the deterministic case, while a penalty-based approach, with decoupled feasible regions for the design and flow variables, dominates other approaches for stochastic instances with many scenarios. © 2024, CC BY.

关键词： mixed-integer linear programming

Index Tracking Using Data-Mining Techniques and mixed-Binary linear programming

学校读者我要写书评

暂无评论

Index Tracking Using Data-Mining Techniques and Mixed-Binary...

IEEE International Conference on Industrial Engineering and Engineering Management

作者： Oliver Strub Philipp Baumann Department of Business Administration University of Bern Bern Switzerland Department of Industrial Engineering and Operations Research UC Berkeley Berkeley USA

ISBN: (纸本)9781467380676

Index tracking has become one of the most common strategies in asset management The index-tracking problem consists of constructing a portfolio that replicates the future performance of an index by including only a subset of the index constituents in the portfolio. Finding the most representative subset is challenging when the number of stocks in the index is large. We introduce a new three-stage approach that at first identifies promising subsets by employing data-mining techniques, then determines the stock weights in the subsets using mixed-binary linear programming, and finally evaluates the subsets based on cross validation. The best subset is returned as the tracking portfolio. Our approach outperforms state-of-the-art methods in terms of out-of-sample performance and running times.

关键词： Cross validation data mining index tracking mixed-integer linear programming principal component analysis

FairWASP: Fast and Optimal Fair Wasserstein Pre-processing

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Xiong, Zikai Dalmasso, Niccolò Mishler, Alan Potluru, Vamsi K. Balch, Tucker Veloso, Manuela Massachusetts Institute of Technology United States J.P. Morgan AI Research New York United States

Recent years have seen a surge of machine learning approaches aimed at reducing disparities in model outputs across different subgroups. In many settings, training data may be used in multiple downstream applications by different users, which means it may be most effective to intervene on the training data itself. In this work, we present FairWASP, a novel pre-processing approach designed to reduce disparities in classification datasets without modifying the original data. FairWASP returns sample-level weights such that the reweighted dataset minimizes the Wasserstein distance to the original dataset while satisfying (an empirical version of) demographic parity, a popular fairness criterion. We show theoretically that integer weights are optimal, which means our method can be equivalently understood as duplicating or eliminating samples. FairWASP can therefore be used to construct datasets which can be fed into any classification method, not just methods which accept sample weights. Our work is based on reformulating the pre-processing task as a large-scale mixed-integer program (MIP), for which we propose a highly efficient algorithm based on the cutting plane method. Experiments demonstrate that our proposed optimization algorithm significantly outperforms state-of-the-art commercial solvers in solving both the MIP and its linear program relaxation. Further experiments highlight the competitive performance of FairWASP in reducing disparities while preserving accuracy in downstream classification settings. Copyright © 2023, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Pre-trained mixed integer Optimization through Multi-variable Cardinality Branching

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Chen, Yanguang Gao, Wenzhi Ge, Dongdong Ye, Yinyu Shanghai University of Finance and Economics China Stanford University United States Shanghai Jiaotong University China

In this paper, we propose a Pre-trained mixed integer Optimization framework (PreMIO) that accelerates online mixed integer program (MIP) solving with offline datasets and machine learning models. Our method is based on a data-driven multi-variable cardinality branching procedure that splits the MIP feasible region using hyperplanes chosen by the concentration inequalities. Unlike most previous ML+MIP approaches that either require complicated implementation or suffer from a lack of theoretical justification, our method is simple, flexible, provable and explainable. Numerical experiments on both classical OR benchmark datasets and real-life instances validate the efficiency of our proposed method. Copyright © 2023, The Authors. All rights reserved.

关键词： mixed-integer linear programming

A mixed-integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Philip, Allen George Ren, Zhongqiang Rathinam, Sivakumar Choset, Howie Department of Mechanical Engineering Texas A&M University College StationTX77843-3123 United States Shanghai Jiao Tong University 800 Dongchuan Road Shanghai China Carnegie Mellon University 5000 Forbes Ave. PittsburghPA15213 United States

This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP), which seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot. The formulation relies on the key idea that when the targets move along lines, their trajectories become convex sets within the space-time coordinate system. The problem then reduces to finding the shortest path within a graph of convex sets, subject to some speed constraints. We compare our formulation with the current state-of-the-art mixed integer Conic Program (MICP) formulation for the MT-TSP. The experimental results show that our formulation outperforms the MICP for instances with up to 20 targets, with up to two orders of magnitude reduction in runtime, and up to a 60% tighter optimality gap. We also show that the solution cost from the convex relaxation of our formulation provides significantly tighter lower-bounds for the MT-TSP than the ones from the MICP. Copyright © 2024, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Coordinated Vehicle Platooning on Tree Networks: Efficient Time Discretization and Strengthened Formulation

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Luo, Fengqiao Uber Technologies Inc. Northwestern University EvanstonIL60208 United States

We consider the coordinated vehicle platooning problem on a tree network with time constraints while the routes of vehicles are given. The problem is to coordinate the departure time of each vehicle to enable platoon formation hence maximizing the total fuel saving. For this problem setting, relative time windows can be defined for all vehicles to which an efficient time discretization can be applied. This property leads to a tight mixed-integer linear program reformulation as compared to the continuous-time formulation involving big-M coefficients proposed in our previous work. It is demonstrated by systematic numerical experiments that the reformulation outperforms the continuous-time formulation for this family of problem *** Codes 90-10 © 2022, CC BY.

关键词： mixed-integer linear programming