Threshold-aware Learning to Generate Feasible Solutions for Mixed
Integer Programs
- URL: http://arxiv.org/abs/2308.00327v1
- Date: Tue, 1 Aug 2023 07:03:16 GMT
- Title: Threshold-aware Learning to Generate Feasible Solutions for Mixed
Integer Programs
- Authors: Taehyun Yoon, Jinwon Choi, Hyokun Yun, Sungbin Lim
- Abstract summary: Neural diving (ND) is one of the learning-based approaches to generating partial discrete variable assignments in Mixed Programs (MIP)
We introduce a post-hoc method and a learning-based approach for optimizing the coverage.
Experimental results demonstrate that learning a deep neural network to estimate the coverage for finding high-quality feasible solutions achieves state-of-the-art performance in NeurIPS ML4CO datasets.
- Score: 5.28005598366543
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding a high-quality feasible solution to a combinatorial optimization (CO)
problem in a limited time is challenging due to its discrete nature. Recently,
there has been an increasing number of machine learning (ML) methods for
addressing CO problems. Neural diving (ND) is one of the learning-based
approaches to generating partial discrete variable assignments in Mixed Integer
Programs (MIP), a framework for modeling CO problems. However, a major drawback
of ND is a large discrepancy between the ML and MIP objectives, i.e., variable
value classification accuracy over primal bound. Our study investigates that a
specific range of variable assignment rates (coverage) yields high-quality
feasible solutions, where we suggest optimizing the coverage bridges the gap
between the learning and MIP objectives. Consequently, we introduce a post-hoc
method and a learning-based approach for optimizing the coverage. A key idea of
our approach is to jointly learn to restrict the coverage search space and to
predict the coverage in the learned search space. Experimental results
demonstrate that learning a deep neural network to estimate the coverage for
finding high-quality feasible solutions achieves state-of-the-art performance
in NeurIPS ML4CO datasets. In particular, our method shows outstanding
performance in the workload apportionment dataset, achieving the optimality gap
of 0.45%, a ten-fold improvement over SCIP within the one-minute time limit.
Related papers
- BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
Constraint Problems Optimization (COP) pose intricate challenges in problems usually addressed through Branch and Bound (B&B) methods.
We propose a novel neural network algorithm based on a depth-first search algorithm for solving COP.
Our method identifies feasible solutions with a gap of less than 17.63% within the initial 5 feasible solutions.
arXiv Detail & Related papers (2023-12-26T03:09:08Z) - Score-Based Methods for Discrete Optimization in Deep Learning [30.446056972242616]
We investigate a score-based approximation framework to solve such problems.
We experimentally demonstrate, in adversarial set classification tasks, that our method achieves a superior trade-off in terms of speed and solution quality compared to methods.
arXiv Detail & Related papers (2023-10-15T17:14:17Z) - Mixture Weight Estimation and Model Prediction in Multi-source
Multi-target Domain Adaptation [22.933419188759707]
We consider the problem of learning a model from multiple heterogeneous sources.
The goal of learner is to mix these data sources in a target-distribution aware way.
arXiv Detail & Related papers (2023-09-19T16:29:34Z) - A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical
Computation Offloading [62.34538208323411]
We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs)
MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
arXiv Detail & Related papers (2023-09-02T11:01:16Z) - Federated Compositional Deep AUC Maximization [58.25078060952361]
We develop a novel federated learning method for imbalanced data by directly optimizing the area under curve (AUC) score.
To the best of our knowledge, this is the first work to achieve such favorable theoretical results.
arXiv Detail & Related papers (2023-04-20T05:49:41Z) - DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
We introduce a new graph-based diffusion framework, namely DIFUSCO.
Our framework casts NPC problems as discrete 0, 1-vector optimization problems.
For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.
arXiv Detail & Related papers (2023-02-16T11:13:36Z) - Addressing the issue of stochastic environments and local
decision-making in multi-objective reinforcement learning [0.0]
Multi-objective reinforcement learning (MORL) is a relatively new field which builds on conventional Reinforcement Learning (RL)
This thesis focuses on what factors influence the frequency with which value-based MORL Q-learning algorithms learn the optimal policy for an environment.
arXiv Detail & Related papers (2022-11-16T04:56:42Z) - Sample-based and Feature-based Federated Learning via Mini-batch SSCA [18.11773963976481]
This paper investigates sample-based and feature-based federated optimization.
We show that the proposed algorithms can preserve data privacy through the model aggregation mechanism.
We also show that the proposed algorithms converge to Karush-Kuhn-Tucker points of the respective federated optimization problems.
arXiv Detail & Related papers (2021-04-13T08:23:46Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model.
The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22: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) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
Self-directed Online Learning Optimization integrates Deep Neural Network (DNN) with Finite Element Method (FEM) calculations.
Our algorithm was tested by four types of problems including compliance minimization, fluid-structure optimization, heat transfer enhancement and truss optimization.
It reduced the computational time by 2 5 orders of magnitude compared with directly using methods, and outperformed all state-of-the-art algorithms tested in our experiments.
arXiv Detail & Related papers (2020-02-04T20:00:28Z)
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.