the incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integerprogramming solvers. these solvers are the foremost method for solving discrete ...
ISBN:
(纸本)9781713871088
the incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integerprogramming solvers. these solvers are the foremost method for solving discrete optimization problems and have a vast array of applications in machine learning, operations research, and many other fields. Choosing cutting planes effectively is a major research topic in the theory and practice of integerprogramming. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to an integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut. these guarantees apply to infinite families of cutting planes, such as the family of Gomory mixed integer cuts, which are responsible for the main breakthrough speedups of integerprogramming solvers. We exploit geometric and combinatorial structure of branch-and-cut in our analysis, which provides a key missing piece for the recent generalization theory of branch-and-cut.
We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as ...
详细信息
ISBN:
(纸本)9781467358125
We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as well as a preset budget and hop, the STPRBH seeks to find a subtree that includes the root node and maximizes the sum of the total edge revenues respecting the budget and hop constraints. these constraints impose limits on the total cost of the network and the number of edges between any vertex and the root. Not surprisingly, the STPRBH is NP-hard. For this challenging network design problem that arises in telecommunication settings and multicast routing, we present several polynomial size formulations. We propose an enhanced formulation based on the classical work of Miller, Tucker, and Zemlin by using additional set of variables representing the rank-order of visiting the nodes. Also, we investigate a new formulation for the STPRBH by tailoring a partial rank-1 of the Reformulation-Linearization Technique. Extensive results are exhibited using a set of benchmark instances to compare the proposed formulations by using a general purpose MIP solver.
Over the last few years, energy consumption and carbon emissions have been the subject of a great deal of attention, due to the ever-increasing climate change and diminishing of fossil energy resources. In this contex...
详细信息
ISBN:
(数字)9781728198811
ISBN:
(纸本)9781728198828
Over the last few years, energy consumption and carbon emissions have been the subject of a great deal of attention, due to the ever-increasing climate change and diminishing of fossil energy resources. In this context, this article aims to minimize the maximum completion time (makespan) by taking into account environmental aspects in a production system. In particular, we consider a flow shop group scheduling problem with sequence-dependent setup times, learning effect related to the ability of each operator as well as machine speeds and the various carbon emissions associated withthem, inspired by a real case study of the manufacture of forged connecting rods in a metallurgy factory. the objective is to determine both an optimal scheduling of the groups and the jobs within the groups in order to minimize the makespan by restricting the carbon emissions of the system. A mixed integer linear programming model is formulated, the computational results are also presented and discussed through the different scenarios.
Edge computing has emerged as a promising paradigm to fulfill the escalating demands of latency-sensitive and computationally intensive applications. In this context, efficient server deployment and service placement ...
Edge computing has emerged as a promising paradigm to fulfill the escalating demands of latency-sensitive and computationally intensive applications. In this context, efficient server deployment and service placement have become imperative to optimize performance and increase platform profit. In this paper, we investigate the problem of server deployment and service placement in a multi-user scenario, aiming to enhance the profit of Mobile Network Operators (MNOs) while considering constraints related to distance thresholds, resource limitations, and connectivity requirements. then, we propose a novel two-stage method to decouple the problem, breaking down server deployment and service placement into two distinct yet interconnected stages. In stage I, the server deployment is formulated as a combinatorialoptimization problem within the framework of a Markov Decision Process (MDP), where the state space, action space, and penalty function are defined to effectively model the issue. We propose the SDQ algorithm to establish a relatively stable server deployment strategy. In stage II, the service placement is formulated as a constrained integer linear programming problem. We propose the SPIB-TDB algorithm to optimize service placement. Extensive experimentation validates the exceptional performance of our proposed algorithms in enhancing the profit of MNOs.
Constraints applied on classic frequent patterns are too strict and may cause interesting patterns to be missed. Hence, researchers have proposed to mine a more relaxed version of frequent patterns, where transactions...
详细信息
Constraints applied on classic frequent patterns are too strict and may cause interesting patterns to be missed. Hence, researchers have proposed to mine a more relaxed version of frequent patterns, where transactions are allowed to miss some items in the itemset they support. Patterns exhibiting such "faults" are called frequent fault-tolerant patterns (FFT-patterns) if they are significant in number. In this paper, the term "pattern" is distinguished from "item-set" as referring to a pair (tidset x itemset). Unlike classical frequent patterns, the number of FFT-patterns grows exponentially not only withthe number of items, but also withthe number of transactions. Since the latter may reach millions, mining FFT-patterns by enumerating them becomes infeasible. Hence, the challenge is to represent FFT-patterns concisely without losing any useful information. To address this, we draw on the observation that, in transactional databases, the transactions themselves are not important from the data mining point-of-view;i.e. researchers are interested in finding itemsets contained in lots of transactions, rather than in the transactions per se. therefore, we propose to mine only the frequent itemsets along withthe statistical information of the supporting transaction sets, rather than enumerate entire FFT-patterns. then we present our approach - the BIAS framework, consisting of Backtracking algorithm, integer Linear programming (ILP) constraints, and aggregation statistics to solve this problem. Algorithms under this framework not only increase the efficiency of the FFT-patterns mining process by more than an order of magnitude, but also provide a more comprehensive analysis of FFT-Patterns.
To tackle the massive access and different computation offloading requirements of IoT devices in 5G MEC system, Dynamic User Pairing NOMA-based offloading is considered in this paper. An overall energy consumption min...
详细信息
To tackle the massive access and different computation offloading requirements of IoT devices in 5G MEC system, Dynamic User Pairing NOMA-based offloading is considered in this paper. An overall energy consumption minimization framework is established by joint optimizing user pairing, of-floading decision and uplink power control under the time and maximum multiplexing number of user constraints. Due to the combinatorial nature of the formulated mixed integer non-linear programming problem, we adapt two-phase approach to solve the challenging problem. First, a low-complexity heuristic algorithm is designed to solve the user pairing problem. After we get the sub-optimal user pairing scheme, the original problem is proved to be a convex problem, we then get the optimal offloading decision and transmission power of devices. Numerical results show that the proposed DUP NOMA-based offloading scheme can significantly improve system performance in terms of energy consumption comparing to OMA and Fixed User Pairing NOMA based offloading.
Network Function Virtualization (NFV) enables cloud service providers (CSPs) to flexibly place their network functions on common off-the-shelf servers in the form of virtual network functions (VNF), without incurring ...
详细信息
ISBN:
(数字)9781728187808
ISBN:
(纸本)9781728187815
Network Function Virtualization (NFV) enables cloud service providers (CSPs) to flexibly place their network functions on common off-the-shelf servers in the form of virtual network functions (VNF), without incurring costly capital and operating expenses (CAPEX/OPEX). In the NFV-enabled network, service function chains (SFCs) are responsible for accomplishing users' service requests by steering traffic through a set of VNFs in a specified order. therefore, it is an important but intractable issue for CSPs to devise an optimal VNF placement scheme to enhance network performance and profits. In this paper, we focus on the VNF placement problem for mapping SFC requests (SFCRs) in NFV-enabled networks, considering the delay requirement of SFCRs. To improve resource utilization, we consider the basic resource overheads and sharability of VNF instances. then we formulate the problem as an integer linear programming (ILP) model, withthe purpose of total resource consumption minimization. Afterward, the novel SFCR mapping algorithm (SMA) and VNF request adjustment algorithm (VAA) are proposed to map SFCRs and optimize the placement of VNF requests. Simulation results show that our approach is near-optimal in terms of node resource consumption. Besides, it provides higher performance in terms of node resource consumption, average VNF utilization and the number of activated servers compared withthe benchmarks.
A solver’s runtime and the quality of the solutions it generates are strongly influenced by its parameter settings. Finding good parameter configurations is a formidable challenge, even for fixed problem instance dis...
详细信息
ISBN:
(纸本)9783031248658
A solver’s runtime and the quality of the solutions it generates are strongly influenced by its parameter settings. Finding good parameter configurations is a formidable challenge, even for fixed problem instance distributions. However, when the instance distribution can change over time, a once effective configuration may no longer provide adequate performance. Realtime algorithm configuration (RAC) offers assistance in finding high-quality configurations for such distributions by automatically adjusting the configurations it recommends based on instances seen so far. Existing RAC methods treat the solver to be configured as a black box, meaning the solver is given a configuration as input, and it outputs either a solution or runtime as an objective function for the configurator. However, analyzing intermediate output from the solver can enable configurators to avoid wasting time on poorly performing configurations. To this end, we propose a gray-box approach that utilizes intermediate output during evaluation and implement it within *** pairwise comparisons to determine whether ongoing evaluations can be terminated to free resources. We compare our realtime gray-box configurator to a black-box equivalent on several experimental settings and show that our approach reduces the total solving time in several scenarios.
A major concern in designing sensor networks is the deployment problem. However, establishing an efficient algorithm for the real-world deployment problem is challenging due to three issues, which are 1) the realistic...
A major concern in designing sensor networks is the deployment problem. However, establishing an efficient algorithm for the real-world deployment problem is challenging due to three issues, which are 1) the realistic mixed-integer nonlinear programming problem (MINLP) with mixed-variable; 2) the combinatorial subset selection problem; and 3) the expensive computational cost for fitness evaluation in the 3-D coverage problem. therefore, this paper addresses these challenges and proposes a surrogate-assisted hybrid metaheuristic for mixed-variable 3-D deployment optimization of directional sensor networks (DSNs). First, an MINLP with flexible coordinate transformation technique and an efficient mixed-variable encoding scheme are introduced to model and represent the problem. We propose hybrid metaheuristic which applies two reproduction methods respectively for discrete and continuous variables. Second, we design sparse population-based incremental learning (s-PBIL) to handle inherent subset selection problem. s-PBIL could accurately learn the required information, and automatically learn a sparse distribution. third, a mixed-variable surrogate with unifying space under Bayesian model management is incorporated to reduce the expensive computational cost. Experiment results on real-world deployment scenarios scaling from small-size to large-size show the effectiveness of the proposed algorithm.
the paper deals with low-power adaptive scheduling of synchronous and flexible real-time OS tasks. A software reconfiguration scenario is assumed to be any run-time operation allowing the addition-removal-update of OS...
详细信息
the paper deals with low-power adaptive scheduling of synchronous and flexible real-time OS tasks. A software reconfiguration scenario is assumed to be any run-time operation allowing the addition-removal-update of OS tasks to adapt the system to its environment under well-defined conditions. the problem is that any reconfiguration can push the system to an unfeasible behavior where temporal properties are violated or the energy consumption is possibly high and unacceptable. A task in the system can change its characteristics at any time when a reconfiguration scenario is applied, it can also be stopped or replaced by another one. the difficulty is how to find the new temporal parameters of the systems tasks after any reconfiguration. We use a DVS processor which is with a variable speed to support run-time solutions that re-obtain the system's feasibility. the challenge is how to compute the best combinations between available processor speeds for a good compromise between execution time and energy consumption. We propose a combinatorialoptimization method based on integerprogramming and heuristics. We propose also a solution when the available speeds do not allow the feasibility of the system. Both approaches include a mechanism to adjust the deadlines of tasks to satisfy the feasibility conditions and overcome the problem of rejected tasks. this mechanism makes the scheduling more flexible and able to react in accordance with its environment.
暂无评论