A global forcing set for maximal matchings of a graph G = (V(G), E(G)) is a set S subset of E(G) such that M-1 boolean AND S # M-2 boolean AND S for each pair of maximal matchings M-1 and M-2 of G. The smallest such s...
详细信息
A global forcing set for maximal matchings of a graph G = (V(G), E(G)) is a set S subset of E(G) such that M-1 boolean AND S # M-2 boolean AND S for each pair of maximal matchings M-1 and M-2 of G. The smallest such set is called a minimum global forcing set, its size being the global forcing number for maximal matchings phi(gm) (G) of G. In this paper, we establish lower and upper bounds on the forcing number for maximal matchings of the corona product of graphs. We also introduce an integer linear programming model for computing the forcing number for maximal matchings of graphs.
Multiple Constant Multiplication (MCM) is a ubiquitous problem for numerous computation-intensive applications. One efficient approach is to replace generic multipliers by multiplierless architectures based on bit-shi...
详细信息
ISBN:
(纸本)9798350341515
Multiple Constant Multiplication (MCM) is a ubiquitous problem for numerous computation-intensive applications. One efficient approach is to replace generic multipliers by multiplierless architectures based on bit-shifts and additions. The adder graphs describing the multiplierless circuits can be optimized according to various metrics. In this paper, we optimize for throughput and improve the state-of-the-art for the design of pipelined adder graphs. In contrast to existing approaches, which pipeline a posteriori or use heuristics, our solution is to optimally solve the pipelined adder graph design problem using Mixed-integer linear programming (MILP). We first model the pipelining and its cost, and then incorporate it into the state-of-the-art ILP model for the MCM design. Fusing the MCM design with pipelining into a single global optimization problem exactly solved by powerful MILP solvers demonstrated clear benefits on numerous benchmarks. Moreover, mathematical modeling allows for an easily extendable tool which can adapt to evolving hardware models/metrics.
We show how to extend the integerprogramming (IP) approach to score-based causal discovery by including pricing. Pricing allows the addition of new IP variables during solving, rather than requiring them all to be pr...
详细信息
We show how to extend the integerprogramming (IP) approach to score-based causal discovery by including pricing. Pricing allows the addition of new IP variables during solving, rather than requiring them all to be present initially. The dual values of acyclicity constraints allow this addition to be done in a principled way. We have extended the GOBNILP algorithm to effect a branch-price-and-cut method for DAG learning. Empirical results show that implementing a delayed pricing approach can be beneficial. The current pricing algorithm in GOBNILP is slow, so further work on fast pricing is required.
Missing or incomplete data poses a significant challenge during data collection for forecasting, estimation, and decision-making purposes. Given the profound impact of data quality on the performance of machine learni...
详细信息
ISBN:
(纸本)9798350361513;9798350372304
Missing or incomplete data poses a significant challenge during data collection for forecasting, estimation, and decision-making purposes. Given the profound impact of data quality on the performance of machine learning algorithms, data imputation plays a crucial role in many applications. Considering potential dependencies between data attributes enhances the reliability of the imputation process. In this paper, we address this by incorporating fuzzy relaxation in the differential dependencies (DDs) among attributes and propose a novel fuzzy multi-objective linear (FMOL) model to achieve optimal imputation performance. The proposed model aims to maximize the imputation rate while minimizing violations of crisp DDs. We employ the Improved Zimmermann Method to solve the FMOL model effectively. Experimental results on the Kaggle dataset demonstrate that our proposed approach outperforms existing methods in terms of imputed fields and imputation accuracy.
The top two divisions of the Argentinean professional basketball system have since 2014-2015 used a season schedule format similar to that used by the NBA in which games are played all through the week, replacing the ...
详细信息
The top two divisions of the Argentinean professional basketball system have since 2014-2015 used a season schedule format similar to that used by the NBA in which games are played all through the week, replacing the previous setup where all games were scheduled on weekends. This change has confronted the Argentinean league organizers with new scheduling challenges, one of which is the assignment of referees to games. The present article addresses this assignment problem using a tool based on an integer linear programming model. The objective is to minimize the total cost of trips made by the referees while also satisfying a series of other conditions. The problem is broken down into a series of relatively small subproblems representing successive periods of the season, and the solution is obtained using a rolling horizon heuristic. The approach was tested by applying it to the First Division's 2015-2016 season, the last one before introducing the approach presented in this article, when referees were still assigned using manual methods. The travel costs simulated by the model were 26% lower than the total travel costs actually incurred under the manual assignments, and all of the restrictions that had been requested by league officials were satisfied. The model was used by the First Division for the 2016-2017 and 2017-2018 seasons and in 2017-2018 also by the Second Division.
Motivated by power system cyber-physical security applications, this article investigates a variant of the connected dominating set problem called the relaxed connected dominating set (RCDS) problem, where between eve...
详细信息
Motivated by power system cyber-physical security applications, this article investigates a variant of the connected dominating set problem called the relaxed connected dominating set (RCDS) problem, where between every two nodes in the solution dominating set there exists a path not traversing two consecutive nodes not in the set. The RCDS problem is NP-hard. To facilitate solving, presolving and problem reduction techniques are developed. In addition, three integer program formulations are obtained using single commodity flow, Dantzig-Fulkerson-Johnson and Miller-Tucker-Zemlin ideas to enforce graph connectedness. For a realistic power network repository (MATPOWER 7) including graphs with 70k nodes, our presolving and reduction procedures simplify problem instances to on average 30% of the original sizes. All reduced instances, when modeled by our formulations, can be solved with optimality gap less than 0.5% within 20 min using a PC with Gurobi 9.
This paper proposes a scheduling model for updating resource allocations for virtualized networks (VNs) without congestion. The proposed model determines the schedule of migrating traffic flows on VNs from old routes ...
详细信息
ISBN:
(纸本)9798350310900
This paper proposes a scheduling model for updating resource allocations for virtualized networks (VNs) without congestion. The proposed model determines the schedule of migrating traffic flows on VNs from old routes to new routes. The model aims to minimize the number of rounds required to complete the update of all existing VNs. We evaluate the performance of model in terms of the percentage of trials where feasible update scheduling exists and the number of rounds required to complete the update. Numerical results show that more rounds are required to achieve congestion-free update when the traffic demand or the number of VNs increases. The number of required rounds tends to remain the same when the maximum number of rounds exceeds a certain value;this observation helps network operators estimate the time required for VN update.
Purpose The purpose of this paper is to describe an integer linear programming model to schedule the maintenance crew and the maintenance tasks in a bus operating company. Design/methodology/approach The proposed meth...
详细信息
Purpose The purpose of this paper is to describe an integer linear programming model to schedule the maintenance crew and the maintenance tasks in a bus operating company. Design/methodology/approach The proposed methodology relies on an integer linear programming model that finds feasible maintenance schedules. It minimizes the costs associated with maintenance crew and the costs associated with unavailability. The model is applied in a real-world case study of a Portuguese bus operating company. A constructive heuristic approach is put forward, based on solving the maintenance scheduling problem for each bus separately. Findings The heuristic finds better solutions than the exact methods (based on branch-and-bound techniques) in a much lower computational time. Practical implications The results suggest the relevance of such heuristic approaches for maintenance scheduling in practice. Originality/value This proposed model is an effective decision-making support method that provides feasible maintenance schedules for the maintenance technicians and for the maintenance tasks in a fleet of buses. It also complies with several operational, technical and labour constraints.
This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Gu...
详细信息
This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Guillotine constraints seek to ensure that items are arranged in such a way that cuts from one edge of the container to the opposite edge completely separate them. In particular, we consider the possibility of 2, 3, and 4 cutting stages in a predefined sequence. These constraints are considered within a two-level iterative approach that combines the resolution of integer linear programming and constraint programming models. Experiments with instances of the literature are carried out, and the results show that the proposed approach can solve in less than 500 s approximately 60% and 50% of the instances for the two- and three-dimensional cases, respectively. For the two-dimensional case, in comparison with the recent literature, it was possible to improve the upper bound for 16% of the instances.
The solar power plant is a large-scale photovoltaic (PV) system aimed to generate solar power for the electricity grid. It includes PV arrays (PVAs), cables, and other electrical accessories. Moreover, the solar power...
详细信息
ISBN:
(纸本)9798350315097
The solar power plant is a large-scale photovoltaic (PV) system aimed to generate solar power for the electricity grid. It includes PV arrays (PVAs), cables, and other electrical accessories. Moreover, the solar power plant builder must consider various parameters and design regulations. The cable routing problem (CRP) is critical in large-scale solar power plant design. The objective of our CRP is to minimize the installation cost of the cable by determining the partition of the photovoltaic array and the cable routing. In this study, we use the quantum computer to solve the CRP, an NP-hard integer linear programming (ILP) problem, and show its advantages over classic computers. We transfer the ILP CRP into the quadratic unconstrained binary optimization (QUBO) model and solve it by the advanced quantum annealer. Finally, we analyze the computational results and discuss the advantages of our approach to solving the CRP.
暂无评论