Integrating nonlinear branch-and-bound and outer approximation for convex Mixed Integer Nonlinear Programming

In this paper, we present a new hybrid algorithm for convex Mixed Integer Nonlinear Programming (MINLP). The proposed hybrid algorithm is an improved version of the classical nonlinear branch-and-bound (BB) procedure, where the enhancements are obtained with the application of the outer approximation algorithm on some nodes of the enumeration tree. The two methods are combined in such a way that each one collaborates to the convergence of the other. Computational experiments with benchmark instances of the MINLP problem show the good performance of the proposed algorithm, which is compared to the outer approximation algorithm, the nonlinear BB algorithm and the hybrid algorithm implemented in the solver Bonmin.     

Discretization orders for protein side chains

Proteins are important molecules that are widely studied in biology. Since their three-dimensional conformations can give clues about their function, an optimal methodology for the identification of such conformations has been researched for many years. Experiments of Nuclear Magnetic Resonance (NMR) are able to estimate distances between some pairs of atoms forming the protein, and the problem of identifying the possible conformations satisfying the available distance constraints is known in the scientific literature as the Molecular Distance Geometry Problem (MDGP). When some particular assumptions are satisfied, MDGP instances can be discretized, and solved by employing an ad-hoc algorithm, named the interval Branch & Prune. When dealing with molecules such as proteins, whose chemical structure is known, a priori information can be exploited for generating atomic orderings that allow for the discretization. In previous publications, we presented a handcrafted order for the protein backbones. In this work, we propose 20 new orders for the 20 side chains that can be present in proteins. Computational experiments on artificial and real instances from NMR show the usefulness of the proposed orders.     

A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.     

A numerical study of an MPI/OpenMP implementation based on asynchronous threads for a three-dimensional splitting scheme in heat transfer problems

We present the results of a study of the parallel algorithms based on MPI and OpenMP for vector splitting schemes in heat transfer problems. We compare the three parallel implementations: MPI, “simple” MPI/OpenMP (#pragma omp directives applied to MPI-based code), and MPI/OpenMP with “postman” threads. The main idea of the last algorithm is to assign one thread within each computational node to perform the data transfer. This approach allows us to implement overlapping of useful computations and data transfer. The results show that the introducing postman threads can significantly improve the performance of an MPI/OpenMP implementation; nevertheless, for the considered class of numerical algorithms, it is more reasonable to use an MPI implementation.     

An OpenMP version of the parallel algorithm for calculation of unsteady gas flow through porous objects with energy sources: Analysis and application

Gas flows in the gravity field through the porous objects with energy sources, which may originate from the natural or man-caused disasters, are investigated. An OpenMP version of the parallel algorithm has been developed for calculating unsteady 2D gas flows through porous self-heating media of complex subsurface geometries. The structure of the sequential algorithm and the transition from it to the OpenMP version are described; the performance and efficiency of parallelization are analyzed. Unsteady gas flows through axisymmetric porous self-heating objects with a partial closure of the object outlet (with a top cover) are investigated by means of the developed parallel algorithm. The influence of the partial closure of the object outlet on the cooling process of the porous objects with a nonuniform distribution of heat sources is analyzed.     

On approximation of the best case optimal value in interval linear programming

Interval linear programming addresses problems with uncertain coefficients and the only information that we have is that the true values lie somewhere in the prescribed intervals. For the inequality constraint problem, computing the worst case scenario and the corresponding optimal value is an easy task, but the best case optimal value calculation is known to be NP-hard. In this paper, we discuss lower and upper bound approximation for the best case optimal value, and propose suitable methods for both of them. We also propose a not apriori exponential algorithm for computing the best case optimal value. The presented techniques are tested by randomly generated data, and also applied in a simple data classification problem.     

Quantile regression of right-censored length-biased data using the Buckley–James-type method

Length-biased data are encountered frequently due to prevalent cohort sampling in follow-up studies. Quantile regression provides great flexibility for assessing covariate effects on survival time, and is a useful alternative to Cox’s proportional hazards model and the accelerated failure time (AFT) model for survival analysis. In this paper, we develop a Buckley–James-type estimator for right-censored length-biased data under a quantile regression model. The problem of informative right-censoring of length-biased data induced by prevalent cohort sampling must be handled. Following on from the generalization of the Buckley–James-type estimator under the AFT model proposed by Ning et al. (Biometrics 67:1369–1378, 2011), we propose a Buckley–James-type estimating equation for regression coefficients in the quantile regression model and develop an iterative algorithm to obtain the estimates. The resulting estimator is consistent and asymptotically normal. We evaluate the performance of the proposed estimator on finite samples using extensive simulation studies. Analysis of real data is presented to illustrate our proposed methodology.     

Vinyl Polymerisation

The ternary system Poly (methyl methacrylate) Fraction 1/Fraction 2/n-butyl bromide has been studied. A viscometric method is proposed for the estimation of the individual polymer concentration in the two conjugate phases in equilibrium.     

Heuristic methods for single link shared backup path protection

Protecting communication networks against failures is becoming increasingly important as they have become an integrated part of our society. Cable failures are fairly common, but it is unacceptable for a single cable failure to disconnect communication for more than a few seconds—hence protection schemes are employed. In contrast to manual intervention, automatic protection schemes such as shared backup path protection (SBPP) can recover from failure quickly and efficiently. SBPP is a simple but efficient protection scheme that can be implemented in backbone networks with technology available today. In SBPP backup paths are planned in advance for every failure scenario in order to recover from failures quickly and efficiently. Planning SBPP is an NP-hard optimization problem, and previous work confirms that it is time-consuming to solve the problem in practice using exact methods. We present heuristic algorithms and lower bound methods for the SBPP planning problem. Experimental results show that the heuristic algorithms are able to find good quality solutions in minutes. A solution gap of less than \(3.5~\%\) was achieved for 5 of 7 benchmark instances (and a gap of less than \(11~\%\) for the remaining instances.)     

A branch-and-bound algorithm for the coupled task problem

The coupled task problem is to schedule jobs on a single machine where each job consists of two subtasks and where the second subtask has to be started after a given time interval with respect to the first one. The problem has several applications and is NP-hard. In this paper we present a branch-and-bound algorithm for this problem and compare its performance with four integer programming models.     

A cellular-automata model of population dynamics of three species of organisms in Lake Baikal

A cellular automata model of population dynamics of three species of organisms in Lake Baikal is proposed and investigated. Each species is subdivided into age and prey-predator groups. There are eight groups altogether. The model takes into account the spatial distribution of the organisms, seasonal birth rate variation, possible habitat pollution, and water streams. A computational experiment has been carried out for pollution in a southern area of Lake Baikal. It demonstrates that the population dynamics tends to an oscillating process with a period of one year. The minimum pollution at total extinction and maximum pollution not affecting the population dynamics are estimated. The model has been verified with production-to-biomass and occurrence frequency ratios.     

Some point set properties of merotopic spaces and their cohomology groups

Connectedness properties of merotopic spaces (resp. topological spaces, uniform spaces, metric spaces) and the relations to simplicial complexes and cohomology groups (these groups were defined in 1952 byC. H. Dowker [9]) are studied. Furthermore, a cohomological characterization of zero-dimensionality for proximity spaces is proved.     

Modeling and solving the bi-objective minimum diameter-cost spanning tree problem

The bi-objective minimum diameter-cost spanning tree problem (bi-MDCST) seeks spanning trees with minimum total cost and minimum diameter. The bi-objective version generalizes the well-known bounded diameter minimum spanning tree problem. The bi-MDCST is a NP-hard problem and models several practical applications in transportation and network design. We propose a bi-objective multiflow formulation for the problem and effective multi-objective metaheuristics: a multi-objective evolutionary algorithm and a fast nondominated sorting genetic algorithm. Some guidelines on how to optimize the problem whenever a priority order can be established between the two objectives are provided. In addition, we present bi-MDCST polynomial cases and theoretical bounds on the search space. Results are reported for four representative test sets.     

Analysis of Local Search Landscapes for <Emphasis Type="Italic">k</Emphasis>-SAT Instances

Stochastic local search is a successful technique in diverse areas of combinatorial optimisation and is predominantly applied to hard problems. When dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase is helpful for an appropriate parameter adjustment of local search-based procedures. In the present paper, we address parameter estimations in the context of landscapes induced by k-SAT instances: at first, we utilise a sampling method devised by Garnier and Kallel in 2002 for approximations of the number of local maxima in landscapes generated by individual k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. The procedure provides good approximations of the actual number of local maxima, with a deviation typically around 10%. Secondly, we provide a method for obtaining upper bounds for the average number of local maxima in k-SAT instances. The method allows us to obtain the upper bound \(2^{n-O(\sqrt{n/k})}\) for the average number of local maxima, if m is in the region of 2 ^k · n/k.     

Sorption-desorption hysteresis in fibrous silica gel (Santocel C) with isomeric monohydric aliphatic alcohols

By employing the quartz fibre spring technique, sorption-desorption hysteresis at 35° has been studied of Iso-propyl, Iso-Butyl, Sec-Butyl, Tert-Butyl, Active Amyl and Iso-Amyl alcohols on fibrous silica gel (Santocel C) activated at 250°. The isotherms of all the alcohols have clearly defined “knees”. By the application of BET theory, the monolayer capacities are determined. Knowing the specific surface area of fibrous silica gel, assuming oriented sorption of the isomeric alcohols with the OH group attached to surface; the cross-sections of the alcohol molecules are calculated. Excepting Iso-Propyl and Sec-Butyl alcohols, all others have cross-sections greater than that of normal aliphatic alcohols. These higher values are to be expected in view of the side CH₃ groups. The exceptional behaviour of Iso-Propyl and Sec-Butyl alcohols is not clear. Permanent and reproducible hysteresis loops have been obtained in all the cases. Cohan’s theory of hysteresis cannot explain the observations satisfactorily. Cavity theory however explains all the cases of hysteresis. The shapes of the isotherms of the different alcohols in the high relative vapour pressure region indicate a variation in contact angles of the alcohols.     

Mapping integers and hensel codes onto Farey fractions

The order-N Farey fractions, whereN is the largest integer satisfyingN≦√((p?1)/2), can be mapped onto a proper subset of the integers {0, 1,...,p?1} in a one-to-one and onto fashion. However, no completely satisfactory algorithm for affecting the inverse mapping (the mapping of the integers back onto the order-N Farey fractions) appears in the literature. A new algorithm for the inverse mapping problem is described which is based on the Euclidean Algorithm. This algorithm solves the inverse mapping problem for both integers and the Hensel codes of Krishnamurthy et al.     

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primaldual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain certificates that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Acidity function in dipolar aprotic media

The H₀ acidity function has been determined for hydrochloric and trichloroacetic acids in dimethyl sulphoxide (DMSO) and acetonitrile using three amine class of indicators. The variation of H₀ with solvent composition at a fixed concentration of 0.1 M HCI in DMSO-water, acetonitrile-water and DMSO acetonitrile mixtures was also studied. Approximate medium effects on the proton in all these solvents were computed from the H₀ data and the results are discussed.     

Online competitive algorithms for maximizing weighted throughput of unit jobs

We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios.We first give a randomized algorithm RMix with competitive ratio of e/(e−1)≈1.582. This is the first algorithm for this problem with competitive ratio smaller than 2.Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edf_α, whose competitive ratio on s-bounded instances is 2−2/s+o(1/s). For 3-bounded instances its ratio is ≈1.618, matching the known lower bound.In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s=2, our proof gives a lower bound of . Also, in the 2-uniform case, we prove a lower bound of for deterministic memoryless algorithms, matching a known upper bound.Finally, we investigate the multiprocessor case and give a -competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases.