Implementation and Test of Auction Methods for Solving Generalized Network Flow Problems with Separable Convex Cost

We describe the implementation and testing of two methods, based on the auction approach, for solving the problem of minimizing a separable convex cost subject to generalized network flow conservation constraints. The first method is the -relaxation method of Ref. 1; the second is an extension of the auction sequential/shortest path algorithm for ordinary network flow to generalized network flow. We report test results on a large set of randomly generated problems with varying topology, arc gains, and cost function. Comparison with the commercial code CPLEX on linear/quadratic cost problems and with the public-domain code PPRN on nonlinear cost ordinary network problems are also made. The test results show that the auction sequential/shortest path algorithm is generally fastest for solving quadratic cost problems and mixed linear/nonlinear cost problems with arc gain range near 1. The -relaxation method is generally fastest for solving nonlinear cost ordinary network problems and mixed linear/nonlinear cost problems with arc gain range away from 1. CPLEX is generally fastest for solving linear cost and mixed linear/quadratic cost problems with arc gain range near 1.     

Improved Approximation for Guarding Simple Galleries from the Perimeter

We provide an O(log?log?opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size \(O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})\) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log?opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.     

Test sets of integer programs

This article is a survey about recent developments in the area of test sets of families of linear integer programs. Test sets are finite subsets of the integer lattice that allow to improve any given feasible non-optimal point of an integer program by one element in the set. There are various possible ways of defining test sets depending on the view that one takes: theGraver test set is naturally derived from a study of the integral vectors in cones; theScarf test set (neighbors of the origin) is strongly connected to the study of lattice point free convex bodies; the so-calledreduced Gröbner basis of an integer program is obtained from a study of generators of polynomial ideals. This explains why the study of test sets connects various branches of mathematics. We introduce in this paper these three kinds of test sets and discuss relations between them. We also illustrate on various examples such as the minimum cost flow problem, the knapsack problem and the matroid optimization problem how these test sets may be interpreted combinatorially. From the viewpoint of integer programming a major interest in test sets is their relation to the augmentation problem. This is discussed here in detail. In particular, we derive a complexity result of the augmentation problem, we discuss an algorithm for solving the augmentation problem by computing the Graver test set and show that, in the special case of an integer knapsack problem with 3 coefficients, the augmentation problem can be solved in polynomial time.Supported by a Gerhard-Hess-Forschungsförderpreis of the German Science Foundation (DFG).     

Efficient robust optimization for robust control with constraints

This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tractable, the number of variables is quadratic in the number of stages or horizon length N and has no apparent exploitable structure, leading to computational time of per iteration of an interior-point method. We focus on the case when the disturbance set is ∞-norm bounded or the linear map of a hypercube, and the cost function involves the minimization of a quadratic cost. Here we make use of state variables to regain a sparse problem structure that is related to the structure of the original problem, that is, the policy optimization problem may be decomposed into a set of coupled finite horizon control problems. This decomposition can then be formulated as a highly structured quadratic program, solvable by primal-dual interior-point methods in which each iteration requires time. This cubic iteration time can be guaranteed using a Riccati-based block factorization technique, which is standard in discrete-time optimal control. Numerical results are presented, using a standard sparse primal-dual interior point solver, that illustrate the efficiency of this approach.     

Resolving a strange case of efficiency

In a recent paper in the Journal of the Operational Research Society, Tone proposes an alternative to the Farrell cost efficiency index to avoid the ‘strange case’ problem in which firms with identical inputs and outputs but with input prices differing by some factor (eg, one has input prices twice another) will have the same Farrell cost efficiency. We provide an alternative cost efficiency indicator that avoids this problem, allows for decomposition into technical and allocative efficiency, and is easily estimated using DEA type models.     

Optimal Group Testing with Processing Times and Incomplete Identification

We consider the group testing problem for a finite population of possibly defective items with the objective of sampling a prespecified demanded number of nondefective items at minimum cost. Group testing means that items can be pooled and tested together; if the group comes out clean, all items in it are nondefective, while a contaminated group is scrapped. Every test takes a random amount of time and a given deadline has to be met. If the prescribed number of nondefective items is not reached, the demand has to be satisfied at a higher (penalty) cost. We derive explicit formulas for the distributions underlying the cost functionals of this model. It is shown in numerical examples that these results can be used to determine the optimal group size.     

Extending hysteresis operators to spaces of piecewise continuous functions

We consider continuous-time hysteresis operators, defined to be causal and rate independent operators mapping input signals to output signals . We show how a hysteresis operator defined on the set of continuous piecewise monotone functions can be naturally extended to piecewise continuous piecewise monotone functions. We prove that the extension is also a hysteresis operator and that a number of important properties of the original operator are inherited by the extension. Moreover, we define the concept of a discrete-time hysteresis operator and we show that discretizing continuous-time hysteresis operators using standard sampling and hold operations leads to discrete-time hysteresis operators. We apply the concepts and results described above in the context of sampled-data feedback control of linear systems with input hysteresis.     

Some properties of root functions of ordinary second-order differential operators in the absence of the carleman condition

On a finite interval G of the real line, we consider the root functions of an ordinary second-order differential operator without any boundary conditions for the case in which the imaginary part of the spectral parameter is unbounded.We refine the estimates for the C-and L _p -norms of a root function and its first derivative on a compact set contained in the interior of G for the case in which the Carleman condition fails.A sufficient condition is obtained for the root functions of an ordinary second-order differential operator to have the Bessel property, assuming that the Carleman condition fails. We show that, under certain conditions, this problem can be reduced to analyzing the Bessel property of systems of exponentials.     

Kazhdan's Property (T) for the unitary group of aseparable Hilbert space

We show that the unitary group of a separable Hilbert space has Kazhdan's Property (T), when it is equipped with the strong operator topology. More precisely, for every integer m 2, we give an explicit Kazhdan set consisting of m unitary operators and determine an optimal Kazhdan constant for this set. Moreover, we show that a locally compact group with Kazhdan's Property (T) has a finite Kazhdan set if and only if its Bohr compactification has a finite Kazhdan set. As a consequence, if a locally compact group with Property (T) is minimally almost periodic, then it has a finite Kazhdan set.     

Multi-dimensional vector assignment problems

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each of which contains the same number $n$ of $p$-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an $m$-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the $m$ sets of vectors into $n$   $m$-tuples so that no two vectors from the same set are in the same $m$-tuple and so that the sum of the costs of the $m$-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed $m$. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case $m=3$ and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension $p$.     

General Logic-Systems and Finite Consequence Operators

In this paper, the significance of using general logic-systems and finite consequence operators defined on non-organized languages is discussed. Results are established that show how properties of finite consequence operators are independent from language organization and that, in some cases, they depend only upon one simple language characteristic. For example, it is shown that there are infinitely many finite consequence operators defined on any non-organized infinite language L that cannot be generated from any finite logic-system. On the other hand, it is shown that for any nonempty language L, a set map is a finite consequence operator if and only if it is defined by a general logic-system. Simple logic-system examples that determine specific consequence operator properties are given. Mathematics Subject Classification (2000): Primary 03B22, Secondary 03B65     

Some nonlinear complementarity systems algorithms and applications to unilateral boundary-value problems

Summary We consider an open bounded set and the unilateral Dirichlet problem with one or two obstacles, involving a nonlinear differential operator A. Using the finite affine triangular element method, we discretize the corresponding variational inequalities and obtain the complementarity systems with one or two constraints related to a nonlinear finite-dimensional operator F. In [21], [26], we have constructed monotone algorithms for solving such complementarity systems in the linear case, under the hypothesis: F is a P-matrix with nonpositive off-diagonal elements. In the present, we extend the applicability of the mentioned algorithms to the nonlinear case, under the hypothesis: F is continuous, coercive, off-diagonal antitone P-function in R^N. Moreover when F is a convex differentiable operator we apply the Newton method and a global linearization technique to overcome the numerical difficulties due to the nonlinearity of F. Finally we give some applications involving the pseudo-laplace operator [12] and the glaciology operator [24]. In the case of pseudo-laplace operator and a square configuration of , using an optimal regularity theorem due to El Kolli [7] we obtain also an estimate of the discretization error.     

Conley index of nontrivial invariant sets in a Hilbert space

We study flows defined in a Hilbert space by potential completely continuous fields Id-K(·), where K(·) is an operator close to a homogeneous one. The Conley index of the set of fixed points and separatrices joining them (a nontrivial invariant set) is defined for such flows. By using this index, we prove that the equation K(x) = x has infinitely many solutions of arbitrarily large norm provided that the potential φ: ?φ(·) = K(·) is coercive and has an even leading part. As a corollary, we justify the stability of an arbitrary finite number of solutions under small perturbations of the field. We show that the Conley index differs from the classical rotation theory of vector fields when proving existence theorems.     

On ordered-covering mappings and implicit differential inequalities

We define the set of ordered covering of a mapping that acts in partially ordered spaces; we suggest a method for finding the set of ordered covering of vector functions of several variables and the Nemytskii operator acting in Lebesgue spaces. We prove assertions on operator inequalities in arbitrary partially ordered spaces. We obtain conditions that use a set of ordered covering of the corresponding mapping and ensure that the existence of an element u such that f(u) ≥ y implies the solvability of the equation f(x) = y and the estimate x ≤ u for its solution. We study the problem on the existence of the minimal and least solutions. These results are used for the analysis of an implicit differential equation. For the Cauchy problem, we prove a theorem on an inequality of the Chaplygin type.     

Faster algorithms for computing longest common increasing subsequences

We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths n and m, where m?n, we present an algorithm with an output-dependent expected running time of and O(m) space, where ? is the length of an LCIS, σ is the size of the alphabet, and Sort is the time to sort each input sequence. For k?3 length-n sequences we present an algorithm which improves the previous best bound by more than a factor k for many inputs. In both cases, our algorithms are conceptually quite simple but rely on existing sophisticated data structures. Finally, we introduce the problem of longest common weakly-increasing (or non-decreasing) subsequences (LCWIS), for which we present an -time algorithm for the 3-letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

Uniform asymptotics of the eigenvalues and eigenfunctions of the Dirac system with an integrable potential

We consider the Dirac operator on a finite interval with a potential belonging to some set X completely bounded in the space L₁[0, π] and with strongly regular boundary conditions. We derive asymptotic formulas for the eigenvalues and eigenfunctions of the operator; moreover, the constants occurring in the estimates for the remainders depend on the boundary conditions and the set X alone.     

Spectral approximation of quadratic operator polynomials arising in photonic band structure calculations

Galerkin spectral approximation theory for non-self-adjoint quadratic operator polynomials with periodic coefficients is considered. The main applications are complex band structure calculations in metallic photonic crystals, periodic waveguides, and metamaterials. We show that the spectrum of the considered operator polynomials consists of isolated eigenvalues of finite multiplicity with a nonzero imaginary part. The spectral problem is equivalent to a non-compact block operator matrix and norm convergence is shown for a block operator matrix having the same generalized eigenvectors as the original operator. Convergence rates of finite element discretizations are considered and numerical experiments with the $p$ -version and the $h$ -version of the finite element method confirm the theoretical convergence rates.     

Vertex packing problem application to the design of electronic testing fixtures

In this paper, we report on the use of combinatorial optimization techniques to design testing fixtures for Printed Circuit Boards (PCBs). For testing the functionality of a PCB, nail-like testing devices (probes) on the surface of a testing fixture are brought in contact with prespectified test points (pads) on the surface of the PCB. The two design decisions for the testing fixture are: (a) to select from an available set of pads the ones to test (this determines the location of the probes on the fixture) subject to the restriction that in prespecified subsets of the set of pads (these subsets are referred to as nets) and a priori determined number of pads have to be tested (this is referred to as the net restriction), and (b) to choose the probe size to be used for testing each pad (only two available sizes: a large (100 mil) and a small (50 mil)) subject to the considerations that larger size probes are more reliable for testing purposes and probes that are assigned to pads in close proximity should not come in physical contact with each other (it creates short circuits and erroneous test result). Thus, the problem the testing engineer faces is to assign the maximum number of 100 mil probes to an appropriately selected set of pads in a way that avoids the creation of short circuits and accounts for the net restriction. We develop an efficient algorithm to solve the problem using results from the vertex packing literature, which exploit the special structure of an appropriate geometric graph we can define in this application. The algorithm can handle the large size real problem within 2–3 minutes of real time on a microcomputer.