Efficient Hill Climber for Constrained Pseudo-Boolean Optimization Problems

Efficient hill climbers have been recently proposed for single- and multi-objective pseudo-Boolean optimization problems. For $k$-bounded pseudo-Boolean functions where each variable appears in at most a constant number of subfunctions, it has been theoretically proven that the neighborhood of a solution can be explored in constant time. These hill climbers, combined with a high-level exploration strategy, have shown to improve state of the art methods in experimental studies and open the door to the so-called Gray Box Optimization, where part, but not all, of the details of the objective functions are used to better explore the search space. One important limitation of all the previous proposals is that they can only be applied to unconstrained pseudo-Boolean optimization problems. In this work, we address the constrained case for multi-objective $k$-bounded pseudo-Boolean optimization problems. We find that adding constraints to the pseudo-Boolean problem has a linear computational cost in the hill climber.

A pointwise constrained version of the Liapunov convexity theorem for vectorial linear first-order control systems

We generalize the Liapunov convexity theorem's version for vectorial control systems driven by linear ODEs of first-order p = 1 , in any dimension d ∈ N , by including a pointwise state-constraint. More precisely, given a x ‾ ( ⋅ ) ∈ W p , 1 ( [ a , b ] , R d ) solving the convexified p-th order differential inclusion L p x ‾ ( t ) ∈ co { u 0 ( t ) , u 1 ( t ) , … , u m ( t ) } a.e., consider the general problem consisting in finding bang-bang solutions (i.e. L p x ˆ ( t ) ∈ { u 0 ( t ) , u 1 ( t ) , … , u m ( t ) } a.e.) under the same boundary-data, x ˆ ( k ) ( a ) = x ‾ ( k ) ( a ) & x ˆ ( k ) ( b ) = x ‾ ( k ) ( b ) ( k = 0 , 1 , … , p − 1 ); but restricted, moreover, by a pointwise state constraint of the type 〈 x ˆ ( t ) , ω 〉 ≤ 〈 x ‾ ( t ) , ω 〉 ∀ t ∈ [ a , b ] (e.g. ω = ( 1 , 0 , … , 0 ) yielding x ˆ 1 ( t ) ≤ x ‾ 1 ( t ) ). Previous results in the scalar d = 1 case were the pioneering Amar & Cellina paper (dealing with L p x ( ⋅ ) = x ′ ( ⋅ ) ), followed by Cerf & Mariconda results, who solved the general case of linear differential operators L p of order p ≥ 2 with C 0 ( [ a , b ] ) -coefficients. This paper is dedicated to: focus on the missing case p = 1 , i.e. using L p x ( ⋅ ) = x ′ ( ⋅ ) + A ( ⋅ ) x ( ⋅ ) ; generalize the dimension of x ( ⋅ ) , from the scalar case d = 1 to the vectorial d ∈ N case; weaken the coefficients, from continuous to integrable, so that A ( ⋅ ) now becomes a d × d -integrable matrix; and allow the directional vector ω to become a moving AC function ω ( ⋅ ) . Previous vectorial results had constant ω, no matrix (i.e. A ( ⋅ ) ≡ 0 ) and considered: constant control-vertices (Amar & Mariconda) and, more recently, integrable control-vertices (ourselves).

Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

Ecological Literacy And Beyond: Problem-based Learning For Future Professionals.

Ecological science contributes to solving a broad range of environmental problems. However, lack of ecological literacy in practice often limits application of this knowledge. In this paper, we highlight a critical but often overlooked demand on ecological literacy: to enable professionals of various careers to apply scientific knowledge when faced with environmental problems. Current university courses on ecology often fail to persuade students that ecological science provides important tools for environmental problem solving. We propose problem-based learning to improve the understanding of ecological science and its usefulness for real-world environmental issues that professionals in careers as diverse as engineering, public health, architecture, social sciences, or management will address. Courses should set clear learning objectives for cognitive skills they expect students to acquire. Thus, professionals in different fields will be enabled to improve environmental decision-making processes and to participate effectively in multidisciplinary work groups charged with tackling environmental issues.

A hybrid heuristic for the multi-plant capacitated lot sizing problem with setup carry-over

This paper addresses the capacitated lot sizing problem (CLSP) with a single stage composed of multiple plants, items and periods with setup carry-over among the periods. The CLSP is well studied and many heuristics have been proposed to solve it. Nevertheless, few researches explored the multi-plant capacitated lot sizing problem (MPCLSP), which means that few solution methods were proposed to solve it. Furthermore, to our knowledge, no study of the MPCLSP with setup carry-over was found in the literature. This paper presents a mathematical model and a GRASP (Greedy Randomized Adaptive Search Procedure) with path relinking to the MPCLSP with setup carry-over. This solution method is an extension and adaptation of a previously adopted methodology without the setup carry-over. Computational tests showed that the improvement of the setup carry-over is significant in terms of the solution value with a low increase in computational time.

Work disability remains a major problem in rheumatoid arthritis in the 2000s: data from 32 countries in the QUEST-RA Study

Introduction: Work disability is a major consequence of rheumatoid arthritis (RA), associated not only with traditional disease activity variables, but also more significantly with demographic, functional, occupational, and societal variables. Recent reports suggest that the use of biologic agents offers potential for reduced work disability rates, but the conclusions are based on surrogate disease activity measures derived from studies primarily from Western countries. Methods: The Quantitative Standard Monitoring of Patients with RA (QUEST-RA) multinational database of 8,039 patients in 86 sites in 32 countries, 16 with high gross domestic product (GDP) (>24K US dollars (USD) per capita) and 16 low-GDP countries (<11K USD), was analyzed for work and disability status at onset and over the course of RA and clinical status of patients who continued working or had stopped working in high-GDP versus low-GDP countries according to all RA Core Data Set measures. Associations of work disability status with RA Core Data Set variables and indices were analyzed using descriptive statistics and regression analyses. Results: At the time of first symptoms, 86% of men (range 57%-100% among countries) and 64% (19%-87%) of women <65 years were working. More than one third (37%) of these patients reported subsequent work disability because of RA. Among 1,756 patients whose symptoms had begun during the 2000s, the probabilities of continuing to work were 80% (95% confidence interval (CI) 78%-82%) at 2 years and 68% (95% CI 65%-71%) at 5 years, with similar patterns in high-GDP and low-GDP countries. Patients who continued working versus stopped working had significantly better clinical status for all clinical status measures and patient self-report scores, with similar patterns in high-GDP and low-GDP countries. However, patients who had stopped working in high-GDP countries had better clinical status than patients who continued working in low-GDP countries. The most significant identifier of work disability in all subgroups was Health Assessment Questionnaire (HAQ) functional disability score. Conclusions: Work disability rates remain high among people with RA during this millennium. In low-GDP countries, people remain working with high levels of disability and disease activity. Cultural and economic differences between societies affect work disability as an outcome measure for RA.

An analytical approach to the dwarf galaxies cusp problem

Aims. An analytical solution for the discrepancy between observed core-like profiles and predicted cusp profiles in dark matter halos is studied. Methods. We calculate the distribution function for Navarro-Frenk-White halos and extract energy from the distribution, taking into account the effects of baryonic physics processes. Results. We show with a simple argument that we can reproduce the evolution of a cusp to a flat density profile by a decrease of the initial potential energy.

Cold nuclear matter effects on J/psi production as constrained by deuteron-gold measurements at root S(NN)=200 GeV

We present a new analysis of J/psi production yields in deuteron-gold collisions at root s(NN) =200 GeV using data taken from the PHENIX experiment in 2003 and previously published in S. S. Adler [Phys. Rev. Lett 96, 012304 (2006)]. The high statistics proton-proton J/psi data taken in 2005 are used to improve the baseline measurement and thus construct updated cold nuclear matter modification factors (R(dAu)). A suppression of J/psi in cold nuclear matter is observed as one goes forward in rapidity (in the deuteron-going direction), corresponding to a region more sensitive to initial-state low-x gluons in the gold nucleus. The measured nuclear modification factors are compared to theoretical calculations of nuclear shadowing to which a J/psi (or precursor) breakup cross section is added. Breakup cross sections of sigma(breakup)=2.8(-1.4)(+1.7) (2.2(-1.5)(+1.6)) mb are obtained by fitting these calculations to the data using two different models of nuclear shadowing. These breakup cross-section values are consistent within large uncertainties with the 4.2 +/- 0.5 mb determined at lower collision energies. Projecting this range of cold nuclear matter effects to copper-copper and gold-gold collisions reveals that the current constraints are not sufficient to firmly quantify the additional hot nuclear matter effect.

Magnetoconfined levels in a parabolic quantum dot: An analytical solution of a three-dimensional Fock-Darwin problem in a tilted magnetic field

The energy spectrum of an electron confined in a quantum dot (QD) with a three-dimensional anisotropic parabolic potential in a tilted magnetic field was found analytically. The theory describes exactly the mixing of in-plane and out-of-plane motions of an electron caused by a tilted magnetic field, which could be seen, for example, in the level anticrossing. For charged QDs in a tilted magnetic field we predict three strong resonant lines in the far-infrared-absorption spectra.

Dynamical Casimir effect for a massless scalar field between two concentric spherical shells with mixed boundary conditions

In this work we analyze the dynamical Casimir effect for a massless scalar field confined between two concentric spherical shells considering mixed boundary conditions. We thus generalize a previous result in literature [Phys. Rev. A 78, 032521 (2008)], where the same problem is approached for the field constrained to the Dirichlet-Dirichlet boundary conditions. A general expression for the average number of particle creation is deduced considering an arbitrary law of radial motion of the spherical shells. This expression is then applied to harmonic oscillations of the shells, and the number of particle production is analyzed and compared with the results previously obtained under Dirichlet-Dirichlet boundary conditions.

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

ON THE THREE-DIMENSIONAL BLASCHKE-LEBESGUE PROBLEM

The width of a closed convex subset of n-dimensional Euclidean space is the distance between two parallel supporting hyperplanes. The Blaschke-Lebesgue problem consists of minimizing the volume in the class of convex sets of fixed constant width and is still open in dimension n >= 3. In this paper we describe a necessary condition that the minimizer of the Blaschke-Lebesgue must satisfy in dimension n = 3: we prove that the smooth components of the boundary of the minimizer have their smaller principal curvature constant and therefore are either spherical caps or pieces of tubes (canal surfaces).

An alternative to the Pythagorean rule? Reevaluating Problem 1 of cuneiform tablet BM 34 568

The first problem of the Seleucid mathematical cuneiform tablet BM 34 568 calculates the diagonal of a rectangle from its sides without resorting to the Pythagorean rule. For this reason, it has been a source of discussion among specialists ever since its first publication. but so far no consensus in relation to its mathematical meaning has been attained. This paper presents two new interpretations of the scribe`s procedure. based on the assumption that he was able to reduce the problem to a standard Mesopotamian question about reciprocal numbers. These new interpretations are then linked to interpretations of the Old Babylonian tablet Plimpton 322 and to the presence of Pythagorean triples in the contexts of Old Babylonian and Hellenistic mathematics. (C) 2007 Elsevier Inc. All rights reserved.

The random barrier-crossing problem

This paper addresses the time-variant reliability analysis of structures with random resistance or random system parameters. It deals with the problem of a random load process crossing a random barrier level. The implications of approximating the arrival rate of the first overload by an ensemble-crossing rate are studied. The error involved in this so-called ""ensemble-crossing rate"" approximation is described in terms of load process and barrier distribution parameters, and in terms of the number of load cycles. Existing results are reviewed, and significant improvements involving load process bandwidth, mean-crossing frequency and time are presented. The paper shows that the ensemble-crossing rate approximation can be accurate enough for problems where load process variance is large in comparison to barrier variance, but especially when the number of load cycles is small. This includes important practical applications like random vibration due to impact loadings and earthquake loading. Two application examples are presented, one involving earthquake loading and one involving a frame structure subject to wind and snow loadings. (C) 2007 Elsevier Ltd. All rights reserved.

An EFG method for the nonlinear analysis of plates undergoing arbitrarily large deformations

The applicability of a meshfree approximation method, namely the EFG method, on fully geometrically exact analysis of plates is investigated. Based on a unified nonlinear theory of plates, which allows for arbitrarily large rotations and displacements, a Galerkin approximation via MLS functions is settled. A hybrid method of analysis is proposed, where the solution is obtained by the independent approximation of the generalized internal displacement fields and the generalized boundary tractions. A consistent linearization procedure is performed, resulting in a semi-definite generalized tangent stiffness matrix which, for hyperelastic materials and conservative loadings, is always symmetric (even for configurations far from the generalized equilibrium trajectory). Besides the total Lagrangian formulation, an updated version is also presented, which enables the treatment of rotations beyond the parameterization limit. An extension of the arc-length method that includes the generalized domain displacement fields, the generalized boundary tractions and the load parameter in the constraint equation of the hyper-ellipsis is proposed to solve the resulting nonlinear problem. Extending the hybrid-displacement formulation, a multi-region decomposition is proposed to handle complex geometries. A criterium for the classification of the equilibrium`s stability, based on the Bordered-Hessian matrix analysis, is suggested. Several numerical examples are presented, illustrating the effectiveness of the method. Differently from the standard finite element methods (FEM), the resulting solutions are (arbitrary) smooth generalized displacement and stress fields. (c) 2007 Elsevier Ltd. All rights reserved.