Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching

• URL: http://arxiv.org/abs/2305.12352v3
• Date: Fri, 04 Apr 2025 18:09:21 GMT
• Title: Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching
• Authors: Yanguang Chen, Wenzhi Gao, Wanyu Zhang, Dongdong Ge, Huikang Liu, Yinyu Ye,
• Abstract summary: We propose a Pre-trained Mixed Optimization framework (PreMIO) that accelerates online mixed integer program (MIP) solving with offline datasets and machine learning models.<n>Our method is based on a data-driven multi-variable cardinality branching procedure that splits the feasible region using hyperplanes chosen by the concentration inequalities.
• Score: 8.03915440701838
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Probabilistic Federated Prompt-Tuning with Non-IID and Imbalanced Data [35.47385526394076]
  Fine-tuning pre-trained models is a popular approach in machine learning for solving complex tasks with moderate data. Fine-tuning the entire pre-trained model is ineffective in federated data scenarios where local data distributions are diversely skewed. Our approach transforms federated learning into a distributed set modeling task, aggregating diverse sets of prompts to globally fine-tune the pre-trained model.
  arXiv  Detail & Related papers  (2025-02-27T04:31:34Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach. Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Online Parallel Multi-Task Relationship Learning via Alternating Direction Method of Multipliers [37.859185005986056]
  Online multi-task learning (OMTL) enhances streaming data processing by leveraging the inherent relations among multiple tasks. This study proposes a novel OMTL framework based on the alternating direction multiplier method (ADMM), a recent breakthrough in optimization suitable for the distributed computing environment.
  arXiv  Detail & Related papers  (2024-11-09T10:20:13Z)
• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Online Variational Sequential Monte Carlo [49.97673761305336]
  We build upon the variational sequential Monte Carlo (VSMC) method, which provides computationally efficient and accurate model parameter estimation and Bayesian latent-state inference. Online VSMC is capable of performing efficiently, entirely on-the-fly, both parameter estimation and particle proposal adaptation.
  arXiv  Detail & Related papers  (2023-12-19T21:45:38Z)
• Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs [16.006893624836554]
  We propose to solve linear MDPs through the lens of Value-Biased Maximum Likelihood Estimation (VBMLE) VBMLE is computationally more efficient as it only requires solving one optimization problem in each time step. In our regret analysis, we offer a generic convergence result of MLE in linear MDPs through a novel supermartingale construct.
  arXiv  Detail & Related papers  (2023-10-17T18:27:27Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Greedy Modality Selection via Approximate Submodular Maximization [19.22947539760366]
  Multimodal learning considers learning from multi-modality data, aiming to fuse heterogeneous sources of information. It is not always feasible to leverage all available modalities due to memory constraints. We study modality selection, intending to efficiently select the most informative and complementary modalities under certain computational constraints.
  arXiv  Detail & Related papers  (2022-10-22T22:07:27Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Mixed-Integer Optimization with Constraint Learning [4.462264781248437]
  We establish a broad methodological foundation for mixed-integer optimization with learned constraints. We exploit the mixed-integer optimization-representability of many machine learning methods. We demonstrate the method in both World Food Programme planning and chemotherapy optimization.
  arXiv  Detail & Related papers  (2021-11-04T20:19:55Z)
• Effective multi-view registration of point sets based on student's t mixture model [15.441928157356477]
  This paper proposes an effective registration method based on Student's t Mixture Model (StMM) It is more efficient to achieve multi-view registration since all t-distribution centroids can be obtained by the NN search method. Experimental results illustrate its superior performance and accuracy over state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-12-13T08:27:29Z)
• Density Fixing: Simple yet Effective Regularization Method based on the Class Prior [2.3859169601259347]
  We propose a framework of regularization methods, called density-fixing, that can be used commonly for supervised and semi-supervised learning. Our proposed regularization method improves the generalization performance by forcing the model to approximate the class's prior distribution or the frequency of occurrence.
  arXiv  Detail & Related papers  (2020-07-08T04:58:22Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  convex mixed-integer programming formulation for non-rigid shape matching. We propose a novel shape deformation model based on an efficient low-dimensional discrete model.
  arXiv  Detail & Related papers  (2020-02-28T09:54:06Z)

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.