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

Walkability Optimization: Formulations, algorithms, and a Case Study of Toronto

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Huang, Weimin Khalil, Elias B. Department of Mechanical & Industrial Engineering University of Toronto Scale AI Research Chair in Data-Driven Algorithms for Modern Supply Chains Canada

The concept of walkable urban development has gained increased attention due to its public health, economic, and environmental sustainability benefits. Unfortunately, land zoning and historic under-investment have resulted in spatial inequality in walkability and social inequality among residents. We tackle the problem of Walkability Optimization through the lens of combinatorial optimization. The task is to select locations in which additional amenities (e.g., grocery stores, schools, restaurants) can be allocated to improve resident access via walking while taking into account existing amenities and providing multiple options (e.g., for restaurants). To this end, we derive Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) models. Moreover, we show that the problem's objective function is submodular in special cases, which motivates an efficient greedy heuristic. We conduct a case study on 31 underserved neighborhoods in the City of Toronto, Canada. MILP finds the best solutions in most scenarios but does not scale well with network size. The greedy algorithm scales well and finds near-optimal solutions. Our empirical evaluation shows that neighbourhoods with low walkability have a great potential for transformation into pedestrian-friendly neighbourhoods by strategically placing new amenities. Allocating 3 additional grocery stores, schools, and restaurants can improve the "WalkScore" by more than 50 points (on a scale of 100) for 4 neighbourhoods and reduce the walking distances to amenities for 75% of all residential locations to 10 minutes for all amenity types. Our code and paper appendix are available at https://***/khalil-research/walkability. © 2022, CC BY.

关键词： Combinatorial optimization

CaVE: A Cone-Aligned Approach for Fast Predict-then-optimize with Binary Linear Programs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Tang, Bo Khali, Elias B. SCALE AI Research Chair in Data-Driven Algorithms for Modern Supply Chains Department of Mechanical and Industrial Engineering University of Toronto Canada

The end-to-end predict-then-optimize framework, also known as decision-focused learning, has gained popularity for its ability to integrate optimization into the training procedure of machine learning models that predict the unknown cost (objective function) coefficients of optimization problems from contextual instance information. Naturally, most of the problems of interest in this space can be cast as integer linear programs. In this work, we focus on binary linear programs (BLPs) and propose a new end-to-end training method to predict-then-optimize. Our method, Cone-aligned Vector Estimation (CaVE), aligns the predicted cost vectors with the normal cone corresponding to the true optimal solution of a training instance. When the predicted cost vector lies inside the cone, the optimal solution to the linear relaxation of the binary problem is optimal. This alignment not only produces decision-aware learning models, but also dramatically reduces training time as it circumvents the need to solve BLPs to compute a loss function with its gradients. Experiments across multiple datasets show that our method exhibits a favorable trade-off between training time and solution quality, particularly with large-scale optimization problems such as vehicle routing, a hard BLP that has yet to benefit from predict-then-optimize methods in the literature due to its difficulty. Copyright © 2023, The Authors. All rights reserved.

关键词： Machine learning

Deep Learning for Two-Stage Robust Integer Optimization

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dumouchelle, Justin Julien, Esther Kurtz, Jannis Khalil, Elias B. University of Toronto Canada SCALE AI Research Chair in Data-Driven Algorithms for Modern Supply Chains Canada TU Delft Netherlands University of Amsterdam Netherlands

Robust optimization is an established framework for modeling optimization problems with uncertain parameters. While static robust optimization is often criticized for being too conservative, two-stage (or adjustable) robust optimization (2RO) provides a less conservative alternative by allowing some decisions to be made after the uncertain parameters have been revealed. Unfortunately, in the case of integer decision variables, existing solution methods for 2RO typically fail to solve large-scale instances, limiting the applicability of this modeling paradigm to simple cases. We propose NEUR2RO, a deep-learning-augmented instantiation of the column-and-constraint-generation (CCG) algorithm, which expands the applicability of the 2RO framework to large-scale instances with integer decisions in both stages. A custom-designed neural network is trained to estimate the optimal value and feasibility of the second-stage problem. The network can be incorporated into CCG, leading to more computationally tractable subproblems in each of its iterations. The resulting algorithm enjoys approximation guarantees which depend on the neural network’s prediction error. In our experiments, NEUR2RO produces high-quality solutions quickly, outperforming state-of-the-art methods on two-stage knapsack, capital budgeting, and facility location problems. Compared to existing methods, which often run for hours, NEUR2RO finds better solutions in a few seconds or minutes. Our code is available at https://***/khalil-research/Neur2RO. Copyright © 2023, The Authors. All rights reserved.

关键词： Budget control

Machine Learning for Cutting Planes in Integer Programming: A Survey

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Deza, Arnaud Khalil, Elias B. Department of Mechanical & Industrial Engineering University of Toronto Canada SCALE AI Research in Data-Driven Algorithms for Modern Supply Chains Canada

We survey recent work on machine learning (ML) techniques for selecting cutting planes (or cuts) in mixed-integer linear programming (MILP). Despite the availability of various classes of cuts, the task of choosing a set of cuts to add to the linear programming (LP) relaxation at a given node of the branch-and-bound (B&B) tree has defied both formal and heuristic solutions to date. ML offers a promising approach for improving the cut selection process by using data to identify promising cuts that accelerate the solution of MILP instances. This paper presents an overview of the topic, highlighting recent advances in the literature, common approaches to data collection, evaluation, and ML model architectures. We analyze the empirical results in the literature in an attempt to quantify the progress that has been made and conclude by suggesting avenues for future *** Codes Artificial Intelligence © 2023, CC BY.

关键词： Integer programming

Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Xu, Yudong Khalil, Elias B. Sanner, Scott Department of Mechanical & Industrial Engineering University of Toronto Canada Scale Ai Research in Data-Driven Algorithms for Modern Supply Chains China

The Abstraction and Reasoning Corpus (ARC) aims at benchmarking the performance of general artificial intelligence algorithms. The ARC's focus on broad generalization and fewshot learning has made it difficult to solve using pure machine learning. A more promising approach has been to perform program synthesis within an appropriately designed Domain Specific Language (DSL). However, these too have seen limited success. We propose Abstract Reasoning with Graph Abstractions (ARGA), a new object-centric framework that first represents images using graphs and then performs a search for a correct program in a DSL that is based on the abstracted graph space. The complexity of this combinatorial search is tamed through the use of constraint acquisition, state hashing, and Tabu search. An extensive set of experiments demonstrates the promise of ARGA in tackling some of the complicated object-centric tasks of the ARC rather efficiently, producing programs that are correct and easy to understand. © 2022, CC BY.

关键词： Tabu search

TACKLING THE ABSTRACTION AND REASONING CORPUS WITH VISION TRANSFORMERS: THE IMPORTANCE OF 2D REPRESENTATION, POSITIONS, AND OBJECTS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Wenhao Xu, Yudong Sanner, Scott Khalil, Elias B. Department of Mechanical & Industrial Engineering University of Toronto Canada Vector Institute for Artificial Intelligence Canada Scale AI Research Chair in Data-Driven Algorithms for Modern Supply Chains Canada

The Abstraction and Reasoning Corpus (ARC) is a popular benchmark focused on visual reasoning in the evaluation of Artificial Intelligence systems. In its original framing, an ARC task requires solving a program synthesis problem over small 2D images using a few input-output training pairs. In this work, we adopt the recently popular data-driven approach to the ARC and ask whether a Vision Transformer (ViT) can learn the implicit mapping, from input image to output image, that underlies the task. We show that a ViT—otherwise a state-of-the-art model for images—fails dramatically on most ARC tasks even when trained on one million examples per task. This points to an inherent representational deficiency of the ViT architecture that makes it incapable of uncovering the simple structured mappings underlying the ARC tasks. Building on these insights, we propose VITARC, a ViT-style architecture that unlocks some of the visual reasoning capabilities required by the ARC. Specifically, we use a pixel-level input representation, design a spatially-aware tokenization scheme, and introduce a novel object-based positional encoding that leverages automatic segmentation, among other enhancements. Our task-specific VITARC models achieve a test solve rate close to 100% on more than half of the 400 public ARC tasks strictly through supervised learning from input-output grids. This calls attention to the importance of imbuing the powerful (Vision) Transformer with the correct inductive biases for abstract visual reasoning that are critical even when the training data is plentiful and the mapping is noise-free. Hence, VITARC provides a strong foundation for future research in visual reasoning using transformer-based architectures. © 2024, CC BY.

关键词： Mapping

Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Alomrani, Mohammad Ali Moravej, Reza Khalil, Elias B. Department of Electrical & Computer Engineering University of Toronto Canada Department of Mechanical & Industrial Engineering SCALE AI Research in Data-Driven Algorithms for Modern Supply Chains University of Toronto Canada

The challenge in the widely applicable online matching problem lies in making irrevocable assignments while there is uncertainty about future inputs. Most theoretically-grounded policies are myopic or greedy in nature. In real-world applications where the matching process is repeated on a regular basis, the underlying data distribution can be leveraged for better decision-making. We present an end-to-end Reinforcement Learning framework for deriving better matching policies based on trial-and-error on historical data. We devise a set of neural network architectures, design feature representations, and empirically evaluate them across two online matching problems: Edge-Weighted Online Bipartite Matching and Online Submodular Bipartite Matching. We show that most of the learning approaches perform consistently better than classical baseline algorithms on four synthetic and real-world datasets. On average, our proposed models improve the matching quality by 3-10% on a variety of synthetic and real-world datasets. Our code is publicly available at https://***/lyeskhalil/CORL. © 2021, CC BY.

关键词： Reinforcement learning

LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Xu, Yudong Li, Wenhao Vaezipoor, Pashootan Sanner, Scott Khalil, Elias B. Department of Mechanical & Industrial Engineering University of Toronto Canada Department of Computer Science University of Toronto Vector Institute for Artificial Intelligence Canada Department of Mechanical & Industrial Engineering University of Toronto Scale AI Research Chair in Data-Driven Algorithms for Modern Supply Chains Canada

Can a Large Language Model (LLM) solve simple abstract reasoning problems? We explore this broad question through a systematic analysis of GPT on the Abstraction and Reasoning Corpus (ARC) (Chollet, 2019), a representative benchmark of abstract reasoning ability from limited examples in which solutions require some "core knowledge" of concepts such as objects, goal states, counting, and basic geometry. GPT-4 solves only 13/50 of the most straightforward ARC tasks when using textual encodings for their two-dimensional input-output grids. Our failure analysis reveals that GPT-4’s capacity to identify objects and reason about them is significantly influenced by the sequential nature of the text that represents an object within a text encoding of a task. To test this hypothesis, we design a new benchmark, the 1D-ARC, which consists of one-dimensional (array-like) tasks that are more conducive to GPT-based reasoning, and where it indeed performs better than on the (2D) ARC. To alleviate this issue, we propose an object-based representation that is obtained through an external tool, resulting in nearly doubling the performance on solved ARC tasks and near-perfect scores on the easier 1D-ARC. Although the state-of-the-art GPT-4 is unable to "reason" perfectly within non-language domains such as the 1D-ARC or a simple ARC subset, our study reveals that the use of object-based representations can significantly improve its reasoning ability. Visualizations, GPT logs, and data are available at https://***/LLM4ARC. © 2023, CC BY.

关键词： Abstracting

Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Khalil, Elias B. Vaezipoor, Pashootan Dilkina, Bistra Department of Mechanical & Industrial Engineering University of Toronto Canada Scale AI Research Chair in Data-Driven Algorithms for Modern Supply Chains Department of Computer Science University of Toronto Canada Vector Institute for Artificial Intelligence Canada Department of Computer Science University of Southern California United States

In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure, the instance can be solved to global optimality by branching only on the variables in the backdoor. Constructing datasets of pre-computed backdoors for widely used MIP benchmark sets or particular problem families can enable new questions around novel structural properties of a MIP, or explain why a problem that is hard in theory can be solved efficiently in practice. Existing algorithms for finding backdoors rely on sampling candidate variable subsets in various ways, an approach which has demonstrated the existence of backdoors for some instances from MIPLIB2003 and MIPLIB2010. However, these algorithms fall short of consistently succeeding at the task due to an imbalance between exploration and exploitation. We propose BaMCTS, a Monte Carlo Tree Search framework for finding backdoors to MIPs. Extensive algorithmic engineering, hybridization with traditional MIP concepts, and close integration with the CPLEX solver have enabled our method to outperform baselines on MIPLIB2017 instances, finding backdoors more frequently and more efficiently. © 2021, CC BY.

关键词： Integer programming