检索结果-内蒙古大学图书馆

A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Pacheco, Bruno Machado Antunes, Pedro Marcolin Camponogara, Eduardo Seman, Laio Oriel Rosa, Vinícius Ramos Vieira, Bruno Ferreira Longhi, Cesar CIRRELT and Département d’Informatique et de Recherche Opérationnelle Université de Montréal MontréalQC Canada Department of Automation and Systems Engineering Federal University of Santa Catarina SC Florianópolis Brazil Petrobras Research Center RJ Rio de Janeiro Brazil Department of Automation and Systems Engineering The Federal University of Santa Catarina Brazil

This paper introduces a novel algorithm for mixed-integer Nonlinear programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objective or constraints contain black-box functions only known at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the multilinear constraints resulting from the multilinear interpolations used to approximate the true functions. Supported by the fact that our proposed relaxation defines the convex hull of the original problem, we propose a novel algorithm that iteratively solves the MILP relaxation and refines the solution space through variable fixing and exclusion strategies. This approach ensures convergence to an optimal solution, which we demonstrate, while maintaining computational efficiency. We apply the proposed algorithm to a real-world offshore oil production optimization problem. In comparison to the Gurobi solver, our algorithm was able to find the optimal solution at least four times faster, and to consistently provide better incumbents under limited time. © 2025, CC BY.

关键词： mixed-integer linear programming

Relax-and-round strategies for solving the Unit Commitment problem with AC Power Flow constraints

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Gómez, Dolores Göttlich, Simone Ríos-Alborés, Alfredo Salgado, Pilar Universidade de Santiago de Compostela Departamento de Matemática Aplicada Santiago de Compostela15782 Spain Santiago de Compostela15782 Spain University of Mannheim School of Business Informatics and Mathematics Mannheim68159 Germany

The Unit Commitment problem with AC power flow constraints (UC-ACOPF) is a non-convex mixed-integer nonlinear programming (MINLP) problem encountered in power systems. Its combination of combinatorial complexity and non-convex nonlinear constraints makes it particularly challenging. A common approach to tackle this issue is to relax the integrality condition, but this often results in infeasible solutions. Consequently, rounding heuristics are frequently employed to restore integer feasibility. This paper addresses recent advancements in heuristics aimed at quickly obtaining feasible solutions for the UC-ACOPF problem, focusing specifically on direct relax-and-round strategies. We propose a model-based heuristic that rescales the solution of the integer-relaxed problem before rounding. Furthermore, we introduce rounding formulas designed to enforce combinatorial constraints and aim to maintain AC feasibility in the resulting solutions. These methodologies are compared against standard direct rounding techniques in the literature, applied to a 6-bus and a 118-bus test systems. Additionally, we integrate the proposed heuristics into an implementation of the Feasibility Pump (FP) method, demonstrating their utility and potential to enhance existing rounding *** Codes 49, 65 © 2025, CC BY-NC-ND.

关键词： mixed-integer linear programming

The robust selection problem with information discovery

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chen, Xiaoyu Goerigk, Marc Poss, Michael LIRMM University of Montpellier CNRS Montpellier France Business Decisions and Data Science University of Passau Germany

We explore a multiple-stage variant of the min-max robust selection problem with budgeted uncertainty that includes queries. First, one queries a subset of items and gets the exact values of their uncertain parameters. Given this information, one can then choose the set of items to be selected, still facing uncertainty on the unobserved parameters. In this paper, we study two specific variants of this problem. The first variant considers objective uncertainty and focuses on selecting a single item. The second variant considers constraint uncertainty instead, which means that some selected items may fail. We show that both problems are NP-hard in general. We also propose polynomial-time algorithms for special cases of the sets of items that can be queried. For the problem with constraint uncertainty, we also show how the objective function can be expressed as a linear program, leading to a mixed-integer linear programming reformulation for the general case. We illustrate the performance of this formulation using numerical experiments. Copyright © 2025, The Authors. All rights reserved.

关键词： mixed-integer linear programming

SOME RECENT RESULTS ON THE PUNCTUAL QUOT SCHEMES

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Biswas, Indranil Gangopadhyay, Chandranandan Sebastian, Ronnie Department of Mathematics Shiv Nadar University NH91 Tehsil Dadri Uttar Pradesh Greater Noida201314 India Department of Mathematics Indian Institute of Science Education and Research Maharashtra Pune411008 India Department of Mathematics Indian Institute of Technology Bombay Powai Maharashtra Mumbai400076 India

Let C be a smooth projective curve defined over the field of complex numbers. Let E be a vector bundle on C, and fix an integer d ≥ 1. Let Q:= Quot(E, d) be the Quot Scheme which parameterizes all torsion quotients of E of degree d. In this article, we survey some recent results on various invariants of Q. Copyright © 2025, The Authors. All rights reserved.

关键词： mixed-integer linear programming

Kolmogorov widths of the class W11

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Malykhin, Yuri

关键词： mixed-integer linear programming

EQUIVAMAP: LEVERAGING LLMS FOR AUTOMATIC EQUIVALENCE CHECKING OF OPTIMIZATION FORMULATIONS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhai, Haotian Lawless, Connor Vitercik, Ellen Leqi, Liu The University of Texas Austin United States Stanford University United States

A fundamental problem in combinatorial optimization is identifying equivalent formulations, which can lead to more efficient solution strategies and deeper insights into a problem’s computational complexity. The need to automatically identify equivalence between problem formulations has grown as optimization copilots—systems that generate problem formulations from natural language descriptions—have proliferated. However, existing approaches to checking formulation equivalence lack grounding, relying on simple heuristics which are insufficient for rigorous validation. Inspired by Karp reductions, in this work we introduce quasi-Karp equivalence, a formal criterion for determining when two optimization formulations are equivalent based on the existence of a mapping between their decision variables. We propose EquivaMap, a framework that leverages large language models to automatically discover such mappings, enabling scalable and reliable equivalence verification. To evaluate our approach, we construct the first open-source dataset of equivalent optimization formulations, generated by applying transformations such as adding slack variables or valid inequalities to existing formulations. Empirically, EquivaMap significantly outperforms existing methods, achieving substantial improvements in correctly identifying formulation equivalence.2 © 2025, CC BY-NC-ND.

关键词： mixed-integer linear programming

On Data-Driven Robust Optimization With Multiple Uncertainty Subsets: Unified Uncertainty Set Representation and Mitigating Conservatism

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Li, Yun Yorke-Smith, Neil Keviczky, Tamas Delft Center for Systems and Control Delft University of Technology Delft Netherlands STAR Lab Delft University of Technology Delft Netherlands

Constructing uncertainty sets as unions of multiple subsets has emerged as an effective approach for creating compact and flexible uncertainty representations in data-driven robust optimization (RO). This paper focuses on two separate research questions. The first concerns the computational challenge in applying these uncertainty sets in RO-based predictive control. To address this, a monolithic mixed-integer representation of the uncertainty set is proposed to uniformly describe the union of multiple subsets, enabling the computation of the worst-case uncertainty scenario across all subsets within a single mixed-integer linear programming (MILP) problem. The second research question focuses on mitigating the conservatism of conventional RO formulations by leveraging the structure of the uncertainty set. To achieve this, a novel objective function is proposed to exploit the uncertainty set structure and integrate the existing RO and distributionally robust optimization (DRO) formulations, yielding less conservative solutions than conventional RO formulations while avoiding the high-dimensional continuous uncertainty distributions and incurring high computational burden typically associated with existing DRO formulations. Given the proposed formulations, numerically efficient computation methods based on column-and-constraint generation (CCG) are also developed. Extensive simulations across three case studies are performed to demonstrate the effectiveness of the proposed schemes. © 2025, CC BY.

关键词： mixed-integer linear programming

A Note on the Conversion of Nonnegative integers to the Canonical Signed-digit Representation

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cintra, R.J. Signal Processing Group Department of Technology UFPE Caruaru Brazil

This note addresses the signed-digit representation of non-negative integer binary numbers. We review and revisit popular literature methods for canonical signed-digit representation. A method based on string substitu... 详细信息

关键词： mixed-integer linear programming

BOOST: Microgrid Sizing using Ordinal Optimization

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chehade, Mohamad Fares El Hajj Karaki, Sami Chandra Department of Electrical and Computer Engineering The University of Texas at Austin AustinTX United States Electrical and Computer Engineering Department American University of Beirut Beirut Lebanon

The transition to sustainable energy systems has highlighted the critical need for efficient sizing of renewable energy resources in microgrids. In particular, designing photovoltaic (PV) and battery systems to meet residential loads is challenging due to trade-offs between cost, reliability, and environmental impact. While previous studies have employed dynamic programming and heuristic techniques for microgrid sizing, these approaches often fail to balance computational efficiency and accuracy. In this work, we propose BOOST, or Battery-solar Ordinal Optimization Sizing Technique, a novel framework for optimizing the sizing of PV and battery components in microgrids. Ordinal optimization enables computationally efficient evaluations of potential designs while preserving accuracy through robust ranking of solutions. To determine the optimal operation of the system at any given time, we introduce a mixed-integer linear programming (MILP) approach, which achieves lower costs than the commonly used dynamic programming methods. Our numerical experiments demonstrate that the proposed framework identifies optimal designs that achieve a levelized cost of energy (LCOE) as low as 8.84 ¢/kWh, underscoring its potential for cost-effective microgrid design. The implications of our work are significant: BOOST provides a scalable and accurate methodology for integrating renewable energy into residential microgrids, addressing economic and environmental goals simultaneously. © 2025, CC BY.

关键词： mixed-integer linear programming