Bandwidth Selection and Reconstruction Quality in Point-Based Surfaces

We investigate the influence of bandwidth selection in the reconstruction quality of point-based surfaces. While the problem has received relatively little attention in the literature, we show that appropriate selection plays a significant role in the quality of reconstructed surfaces. We show how to compute optimal bandwidths for one class of moving least-squares surfaces by formulating the polynomial fitting step as a kernel regression problem for both noiseless and noisy data. In the context of Levin's projection, we also discuss the implications of the two-step projection for bandwidth selection. We show experimental comparisons of our method, which outperforms heuristically chosen functions and weights previously proposed. We also show the influence of bandwidth on the reconstruction quality of different formulations of point-based surfaces. We provide, to the best of our knowledge, the first quantitative comparisons between different MLS surface formulations and their optimal bandwidths. Using these experiments, we investigate the choice of effective bandwidths for these alternative formulations. We conclude with a discussion of how to effectively compare the different MLS formulations in the literature.     

Efficient DC programming approaches for the asymmetric eigenvalue complementarity problem

In this paper, we propose nonlinear programming (NLP) formulations and difference of convex functions (DC) programming approaches for the asymmetric eigenvalue complementarity problem (EiCP). The EiCP has a solution if and only if these NLP formulations have zero global optimal value. We reformulate the NLP formulations as DC programs which can be efficiently solved by a DC algorithm. Some preliminary numerical results illustrate the good performance of the proposed methods.     

Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: Complexity,properties and formulations

We consider a variant of the Min-Degree Constrained Minimum Spanning Tree Problem where the central and terminal nodes are fixed a priori. We prove that the optimization problem is NP-Hard even for complete graphs and the feasibility problem is NP-Complete even if there is an edge between each central and each terminal in the input graph. Actually, this complexity result still holds when the minimum degree of each central node is restricted to be a same value d ≥ 2. We derive necessary and sufficient conditions for feasibility. We present several integer linear programming formulations – based on known formulations for the minimum spanning tree problem – along with a theoretical comparison among the lower bounds provided by their linear relaxations. We propose three Lagrangian heuristics. Computational experiments compare the performances of the heuristics and the formulations.     

An efficient frontier for sum deviation JIT sequencing problem in mixed-model systems via apportionment

In this paper, the sum deviation just-in-time (JIT) sequencing problem in mixed-model production systems is studied relating with the discrete apportionment problem together with their respective mathematical formulations. The assignment formulation for the first problem is brieffy discussed followed by the existence of JIT cyclic sequences. Presenting the concise discussion on divisor methods for the discrete apportionment problem, we have proposed two mean-based divisor functions for this problem claiming that they are better than the existing divisors; hence, we found a better bound for the JIT sequencing problem. The linkage of both the problems is characterized in terms of similar type of objective functions. The problems are shown equivalent via suitable transformations and similar properties. The joint approaches for the two problems are discussed in terms of global and local deviations proposing equitably efficient solution.     

The vendor location problem

The vendor location problem is the problem of locating a given number of vendors and determining the number of vehicles and the service zones necessary for each vendor to achieve at least a given profit. We consider two versions of the problem with different objectives: maximizing the total profit and maximizing the demand covered. The demand and profit generated by a demand point are functions of the distance to the vendor. We propose integer programming models for both versions of the vendor location problem. We then prove that both are strongly NP-hard and we derive several families of valid inequalities to strengthen our formulations. We report the outcomes of a computational study where we investigate the effect of valid inequalities in reducing the duality gaps and the solution times for the vendor location problem.     

Measuring convergence of mixed finite element discretizations: an application to shell structures

We consider the problem of assessing the convergence of mixed-formulated finite elements. When displacement-based formulations are considered, convergence measures of finite element solutions to the exact solution of the mathematical problem are well known. However when mixed formulations are considered, there is no well-established method to measure the convergence of the finite element solution. We first review a number of approaches that have been employed and discuss their limitations. After having stated the properties that an ideal error measure would possess, we introduce a new physics-based procedure. The new proposed error measure can be used for many different types of mixed formulations and physical problems. We illustrate its use in an assessment of the performance of the MITC family of shell elements.     

Heuristics for capacity planning problems with congestion

Motivated by a problem in the semiconductor industry, we develop improved formulations for the problem of planning capacity acquisition and deletion over time when resources are subject to congestion, motivated by a problem in the semiconductor industry. We use nonlinear clearing functions to relate the expected output of a production resource in a planning period to the expected work in process (WIP) inventory level. Exploiting the properties of the clearing function allows us to formulate the single workcenter problem as a shortest path problem. This forms the basis for two greedy constructive heuristics and a Lagrangian heuristic for the multistage problem. The latter procedure also provides lower bounds on the optimal value. We present computational experiments showing that the proposed heuristics obtain high-quality solutions in modest CPU times.     

Multi-item dynamic production-distribution planning in process industries with divergent finishing stages

This paper examines a multi-item dynamic production-distribution planning problem between a manufacturing location and a distribution center. Transportation costs between the manufacturing location and the distribution center offer economies of scale and can be represented by general piecewise linear functions. The production system at the manufacturing location is a serial process with a multiple parallel machines bottleneck stage and divergent finishing stages. A predetermined production sequence must be maintained on the bottleneck machines. A tight mixed-integer programming model of the production process is proposed, as well as three different formulations to represent general piecewise linear functions. These formulations are then used to develop three equivalent mathematical programming models of the manufacturer-distributor flow planning problem. Valid inequalities to strengthen these formulations are proposed and the strategy of adding extra 0–1 variables to improve the branching process is examined. Tests are performed to compare the computational efficiency of these models. Finally, it is shown that by adding valid inequalities and extra 0–1 variables, major computational improvements can be achieved.     

A comparative study of formulations and solution methods for the discrete ordered p-median problem

This paper presents several new formulations for the Discrete Ordered Median Problem (DOMP) based on its similarity with some scheduling problems. Some of the new formulations present a considerably smaller number of constraints to define the problem with respect to some previously known formulations. Furthermore, the lower bounds provided by their linear relaxations improve the ones obtained with previous formulations in the literature even when strengthening is not applied. We also present a polyhedral study of the assignment polytope of our tightest formulation showing its proximity to the convex hull of the integer solutions of the problem. Several resolution approaches, among which we mention a branch and cut algorithm, are compared. Extensive computational results on two families of instances, namely randomly generated and from Beasley's OR-library, show the power of our methods for solving DOMP.     

Determining Attributes to Maximize Visibility of Objects

In recent years, there has been significant interest in the development of ranking functions and efficient top-k retrieval algorithms to help users in ad hoc search and retrieval in databases (e.g., buyers searching for products in a catalog). We introduce a complementary problem: How to guide a seller in selecting the best attributes of a new tuple (e.g., a new product) to highlight so that it stands out in the crowd of existing competitive products and is widely visible to the pool of potential buyers. We develop several formulations of this problem. Although the problems are NP-complete, we give several exact and approximation algorithms that work well in practice. One type of exact algorithms is based on Integer Programming (IP) formulations of the problems. Another class of exact methods is based on maximal frequent item set mining algorithms. The approximation algorithms are based on greedy heuristics. A detailed performance study illustrates the benefits of our methods on real and synthetic data.     

Maximum likelihood estimation of Gaussian models with missing data—Eight equivalent formulations

In this paper we derive the maximum likelihood problem for missing data from a Gaussian model. We present in total eight different equivalent formulations of the resulting optimization problem, four out of which are nonlinear least squares formulations. Among these formulations are also formulations based on the expectation–maximization algorithm. Expressions for the derivatives needed in order to solve the optimization problems are presented. We also present numerical comparisons for two of the formulations for an ARMAX model.     

The robust vehicle routing problem with time windows

This paper addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different robust approach. The first formulation extends the well-known resource inequalities formulation by employing adjustable robust optimization. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The second formulation generalizes a path inequalities formulation to the uncertain context. The uncertainty appears implicitly in this formulation, so that we develop a new cutting plane technique for robust combinatorial optimization problems with complicated constraints. In particular, efficient separation procedures are discussed. We compare the two formulations on a test bed composed of maritime transportation instances. These results show that the solution times are similar for both formulations while being significantly faster than the solutions times of a layered formulation recently proposed for the problem.     

Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

Remarks on the paper “Optimal control of a class of linear multivariable systems with integral quadratic energy constraint ”

An optimal periodic control problem for a system described by differential equations is considered. Control units are assumed to generate control actions with the square-integrable derivative. The above problem is approximated by a sequence of discretized problems containing trigonometric polynomials, which approximate the state and control variables, and the functions in the criterion and differential equations. The conditions for a sequence of optimal solutions to discretized problems, which are to be a generalized minimizing sequence for the basic problem, are given. Extensions to more general problem formulations are presented. The possibility of application is illustrated by the example of an optimal periodic control problem for a chemical reactor.     

Linear Formulations for the Vehicle Routing Problem with Synchronization Constraints

This paper studies a vehicle routing problem with synchronization constraints and time windows. In this problem, a subset of nodes requires more than one vehicle to satisfy its demand simultaneously. We propose three new mixed integer linear formulations for this problem and we evaluate their efficiency over a large set of instances taken from the literature. The computational results reveal that the proposed linear formulations allow solving larger instances in a shorter computational time than the ones previously proposed in the literature.     

An incremental elastic-plastic Finite Element solver in a workstation cluster environment Part I. Formulations and parallel processing

We discuss solution schemes for the incremental elastic-plastic structural problem, discretized by means of the Finite Element method. Attention is focused on their formulation and implementation in a parallel computing environment defined by a cluster of workstations connected by means of a network. The availability of parallel computers allows one to consider possible formulations and solution strategies so far not considered competitive with the classical Newton-like schemes implying the definition of an elastic-plastic tangent stiffness matrix. The solution strategies herein considered are based on the explicit integration of the actual elastic-plastic rate problem. This, in turn, is phrased in terms of two different formulations, whose relative advantages—particularly with respect to their integration in parallel—are discussed. A − gl (displacemen plastic multiplier) formulation of the structural rate theory of plasticity [1], integrated by means of an explicit, element-by-element scheme, seems to be the most promising one.     

Dual Block-Coordinate Forward-Backward Algorithm with Application to Deconvolution and Deinterlacing of Video Sequences

Optimization methods play a central role in the solution of a wide array of problems encountered in various application fields, such as signal and image processing. Especially when the problems are highly dimensional, proximal methods have shown their efficiency through their capability to deal with composite, possibly nonsmooth objective functions. The cornerstone of these approaches is the proximity operator, which has become a quite popular tool in optimization. In this work, we propose new dual forward-backward formulations for computing the proximity operator of a sum of convex functions involving linear operators. The proposed algorithms are accelerated thanks to the introduction of a block-coordinate strategy combined with a preconditioning technique. Numerical simulations emphasize the good performance of our approach for the problem of jointly deconvoluting and deinterlacing video sequences.     

Formulations for an inventory routing problem

In this paper, we present and compare formulations for the inventory routing problem (IRP) where the demand of customers has to be served, over a discrete time horizon, by capacitated vehicles starting and ending their routes at a depot. The objective of the IRP is the minimization of the sum of inventory and transportation costs. The formulations include known and new mathematical programming formulations. Valid inequalities are also presented. The formulations are tested on a large set of benchmark instances. One of the most significant conclusions is that the formulations that use vehicle‐indexed variables are superior to the more compact, aggregate formulations.     

机器学习方法在蛋白质折叠结构预测中的应用研究

蛋白质的生物功能是由它们的空间折叠结构决定的,理解蛋白质的折叠过程是生物信息学领域中极具挑战性的问题之一。近年来,各种优化方法用于蛋白质空间折叠结构预测。这些方法仍存在着不足,算法在变量数目增大时,难以收敛到全局最优解,并容易产生早熟收敛,从而影响求解精度和效率。针对蛋白质结构预测模型多变量多极值的特点,文章采用机器学习方法对蛋白质进行折叠结构预测。