MILP-StuDio: MILP Instance Generation via Block Structure Decomposition

• URL: http://arxiv.org/abs/2410.22806v2
• Date: Thu, 31 Oct 2024 07:03:13 GMT
• Title: MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
• Authors: Haoyang Liu, Jie Wang, Wanbo Zhang, Zijie Geng, Yufei Kuang, Xijun Li, Bin Li, Yongdong Zhang, Feng Wu,
• Abstract summary: Mixed-integer linear programming (MILP) is one of the most popular mathematical formulations with numerous applications. We propose a novel MILP generation framework, called Block Structure Decomposition (MILP-StuDio), to generate high-quality instances by preserving the block structures.
• Score: 55.79888361191114
• License:
• Abstract: Mixed-integer linear programming (MILP) is one of the most popular mathematical formulations with numerous applications. In practice, improving the performance of MILP solvers often requires a large amount of high-quality data, which can be challenging to collect. Researchers thus turn to generation techniques to generate additional MILP instances. However, existing approaches do not take into account specific block structures -- which are closely related to the problem formulations -- in the constraint coefficient matrices (CCMs) of MILPs. Consequently, they are prone to generate computationally trivial or infeasible instances due to the disruptions of block structures and thus problem formulations. To address this challenge, we propose a novel MILP generation framework, called Block Structure Decomposition (MILP-StuDio), to generate high-quality instances by preserving the block structures. Specifically, MILP-StuDio begins by identifying the blocks in CCMs and decomposing the instances into block units, which serve as the building blocks of MILP instances. We then design three operators to construct new instances by removing, substituting, and appending block units in the original instances, enabling us to generate instances with flexible sizes. An appealing feature of MILP-StuDio is its strong ability to preserve the feasibility and computational hardness of the generated instances. Experiments on the commonly-used benchmarks demonstrate that using instances generated by MILP-StuDio is able to significantly reduce over 10% of the solving time for learning-based solvers.

Related papers

• Tender: Accelerating Large Language Models via Tensor Decomposition and Runtime Requantization [0.6445087473595953]
  Large language models (LLMs) demonstrate outstanding performance in various tasks in machine learning. deploying LLM inference poses challenges due to the high compute and memory requirements. We present Tender, an algorithm-hardware co-design solution that enables efficient deployment of LLM inference at low precision.
  arXiv  Detail & Related papers  (2024-06-16T09:51:55Z)
• A General Framework for Learning from Weak Supervision [93.89870459388185]
  This paper introduces a general framework for learning from weak supervision (GLWS) with a novel algorithm. Central to GLWS is an Expectation-Maximization (EM) formulation, adeptly accommodating various weak supervision sources. We also present an advanced algorithm that significantly simplifies the EM computational demands.
  arXiv  Detail & Related papers  (2024-02-02T21:48:50Z)
• A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability [66.37474135424637]
  We propose G2MILP, the first deep generative framework for MILP instances. G2MILP represents MILP instances as bipartite graphs, and applies a masked variational autoencoder to iteratively corrupt and replace parts of the original graphs to generate new ones. We design a suite of benchmarks to evaluate the quality of the generated MILP instances.
  arXiv  Detail & Related papers  (2023-10-04T13:34:34Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach [73.62265030773652]
  We present BRIEE, an algorithm for efficient reinforcement learning in Markov Decision Processes with block-structured dynamics. BRIEE interleaves latent states discovery, exploration, and exploitation together, and can provably learn a near-optimal policy. We show that BRIEE is more sample efficient than the state-of-art Block MDP algorithm HOMER RL and other empirical baselines on challenging rich-observation combination lock problems.
  arXiv  Detail & Related papers  (2022-01-31T19:47:55Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  Federated learning (FL) is vulnerable to external attacks on FL models during parameters transmissions. In this paper, we propose effective MP algorithms to combat state-of-the-art defensive aggregation mechanisms. Our experimental results demonstrate that the proposed CMP algorithms are effective and substantially outperform existing attack mechanisms.
  arXiv  Detail & Related papers  (2021-01-28T03:28:18Z)
• On Application of Block Kaczmarz Methods in Matrix Factorization [2.335152769484957]
  We discuss a block Kaczmarz solver that replaces the least-squares subroutine in the common alternating scheme for matrix factorization. We find block sizes that produce a solution comparable to that of the least-squares solver for only a fraction of the runtime and working memory requirement.
  arXiv  Detail & Related papers  (2020-10-20T21:29:50Z)
• Binary matrix factorization on special purpose hardware [5.926928436252818]
  We focus on the important binary matrix factorization (BMF) problem which has many applications in data mining. We propose two QUBO formulations for BMF and show how clustering constraints can easily be incorporated into these formulations. We also propose a simple baseline algorithm which outperforms our more sophisticated methods in a few situations.
  arXiv  Detail & Related papers  (2020-10-17T01:44:24Z)
• Exploring Instance Generation for Automated Planning [1.6735240552964108]
  Constraint programming and automated planning are examples of these areas. The efficiency of each solving method varies not only between problems, but also between instances of the same problem. We propose a new approach where the whole planning problem description is modelled using Essence.
  arXiv  Detail & Related papers  (2020-09-21T19:58:33Z)

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.