Second-order cover inequalities

We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives. Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities that limit sums over disjoint subsets of variables to be at most one.      

Backbone guided tabu search for solving the UBQP problem

We propose a backbone-guided tabu search (BGTS) algorithm for the Unconstrained Binary Quadratic Programming (UBQP) problem that alternates between two phases: (1) a basic tabu search procedure to optimize the objective function as far as possible; (2) a strategy using the TS notion of strongly determined variables to alternately fix and free backbone components of the solutions which are estimated likely to share values in common with an optimal solution. Experimental results show that the proposed method is capable of finding the best-known solutions for 21 large random instances with 3000 to 7000 variables and boosts the performance of the basic TS in terms of both solution quality and computational efficiency.     

Alternating control tree search for knapsack/covering problems

The Multidimensional Knapsack/Covering Problem (KCP) is a 0–1 Integer Programming Problem containing both knapsack and weighted covering constraints, subsuming the well-known Multidimensional Knapsack Problem (MKP) and the Generalized (weighted) Covering Problem. We propose an Alternating Control Tree Search (ACT) method for these problems that iteratively transfers control between the following three components: (1) ACT-1, a process that solves an LP relaxation of the current form of the KCP. (2) ACT-2, a method that partitions the variables according to 0, 1, and fractional values to create sub-problems that can be solved with relatively high efficiency. (3) ACT-3, an updating procedure that adjoins inequalities to produce successively more constrained versions of KCP, and in conjunction with the solution processes of ACT-1 and ACT-2, ensures finite convergence to optimality. The ACT method can also be used as a heuristic approach using early termination rules. Computational results show that the ACT-framework successfully enhances the performance of three widely different heuristics for the KCP. Our ACT-method involving scatter search performs better than any other known method on a large set of KCP-instances from the literature. The ACT-based methods are also found to be highly effective on the MKP.     

Optical scattering measurements and implications on thermal noise in Gravitational Wave detectors test-mass coatings

Photographs of the LIGO Gravitational Wave detector mirrors illuminated by the standing beam were analyzed with an astronomical software tool designed to identify stars within images, which extracted hundreds of thousands of point-like scatterers uniformly distributed across the mirror surface, likely distributed through the depth of the coating layers. The sheer number of the observed scatterers implies a fundamental, thermodynamic origin during deposition or processing. These scatterers are a possible source of the mirror dissipation and thermal noise foreseen by V. Braginsky and Y. Levin, which limits the sensitivity of observatories to Gravitational Waves. This study may point the way towards the production of mirrors with reduced thermal noise and an increased detection range.     

Rapid three-dimensional functional magnetic resonance imaging of the initial negative BOLD response

Functional MRI is most commonly used to study the local changes in blood flow that accompanies neuronal activity. In this work we introduce a new approach towards acquiring and analyzing fMRI data that instead provides the potential to study the initial oxygen consumption in the brain that accompanies activation. As the oxygen consumption is closer in timing to the underlying neuronal activity than the subsequent blood flow, this approach promises to provide more precise information about the location and timing of activity. Our approach is based on using a new single shot 3D echo-volumar imaging sequence which samples a small central region of 3D k-space every 100ms, thereby giving a low spatial resolution snapshot of the brain with extremely high temporal resolution. Explicit and simple rules for implementing the trajectory are provided, together with a straightforward reconstruction algorithm. Using our approach allows us to effectively study the behavior of the brain in the time immediately following activation through the initial negative BOLD response, and we discuss new techniques for detecting the presence of the negative response across the brain. The feasibility and efficiency of the approach is confirmed using data from a visual-motor task and an auditory-motor-visual task. The results of these experiments provide a proof of concept of our methodology, and indicate that rapid imaging of the initial negative BOLD response can serve an important role in studying cognition tasks involving rapid mental processing in more than one region.     

A generalized Farkas lemma with applications to quasidifferentiable programming

For sublinear mappings between normed linear spaces a generalization of Farkas' lemma is established thus extending the known results to include a class of non-linear functions. A generalized Motzkin alternative theorem is established and as an application we provide a Kuhn-Tucker type necessary optimality condition for a non-differentiable mathematical programming problem.

---

Zusammenfassung Die Arbeit behandelt eine Verallgemeinerung des Lemmas von Farkas für sublineare Abbildungen zwischen normierten linearen Räumen. Ferner wird eine verallgemeinerte Version des Motzkin-Alternative-Theorems hergeleitet. Als Anwendung ergibt sich eine notwendige Optimalitätsbedingung vom Kuhn-Tucker-Typ für quasidifferenzierbare vektorwertige Optimierungsaufgasben.