RETRACTED ARTICLE: Discrete optimization method based on grassmannian parameterization in multidimensional dichotomic data structuring

A solution of the large computational time problem arising in multidimensional data structuring is addressed by employing algebraic properties of finite geometries. A vector parameterization of the Grassmannian Gr₂(k, n) is proposed which makes it possible to minimize the amount of memory and reduce the number of operations required to solve the problem. An algorithm based on this parameterization and the Gray codes is constructed; the algorithm is suitable for parallel computation, which further reduces computation time.     

Scheduling jobs on a <Emphasis Type="Italic">k</Emphasis>-stage flexible flow-shop

We consider the problem of makespan minimization on a flexible flow shop with k stages and m _s machines at any stage. We propose a heuristic algorithm based on the identification and exploitation of the bottleneck stage, which is simple to use and to understand by practitioners. A computational experiment is conducted to evaluate the performance of the proposed method. The study shows that our method is, in average, comparable with other bottleneck-based algorithms, but with smaller variance, and that it requires less computational effort.     

H∞norm approximation of discrete-time systems by constant matrices

The problem of approximating a given discrete-time system by a constant matrix in H_∞ norms sense is considered. A computational scheme is given. Some related results are developed. The solution is based on allpass imbedding of bounded real matrices.     

Numerical analysis of a modified finite element nonlinear Galerkin method

Summary. A fully discrete modified finite element nonlinear Galerkin method is presented for the two-dimensional equation of Navier-Stokes type. The spatial discretization is based on two finite element spaces X_H and X_h defined on a coarse grid with grid size H and a fine grid with grid size h << H, respectively; the time discretization is based on the Euler explicit scheme with respect to the nonlinear term. We analyze the stability and convergence rate of the method. Comparing with the standard finite element Galerkin method and the nonlinear Galerkin method, this method can admit a larger time step under the same convergence rate of same order. Hence this method can save a large amount of computational time. Finally, we provide some numerical tests on this method, the standard finite element Galerkin method, and the nonlinear Galerkin method, which are in a good agreement with the theoretical analysis.Mathematics Subject Classification (2000): 35Q30, 65M60, 65N30, 76D05     

Considering manufacturing cost and scheduling performance on a CNC turning machine

A well known industry application that allows controllable processing times is the manufacturing operations on CNC machines. For each turning operation as an example, there is a nonlinear relationship between the manufacturing cost and its required processing time on a CNC turning machine. If we consider total manufacturing cost (F₁) and total weighted completion time (F₂) objectives simultaneously on a single CNC machine, making appropriate processing time decisions is as critical as making job sequencing decisions. We first give an effective model for the problem of minimizing F₁ subject to a given F₂ level. We deduce some optimality properties for this problem. Based on these properties, we propose a heuristic algorithm to generate an approximate set of efficient solutions. Our computational results indicate that the proposed algorithm performs better than the GAMS/MINOS commercial solver both in terms of solution quality and computational requirements such that the average CPU time is only 8% of the time required by the GAMS/MINOS.     

Detecting Changes in Slope With an L0 Penalty

While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L₀ penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L₀ penalty is more reliable at estimating changepoint locations than using an L₁ penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online.     

Finding independent sets in a graph using continuous multivariable polynomial formulations

Two continuous formulations of the maximum independent set problem on a graph G=(V,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x ₀ in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x₀) and H(x₀), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented.     

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}. The objective is to find k paths P₁,…,P_k such that P_i is a path from s_i to t_i and P_i and P_j have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

Nonstationary Positive Definite Tapering On The Plane

A common problem in spatial statistics is to predict a random field f at some spatial location t ₀ using observations f(t ₁), …, f(t_n ) at . Recent work by Kaufman et al. and Furrer et al. studies the use of tapering for reducing the computational burden associated with likelihood-based estimation and prediction in large spatial datasets. Unfortunately, highly irregular observation locations can present problems for stationary tapers. In particular, there can exist local neighborhoods with too few observations for sufficient accuracy, while others have too many for computational tractability. In this article, we show how to generate nonstationary covariance tapers T(s, t) such that the number of observations in {t: T(s, t) > 0} is approximately a constant function of s. This ensures that tapering neighborhoods do not have too many points to cause computational problems but simultaneously have enough local points for accurate prediction. We focus specifically on tapering in two dimensions where quasi-conformal theory can be used. Supplementary materials for the article are available online.     

Weak ɛ-Nets for Points on a Hypersphere

A weak ε -net for a set of points M, is a set of points W (not necessarily in M) where every convex set containing ε |M| points in M must contain at least one point in W. Weak ε-nets have applications in diverse areas such as computational geometry, learning theory, optimization, and statistics. Here we show that if M is a set of points quasi-uniformly distributed on a unit sphere S ^d-1 , then there is a weak ε-net of size for M, where k _d is exponential in d. A set of points M is quasi-uniformly distributed on S ^d-1 if, for any spherical cap , we have for three positive constants c_1, c_2, and c ₃ . Further, we show that reducing our upper bound by asymptotically more than a factor directly implies the solution of a long unsolved problem of Danzer and Rogers. Received April 12, 1995, and in revised form May 8, 1995.     

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

In this paper, we consider problem (P) of minimizing a quadratic function q(x)=x ^t Qx+c ^t x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x _i ²=x _i, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved. We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods to several other exact solution methods. Furthermore, we report computational results for the max-cut problem.     

Applied systems and cybernetics,volume III: Human systems,sociocybernetics, management and organizations: G.E. LASKER (Ed.) Proceedings of the international congress on applied Systems research and cybernetics; Pergamon Press,New York, 1981, xxx + 515 pages, $80.00

This note considers a special case of the assignment problem when n jobs are to be grouped together into a set of m categories (m > 3). Solving this particular case through the available transportation or assignment algorithms would entail a heavy computational burden, particularly in problems involving dense matrices. A preprocessing technique requiring sorting of (₂^m) n-arrays once is outlined, which is capable of reducing the dimension and eliminating several arcs for such a problem. The procedure offers an overall computational advantage over the other available algorithms applied directly. An illustrative example is included.     

A note on the growth bound ofC 0-semigroups

A class ofC ₀-semigroups is proposed in this paper based on linear transport theory, and it is shown that the growth bound of theC ₀-semigroup of this kind coincides with the spectral bound of the corresponding generator. As an application, the asymptotic behavior of the time dependent solution for the neutron transport problem arising in a reflecting slab is studied.     

The Nehari problem for nonexponentially stable systems

The Nehari problem and its suboptimal extension are solved under the assumption that the system (A, B, C) has bounded controllability and observability maps, an L₂-impulse response and a transfer matrix that is bounded and holomorphic on the right half-plane. Exponential stability of the semigroup is not assumed and the Hankel operator is not compact. The new contribution is an explicit parameterization of all solutions given in terms of the system parametersA, B, C.     

Multi-family scheduling in a two-machine reentrant flow shop with setups

This paper considers a two-machine multi-family scheduling problem with reentrant production flows. The problem consists of two machines, M₁ and M₂, and each job has the processing route (M₁, M₂, M₁, M₂). There are identical jobs in the same family and the jobs in the same family are processed in succession. Each machine needs a setup time before the first job in a family is processed. The objective is to minimize the maximum completion time. Examples of such a problem occur in the bridge construction, semiconductor industry and job processing on numerical controlled machines, where they usually require that the jobs are reprocessed once and there are identical jobs in the same family. This problem is shown to be NP-hard. A branch-and-bound algorithm is proposed, and computational experiments are provided.     

Exercise Boundary Near Maturity for an American Option on Several Assets

We consider an American put option on a linear function of d dividend-paying assets. The value function of this option is given as the solution of a free boundary problem. When d = 1, the behavior of the free boundary near the maturity of the option is well known. In this article, we extend to the case d > 1 the study of the free boundary near maturity. A parameterization of the stopping region at time t is given. That enables us to define and give a convergence rate for this region when t goes to the maturity.     

Error estimates for two‐level penalty finite volume method for the stationary Navier–Stokes equations

Two‐level penalty finite volume method for the stationary Navier–Stokes equations based on the P₁ ? P₀ element is considered in this paper. The method involves solving one small penalty Navier–Stokes problem on a coarse mesh with mesh size H = ?^{1 / 4}h^{1 / 2}, a large penalty Stokes problem on a fine mesh with mesh size h, where 0 < ? < 1 is a penalty parameter. The method we study provides an approximate solution with the convergence rate of same order as the penalty finite volume solution (u_?h,p_?h), which involves solving one large penalty Navier–Stokes problem on a fine mesh with the same mesh size h. However, our method can save a large amount of computational time. Copyright © 2013 John Wiley & Sons, Ltd.     

Max-min sum minimization transportation problem

A non-convex optimization problem involving minimization of the sum of max and min concave functions over a transportation polytope is studied in this paper. Based upon solving at most (g+1)(< p) cost minimizing transportation problems with m sources and n destinations, a polynomial time algorithm is proposed which minimizes the concave objective function where, p is the number of pairwise disjoint entries in the m× n time matrix {t _ij } sorted decreasingly and T ^g is the minimum value of the max concave function. An exact global minimizer is obtained in a finite number of iterations. A numerical illustration and computational experience on the proposed algorithm is also included. We are thankful to Prof. S. N. Kabadi, University of New Brunswick-Fredericton, Canada, who initiated us to the type of problem discussed in this paper. We are also thankful to Mr. Ankit Khandelwal, Ms. Neha Gupta and Ms. Anuradha Beniwal, who greatly helped us in the implementation of the proposed algorithm.