Abstract Point cloud registration is a fundamental problem in computer vision. The problem encompasses critical tasks such as feature estimation, correspondence matching, and transformation estimation. The point cloud registration problem can be cast as a quantile matching problem. We refined the quantile assignment algorithm by integrating prevalent feature descriptors and transformation estimation methods to enhance the correspondence between the source and target point clouds. We evaluated the performances of these descriptors and methods with our approach through controlled experiments on a dataset we constructed using well-known 3D models. This systematic investigation led us to identify the most suitable methods for complementing our approach. Subsequently, we devised a new end-to-end, coarse-to-fine pairwise point cloud registration framework. Finally, we tested our framework on indoor and outdoor benchmark datasets and compared our results with state-of-the-art point cloud registration methods.

In this paper we deal with the problem of deciding the best assortment and cut of defective bidimensional stocks. The problem, originating in a glass manufacturing process, can arise in various industrial contexts. We propose a novel bilevel programming approach describing a competition between two decision makers with contrasting objectives: one aims at fulfilling production requirements, the other at generating defects that, damaging the products, reduce yield as much as possible. By exploiting nice properties of adversarial optimal solutions, the bilevel program is rewritten as a one-level 0-1 linear program. Computational results achieved on random instances with realistic features are discussed, showing the quality and the benefits of the proposed approach in reducing the yield loss from defective material in a worst-case perspective.

MOTIVATION: Synthesizing proteins in heterologous hosts is an important tool in biotechnology. However, the genetic code is degenerate and the codon usage is biased in many organisms. Synonymous codon changes that are customized for each host organism may have a significant effect on the level of protein expression. This effect can be measured by using metrics, such as codon adaptation index, codon pair bias, relative codon bias and relative codon pair bias. Codon optimization is designing codons that improve one or more of these objectives. Currently available algorithms and software solutions either rely on heuristics without providing optimality guarantees or are very rigid in modeling different objective functions and restrictions. RESULTS: We develop an effective mixed integer linear programing (MILP) formulation, which considers multiple objectives. Our numerical study shows that this formulation can be effectively used to generate (Pareto) optimal codon designs even for very long amino acid sequences using a standard commercial solver. We also show that one can obtain designs in the efficient frontier in reasonable solution times and incorporate other complex objectives, such as mRNA secondary structures in codon design using MILP formulations. AVAILABILITY AND IMPLEMENTATION: http://alpersen.bilkent.edu.tr/codonoptimization/CodonOptimization.zip.

Abstract We consider bilateral trade of an object between a seller and a buyer through an intermediary who aims to maximize his/her expected gains as in the previous study, in a Bayes‐Nash equilibrium framework where the seller and buyer have private, discrete valuations for the object. Using duality of linear network optimization, the intermediary's initial problem is transformed into an equivalent linear programming problem with explicit formulae of expected revenues of the seller and the expected payments of the buyer, from which the optimal mechanism is immediately obtained. Then, an extension of the same problem is considered for a risk‐averse intermediary. Through a computational analysis, we observe that the structure of the optimal mechanism is fundamentally changed by switching from risk‐neutral to risk‐averse environment.

We consider the network loading problem (NLP) under a polyhedral uncertainty description of traffic demands. After giving a compact multicommodity flow formulation of the problem, we state a decomposition property obtained from projecting out the flow variables. This property considerably simplifies the resulting polyhedral analysis and computations by doing away with metric inequalities. Then we focus on a specific choice of the uncertainty description, called the “hose model,” which specifies aggregate traffic upper bounds for selected endpoints of the network. We study the polyhedral aspects of the NLP under hose demand uncertainty and use the results as the basis of an efficient branch-and-cut algorithm. The results of extensive computational experiments on well-known network design instances are reported.

In many signal processing applications the core problem reduces to a linear system of equations. Coefficient matrix uncertainties create a significant challenge in obtaining reliable solutions. In this paper, we present a novel formulation for solving a system of noise contaminated linear equations while preserving the structure of the coefficient matrix. The proposed method has advantages over the known Structured Total Least Squares (STLS) techniques in utilizing additional information about the uncertainties and robustness in ill-posed problems. Numerical comparisons are given to illustrate these advantages in two applications: signal restoration problem with an uncertain model and frequency estimation of multiple sinusoids embedded in white noise.

Abstract We investigate a network design problem under traffic uncertainty that arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network to support all possible traffic matrices while minimizing the total reservation cost. The problem admits several versions depending on the desired topology of the reserved links, and the nature of the traffic data uncertainty. We present compact linear mixed‐integer programming formulations for the problem with the classical hose traffic model and for a less conservative robust variant relying on the traffic statistics that are often available. These flow‐based formulations allow us to solve optimally medium‐to‐large instances with commercial MIP solvers. We also propose a combined branch‐and‐price and cutting‐plane algorithm to tackle larger instances. Computational results obtained for several classes of instances are reported and discussed. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 100–115 2007

We describe the development of a data-level, massively parallel, software system for the solution of multicommodity network flow problems. Using a smooth linear-quadratic penalty (LQP) algorithm we transform the multicommodity network flow problem into a sequence of independent min-cost network flow subproblems. The solution of these problems is coordinated via a simple, dense, nonlinear master program to obtain a solution that is feasible within some user-specified tolerance to the original multicommodity network flow problem. Particular emphasis is placed on the mapping of both the subproblems and master problem data to the processing elements of a massively parallel computer, the Connection Machine CM-2. As a result of this design we can solve large and sparse optimization problems on current SIMD massively parallel architectures. Details of the implementation are reported, together with summary computational results with a set of test problems drawn from a Military Airlift Command application.

The central theme of this paper is the design and evaluation of a parallel decomposition algorithm for multicommodity network flow problems based on the notion of piecewise linear-quadratic penalty (LQP) functions. The algorithm induces separability of both the constraint set and the objective function by commodity during the subproblem phase. Hence it is suitable for implementations on coarse grain parallel architectures. A master problem, of significantly smaller dimension than the original problem, uses dense linear algebra computations. Hence it exploits a vector architecture, but is also suited for parallel implementation and can be executed using Basic Linear Algebra (BLAS) subroutines. Computational results on a CRAY Y-MPE264 supercomputer with a set of large multicommodity network flow problems drawn from a military application are presented and analyzed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.