Knowledge engineering mixed-integer linear programming: constraint typology

• URL: http://arxiv.org/abs/2102.12574v1
• Date: Sat, 20 Feb 2021 20:07:24 GMT
• Title: Knowledge engineering mixed-integer linear programming: constraint typology
• Authors: Vicky Mak-Hau and John Yearwood and William Moran
• Abstract summary: We investigate the constraint typology of mixed-integer linear programming MILP formulations. MILP is a commonly used mathematical programming technique for modelling and solving real-life scheduling, routing, planning, resource allocation, timetabling optimization problems.
• Score: 2.4002205752931625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate the constraint typology of mixed-integer linear programming MILP formulations. MILP is a commonly used mathematical programming technique for modelling and solving real-life scheduling, routing, planning, resource allocation, timetabling optimization problems, providing optimized business solutions for industry sectors such as: manufacturing, agriculture, defence, healthcare, medicine, energy, finance, and transportation. Despite the numerous real-life Combinatorial Optimization Problems found and solved, and millions yet to be discovered and formulated, the number of types of constraints, the building blocks of a MILP, is relatively much smaller. In the search of a suitable machine readable knowledge representation for MILPs, we propose an optimization modelling tree built based upon an MILP ontology that can be used as a guidance for automated systems to elicit an MILP model from end-users on their combinatorial business optimization problems.

Related papers

• Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
  We develop an automated approach to creating optimization models from natural language descriptions for commercial solvers. We identify the three core challenges of autoformulation: (1) defining the vast, problem-dependent hypothesis space, (2) efficiently searching this space under uncertainty, and (3) evaluating formulation correctness.
  arXiv  Detail & Related papers  (2024-11-03T20:41:38Z)
• OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling [62.19438812624467]
  Large language models (LLMs) have exhibited their problem-solving abilities in mathematical reasoning. We propose OptiBench, a benchmark for End-to-end optimization problem-solving with human-readable inputs and outputs.
  arXiv  Detail & Related papers  (2024-07-13T13:27:57Z)
• OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models [21.519880445683107]
  This paper introduces OptiMUS, a Large Language Model (LL)M-based agent designed to formulate and solve (mixed integer) linear programming problems from their natural language descriptions. OptiMUS can develop mathematical models, write and debug solver code, evaluate the generated solutions, and improve its model and code based on these evaluations. Experiments demonstrate that OptiMUS outperforms existing state-of-the-art methods on easy datasets by more than $20%$ and on hard datasets by more than $30%$.
  arXiv  Detail & Related papers  (2024-02-15T18:19:18Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming [11.293025183996832]
  Mixed Linear Programming (MILP) offers a powerful modeling language for a wide range of applications. In recent years, there has been an explosive development in the use of machine learning algorithms for enhancing all main tasks involved in the branch-and-bound algorithm. In particular, we give detailed attention to machine learning algorithms that automatically optimize some metric of branch-and-bound efficiency.
  arXiv  Detail & Related papers  (2024-02-08T09:19:26Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• OptiMUS: Optimization Modeling Using MIP Solvers and large language models [21.519880445683107]
  We introduce OptiMUS, a Large Language Model (LLM)-based agent designed to formulate and solve MILP problems from their natural language descriptions. To benchmark our agent, we present NLP4LP, a novel dataset of linear programming (LP) and mixed integer linear programming (MILP) problems. Our experiments demonstrate that OptiMUS solves nearly twice as many problems as a basic LLM prompting strategy.
  arXiv  Detail & Related papers  (2023-10-09T19:47:03Z)
• AI-Copilot for Business Optimisation: A Framework and A Case Study in Production Scheduling [3.522755287096529]
  We propose an AI-Copilot for business optimisation problem formulation. For token limitations, we introduce modularization and prompt engineering techniques. We design performance evaluation metrics that are better suited for assessing the accuracy and quality of problem formulations.
  arXiv  Detail & Related papers  (2023-09-22T23:45:21Z)
• A Survey for Solving Mixed Integer Programming via Machine Learning [76.04988886859871]
  This paper surveys the trend of machine learning to solve mixed integer (MIP) problems. In this paper, we first introduce the formulation and preliminaries of MIP and several traditional algorithms to solve MIP. Then, we advocate further promoting the different integration of machine learning and MIP algorithms.
  arXiv  Detail & Related papers  (2022-03-06T05:03:37Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• A Knowledge Representation Approach to Automated Mathematical Modelling [1.8907108368038215]
  We propose a new mixed-integer linear programming (MILP) model ontology and a novel constraint typology of MILP formulations. MILP is a commonly used mathematical programming technique for modelling and solving real-life scheduling, routing, planning, resource allocation, and timetabling optimization problems. Our aim is to develop a machine-readable knowledge representation for MILP that allows us to map an end-user's natural language description of the business optimization problem to an MILP formal specification.
  arXiv  Detail & Related papers  (2020-11-12T10:29:57Z)

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.