We consider sensitivity analysis for mixedbinaryquadratic Programs (MBQPs) with respect to changing right-hand-sides (rhs). We show that even if the optimal solution of a given MBQP is known, it is NP-hard to approx...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We consider sensitivity analysis for mixedbinaryquadratic Programs (MBQPs) with respect to changing right-hand-sides (rhs). We show that even if the optimal solution of a given MBQP is known, it is NP-hard to approximate the change in objective function value with respect to changes in rhs. Next, we study algorithmic approaches to obtaining dual bounds for MBQP with changing rhs. We leverage Burer's completely-positive (CPP) reformulation of MBQPs. Its dual is an instance of co-positive programming (COP), and can be used to obtain sensitivity bounds. We prove that strong duality between the CPP and COP problems holds if the feasible region is bounded or if the objective function is convex, while the duality gap can be strictly positive if neither condition is met. We also show that the COP dual has multiple optimal solutions, and the choice of the dual solution affects the quality of the bounds with rhs changes. We finally provide a method for finding good nearly optimal dual solutions, and we present preliminary computational results on sensitivity analysis for MBQPs.
Many-core Network-on-Chip (NoC) processors are emerging in broad application areas, including those with timing requirements, such as real-time and multimedia applications. Typically, these processors employ core-leve...
详细信息
Many-core Network-on-Chip (NoC) processors are emerging in broad application areas, including those with timing requirements, such as real-time and multimedia applications. Typically, these processors employ core-level backup to improve yield. However, when defective cores are replaced by backup ones, the NoC topology changes. Consequently, a fine-tuned application based on timing parameters given by one topology may not meet the expected timing behavior under the new one. We first develop a metric to measure timing similarity of an application on different NoC topologies and then propose mixed binary quadratic programming and greedy algorithms to reconfigure a defect-tolerant many-core NoC.
Techniques based on sharing data and computation among queries have been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is ...
详细信息
Techniques based on sharing data and computation among queries have been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of rigorous modeling and theoretical study for query processing and optimization. Query batching in database systems has strong resemblance to order batching in the warehousing context. While the latter is a well-studied problem, the literature on optimization techniques for query batching problem is quite scarce/nonexistent. In this study, we develop a mixedbinaryquadratic Program (MBQP) to optimize query-batching in a database system. This model uses the coefficients of a linear regression on the query retrieval time, trained by a large set of randomly generated query sets. We also propose two heuristics, the so-called restricted-cardinality search methods I and II, for solving the proposed MBQP. To demonstrate the effectiveness of our proposed techniques, we conduct a comprehensive computational study over randomly generated instances of three well-known database benchmarks. The computational results show that when the proposed MBQP is solved using the designed heuristics, an improvement of up to 61.8% in retrieving time is achieved. (C) 2020 Elsevier Ltd. All rights reserved.
暂无评论