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

A Risk Reduction Approach in Optical Backbone Network

学校读者我要写书评

暂无评论

A Risk Reduction Approach in Optical Backbone Network

IEEE International Conference on Signal Processing, Computing and Control (ISPCC)

作者： Dinesh Kumar Rajiv Kumar Neeru Sharma JUIT Waknaghat Solan HP India

ISBN: (纸本)9781728139890

Optical networks are widely used today and in case of any natural disaster, they ensure connectivity. Disaster management schemes proposed in past have many problems associated with them; cost of recovery of fiber being the major one. A small interruption in the optical network results in the loss of large number of data packets during the recovery processes and sometimes the recovery process takes a long time. To address these problems, the low risk failure optical network can be designed by considering the seismic hazard map of India. In this paper, we propose a restoration model to cater the sudden failure in the optical network. New links are added to the network. We have tried to increase the capacity of the safer links and their subsequent physical routes under minimum cost with the aim to reduce the possibilities of failure in the network. The mathematical model for integer linear programming (ILP) for risk aware provisioning scheme has been proposed, the proactive and reactive approach has also been discussed. The proposed scheme reduces the possibility of failure in communication network caused by the disaster.

关键词： disasters emergency management integer programming linear programming optical fibre networks risk management telecommunication network reliability telecommunication network routing Fiber optic networks telecommunication network reliability telecommunication network routing crisis management backbone network integer programming linear programming Risk Management Disasters data packets Emergency Services RECOVERY PROCESS sudden failure HAZARD MAPPING Probability

Approximate Submodularity and Its Implications in Discrete Optimization

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Ajayi, Temitayo Lee, Taewoo Schaefer, Andrew J. Nature Source Improved Plants United States Department of Industrial Engineering University of Houston United States

Submodularity is a key property in discrete optimization. Submodularity has been widely used for analyzing the greedy algorithm to give performance bounds and providing insight into the construction of valid inequalities for mixed-integer programs. In recent years, researchers started to study approximate submodularity, with a primary focus on providing performance bounds for iterative approaches. In this paper, we study approximate submodularity from a different perspective in order to broaden its use cases in discrete optimization. We define metrics that quantify approximate submodularity, which we then use to derive new properties about both approximate submodularity preservation and the well-known Lovász extension for set functions. We also show that previous analyses of mixed-integer sets, such as the submodular knapsack polytope, can be extended to the approximate submodularity setting. Our work demonstrates that one may generalize many of the analytical tools used in submodular optimization into the approximate submodularity context. Copyright © 2019, The Authors. All rights reserved.

关键词： integer programming

A computational comparison of optimization methods for the Golomb ruler problem

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Kocuk, Burak van Hoeve, Willem-Jan Sabancı University Istanbul34956 Turkey Carnegie Mellon University PittsburghPA15213 United States

The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and communications, and it can be seen as a challenge for combinatorial optimization algorithms. Although constructing high quality rulers is well-studied, proving optimality is a far more challenging task. In this paper, we provide a computational comparison of different optimization paradigms, each using a different model (linear integer, constraint programming and quadratic integer) to certify that a given Golomb ruler is optimal. We propose several enhancements to improve the computational performance of each method by exploring bound tightening, valid inequalities, cutting planes and branching strategies. We conclude that a certain quadratic integer programming model solved through a Benders decomposition and strengthened by two types of valid inequalities performs the best in terms of solution time for small-sized Golomb ruler problem instances. On the other hand, a constraint programming model improved by range reduction and a particular branching strategy could have more potential to solve larger size instances due to its promising parallelization features. Copyright © 2019, The Authors. All rights reserved.

关键词： integer programming

The disassembly line design problem

学校读者我要写书评

暂无评论

The disassembly line design problem

International Conference on Industrial Engineering and Systems Management (IESM)

作者： Jinlin Li Xiaohong Chen Chengbin Chu School of Business Central South University Changsha P.R. China Département Ingénierie des Systèmes Université Paris-Est ESIEE Paris Noisy le Grand CEDEX France

In the design of disassembly lines, the equipment requirements is a common index to measure the cost-efficiency of a processing alternative, but it is seldom considered in the literature. This paper investigates the integrated decision of disassembly line balancing and equipment configuration, i.e., the disassembly line design problem. A linear mixed integer programming (MIP) formulation is developed, and a dynamic programming approach is proposed to solve the problem.

关键词： Task analysis Robots Tools Dynamic programming Manuals Indexes integer programming

Balanced ranking with diversity constraints

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Yang, Ke Gkatzelis, Vasilis Stoyanovich, Julia New York University Department of Computer Science and Engineering Drexel University Department of Computer Science

Many set selection and ranking algorithms have recently been enhanced with diversity constraints that aim to explicitly increase representation of historically disadvantaged populations, or to improve the overall representativeness of the selected set. An unintended consequence of these constraints, however, is reduced in-group fairness: the selected candidates from a given group may not be the best ones, and this unfairness may not be well-balanced across groups. In this paper we study this phenomenon using datasets that comprise multiple sensitive attributes. We then introduce additional constraints, aimed at balancing the in-group fairness across groups, and formalize the induced optimization problems as integer linear programs. Using these programs, we conduct an experimental evaluation with real datasets, and quantify the feasible trade-offs between balance and overall performance in the presence of diversity constraints. Copyright © 2019, The Authors. All rights reserved.

关键词： integer programming

Inferring lower runtime bounds for integer programs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Frohn, Florian Naaf, Matthias Brockschmidt, Marc Giesl, Jürgen Max Planck Institute for Informatics Saarland Informatics Campus Campus E1 4 Saarbrücken66123 Germany RWTH Aachen University Aachen Germany Microsoft Research Cambridge United Kingdom LuFG Informatik 2 RWTH Aachen University Ahornstr. 55 Aachen52074 Germany

We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symbolic representations of program executions using a framework for iterative, under-approximating program simpliﬁcation. The core of this simpliﬁcation is a method for (under-approximating) program acceleration based on recurrence solving and a variation of ranking functions. Afterwards, we deduce asymptotic lower bounds from the resulting simpliﬁed programs using a special-purpose calculus and an SMT encoding. We implemented our technique in our tool LoAT and show that it infers non-trivial lower bounds for a large class of examples. Copyright © 2019, The Authors. All rights reserved.

关键词： integer programming

Image Captioning with Clause-Focused Metrics in a Multi-Modal Setting for Marketing

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Harzig, Philipp Zecha, Dan Lienhart, Rainer Kaiser, Carolin Schallner, René Multimedia Computing and Computer Vision Lab University of Augsburg Augsburg86159 Germany GfK Verein Nuremberg90419 Germany

Automatically generating descriptive captions for images is a well-researched area in computer vision. However, existing evaluation approaches focus on measuring the similarity between two sentences disregarding fine-grained semantics of the captions. In our setting of images depicting persons interacting with branded products, the subject, predicate, object and the name of the branded product are important evaluation criteria of the generated captions. Generating image captions with these constraints is a new challenge, which we tackle in this work. By simultaneously predicting integer-valued ratings that describe attributes of the human-product interaction, we optimize a deep neural network architecture in a multi-task learning setting, which considerably improves the caption quality. Furthermore, we introduce a novel metric that allows us to assess whether the generated captions meet our requirements (i.e., subject, predicate, object, and product name) and describe a series of experiments on caption quality and how to address annotator disagreements for the image ratings with an approach called soft targets. We also show that our novel clause-focused metrics are also applicable to other image captioning datasets, such as the popular MSCOCO dataset. Copyright © 2019, The Authors. All rights reserved.

关键词： integer programming

Temporal ordered clustering in dynamic networks

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Turowski, Krzysztof Sreedharan, Jithin K. Szpankowski, Wojciech Center for Science of Information Dept. of Computer Science Purdue University West LafayetteIN United States

In temporal ordered clustering, given a single snapshot of a dynamic network, we aim at partitioning its nodes into K ordered clusters C1 ă ¨ ¨ ¨ ă CK such that for i ă j nodes in cluster Ci arrive to the dynamic graph before nodes in cluster Cj. The problem of inferring evolution of a dynamic network is of considerable significance in many applications ranging from predicting the age of proteins to track the expansion of fake news in online social networks. We first formulate our problem for a general dynamic graph, and propose an integer programming framework that finds the optimal partial order, which describes the clusters achieving the best precision (i.e., fraction of successfully ordered node pairs in the partial order) for a particular density (i.e., fraction of comparable node pairs in the partial order). We provide a method to solve a linear programming relaxation of the original optimization using importance sampling on a Markov chain corresponding to the graph evolution. Inspired by this solution, we design unsupervised and supervised algorithms to find temporal ordered clusters. Finally, we instantiate our model to the duplication-divergence model (also known as the vertex copying model) which turns out to present a real challenge when compared to other network models, as explained in the paper. We validate the proposed algorithms tailored to the duplication-divergence model on synthetic data and various real-world networks. Copyright © 2019, The Authors. All rights reserved.

关键词： integer programming

Compact MILP Formulations for the p-Center Problem 1

学校读者我要写书评

暂无评论

5th International Symposium on Combinatorial Optimization (ISCO)

作者： Ales, Zacharie Elloumi, Sourour ENSTA ParisTech UMA F-91762 Palaiseau France Lab CEDRIC Paris France

ISBN: (数字)9783319961514

ISBN: (纸本)9783319961514;9783319961507

The p-center problem consists in selecting p centers among M to cover N clients, such that the maximal distance between a client and its closest selected center is minimized. For this problem we propose two new and compact integer formulations. Our first formulation is an improvement of a previous formulation. It significantly decreases the number of constraints while preserving the optimal value of the linear relaxation. Our second formulation contains less variables and constraints but it has a weaker linear relaxation bound. We besides introduce an algorithm which enables us to compute strong bounds and significantly reduce the size of our formulations. Finally, the efficiency of the algorithm and the proposed formulations are compared in terms of quality of the linear relaxation and computation time over instances from OR-Library.

关键词： p-center Discrete location Equivalent formulations integer programming