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

integer programs with prescribed number of solutions and a weighted version of Doignon-bell-scarf's theorem

17th international conference on integer programming and combinatorial optimization, IPCO 2014

作者： Aliev, Iskander De Loera, Jesús A. Louveaux, Quentin Cardiff University United Kingdom University of California Davis United States Université de Liège Belgium

ISBN: (纸本)9783319075563

In this paper we study a generalization of the classical feasibility problem in integer linear programming, where an ILP needs to have a prescribed number of solutions to be considered solved. We first provide a generalization of the famous Doignon-Bell-Scarf theorem: Given an integer k, we prove that there exists a constant c(k,n), depending only on the dimension n and k, such that if a polyhedron {x: Ax≤b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. the second contribution of the article presents a structure theory that characterizes precisely the set sg ≥ k (A) of all vectors b such that the problem Ax = b, x ≥ 0, x Ε Zn, has at least k-solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computation. Similar results can be derived for those right-hand-side vectors that have exactly k solutions or fewer than k solutions. Finally we show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of sg ≥ (A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have exactly k solutions (similarly for at least k or less than k solutions). Under the same assumptions we prove that the k-Frobenius number can be computed in polynomial time. © 2014 Springer international Publishing Switzerland.

关键词： Bells

来源：评论

学校读者我要写书评

暂无评论

AN ANALYSIS OF OPTIMIZED CAPEX FOR MULTI-CORE FIBER BASED OPTICAL NETWORKS

AN ANALYSIS OF OPTIMIZED CAPEX FOR MULTI-CORE FIBER BASED OP...

引用

the 13th international conference on Optical Communications and Networks, ICOCN 2014(2014第13届光通信与网络国际会议)

作者： Yao Li Nan Hua Xiaoping Zheng Tsinghua National Laboratory for Information Science and Technology Department of Electronic Engineering Tsinghua UniversityBeijing 100084P.R. China

In this article,we investigate the costs of optical network Capital Expenditure(CapEx)components which include fiber,optical amplifier(OA),cable and *** CapEx of high-capacity optical network under given traffic requests is optimized,and results are analyzed to evaluate the influences of Multi-core Fiber(MCF)communication system on the components of optical network *** solve the optimization problem,network CapEx is modelled and an integer linear programming(ILP)formulation is *** results show that by using MCF communication system,optical network CapEx can be reduced *** cost of OA takes the largest proportion of the network CapEx,and can be reduced by deploying MCF communication system to optical *** density can be increased by using MCF,thus decreasing the costs of cable and conduit.

关键词： Multi-core fiber Network CapEx optimization integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Supplier Selection by Multi-Attribute combinatorial Bidding

Supplier Selection by Multi-Attribute Combinatorial Bidding

引用

Hawaii international conference on System Sciences

作者： Joice Cavalheiro Ribeiro Giacon Hugo T. Yoshida Yoshizaki Gilberto Montibeller Universidade de Sao Paulo London School of Economics and Political Science

ISBN: (纸本)9781479925056

Supplier selection is a challenging decision that has strategic importance for organizations. Cost is no longer the sole factor in the selection of suppliers, and the complexity of this issue arises from the interplay of several situation-specific criteria (such as total cost, CO_(2e) emissions, development time, lead time) as well as the combinatorial nature of this problem. this paper proposes an approach based on combinatorial optimization (integer linear programming) combined with multi-criteria value analysis to establish priorities and trade-offs among the defined criteria for combinatorial bidding. the approach was employed in a real-world decision, the selection of a supplier for a cosmetics packaging set for a new product line. the obtained solution is compared against standard multi-criteria optimization (without a combinatorial auction formulation) and also against single criterion optimization. the paper also reports on the challenges and advantages of applying the framework in the case study.

关键词： Mathematical model Equations optimization Analytical models Companies Adaptation models Computational modeling

来源：评论

学校读者我要写书评

暂无评论

A new algorithm for dynamic scheduling with partially substitutability constrained resource on critical chain 8

引用

8th international conference on Management Science and Engineering Management, ICMSEM 2014

作者： Yang, Qin Wang, Yushi Wu, S. Wang, Wenke Wang, Tingting Business School Sichuan Normal University Chengdu610064 China

ISBN: (纸本)9783642551215

A dynamic scheduling for the constrained resource with partially substitutability based on the critical chain can not only improve the work efficiency of the system, but also achieve the replacement of resources and reduce the utilization of the core resources. this problem is influenced by operating time and setup time of jobs and aims at minimizing total tardiness. Plant growth simulation algorithm is inspired by the photostrophism mechanism and mainly be utilized to solve the global optimization of integer programming problem in the beginning. It possesses the convenience to determine the parameters, stability and accuracy to solve the problem and excellent global optimization ability which make it get extensive and effective application and promotion inmany engineering and technical fields. Firstly, describe the problem as a dynamic scheduling problem with machine eligibility restrictions who has machines in parallel with different speeds and jobs with different release date and due date. Secondlymodel the scheduling problem and design the rescheduling rule according to the time series of jobs. thirdly, adopt and optimize the new algorithm-plant growth simulation algorithm to get optimization by iterating. Finally, conduct simulation experiment and test the feasibility and superiority of the method by comparing with PSO and GA. © Springer-Verlag Berlin Heidelberg 2014.

关键词： Global optimization

来源：评论

学校读者我要写书评

暂无评论

An improved ACO algorithm for the bin packing problem with conflicts based on graph coloring model

An improved ACO algorithm for the bin packing problem with c...

引用

international conference on Management Science and Engineering (ICMSE)

作者： Ye Yuan Yi-jun Li Yan-qing Wang School of Management Harbin Institute of Technology Harbin Heilongjiang CN

Bin packing problem with conflicts(BPPC) is a complex combinatorial optimization problem originated from logistics, whose objective is packing all the items with the least number of bins and satisfying the conflict constraints among the items. In this paper, we firstly give the description and 0-1 integer programming model of BPPC, and then transform the model into the representation of conflict graph structure. After that, an ant colony optimization(ACO) algorithm framework is proposed for solving the conflict elimination procedure of BPPC based on a graph coloring heuristic, according to the results of conflict elimination, an improved first-fit decreasing algorithm is used to finish the packing operations of the subsets of items without conflicts. the experiments show that the improve ACO algorithm in this paper is valid and could provide a feasible and high-quality solutions of BPPC efficiently.

关键词： Algorithm design and analysis Heuristic algorithms Image color analysis Color optimization Graph theory Linear programming

来源：评论

学校读者我要写书评

暂无评论

Adaptive embedded systems: New composed technical solutions for feasible low-power and real-time flexible OS tasks

Adaptive embedded systems: New composed technical solutions ...

引用

international conference on Informatics in Control, Automation and Robotics (ICINCO)

作者： Hamza Chniter Mohamed Khalgui Fethi Jarray INSAT Institute University of Carthage Carthage Tunisia ISI Institute Mednine Tunisia FST faculty University of Elmanar Elmanar Tunisia Laboratoire CEDRIC CNAM France

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 combinatorial optimization method based on integer programming 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.

关键词： Real-time systems Energy consumption Embedded systems Linear programming Processor scheduling Time factors Computational modeling

来源：评论

学校读者我要写书评

暂无评论

Advances in discrete optimization

引用

optimization 2013年第8期62卷 1003-1006页

作者： Sifaleras, Angelo Paparrizos, Konstantinos Demyanov, Vladimir F. Univ Macedonia Dept Technol Management Naousa Greece Univ Macedonia Dept Appl Informat Thessaloniki Greece St Petersburg State Univ Dept Appl Math & Control Proc St Petersburg 199034 Russia

We are presenting in this special issue selected, peer-reviewed, papers that were presented at the 1st international Symposium and 10th Balkan conference on Operational Research (BALCOR 2011), which was held during Se... 详细信息

关键词： mathematical programming combinatorial optimization network optimization integer programming 90C27 65K05 90B10 90C10 91A90

来源：评论

学校读者我要写书评

暂无评论

the Generate-and-Solve Framework Revisited: Generating by Simulated Annealing

The Generate-and-Solve Framework Revisited: Generating by Si...

引用

13th European conference on Evolutionary Computation in combinatorial optimization (EvoCOP)

作者： Saraiva, Rommel D. Nepomuceno, Napoleao V. Pinheiro, Placido R. State Univ Ceara UECE Fortaleza Ceara Brazil Univ Fortaleza UNIFOR Grad Program Appl Informat Fortaleza Ceara Brazil

ISBN: (纸本)9783642371981

the Generate-and-Solve is a hybrid framework to cope with hard combinatorial optimization problems by artificially reducing the search space of solutions. In this framework, a metaheuristic engine works as a generator of reduced instances of the problem. these instances, in turn, can be more easily handled by an exact solver to provide a feasible (optimal) solution to the original problem. this approach has commonly employed genetic algorithms and it has been particularly effective in dealing with cutting and packing problems. In this paper, we present an instantiation of the framework for tackling the constrained two-dimensional non-guillotine cutting problem and the container loading problem using a simulated annealing generator. We conducted computational experiments on a set of difficult benchmark instances. Results show that the simulated annealing implementation overachieves previous versions of the Generate-and-Solve framework. In addition, the framework is shown to be competitive with current state-of-the-art approaches to solve the problems studied here.

关键词： combinatorial optimization Hybrid Metaheuristics Cutting and Packing Simulated Annealing integer programming

来源：评论

学校读者我要写书评

暂无评论

An Artificial Intelligence Based Novel Approach for Real-time Allocation of Armament to Hostile Targets

An Artificial Intelligence Based Novel Approach for Real-tim...

引用

10th international Bhurban conference on Applied Science and Technology (IBCAST)

作者： Shahzad, Atif Ur-Rehman, Raza CESAT Islamabad Pakistan

ISBN: (纸本)9781467344265;9781467344258

For some specified targets, it is desired to identify the optimal configuration for the assignment of weapons for a given deployment of different types of weapon systems along with their required quantity in order to achieve a desired level of damage subject to the minimal cost and mission specific constraints. this problem, in its essence, is an NP-complete combinatorial optimization problem in the area of command and control research. In defense-related applications of artificial intelligence, this problem is referred as Weapon Target Assignment (WTA) problem. the problem can be formulated as a non-linear integer programming problem for which no exact methods exist to solve even the small size instances. Our focus is on the Dynamic Weapon Target Assignment (DWTA) problem. A discrete-event system simulation model is developed taking into account the resource constraints, resource capability constraints, strategy constraints and engagement feasibility constraints. three different methods are employed;MMR, Reactive Tabu Search and a newly proposed artificial intelligence based simulation-optimization hybrid framework. A set of rules is generated based on the optimization module that is then employed for real-time control. the computational results show very promising prospects of the proposed approach, not only for DWTA but also for any real-time decision-making problem like Cooperative Unmanned Air Vehicle Mission Assignment etc.

关键词： artificial intelligence combinatorial mathematics computational complexity decision making discrete event simulation integer programming military computing nonlinear programming search problems weapons

来源：评论

学校读者我要写书评

暂无评论

A multistart local search heuristic for knapsack problem

A multistart local search heuristic for knapsack problem

引用

19th international conference on Industrial Engineering and Engineering Management: Assistive Technology of Industrial Engineering

作者： Lin, Geng Department of Mathematics Minjiang University Fuzhou China

ISBN: (纸本)9783642383908

Knapsack problem is one of classical combinatorial optimization problems, and has a lot of applications. It is known to be NP-hard. In this paper we propose a multistart local search heuristic for solving the knapsack problem. Firstly, knapsack problem is converted into an unconstrained integer programming by penalty method. then an iterative local search method is presented to solve the resulting unconstrained integer programming. the computational results on three benchmarks show that the proposed algorithm can find high quality solutions in an effective manner. © 2013 Springer-Verlag Berlin Heidelberg.

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：