Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization

• URL: http://arxiv.org/abs/2009.07961v2
• Date: Mon, 6 Dec 2021 14:18:18 GMT
• Title: Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization
• Authors: Rishabh Gupta, Qi Zhang
• Abstract summary: This work addresses inverse linear optimization where the goal is to infer the unknown cost vector of a linear program. We introduce a new formulation of the problem that, compared to other existing methods, allows the recovery of a less restrictive and generally more appropriate admissible set of cost estimates.
• Score: 12.610576072466895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work addresses inverse linear optimization where the goal is to infer the unknown cost vector of a linear program. Specifically, we consider the data-driven setting in which the available data are noisy observations of optimal solutions that correspond to different instances of the linear program. We introduce a new formulation of the problem that, compared to other existing methods, allows the recovery of a less restrictive and generally more appropriate admissible set of cost estimates. It can be shown that this inverse optimization problem yields a finite number of solutions, and we develop an exact two-phase algorithm to determine all such solutions. Moreover, we propose an efficient decomposition algorithm to solve large instances of the problem. The algorithm extends naturally to an online learning environment where it can be used to provide quick updates of the cost estimate as new data becomes available over time. For the online setting, we further develop an effective adaptive sampling strategy that guides the selection of the next samples. The efficacy of the proposed methods is demonstrated in computational experiments involving two applications, customer preference learning and cost estimation for production planning. The results show significant reductions in computation and sampling efforts.

Related papers

• Self-Supervised Learning of Iterative Solvers for Constrained Optimization [0.0]
  We propose a learning-based iterative solver for constrained optimization. It can obtain very fast and accurate solutions by customizing the solver to a specific parametric optimization problem. A novel loss function based on the Karush-Kuhn-Tucker conditions of optimality is introduced, enabling fully self-supervised training of both neural networks.
  arXiv  Detail & Related papers  (2024-09-12T14:17:23Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Experiment Planning with Function Approximation [49.50254688629728]
  We study the problem of experiment planning with function approximation in contextual bandit problems. We propose two experiment planning strategies compatible with function approximation. We show that a uniform sampler achieves competitive optimality rates in the setting where the number of actions is small.
  arXiv  Detail & Related papers  (2024-01-10T14:40:23Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• A Data Driven Sequential Learning Framework to Accelerate and Optimize Multi-Objective Manufacturing Decisions [1.5771347525430772]
  This paper presents a novel data-driven Bayesian optimization framework that utilizes sequential learning to efficiently optimize complex systems. The proposed framework is particularly beneficial in practical applications where acquiring data can be expensive and resource intensive. It implies that the proposed data-driven framework can lead to similar manufacturing decisions with reduced costs and time.
  arXiv  Detail & Related papers  (2023-04-18T20:33:08Z)
• Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming [10.06803520598035]
  We develop a new approach to the problem called maximum optimality margin which the machine learning loss function by the optimality condition of the downstream optimization.
  arXiv  Detail & Related papers  (2023-01-26T17:53:38Z)
• Efficient Learning of Decision-Making Models: A Penalty Block Coordinate Descent Algorithm for Data-Driven Inverse Optimization [12.610576072466895]
  We consider the inverse problem where we use prior decision data to uncover the underlying decision-making process. This statistical learning problem is referred to as data-driven inverse optimization. We propose an efficient block coordinate descent-based algorithm to solve large problem instances.
  arXiv  Detail & Related papers  (2022-10-27T12:52:56Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Learning to Reformulate for Linear Programming [11.628932152805724]
  We propose a reinforcement learning-based reformulation method for linear programming (LP) to improve the performance of solving process. We implement the proposed method over two public research LP datasets and one large-scale LP dataset collected from practical production planning scenario.
  arXiv  Detail & Related papers  (2022-01-17T04:58:46Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.