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

An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第1期182卷 413-427页

作者： Zhang, Ji-Hong Wu, Ling-Yun Zhao, Yu-Ying Zhang, Xiang-Sun Tsing Hua Univ Sch Econ & Managements Beijing 100084 Peoples R China Chinese Acad Sci Ctr Bioinformat Acad Math & Syst Sci Beijing 100080 Peoples R China Beijing Foreign Studies Univ Sch Int Business Beijing 100089 Peoples R China

Positional DNA sequencing by hybridization (PSBH) is a recently proposed enhancement of DNA sequencing by hybridization (SBH, potentially a powerful alternative to the DNA sequencing by gel electrophoresis). It has been discussed in many papers and applied to large scale sequencing by hybridization. However, the computational part of PSBH reconstruction is a difficult problem, especially for the occurrence of hybridization errors. So far the problem has not been solved well. Taking PSBH as a combinatorial optimization problem, a novel reconstruction approach to PSBH is presented in this paper. The proposed approach accepts both the negative and positive errors and can greatly reduce ambiguities in the reconstruction of PSBH. The computational experiment shows that our algorithm works satisfactorily and correctly on the test data, especially for the positive errors and k-tuple repetitions. (c) 2006 Elsevier B.V. All rights reserved.

关键词： positional sequencing by hybridization reconstruction of DNA fragment positive errors and negative errors dynamic programming branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

A genetic algorithm for job shop scheduling - A case study

引用

COMPUTERS IN INDUSTRY 1996年第2期31卷 155-160页

作者： Kumar, NSH Srinivasan, G INDIAN INST TECHNOL DEPT HUMANITIES & SOCIAL SCIIND ENGN & MANAGEMENT DIVMADRAS 600036TAMIL NADUINDIA

The problem of scheduling n jobs on m machines with each job having a specific route has been one of considerable research over the last several decades. branch and bound algorithms for determining the optimal makespan have been developed and tested on small sized problems and dispatching rule based heuristic algorithms to minimize specific performance measures such as makespan, flowtime, tardiness, etc, are available to solve large sized problems. This paper addresses the same problem faced by an organization and reports the solution of this problem using genetic algorithms (GA) and a combination of dispatching rules. The proposed algorithm yields an improvement of about 30% in makespan over the present system.

关键词： branch and bound algorithm genetic algorithm dispatching rules job shop scheduling

来源：评论

学校读者我要写书评

暂无评论

Multiphase Mixed-Integer Optimal Control Approach to Aircraft Trajectory Optimization

引用

JOURNAL OF GUIDANCE CONTROL AND DYNAMICS 2013年第5期36卷 1267-1277页

作者： Bonami, Pierre Olivares, Alberto Soler, Manuel Staffetti, Ernesto Aix Marseille Univ CNRS F-13288 Marseille 9 France Univ Rey Juan Carlos Madrid 28943 Spain

In this paper, an approach to aircraft trajectory optimization is presented in which integer and continuous variables are considered. Integer variables model decision-making processes, and continuous variables describe the state of the aircraft, which evolves according to differential-algebraic equations. The problem is formulated as a multiphase mixed-integer optimal control problem. It is transcribed into a mixed-integer nonlinear programming problem by applying a fifth degree Gauss-Lobatto direct collocation method and is then solved using a nonlinear-programming-based branch-and-bound algorithm. The approach is applied to the following en route flight planning problem: Given an aircraft point mass model, a wind forecast, an airspace structure, and the relevant flying information regions with their associated overflying costs, find the control inputs that steer the aircraft from the initial fix to the final fix, following a route of waypoints while minimizing the fuel consumption and overflying costs during the flight. The decision-making process arises in determining the optimal sequence of waypoints. The optimal times at which the waypoints are to be overflown are also to be determined. Numerical results are presented and discussed, showing the effectiveness of the approach.

关键词： Trajectory Optimization Nonlinear Programming branch and bound algorithm North Atlantic Airspace Aircraft Operations Fuel Consumption Collocation Method Air Traffic Management System Commercial Aircraft Aerodynamic Force

来源：评论

学校读者我要写书评

暂无评论

Late work minimization in a small flexible manufacturing system

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2007年第2期52卷 210-228页

作者： Sterna, Malgorzata Poznan Univ Tech Inst Comp Sci Piotrowo 2 PL-60965 Poznan Poland

The paper concerns a small flexible manufacturing system consisting of three CNC machines: a lathe machine, milling machine and measurement center and a single robot, located at the Poznan University of Technology. A short description of the production environment, which can be modeled as the extended job shop system with open shop sections within particular jobs, is followed by the proposition of a branch and bound method. It optimizes production plans within a single shift in order to minimize the late work, i.e. the amount of work executed after a given due date. Based on results of computational experiments, conclusions are formulated on the efficiency of the B&B algorithm and on the behavior of FMS under consideration. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： late work criterion shop scheduling flexible manufacturing system branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Lower bound improvement and forcing rule for quadratic binary programming

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2006年第2-3期33卷 187-208页

作者： Huang, HX Pardalos, PM Prokopyev, OA Tsing Hua Univ Dept Ind Engn Beijing 100084 Peoples R China Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems. From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented.

关键词： quadratic binary programming lower bound forcing rule branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient derivation of numerical dependencies

引用

INFORMATION SYSTEMS 2013年第3期38卷 410-429页

作者： Ciaccia, Paolo Golfarelli, Matteo Rizzi, Stefano Univ Bologna DISI I-40126 Bologna Italy

Numerical dependencies (NDs) are database constraints that limit the number of distinct Y-values that can appear together with any X-value, where both X and Y are sets of attributes in a relation schema. While it is known that NDs are not finitely axiomatizable, there is no study on how to efficiently derive NDs using a set of sound (yet necessarily incomplete) rules. In this paper, after proving that solving the entailment problem for NDs using the chase procedure has exponential space complexity, we show that, given a set of inference rules similar to those used for functional dependencies, the membership problem for NDs is NP-hard. We then provide a graph-based characterization of NDs, which is exploited to design an efficient branch & bound algorithm for ND derivation. Our algorithm adopts several optimization strategies that provide considerable speed-up over a naive approach, as confirmed by the results of extensive tests we made for efficiency and effectiveness using six different datasets. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Numerical dependency Membership problem branch and bound algorithm Projection cardinality estimation

来源：评论

学校读者我要写书评

暂无评论

JOINTLY CONSTRAINED BICONVEX PROGRAMMING

引用

MATHEMATICS OF OPERATIONS RESEARCH 1983年第2期8卷 273-286页

作者： ALKHAYYAL, FA FALK, JE GEORGE WASHINGTON UNIV DEPT OPERAT RESWASHINGTONDC 20052

This paper presents a branch-and-bound algorithm for minimizing the sum of a convex function in x, a convex function in y and a bilinear term in x and y over a closed set. Such an objective function is called biconvex with biconcave functions similarly defined. The feasible region of this model permits joint constraints in x and y to be expressed. The bilinear programming problem becomes a special case of the problem addressed in this paper. We prove that the minimum of a biconcave function over a nonempty compact set occurs at a boundary point of the set and not necessarily an extreme point. The algorithm is proven to converge to a global solution of the nonconvex program. We discuss extensions of the general model and computational experience in solving jointly constrained bilinear programs, for which the algorithm has been implemented.

关键词： biconvex functions. Bilinear programming branch and bound algorithm global convergence nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

FINDING MAXIMUM CLIQUES IN ARBITRARY AND IN SPECIAL GRAPHS

引用

COMPUTING 1991年第4期46卷 321-341页

作者： BABEL, L 1. Mathematisches Institut Technische Universit?t München Arcisstra?e 21 D-W-8000 München 2 Federal Republic of Germany

The classical problem of finding a clique of largest cardinality in an arbitrary graph is NP-complete. For that reason earlier work diverges into two directions. The first concerns algorithms solving the problem for arbitrary graphs in reasonable (but exponential) time, the other restricts to special classes of graphs where polynomial methods can be found. Here, the two directions are combined in a way. A branch and bound algorithm is developed treating the general case. Computational experiments on random graphs show that this algorithm compares favorable to the fastest known method. Furthermore, it consumes only polynomial time for quite a few graph classes. For some of them no polynomial solution method is given so far.

关键词： MAXIMUM CLIQUE PROBLEM branch and bound algorithm POLYNOMIAL SOLVABLE PROBLEMS

来源：评论

学校读者我要写书评

暂无评论

Material Identification From Radiographs Without Energy Resolution

IEEE TRANSACTIONS ON COMPUTATIONAL IMAGING

引用

IEEE TRANSACTIONS ON COMPUTATIONAL IMAGING 2023年 9卷 314-326页

作者： McCann, Michael T. T. Guardincerri, Elena Gonzales, Samuel M. M. Misurek, Lauren A. A. Schei, Jennifer L. L. Klasky, Marc L. L. Los Alamos Natl Lab Theoret Div Los Alamos NM 87545 USA Los Alamos Natl Lab Phys Div Los Alamos NM 87545 USA Los Alamos Natl Lab Nucl Engn & Nonproliferat Div Los Alamos NM 87545 USA Los Alamos Natl Lab Integrated Weap Expt Div Los Alamos NM 87545 USA

We propose a method for performing material identification from radiographs without energy-resolved measurements. Material identification has a wide variety of applications, including in biomedical imaging, nondestructive testing, and security. While existing techniques for radiographic material identification make use of dual energy sources, energy-resolving detectors, or additional (e.g., neutron) measurements, such setups are not always practical- requiring additional hardware and complicating imaging. We tackle material identification without energy resolution, allowing standard X-ray systems to provide material identification information without requiring additional hardware. Assuming a setting where the geometry of each object in the scene is known and the materials come from a known set of possible materials, we pose the problem as a combinatorial optimization with a loss function that accounts for the presence of scatter and an unknown gain and propose a branch and bound algorithm to efficiently solve it. We present experiments on both synthetic data and real, experimental data with relevance to security applications- thick, dense objects imaged with MeV X-rays. We show that material identification can be efficient and accurate, for example, in a scene with three shells (two copper, one aluminum), our algorithm ran in six minutes on a consumer-level laptop and identified the correct materials as being among the top 10 best matches out of 8,000 possibilities.

关键词： Radiography X-ray imaging Security Imaging Detectors Predictive models Energy resolution X-ray radiography material identification combinatorial optimization branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Robust Bayesian Particle Filter for Space Object Tracking Under Severe Uncertainty

引用

JOURNAL OF GUIDANCE CONTROL AND DYNAMICS 2021年第3期45卷 481-498页

作者： Greco, Cristian Vasile, Massimiliano Univ Strathclyde Dept Mech & Aerosp Engn Aerosp Ctr Excellence James Weir Bldg Glasgow G1 1XJ Lanark Scotland

This paper introduces a robust Bayesian particle filter that can handle epistemic uncertainty in the measurements, dynamics, and initial conditions. The robust filter returns robust bounds on the output quantity of interest, rather than a crisp value. Particles are generated with an importance sampling technique and propagated only one time during the estimation process. The proposal distribution is constructed by running a parallel unscented Kalman filter to drive particles in regions of high expected likelihood and achieve a high effective sample size. The bounds are then computed by an inexpensive tuning of the importance weights via numerical optimization. A branch & bound algorithm over simplexes with a Lipschitz bounding function is employed to achieve guaranteed convergence to the lower and upper bounds in a finite number of steps. The filter is applied to the robust computation of the collision probability of SENTINEL 2B with a FENGYUN 1C debris in different operational instances, all characterized by a mix of aleatory and epistemic uncertainty on initial conditions and observation likelihoods.

关键词： Unscented Kalman Filter Sentinel Fengyun branch and bound algorithm Numerical Optimization Satellite Collision Cumulative Distribution Function Number of Particles Computing algorithms Resident Space Object

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：