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

Finding Multiple Optimal Solutions to an integer linear program by Random Perturbations of Its Objective Function

ALGORITHMS 2025年第3期18卷 140-140页

作者： Schulhof, Noah Sukprasert, Pattara Ruppin, Eytan Khuller, Samir Schaffer, Alejandro A. NCI NIH Canc Data Sci Lab Bethesda MD 20892 USA Northwestern Univ Dept Comp Sci Evanston IL 60201 USA Databricks Inc San Francisco CA 94105 USA

integer linear programs (ILPs) and mixed integer programs (MIPs) often have multiple distinct optimal solutions, yet the widely used Gurobi optimization solver returns certain solutions at disproportionately high frequencies. This behavior is disadvantageous, as, in fields such as biomedicine, the identification and analysis of distinct optima yields valuable domain-specific insights that inform future research directions. In the present work, we introduce MORSE (Multiple Optima via Random Sampling and careful choice of the parameter Epsilon), a randomized, parallelizable algorithm to efficiently generate multiple optima for ILPs. MORSE maps multiplicative perturbations to the coefficients in an instance's objective function, generating a modified instance that retains an optimum of the original problem. We formalize and prove the above claim in some practical conditions. Furthermore, we prove that for 0/1 selection problems, MORSE finds each distinct optimum with equal probability. We evaluate MORSE using two measures;the number of distinct optima found in r independent runs, and the diversity of the list (with repetitions) of solutions by average pairwise Hamming distance and Shannon entropy. Using these metrics, we provide empirical results demonstrating that MORSE outperforms the Gurobi method and unweighted variations of the MORSE method on a set of 20 Mixed integer programming Library (MIPLIB) instances and on a combinatorial optimization problem in cancer genomics.

关键词： integer linear program selection problems multiple optima randomized algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Singularity structure simplification for hex mesh via integer linear program

引用

COMPUTER-AIDED DESIGN 2023年 168卷

作者： Duan, Junyi Zheng, Xiaopeng Lei, Na Luo, Zhongxuan Dalian Univ Technol Sch Software Technol Dalian 116024 Liaoning Peoples R China Dalian Univ Technol Int Sch Informat Sci & Engn Dalian 116024 Liaoning Peoples R China

Topology optimization of hexahedral (hex) meshes has been a widely studied topic, with the primary goal of optimizing the singularity structure. Previous works have focused on simplifying complex singularity structures by collapsing sheets/chords. However, these works require a large number of checks during the process to prevent illegal operations. Moreover, the employed simplification strategies are not based on the topological characteristics of the structure, but rather on the rank of the components that can be simplified. To overcome these problems, we analyze how topology operations affect the degree of edges in hex meshes, and introduce a fast and automatic algorithm to simplify the singularity structure of hex meshes. The algorithm relies on sheet operations, using mesh volume as a metric to assess the degree of simplification. Moreover, it designs constraints to prevent illegal operations and employs integer linear program to plan the overall optimization strategy for a mesh. After that, we relax the singularity constraints to further simplify the structure, and handle unreasonable singularities via sheet inflation operation. Our algorithm can also improve singularity structure without merging singularities by adjusting the singularity constraint conditions. Numerous experiments demonstrate the effectiveness and efficiency of our algorithm.

关键词： Hex mesh Singularity structure Simplification integer linear program

来源：评论

学校读者我要写书评

暂无评论

Local Branching Relaxation Heuristics for integer linear programs 1

引用

20th International Conference on the Integration of Constraint programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Huang, Taoan Ferber, Aaron Tian, Yuandong Dilkina, Bistra Steiner, Benoit Univ Southern Calif Los Angeles CA 90007 USA Meta AI FAIR Menlo Pk CA USA

ISBN: (数字)9783031332715

ISBN: (纸本)9783031332708;9783031332715

Large Neighborhood Search (LNS) is a popular heuristic algorithm for solving combinatorial optimization problems (COP). It starts with an initial solution to the problem and iteratively improves it by searching a large neighborhood around the current best solution. LNS relies on heuristics to select neighborhoods to search in. In this paper, we focus on designing effective and efficient heuristics in LNS for integer linear programs (ILP) since a wide range of COPs can be represented as ILPs. Local Branching (LB) is a heuristic that selects the neighborhood that leads to the largest improvement over the current solution in each iteration of LNS. LB is often slow since it needs to solve an ILP of the same size as input. Our proposed heuristics, LB-RELAX and its variants, use the linear programming relaxation of LB to select neighborhoods. Empirically, LB-RELAX and its variants compute as effective neighborhoods as LB but run faster. They achieve state-of-the-art any-time performance on several ILP benchmarks.

关键词： integer linear program Large Neighborhood Search Heuristic Search

来源：评论

学校读者我要写书评

暂无评论

Stand-alone renewable power system scheduling for a green data center using integer linear programming

引用

JOURNAL OF SCHEDULING 2021年第5期24卷 523-541页

作者： Haddad, Maroua Nicod, Jean-Marc Pera, Marie-Cecile Varnier, Christophe Univ Bourgogne Franche Comte CNRS ENSMM FEMTO ST Inst Besancon France Univ Bourgogne Franche Comte FCLAB FEMTO ST Inst UFCCNRS Belfort France

In light of the rapid growth of data centers around the world and their huge energy consumption, several researchers have focused on the task scheduling and resource allocation problem in order to minimize the energy consumed by the data center. Other initiatives focus on the implementation of green energy sources in order to minimize the consumption of fossil fuels and their emission of CO2. As part of the ANR DATAZERO project (Pierson et al. in IEEE Access 7, 2019. https://***/10. 1109/ACCESS.2019.2930368), several research teams have engaged in efforts at defining the main concepts of a full green data center, powered only by renewable energy. Achieving this goal necessitates a focus on the efficient management of an autonomous hybrid power system consisting of solar panels, wind turbines, batteries, and fuel cell systems. The purpose of this work is not to show that a stand-alone data center is economically viable, but rather is feasible. This paper proposes a set of models based on mixed integer linear programs capable of managing the energy commitment to address data center power demand. The approach takes the season and weather forecasts into account at the time of optimization.

关键词： Renewable energy Wind turbine Photovoltaic panel Hybrid energy storage Data center integer linear program Optimization

来源：评论

学校读者我要写书评

暂无评论

A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem

引用

COMPUTERS & OPERATIONS RESEARCH 2023年第1期153卷

作者： Ma, Mengfan Men, Ziyang Rossi, Andre Zhou, Yi Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA Univ Paris 09 PSL LAMSADE UMR 7243 CNRS F-75016 Paris France

Given an undirected graph.. with a cost function on vertices, a collection of subgraphs of G such that in each subgraph, there are some distinguished vertices called terminals, the Partitioned Steiner Tree Problem (PSTP) asks for a minimum cost vertex set such that, in each of the given subgraph G(i), the graph induced by the vertex set spans the terminal set in G(i). The PSTP generalizes the well-known Steiner tree problem and has important applications in computational sustainability, network design, and social network analysis. However, for solving the PSTP, conventional integer programming approaches based on single-commodity flow, multi-commodity flow and subtour elimination integer linear programs, suffer from low computational efficiency due to a substantial number of variables. In this paper, we propose a compact vertex-separator-based integer linear programming formulation with much fewer variables. Enhancing inequalities are also studied for tightening the formulation. We further investigate a branch-and-cut algorithm, a local-branching heuristic algorithm, and a hybrid algorithm combining them. In experiments where both public real-world and synthetic graphs are used, our hybrid algorithm outperforms all conventional approaches, especially for large graphs with more than ten thousand vertices. Further tests also validate the effectiveness of the proposed formulation and enhancing inequalities.

关键词： Partitioned Steiner tree problem integer linear program Vertex-separator Branch-and-cut Local branching

来源：评论

学校读者我要写书评

暂无评论

Total Outer-Independent Domination Number: Bounds and Algorithms

引用

ALGORITHMS 2025年第3期18卷 159-159页

作者： Bosch, Paul Inza, Ernesto Parra Villamar, Ismael Rios Sanchez-Santiesteban, Jose Luis Univ Desarrollo Fac Ingn Santiago 7550000 Chile Univ Autonoma Estado Morelos Ctr Invest Ciencias Cuernavaca 62209 Mexico Univ Autonoma Guerrero Fac Matemat Chilpancingo 39070 Mexico Univ Autonoma Guerrero Fac Matemat Acapulco de Juarez 39650 Mexico

In graph theory, the study of domination sets has garnered significant interest due to its applications in network design and analysis. Consider a graph G(V,E);a subset of its vertices is a total dominating set (TDS) if, for each x is an element of V(G), there exists an edge in E(G) connecting x to at least one vertex within this subset. If the subgraph induced by the vertices outside the TDS has no edges, the set is called a total outer-independent dominating set (TOIDS). The total outer-independent domination number, denoted as gamma toi(G), represents the smallest cardinality of such a set. Deciding if a given graph has a TOIDS with at most r vertices is an NP-complete problem. This study introduces new lower and upper bounds for gamma toi(G) and presents an exact solution approach using integer linear programming (ILP). Additionally, we develop a heuristic and a procedure to efficiently obtain minimal TOIDS.

关键词： graph theory total outer-independent dominating set integer linear program heuristic algorithm time complexity

来源：评论

学校读者我要写书评

暂无评论

Truthful and Optimal Data Preservation in Base Station-less Sensor Networks: An Integrated Game Theory and Network Flow Approach

引用

ACM TRANSACTIONS ON SENSOR NETWORKS 2024年第1期20卷 1-40页

作者： Yu, Yuning Hsu, Shanglin Chen, Andre Chen, Yutian Tang, Bin Calif State Univ Dominguez Hills 1000 E Victoria St Carson CA 90747 USA Calif State Univ Long Beach 1250 Bellflower Blvd Long Beach CA 90840 USA

We aim to preserve a large amount of data generated inside base station-less sensor networks (BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration);as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP: data preservation problem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design aminimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit. In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of

关键词： Base station-less sensor networks data preservation energy-efficiency network flow (minimum cost flow and maximum flow) integer linear program game theory algorithmic mechanism design

来源：评论

学校读者我要写书评

暂无评论

A Non-linear Optimization Model for Controlling the Real Area of Contact in Surface Texture Design

引用

LUBRICANTS 2025年第4期13卷 163-163页

作者： Eksioglu, Sandra D. Zou, Min Univ Arkansas Coll Engn 4183 Bell Eng Bld Fayetteville AR 72701 USA

Motivated by the potential of surface texturing to enhance the tribological performance of micro- and nano-electromechanical systems (MEMS/NEMS), this study proposes a novel non-linear optimization approach for designing textured surfaces. This model minimizes the contact area between interacting surfaces and deformation during sliding under dry conditions by controlling key design parameters, such as the size and shape of the designed surface. We test the performance of the proposed model using the lotus leaf surface with dimensions of 248 x 136 micrometers. Due to the large size of the model, we propose a solution approach which consists of a data aggregation step, an optimization step, and a data disaggregation step. The optimization step decomposes the model into smaller models that are easier to solve. Via the sensitivity analysis, we highlight the trade-offs between data aggregation and model decomposition and their effect on the quality of the solutions found. In conclusion, our approach bridges the gap between fabrication capabilities and design requirements, paving the way for significant advances in tribological performance and surface engineering.

关键词： surface texture design integer linear program non-linear optimization

来源：评论

学校读者我要写书评

暂无评论

Best Match Graphs With Binary Trees

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第3期20卷 1679-1690页

作者： Schaller, David Geiss, Manuela Hellmuth, Marc Stadler, Peter F. F. Max Planck Inst Math Sci D-04103 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Dept Comp Sci Bioinformat Grp D-04107 Leipzig Germany Software Competence Ctr Hagenberg GmbH A-4232 Hagenberg Austria Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Vienna Inst Theoret Chem A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Sede Bogota Bogota 111321 Colombia Santa Fe Insitute Santa Fe NM 87501 USA

Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG is binary-explainable, i.e., whether it can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-refinable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.

关键词： Best match graphs binary trees rooted triple consistency polynomial-time algorithm NP-hardness integer linear program

来源：评论

学校读者我要写书评

暂无评论

A Network Flow Approach to Battery Electric Bus Scheduling

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2023年第9期24卷 9098-9109页

作者： Whitaker, Justin Droge, Greg Hansen, Matthew Mortensen, Daniel Gunther, Jacob Utah State Univ USU Dept Elect & Comp Engn Logan UT 84322 USA

A major challenge to adopting battery electric buses into bus fleets is the scheduling of the battery charging while considering route timing constraints and battery charge. This work develops a scheduling framework to balance the use of slow and fast chargers assuming the bus routes and charger locations are fixed. Slow chargers are utilized when possible to lower the cost of charging and fast chargers are used when needed to meet timing constraints and to ensure a sufficient charge for route execution. A directed graph is used to model the available charge times for buses that periodically return to the station to pick up passengers and to recharge its battery. A constrained network flow Mixed-integer linear program (MILP) problem is formulated to optimize the scheduling of chargers as well as to determine the number of chargers required to meet battery state of charge thresholds. Using a randomly generated route schedule for thirty buses, results are presented that demonstrate the ability of the proposed method to find optimal charging plans while considering time-of-use (TOU) costs and allowing for fixed and variable numbers of chargers. These optimal charging plans reduce costs up to 20.9% compared to a thresholding-based plan and up to 12.3% compared to an optimal strategy that does not consider the TOU costs.

关键词： integer linear program optimization optimal scheduling green transportation batteries power demand

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：