Column generation for a multitrip vehicle routing problem with time windows, driver work hours, and heterogeneous fleet

This study addresses a vehicle routing problem with time windows, accessibility restrictions on customers, and a fleet that is heterogeneous with regard to capacity and average speed. A vehicle can performmultiple routes per day, all starting and ending at a single depot, and it is assigned to a single driverwhose totalwork hours are limited.Acolumn generation algorithmis proposed.The column generation pricing subproblem requires a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performingmultiple routes per day and to address the need to set the workday’s start time within the planning horizon. A constructive heuristic and a metaheuristic based on tabu search are also developed to find good solutions.

A nonlinear elliptic problem with terms concentrating in the boundary

In this paper, we investigate the behavior of a family of steady-state solutions of a nonlinear reaction diffusion equation when some reaction and potential terms are concentrated in a e-neighborhood of a portion G of the boundary. We assume that this e-neighborhood shrinks to G as the small parameter e goes to zero. Also, we suppose the upper boundary of this e-strip presents a highly oscillatory behavior. Our main goal here was to show that this family of solutions converges to the solutions of a limit problem, a nonlinear elliptic equation that captures the oscillatory behavior. Indeed, the reaction term and concentrating potential are transformed into a flux condition and a potential on G, which depends on the oscillating neighborhood. Copyright (C) 2012 John Wiley & Sons, Ltd.

A modified Primal-Dual Logarithmic-Barrier Method for solving the Optimal Power Flow problem with discrete and continuous control variables

The aim of solving the Optimal Power Flow problem is to determine the optimal state of an electric power transmission system, that is, the voltage magnitude and phase angles and the tap ratios of the transformers that optimize the performance of a given system, while satisfying its physical and operating constraints. The Optimal Power Flow problem is modeled as a large-scale mixed-discrete nonlinear programming problem. This paper proposes a method for handling the discrete variables of the Optimal Power Flow problem. A penalty function is presented. Due to the inclusion of the penalty function into the objective function, a sequence of nonlinear programming problems with only continuous variables is obtained and the solutions of these problems converge to a solution of the mixed problem. The obtained nonlinear programming problems are solved by a Primal-Dual Logarithmic-Barrier Method. Numerical tests using the IEEE 14, 30, 118 and 300-Bus test systems indicate that the method is efficient. (C) 2012 Elsevier B.V. All rights reserved.

Heuristic methods for the single machine scheduling problem with different ready times and a common due date

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.

Antecedents of the Intent to Recommend: a problem with fast food restaurants

The fast and strong social and economic transformations in the economies of many countries has raised the competition for consumers. One of the elements required to adapt to such scenario is knowing customers and their perceptions about products or services, mainly regarding word of mouth recommendations. This study adapts, to the fast food business, a model originally designed to analyze the antecedents of the intent to recommend by clients of formal restaurants. Three constructs were considered: service quality, satisfaction, and social well-being, the latter comprised of positive and negative affections. Six hypotheses were considered, three of which relating to social well-being (that it influences satisfaction, service quality, and the intent to recommend), two relating to service quality (that in influences the intent to recommend and satisfaction), and one relating to the influence of satisfaction on the intent to recommend. None was rejected, indicating adherence and adjustment of the simplication and adaptation of the consolidated model. Through a successful empirical application, the main contribution made by this research is the simplification of a model through its application in a similar context, but with a different scope.

A new evolutionary clustering search for a no-wait flow shop problem with set-up times

This paper addresses the m-machine no-wait flow shop problem where the set-up time of a job is separated from its processing time. The performance measure considered is the total flowtime. A new hybrid metaheuristic Genetic Algorithm-Cluster Search is proposed to solve the scheduling problem. The performance of the proposed method is evaluated and the results are compared with the best method reported in the literature. Experimental tests show superiority of the new method for the test problems set, regarding the solution quality. (c) 2012 Elsevier Ltd. All rights reserved.

Models for capacitated lot-sizing problem with backlogging, setup carryover and crossover

Setup operations are significant in some production environments. It is mandatory that their production plans consider some features, as setup state conservation across periods through setup carryover and crossover. The modelling of setup crossover allows more flexible decisions and is essential for problems with long setup times. This paper proposes two models for the capacitated lot-sizing problem with backlogging and setup carryover and crossover. The first is in line with other models from the literature, whereas the second considers a disaggregated setup variable, which tracks the starting and completion times of the setup operation. This innovative approach permits a more compact formulation. Computational results show that the proposed models have outperformed other state-of-the-art formulation.

Holographic field theory models of dark energy in interaction with dark matter

We discuss two Lagrangian interacting dark energy models in the context of the holographic principle. The potentials of the interacting fields are constructed. The models are compared with CMB distance information, baryonic acoustic oscillations, lookback time and the Constitution supernovae sample. For both models, the results are consistent with a nonvanishing interaction in the dark sector of the Universe and the sign of coupling is consistent with dark energy decaying into dark matter, alleviating the coincidence problem-with more than 3 standard deviations of confidence for one of them. However, this is because the noninteracting holographic dark energy model is a bad fit to the combination of data sets used in this work as compared to the cosmological constant with cold dark matter model, so that one needs to introduce the interaction in order to improve this model.

Optimal mean-variance control for discrete-time linear systems with Markovian jumps and multiplicative noises

In this paper, we consider the stochastic optimal control problem of discrete-time linear systems subject to Markov jumps and multiplicative noises under two criteria. The first one is an unconstrained mean-variance trade-off performance criterion along the time, and the second one is a minimum variance criterion along the time with constraints on the expected output. We present explicit conditions for the existence of an optimal control strategy for the problems, generalizing previous results in the literature. We conclude the paper by presenting a numerical example of a multi-period portfolio selection problem with regime switching in which it is desired to minimize the sum of the variances of the portfolio along the time under the restriction of keeping the expected value of the portfolio greater than some minimum values specified by the investor. (C) 2011 Elsevier Ltd. All rights reserved.

A Note on Large Deviations for the Stable Marriage of Poisson and Lebesgue with Random Appetites

Let IaS,a"e (d) be a set of centers chosen according to a Poisson point process in a"e (d) . Let psi be an allocation of a"e (d) to I in the sense of the Gale-Shapley marriage problem, with the additional feature that every center xi aI has an appetite given by a nonnegative random variable alpha. Generalizing some previous results, we study large deviations for the distance of a typical point xaa"e (d) to its center psi(x)aI, subject to some restrictions on the moments of alpha.

Introducing education for sustainable development in the undergraduate laboratory: quantitative analysis of bioethanol fuel and its blends with gasoline by using solvatochromic dyes

The concept of Education for Sustainable Development, ESD, has been introduced in a period where chemistry education is undergoing a major change, both in emphasis and methods of teaching. Studying an everyday problem, with an important socio-economic impact in the laboratory is a part of this approach. Presently, the students in many countries go to school in vehicles that run, at least partially, on biofuels; it is high time to let them test these fuels. The use of renewable fuels is not new: since 1931 the gasoline sold in Brazil contains 20 to 25 vol-% of bioethanol; this composition is being continually monitored. With ESD in mind, we have employed a constructivist approach in an undergraduate course, where UV-vis spectroscopy has been employed for the determination of the composition of two fuel blends, namely, bioethanol/water, and bioethanol/gasoline. The activities started by giving a three-part quiz. The first and second ones introduced the students to historical and practical aspects of the theme (biofuels). In the third part, we asked them to develop a UV-vis experiment for the determination of the composition of fuel blends. They have tested two approaches: (i) use of a solvatochromic dye, followed by determination of fuel composition from plots of the empirical fuel polarity versus its composition; (ii) use of an ethanol-soluble dye, followed by determination of the blend composition from a Beer's law plot; the former proved to be much more convenient. Their evaluation of the experiment was highly positive, because of the relevance of the problem; the (constructivist) approach employed, and the bright colors that the solvatochromic dye acquire in these fuel blends. Thus ESD can be fruitfully employed in order to motivate the students; make the laboratory "fun", and teach them theory (solvation). The experiments reported here can also be given to undergraduate students whose major is not chemistry (engineering, pharmacy, biology, etc.). They are low-cost and safe to be introduced at high-school level.

Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization

At each outer iteration of standard Augmented Lagrangian methods one tries to solve a box-constrained optimization problem with some prescribed tolerance. In the continuous world, using exact arithmetic, this subproblem is always solvable. Therefore, the possibility of finishing the subproblem resolution without satisfying the theoretical stopping conditions is not contemplated in usual convergence theories. However, in practice, one might not be able to solve the subproblem up to the required precision. This may be due to different reasons. One of them is that the presence of an excessively large penalty parameter could impair the performance of the box-constraint optimization solver. In this paper a practical strategy for decreasing the penalty parameter in situations like the one mentioned above is proposed. More generally, the different decisions that may be taken when, in practice, one is not able to solve the Augmented Lagrangian subproblem will be discussed. As a result, an improved Augmented Lagrangian method is presented, which takes into account numerical difficulties in a satisfactory way, preserving suitable convergence theory. Numerical experiments are presented involving all the CUTEr collection test problems.

A comparison of deterministic, reliability-based and risk-based structural optimization under uncertainty

In this paper, the effects of uncertainty and expected costs of failure on optimum structural design are investigated, by comparing three distinct formulations of structural optimization problems. Deterministic Design Optimization (DDO) allows one the find the shape or configuration of a structure that is optimum in terms of mechanics, but the formulation grossly neglects parameter uncertainty and its effects on structural safety. Reliability-based Design Optimization (RBDO) has emerged as an alternative to properly model the safety-under-uncertainty part of the problem. With RBDO, one can ensure that a minimum (and measurable) level of safety is achieved by the optimum structure. However, results are dependent on the failure probabilities used as constraints in the analysis. Risk optimization (RO) increases the scope of the problem by addressing the compromising goals of economy and safety. This is accomplished by quantifying the monetary consequences of failure, as well as the costs associated with construction, operation and maintenance. RO yields the optimum topology and the optimum point of balance between economy and safety. Results are compared for some example problems. The broader RO solution is found first, and optimum results are used as constraints in DDO and RBDO. Results show that even when optimum safety coefficients are used as constraints in DDO, the formulation leads to configurations which respect these design constraints, reduce manufacturing costs but increase total expected costs (including expected costs of failure). When (optimum) system failure probability is used as a constraint in RBDO, this solution also reduces manufacturing costs but by increasing total expected costs. This happens when the costs associated with different failure modes are distinct. Hence, a general equivalence between the formulations cannot be established. Optimum structural design considering expected costs of failure cannot be controlled solely by safety factors nor by failure probability constraints, but will depend on actual structural configuration. (c) 2011 Elsevier Ltd. All rights reserved.

New Optimization Algorithms for Structural Reliability Analysis

Solution of structural reliability problems by the First Order method require optimization algorithms to find the smallest distance between a limit state function and the origin of standard Gaussian space. The Hassofer-Lind-Rackwitz-Fiessler (HLRF) algorithm, developed specifically for this purpose, has been shown to be efficient but not robust, as it fails to converge for a significant number of problems. On the other hand, recent developments in general (augmented Lagrangian) optimization techniques have not been tested in aplication to structural reliability problems. In the present article, three new optimization algorithms for structural reliability analysis are presented. One algorithm is based on the HLRF, but uses a new differentiable merit function with Wolfe conditions to select step length in linear search. It is shown in the article that, under certain assumptions, the proposed algorithm generates a sequence that converges to the local minimizer of the problem. Two new augmented Lagrangian methods are also presented, which use quadratic penalties to solve nonlinear problems with equality constraints. Performance and robustness of the new algorithms is compared to the classic augmented Lagrangian method, to HLRF and to the improved HLRF (iHLRF) algorithms, in the solution of 25 benchmark problems from the literature. The new proposed HLRF algorithm is shown to be more robust than HLRF or iHLRF, and as efficient as the iHLRF algorithm. The two augmented Lagrangian methods proposed herein are shown to be more robust and more efficient than the classical augmented Lagrangian method.

The boundedness of penalty parameters in an augmented Lagrangian method with constrained subproblems

Augmented Lagrangian methods are effective tools for solving large-scale nonlinear programming problems. At each outer iteration, a minimization subproblem with simple constraints, whose objective function depends on updated Lagrange multipliers and penalty parameters, is approximately solved. When the penalty parameter becomes very large, solving the subproblem becomes difficult; therefore, the effectiveness of this approach is associated with the boundedness of the penalty parameters. In this paper, it is proved that under more natural assumptions than the ones employed until now, penalty parameters are bounded. For proving the new boundedness result, the original algorithm has been slightly modified. Numerical consequences of the modifications are discussed and computational experiments are presented.