integer linear programs (ILPs) and mixed integerprograms (MIPs) often have multiple distinct optimal solutions, yet the widely used Gurobi optimization solver returns certain solutions at disproportionately high freq...
详细信息
integer linear programs (ILPs) and mixed integerprograms (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 integerprogramming Library (MIPLIB) instances and on a combinatorial optimization problem in cancer genomics.
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 structure...
详细信息
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.
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 larg...
详细信息
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 linearprogramming 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.
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 ...
详细信息
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.
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 (PS...
详细信息
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 integerprogramming 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.
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) ...
详细信息
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.
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 ...
详细信息
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
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 design...
详细信息
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.
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-expl...
详细信息
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.
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 t...
详细信息
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.
暂无评论