Bilevel optimization applied to strategic pricing in competitive electricity markets

In this paper, we present a bilevel programming formulation for the problem of strategic bidding under uncertainty in a wholesale energy market (WEM), where the economic remuneration of each generator depends on the ability of its own management to submit price and quantity bids. The leader of the bilevel problem consists of one among a group of competing generators and the follower is the electric system operator. The capability of the agent represented by the leader to affect the market price is considered by the model. We propose two solution approaches for this non-convex problem. The first one is a heuristic procedure whose efficiency is confirmed through comparisons with the optimal solutions for some instances of the problem. These optimal solutions are obtained by the second approach proposed, which consists of a mixed integer reformulation of the bilevel model. The heuristic proposed is also compared to standard solvers for nonlinearly constrained optimization problems. The application of the procedures is illustrated in case studies with configurations derived from the Brazilian power system.     

Bundle Relaxation and Primal Recovery in Unit Commitment Problems. The Brazilian Case

We consider the inclusion of commitment of thermal generation units in the optimal management of the Brazilian power system. By means of Lagrangian relaxation we decompose the problem and obtain a nondifferentiable dual function that is separable. We solve the dual problem with a bundle method. Our purpose is twofold: first, bundle methods are the methods of choice in nonsmooth optimization when it comes to solve large-scale problems with high precision. Second, they give good starting points for recovering primal solutions. We use an inexact augmented Lagrangian technique to find a near-optimal primal feasible solution. We assess our approach with numerical results.     

Discrete Variational Calculus for B-Spline Curves

In this work, we study discrete variational problems, for B-spline curves, which are invariant under translation and rotation. We show this approach has advantages over studying smooth variational problems whose solutions are approximated by B-spline curves. The latter method has been well studied in the literature but leads to high order approximation problems. We are particularly interested in Lagrangians that are invariant under the special Euclidean group for which B-spline approximated curves are well suited. The main application we present here is the curve completion problem in 2D and 3D. Here, the aim is to find various aesthetically pleasing solutions as opposed to a solution of a physical problem. Smooth Lagrangians with special Euclidean symmetries involve curvature, torsion, and arc length. Expressions of these, in the original coordinates, are highly complex. We show that, by contrast, relatively simple discrete Lagrangians offer excellent results for the curve completion problem. The novel methods we develop for the discrete curve completion problem are general, and can be used to solve other discrete variational problems for B-spline curves. Our method completely avoids the difficulties of high order smooth differential invariants.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

Cutting optimization of structural tubes to build agricultural light aircrafts

In this study we deal with the one-dimensional cutting of metallic structural tubes used in the manufacturing of agricultural light aircrafts. The problem is modeled by mixed integer linear formulations aiming to minimize material trim losses and considering the possibility of generating remainders (leftovers) with enough size to reuse. To validate the application of the models in practice, we carried out experiments with real data of order lists from Ipanema, an agricultural airplane produced by a Brazilian aeronautical company. The models were solved using a modeling language and an optimization software. The computational results show that the models are useful in supporting decisions in this cutting process.     

Extended scaling invariance of one‐dimensional models of liquid dynamics in a horizontal capillary

In this paper, we consider the adaptive numerical solution of one‐dimensional models of liquid dynamics in a horizontal capillary. The bulk liquid is assumed to be initially at rest and is put into motion by capillarity: the smaller is the capillary radius, the steeper becomes the initial transitory of the meniscus location derivative, and as a consequence, the numerical solution to a prescribed accuracy becomes harder to achieve. Therefore, in order to solve a capillary problem effectively, it would be advisable to apply an adaptive numerical method. Here, we show how an extended scaling invariance that can be used to define a family of solutions from a computed one. In the viscous case, the similarity transformation involves solutions of liquids with different density, surface tension, viscosity, and capillary radii, whereas in the inviscid case, we can generate a family of solutions for the same liquid and capillaries with different radii. With our study, we are able to prove that the monitor function, used in the adaptive algorithm, is invariant with respect to the considered scaling group. It follows, from this particular results, that all the solutions within the generated family verify the adaptive criteria used for the computed one. Moreover, all the solutions have the same order of accuracy even if the maximum value of the step size varies under the action of the scaling group. Copyright © 2012 John Wiley & Sons, Ltd.     

Analysis of nonlinear BVPs motivated by fluid film flow over a surface

We study a coupled nonlinear boundary value problem which has been shown to have applications to fluid flow and heat transfer in a fluid film over a stretching surface for set values of the model parameters (one of which determines the size of the problem domain). For arbitrary values of these parameters we are able to establish the existence and uniqueness of a class of monotone solutions. Perturbation solutions are then constructed and used to approximate certain invariants for the solutions. We then study a related boundary value problem formed by imposing an additional boundary condition on one of the governing equations (which results in an ill-posed problem), and we arrive at conditions allowing for solutions to this four-parameter problem to agree with the solutions to the three-parameter problem.     

Heuristics for the mirrored traveling tournament problem

Professional sports leagues are a major economic activity around the world. Teams and leagues do not want to waste their investments in players and structure in consequence of poor schedules of games. Game scheduling is a difficult task, involving several decision makers, different types of constraints, and multiple objectives to optimize. The traveling tournament problem abstracts certain types of sport timetabling issues, where the objective is to minimize the total distance traveled by the teams. In this work, we tackle the mirrored version of this problem. We first propose a fast and effective constructive algorithm. We also describe a new heuristic based on the combination of the GRASP and iterated local search metaheuristics. A strong neighborhood based on ejection chains is also proposed and leads to significant improvements in solution quality. Very good solutions are obtained for the mirrored problem, sometimes even better than those found by other approximate algorithms for the less constrained non-mirrored version. Computational results are shown for benchmark problems and for a large instance associated with the main division of the 2003 edition of the Brazilian soccer championship, involving 24 teams.     

Regularized Solutions of a Nonlinear Convolution Equation on the Euclidean Group

In this paper we apply Fourier analysis on the two and three dimensional Euclidean motion groups to the solution of a nonlinear convolution equation. First, we review the theory of the irreducible unitary representations of the motion group and discuss the corresponding Fourier transform of functions on the motion group. The main reasons why exact solutions of this convolution equation do not exist in many cases are discussed. Techniques for regularization of the problem and numerical methods for finding approximate solutions are presented. Examples are considered and approximate solutions are found.     

The Role of Frame Force in Quantum Detection

A general method is given to solve tight frame optimization problems, borrowing notions from classical mechanics. In this article, we focus on a quantum detection problem, where the goal is to construct a tight frame that minimizes an error term, which in quantum physics has the interpretation of the probability of a detection error. The method converts the frame problem into a set of ordinary differential equations using concepts from classical mechanics and orthogonal group techniques. The minimum energy solutions of the differential equations are proven to correspond to the tight frames that minimize the error term. Because of this perspective, several numerical methods become available to compute the tight frames. Beyond the applications of quantum detection in quantum mechanics, solutions to this frame optimization problem can be viewed as a generalization of classical matched filtering solutions. As such, the methods we develop are a generalization of fundamental detection techniques in radar.      

Numerical Scaling Invariance Applied to the van der Pol Model

In this study we use the van der Pol model to explain a novel numerical application of scaling invariance. The model in point is not invariant to a scaling group of transformations, but by introducing an embedding parameter we are able to recover it from an extended model which is invariant to an extended scaling group. As well known, within a similarity analysis we can define a family of solutions from a computed one, so that the solution of a target problem can be obtained by rescaling the solution of a reference problem. The main idea is to use scaling invariance and numerical analysis to find a reference problem easier to solve, from a numerical viewpoint, than the target problem. This allows us to save human efforts and computational resources every time we have to solve a challenging problem. We test our approach using three stiff solvers available within the most recent releases of MATLAB. Independently from the solver used, by employing the described scaling invariance we are able to significantly reduce the computational cost of the numerical solution of the van der Pol model.      

Almost global existence for solutions of a nonlinear fourth order hyperbolic equation

We study the long time existence of the solutions of the Cauchy problem for a class of nonlinear fourth order hyperbolic equations, in which the principal part is given by the composition of two waves operators with different propagation speeds. The presence of these two speeds makes this problem essentially different from the correspondent one for the second order wave equation. In fact, in the present case, we cannot apply the approach of S. Klainerman, based on the invariance of the D'Alembertian operator under the complete Lorentz group. Furthermore, even the alternative method used by F. John and S. Klainerman, only for the wave equation in three space dimensions, does not seem directly applicable. Nevertheless, thanks to the special structure of the equations, we are able to show the almost global existence of the solutions to the related Cauchy problem. Received December 29, 1995     

Aggregation of scale efficiency

In this article we generalize the aggregation theory in efficiency and productivity analysis by deriving solutions to the problem of aggregation of individual scale efficiency measures, primal and dual, into aggregate primal and dual scale efficiency measures of a group (e.g., industry). The new aggregation result is coherent with aggregation framework and solutions that were earlier derived for other related efficiency measures and can be used in practice for estimation of scale efficiency of an industry or other groups of firms within it.     

The combined cutting stock and lot-sizing problem in industrial processes

Despite its great applicability in several industries, the combined cutting stock and lot-sizing problem has not been sufficiently studied because of its great complexity. This paper analyses the trade-off that arises when we solve the cutting stock problem by taking into account the production planning for various periods. An optimal solution for the combined problem probably contains non-optimal solutions for the cutting stock and lot-sizing problems considered separately. The goal here is to minimize the trim loss, the storage and setup costs. With a view to this, we formulate a mathematical model of the combined cutting stock and lot-sizing problem and propose a solution method based on an analogy with the network shortest path problem. Some computational results comparing the combined problem solutions with those obtained by the method generally used in industry—first solve the lot-sizing problem and then solve the cutting stock problem—are presented. These results demonstrate that by combining the problems it is possible to obtain benefits of up to 28% profit. Finally, for small instances we analyze the quality of the solutions obtained by the network shortest path approach compared to the optimal solutions obtained by the commercial package AMPL.     

An extension of Glimm's method to inhomogeneous strictly hyperbolic systems of conservation laws by “weaker than weak” solutions of the Riemann problem

We construct a generalized solution of the Riemann problem for strictly hyperbolic systems of conservation laws with source terms, and we use this to show that Glimm's method can be used directly to establish the existence of solutions of the Cauchy problem. The source terms are taken to be of the form a^′G, and this enables us to extend the method introduced by Lax to construct general solutions of the Riemann problem. Our generalized solution of the Riemann problem is “weaker than weak” in the sense that it is weaker than a distributional solution. Thus, we prove that a weak solution of the Cauchy problem is the limit of a sequence of Glimm scheme approximate solutions that are based on “weaker than weak” solutions of the Riemann problem. By establishing the convergence of Glimm's method, it follows that all of the results on time asymptotics and uniqueness for Glimm's method (in the presence of a linearly degenerate field) now apply, unchanged, to inhomogeneous systems.     

Optimising the cutting of wood fibre plates in the hardboard industry

Hardboard companies transform eucalyptus trunks into rectangular wood fibre plates basically by means of processes of disintegration and reconstitution of wood fibres. Such plates called hardboards are then cut into ordered items (smaller rectangles) to satisfy customer demands. In this paper, we present approaches to generate cutting patterns that minimize the cost or waste of material, considering different particular constraints associated with longitudinal and transversal saws, head cuts, book rotation and item unloading stations of the cutting machine. The methods are based on dynamic programming recursive formulas combined with greedy constructive heuristics and the primal simplex algorithm. To illustrate the application of these approaches, a case study was carried out in a Brazilian hardboard company. The results show that the approaches are able to produce better solutions than the ones currently used by the company.     

Weak efficiency in multiobjective variational problems under generalized convexity

In this paper, we provide new pseudoinvexity conditions on the involved functionals of a multiobjective variational problem, such that all vector Kuhn-Tucker or Fritz John points are weakly efficient solutions if and only if these conditions are fulfilled. We relate weakly efficient solutions to optimal solutions of weighting problems. We improve recent papers, and we generalize pseudoinvexity conditions used in multiobjective mathematical programming, so as some of their characterization results. The new conditions and results are illustrated with an example.     

A mixed integer linear programming model for reliability optimisation in the component deployment problem

Component deployment is a combinatorial optimisation problem in software engineering that aims at finding the best allocation of software components to hardware resources in order to optimise quality attributes, such as reliability. The problem is often constrained because of the limited hardware resources, and the communication network, which may connect only certain resources. Owing to the non-linear nature of the reliability function, current optimisation methods have focused mainly on heuristic or metaheuristic algorithms. These are approximate methods, which find near-optimal solutions in a reasonable amount of time. In this paper, we present a mixed integer linear programming (MILP) formulation of the component deployment problem. We design a set of experiments where we compare the MILP solver to methods previously used to solve this problem. Results show that the MILP solver is efficient in finding feasible solutions even where other methods fail, or prove infeasibility where feasible solutions do not exist.     

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company.     

A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland

In this paper, we consider a real-life vehicle routeing problem that occurs in a major Swiss company producing pet food and flour. In contrast with usual hypothetical problems, a large variety of restrictions has to be considered. The main constraints are relative to the accessibility and the time windows at customers, the carrying capacities of vehicles, the total duration of routes and the drivers' breaks. To find good solutions to this problem, we propose two heuristic methods: a fast straightforward insertion procedure and a method based on tabu search techniques. Next, the produced solutions are compared with the routes actually covered by the company. Our outcomes indicate that the total distance travelled can be reduced significantly when such methods are used.