numero de especies: 1000

Iberian Conference

in Optimization

Best Western Hotel D. Luís, Coimbra

16-18 November, 2006

Home	Venue	Fees and deadlines	Registration	List of Participants
Conference Programme	Titles and Abstracts	Social Events	Support	Organizers and Contacts

Inconsistency of linear systems is an interesting research area, as it frequently occurs in the mathematical formulation of real problems. In these cases it is interesting to understand and to reformulate the model in order to obtain feasible solutions. The reformulation of the model can be achieved either by the removal of constraints or by changing the coefficients of the model. This last possibility is in many cases more adequate to perform. The reformulation of an inconsistent model by changing both the matrix coefficients and the right hand side of the constraints is itself a nonlinear mathematical problem. The objective function measures the proximity between the original (inconsistent) and the corrected (feasible) problem. Different objective functions lead to different types of corrections and methodologies. In this talk the use of the Frobenius norm for such a goal is investigated. A nonconvex program is then obtained and two different approaches for finding a global optimum to this problem are discussed. The first is based on a tree enumeration procedure that highly relates this problem with the Total Least Squares Problem. The second approach is a branch-and-bound algorithm that is developed by exploiting a reformulation--linearization--convexification technique. Some computational experience is included to highlight the efficiency of these techniques in practice.

We consider the parameter space of all linear optimization problems, in the n-dimensional Euclidean space, whose constraints are indexed by an arbitrary (possibly infinite), but fixed, index set. This space is endowed with an extended distance escribing the uniform convergence topology of the problems' data. A problem is said to be ill-posed w.r.t. certain property (e.g., feasibility or solvability) if arbitrarily small perturbations can yield problems either enjoying or not this property. In this talk we provide some expressions for the distances to infeasibility and to unsolvability exclusively in terms of the problem's data. These results are applied to measure the Lipschitzian behavior of the feasible set and the optimal value.

Continuous optimization polynomial-time upper bounds on the stability number of graphs

An independent or stable set of graph is a pairwise nonadjacent vertex subset. The stability number of a graph is the cardinality of a maximum independent set. It is well known that the determination of the stability number of a graph is NP-hard. Several polynomial-time upper bounds on the stability number of graphs have been proposed. In this presentation, the main classical and new upper bounds on the stability number of a graph and their relative comparisons are presented. Namely, the most recent polynomial-time upper bounds on the stability number of graphs determined using continuous optimization techniques are analyzed.

In Supervised Classification one seeks a function able to classify future entries using the information in a given database. When the construction of such a function is sought, different optimization problems are faced. One needs to use a variety of Mathematical Programming tools, including Convex Analysis, Integer Programming and Multicriteria Analysis. In this talk we will illustrate how these techniques lead to reliable classification procedures, which are, in the worst case, competitive against existing procedures.

A number of problems associated with the spatial structure in the design of networks of protected areas are not trivial, and solutions are not readily approximated intuitively. One such issue is that of identifying minimum size networks capturing the regional species assemblage, where some level of adjacency or connectivity between areas is achieved. These spatial issues fit within the framework of graph theory. I will address three different combinatorial optimization problems concerning connectivity in the design of protected areas for conservation.
This work has been carried out with Diogo Alagador, Kevin Gaston and Leonor Pinto.

Computing Non-Dominated Solutions and Characterizing Weight Indifference Regions in Multiple objective Linear Fractional Programming

In this communication we present a technique to compute the maximum of a weighted sum of the objective functions in multiple objective linear fractional programming (MOLFP). The basic idea of the technique is to divide (by the approximate 'middle') the non-dominated region in two sub-regions and to analyze each of them in order to discard one if it can be proved that the maximum of the weighted sum is in the other. The process is repeated with the remaining region. The process will end when the remaining regions are so little that the differences among their non-dominated solutions are lower than a pre-defined error. Through the discarded regions it is possible to extract conditions that establish weight indifference regions. These conditions define the variation range of the weights that necessarily leads to the same non-dominated solution. These ranges define indifference regions that are characterized. An example, illustrating the concept, is presented. Some computational results indicating the performance of the technique are also presented. Keywords: Multiobjective linear fractional programming; Sum of linear ratios; Weight indifference regions.

Taking into account that an optimization problem can be classified as inconsistent, bounded (i.e., with finite optimal value) or unbounded, we can primarily consider nine classes of dual pair of problems (duality states). The duality theory reduces the number of duality states to six in the case of continuous linear semi-infinite programming problems (i.e., with compact index set and continuous coefficients) and to four in the case of ordinary linear programming problems (which are also continuous if we consider the index set equipped with the discrete topology). We characterize those continuous linear optimization problems such that sufficiently small perturbations of the data preserve the duality state of the corresponding dual pair.

In this talk we discuss the use of time-dependent formulations for routing problems. In particular we discuss:
. A computational comparison between multicommodity flow formulations and time dependent formulations for the traveling salesman problem with and without flow costs (with emphasis on the so-called cumulative travelling salesman problem.
. We produce a formulation combining features of the two previous class of models and present results given from a cutting plane approach developed for the CTSP which is based on time-dependent formulations enhanced with valid inequalities.
. We produce some inequalities which result from projecting the feasible LP set of the Picard and Queyranne into the space of a) flow and design variables and b) design variables alone.
. We show how to adapt similar ideas for the unit demand Vehicle Routing Problem.
Joint work with Teresa Godinho, Tom Magnanti, Pierre Pesneau and José Pires.

A contribution to duality theory, applied to the measurement of risk aversion

In this joint work with John K.-H. Quah we determine the precise connection between the curvature properties of a quasiconcave utility function and the ray-curvature properties of its associated indirect utility function. Our results give the precise connection between an agent's attitude towards income risks and his attitude towards risks in the underlying consumption space.

The ability of dynamically controlling traffic flows in modern technological systems, such as manufacturing and computer-communication networks, raises the possibility of optimizing their performance through appropriate design of dynamic resource allocation policies. While such problems are readily formulated in the framework of Markov decision processes, their solution via the traditional dynamic programming technique is impractical due to the well-known curse of dimensionality. Among the alternative approaches under active development which seek to overcome such limitation, the one based on mathematical programming stands out. This seeks to characterize via mathematical programming constraints the region of performance vectors which are achievable under admissible policies, which allows us to reformulate the original dynamic and stochastic optimization problem as a deterministic mathematical programming problem. The latter's solution yields both useful bounds on optimal performance, and information to design optimal or near-optimal policies. We will review the historical evolution of this approach, and discuss our own leading contributions, concluding with future perspectives.

In this paper, a robust approach to the portfolio selection problem is addressed. This problem consists in optimizing a portfolio of finitely many assets. It is well-known that traditional portfolios based on maximum likelihood estimators have extreme weights that fluctuate substantially over time. As a result, implementing these policies often requires extremely high trading volumes (turnovers) and leads to poor out-of-sample performance. For this reason, we resort to the theory of robust statistics to deal with the instability difficulties associated with the use of maximum likelihood estimators for portfolio optimization. Our contribution is threefold. First, we show how one can compute the portfolio policy that minimizes a robust estimate of risk. Then, we characterize the analytical properties of the resulting robust minimum-risk policies. Finally, we give a comparison of the out-of-sample performance of the proposed policies to that of the classical policies.

First and second order necessary and sufficient conditions for a point to be an efficient element of a set in an orderer linear space are studied. To this aim, we use first and second order tangent sets. As an application, we establish necessary and sufficient conditions for a point to be a local solution of a vector optimization problem with a nonsmooth objective function. We also establish sufficient conditions when the initial space is finite dimensional so that there is no gap with necessary conditions. Multiplier rules are also given for a constrained problem.

Solving Irregular Strip Packing problems by hybridising simulated annealing and linear programming

In this talk a hybrid algorithm to solve irregular strip packing problems is presented. The metaheuristic simulated annealing is used to guide the search over the solution space while linear programming models are solved to generate neighbourhoods during the search process. These linear programming models, which are used to locally optimise the layouts, derive from the application of compaction and separation algorithms.
The Irregular Strip Packing problem belongs to a more general class of combinatorial optimisation problems - the Cutting and Packing problems. In these problems, one or more big items, either material or space, must be divided into smaller pieces. Usually the objective is the waste minimisation, i.e. the portions of the big items that are not used to produce small pieces. In Cutting and Packing problems, on the one hand, decisions have to be taken on which pieces to produce and from which big item, which is a hard combinatorial problem. On the other hand, a specific geometric problem arises: how to cut the small pieces. These two problems are interlaced and solutions must be feasible both from the "quantitative" viewpoint (i.e. minimum or maximum number of small pieces to produce, availability of big items) and from the geometric viewpoint (i.e. no overlapping between the small pieces, containment of the small pieces inside the big items).
The focus of this talk is on the 2D Irregular Strip Packing problem, also known as nesting problem, and specially on a variant of the problem that arises in the garment industry. In its most general formulation, the nesting problem is a two dimensional Cutting and Packing problem where both the small and the big pieces have irregular (non-rectangular) shapes. Small pieces can be placed with an arbitrary orientation.
In the literature we can find several algorithms that follow different approaches to tackle the different issues present in nesting problems. For some of those issues there are techniques that clearly outperform all the other available. That is the case of the no-fit-polygon concept, used to ensure the geometric feasibility of a layout, and the case of the algorithms based on linear programming compaction models, used to obtain layouts that are local optima. There are also a few simple greedy heuristics that are very effective in achieving a "good" layout rapidly. In order to avoid local optima, metaheuristics have become very popular in this field. A very promising approach is the use of hybrid algorithms that combine metaheuristics and linear programming compaction models. This is the approach followed in the research work presented in this talk, where a simulated annealing algorithm is used to guide the search through the solution space, being the neighbourhood structure based on linear programming compaction models. Computational tests were run using instances that are commonly used as benchmarks in the literature. The best results published so far have been improved by this new hybrid packing algorithm. Joint work with António Miguel Gomes.

During the last decades, several evolutionary optimization algorithms, inspired in natural and biological processes, have been developed. In general, these algorithms recognize the existence of biological/natural processes that can be used to solve engineering problems. In spite of the relative success of these algorithms to complex engineering problems, it is important to evaluate their advantages and shortcomings, in order to define classes of problems which are more suitable for the different evolutionary algorithms. One of the most promising approaches is in multiobjective optimization, where the population based algorithms evidence a clear advantage over other approaches. In these problems, the aim is not to choose a single solution, but to determine the set of solutions that express different compromises between the different conflicting objectives. Thus, the task consists in finding this set of solutions, the Pareto optimal set, in a multidimensional space. In this presentation, an overview of the last developments in multiobjective optimization will be presented, together with some examples on structural optimization.

Design and Scheduling of Flexible Processing Systems: Optimization Based Approaches

Flexible production systems are characterized by a high flexibility response towards marketing changes given that they appear as able to ensure responsiveness and/or adaptation towards lower volume and higher value-added materials trends observed nowadays in the developed economies. This flexibility is achieved through an adequate use of the involved resources requiring the support of decision tools that help the associated decision making process. In the process industry this fact is strained as the processes involved are characterized by an elevated complexity. Various processes are often operated where multiple routes for the same product may be present with recirculation, storage sharing, re-use of resources etc. The use of optimization based approaches as adequate tools to design and operation of such flexible processing systems is discussed. Single production facilities and multi-site flexible manufacturing systems are considered. The scheduling problem is characterized and the different aspects that must be considered at the operational level are detailed. Processes, time and operational pre-requisites are modelled through the use of Mixed Integer Linear formulations and very generic models obtained. As final result the optimal operation of the systems resources so as to guarantee the required demand requisites is obtained while guaranteeing a pre-defined objective. The design problem is also addressed where due to the presence of a resource sharing policy no system can be designed without knowing how it is going to be operated. Consequently, design and scheduling aspects are considered simultaneously leading to more complex problems. The final system design and the associated scheduling are obtained as final result. Various examples are shown where different aspects are addressed. In particular it are considered the plants and supply chains detailed operation, the detailed design where system topology is studied as well as the design of supply chain structures with environmental considerations such as the reverse logistics case. All models are Mixed Integer Programming models that are solved through standard branch and bound techniques. Finally, some conclusions are drawn and directions for future work are presented.

Given a tree network $T$ with $n$ nodes, let $P(L)$ be the subset of all discrete paths whose length is bounded above by a prespecified value $L$. We consider the location of a path-shaped facility P in $P(L)$, where customers are represented by the nodes of the tree. We use a bi-criteria model to represent the total transportation cost of the customers to the facility. Each node is associated with a pair of nonnegative weights; the center-weight, and the median-weight. In this doubly weighted model, a path P is assigned a pair of values, (MAX(P), SUM(P)), which are, respectively, the maximum center-weighted distance, and the sum of the median-weighted distances from P to the nodes of the tree. Viewing $P(L)$ and the planar set \{(MAX(P),SUM(P)): P in P(L)\} as the decision space and bi-criteria or outcome space respectively, in this paper we focus on finding all the nondominated points of the bi-criteria space. We prove that there are at most $2n$ nondominated outcomes, even though the total number of efficient paths can be $\Omega(n^2)$, and they can all be generated in $O(n \log n)$ optimal time. We apply this result to solve the cent-dian model, whose objective is a convex combination of the weighted center and weighted median functions. We also solve the restricted models, where the goal is to minimize one of the two functions, MAX or SUM, subject to an upper bound on the other one, both with and without a constraint on the length of the path. All these problems are solved in linear time, once the set of nondominated outcomes has been obtained, which in turn results in an overall complexity of $O(n \log n)$. The latter bounds improve upon the best known results by a factor of $O(\log n)$. In addition, we study the problems of locating a path which minimizes the range, which is defined as the difference between the maximum and the minimum distances from the vertices of the network to a facility, and locating a path which minimizes a convex combination of the maximum and the minimum distance from the facility to the other points of the network, which is the well-known Hurwicz criterion in decision theory. We prove that on general networks these problems are NP-hard, while on trees with n vertices, we provide an $O(n)$ time algorithm for each of these problems. We also consider the problems as bicriterion path problems introducing two partial orders induced by the maximum and the minimum distance criteria. For each partial order, we provide a complete representation of the set of Pareto-Optimal paths in the outcome space in $O(n \log n)$ time.

A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two-and three-index formulations, the set partitioning formulation, and various formulations based on extra variables representing the flow of one or more commodities. Until now, there has not been a systematic study of how these formulations relate to each other. An exception is a paper of Luis Gouveia, which shows that a one-commodity flow formulation of Gavish and Graves yields, by projection, certain `multistar' inequalities in the two-index space.
We give a survey of formulations for the capacitated VRP, and then present various results of a similar flavour to those of Gouveia. In particular, we show that:
. the three-index formulation, augmented by certain families of valid inequalities, gives the same lower bound as the two-index formulation, augmented by certain simpler families of valid inequalities,
. the two-commodity flow formulation of Baldacci et al. gives the same lower bound and the same multistar inequalities as the one-commodity Gavish and Graves formulation,
. a certain non-standard multi-commodity flow formulation, with one commodity per customer, implies by projection certain `hypotour-like' inequalities in the two-index space,
. the set partitioning formulation implies by projection both multistar and hypotour-like inequalities in the two-index space.

Global and multi-local optimization in the semi-infinite programming context

Semi-infinite programming (SIP) problems appear in some important engineering fields such as air pollution control, optimal signal sets design, production planning and robot trajectory planning. Numerical methods for solving SIP problems can be classified in three major classes: discretization, exchange and reduction type methods. In the context of a reduction type method for SIP, multi--local optimization plays an important role. Getting the optimal feeding trajectory in a fed--batch fermentation processes can be formulated as a SIP problem. When some assumptions are made about the feeding trajectory, this SIP problem can be reformulated as a global optimization problem. The talk will be divided in two major parts. One is devoted to the global optimization and applications to control optimization and another is devoted to the multi--local optimization field with application to semi--infinite programming.

The classic problem of selecting efficient portfolios was formulated by Markowitz (1952). Modern portfolio selection theory usually deals with two opposite concepts: risk aversion and maximization of returns. The investor wishes to select the best combination of risk-return in order to maximize their wealth. The main point of the modelling of this problem is how the risk and assets profitability are defined and measured. Classic models consider an asset return as a random variable and its profitability is defined as the mathematical expectation of that random variable. Since the formulation of the mean-variance model a variety of enlarged and improved models have been developed in several directions. One dealt with alternative portfolio selection models, for instance, semi-variance model (Markowitz, 1959), mean-absolute deviation model (Konno and Yamazaki, 1991) or mean-downside risk models (Speranza, 1993). Another approach concerned the modelling of uncertainty and the knowledge of the experts provided by fuzzy set theory (Watada, 1997; Tanaka and Guo, 1999). In the paper we provide some new models for portfolio selection in which the returns on the securities are considered as fuzzy numbers rather than random variables. The return on each asset and their membership functions are described using historical data and the risk of the investment is approximated by mean-intervals which evaluate the downside risk for a given portfolio (León et al, 2004, Vercher, 2005). In order to illustrate the performance of our methods we have used weekly returns corresponding to a selection of assets from the Spanish Stock Market.

Optimization problems defined by functions for which derivatives are unavailable or available at a prohibitive cost are appearing more and more frequently in computational science and engineering. Increasing complexity in mathematical modeling, higher sophistication of scientific computing, and abundance of legacy codes are some of the reasons why derivative free optimization is currently an area of great demand. The goal of this talk to review some of the basic concepts on which globally convergent derivative free methods are based on and to highlight what is currently being developed. Typically, the methods are either based on fixed geometry (direct and pattern search) or on variable geometry (sampling based trust regions methods), but can also result from a combination of both. These methods tend to perform well when asked to identify global minimizers or can be appropriately modified to do so. Practical derivative free optimization is illustrated with problems arising from different sources (simulation of a mechanical system with contact, parameter estimation in astrophysics, and others) as well as from benchmarking problems in CUTEr.

A tolerant derivative-free nonmonotone line search method is proposed and analyzed. As a globalization strategy, it allows several consecutive increases in the objective function and also non descent directions for minimization problems. We present large-scale numerical experiments with gradient type methods, and also with the inverse SR1 update that could produce non descent directions.

Conditions for approximate Pareto solutions of nonconvex multiobjective optimization problems via scalarization

The main objective of this work is to characterize approximate solutions of nonconvex Pareto optimization problems through approximate solutions of associated scalar optimization problems. For this aim, a recent epsilon-efficiency concept introduced by ourselves (Math. Meth. Oper. Res., 2006, published online) is considered and several monotone and order-representing nonconvex scalarization processes are proposed, whose approximate solutions are epsilon-efficient solutions of the Pareto problem.

Leonor S. Pinto
numero de especies: 1000 Technical University of Lisbon, Portugal

In the design of protected areas networks the spatial configuration of the sites selected is an important issue. I will address a design problem when species to be protected have levels of dispersal quite dissimilar. Each species has its own habitat sites, a graph describing adjacencies between sites, and a target number of sites. Feasible solutions are subsets of sites whose habitats, for each species, induce in the corresponding graph a connected component with the required number of sites. An integer cutting algorithm to obtain minimum size feasible solutions and lower bounds is described. Results of the covering polytope are used to speed up the procedure. Computational experiments comparing two formulations are reported.

The semi-continuous quadratic mixture design problem (SCQMDP) is described as a problem with linear, quadratic and semi-continuity constraints. Moreover, a linear cost objective and an integer valued objective are introduced. The research question is to deal with the SCQMD problem from a branch-and-bound perspective generating robust solutions. The industry the problem originates from, applies different approaches to generate good acceptable solutions. Solvers are usually based on concepts such as generating random solutions, clustering, non-linear programming local search and grid search. The research question of our investigation is whether we can construct a specific Branch-and-Bound approach for the SCQMD problem, taken into account its semi-continuous character. The algorithm is tested on several cases derived from industry.

An algorithm for a bicriterion - minimum cost/minimum label -spanning tree problem

Marta Pascoal
numero de especies: 1000 University of Coimbra and Institute of Systems Engineering and Computers of Coimbra, Portugal

We deal with a bicriteria spanning tree problem relevant in some application fields such as telecommunication networks or electric networks. Each arc is assigned with a cost value and a label (such as a color). The first criterion intends to minimize the total cost of the spanning tree (the summation of its arc costs), while the second intends to get the solution with a minimum number of different labels. As these criteria are generally conflicting we developed an algorithm to generate the set of non-dominated spanning trees. Computational experiments are presented and results discussed.

On solution methods to generate Stackelberg equilibria of a Huff based location problem

Eligius M. T. Hendrix
numero de especies: 1000 University of Almería, Spain, and University of Wageningen, The Netherlands

Huff introduced a simple model in 1963 that describes the attractiveness of retailer plants for clients. We study the situation where two competing chains intend to open each a new facility in a trade area. This leads to a Game theoretic model with two players, usually called leader (the chain who locates first) and follower (the other chain), each dealing with a Global Optimisation problem. Several Branch-and-Bound techniques are investigated to find solutions to this problem. This talk reports on findings on this topic.

Maria João Alves
numero de especies: 1000 University of Coimbra and INESC Coimbra, Portugal

In this talk we propose a multiobjective genetic algorithm based on the weighted Tchebycheff scalarizing function, which aims to generate a good approximation of the whole nondominated solution set (Pareto front) of a multiobjective combinatorial problem. Concerning multiobjective evolutionary algorithms, basically two classes of approaches can be distinguished: those that are based on the dominance relation and those that are based on scalarizing functions. The former type, which has been more often considered in the literature, uses the dominance relation to primarily base the fitness assignment. The second type of approaches considers scalarizing functions that temporarily aggregate the several objective functions. The algorithm we propose belongs to the second class. The algorithm performs multiple runs of a multiobjective genetic process, each one aiming at searching for potentially nondominated solutions in a different part of the Pareto front. These processes consider different parameters (pre-defined weight vectors) which act as pivots to dynamically define the weights assigned to the objective functions in the weighted-Tchebycheff metric. Thus, each process focuses the search on a particular nondominated region, leading to an iterative approximation of the entire nondominated set. An interactive version of this algorithm is also proposed. The algorithm has been experimented in the multiobjective multidimensional 0/1 knapsack problem, for which a specialized routine to repair infeasible solutions was implemented. Computational results are presented for some benchmark instances used in the literature of the area. On the basis of these results, the algorithm is compared with other evolutionary algorithms.

Fuzzy inference systems (FIS) are based on concepts and operations associated with fuzzy set theory and fuzzy logic [3]. FIS systems are mappings from an input space to an output space, and therefore they allow constructing structures that can be used to generate responses - outputs- to certain stimulations - inputs - based on stored knowledge on how the responses and stimulations relate. FIS knowledge is encoded in a set of rules that express the relations between the input of the system and the required outputs. FIS are used to reason with imprecise or incomplete knowledge and they have been successfully applied to many types of problems such as monitoring and diagnostic, control, classification, optimization, multicriteria decision making, group decision making, and so forth [3]. In this presentation we discuss a new method, based on the Takagi Sugeno and Kang (TSK) inference scheme [5] and Choquet integration [1] [2], in which the aggregation method is more general than the TSK and takes into account not only the activation pattern of the rules but also the synergies between them. These synergies are encoded in a rule correlation matrix and the rule outputs are aggregated by means of Choquet integration, a well-known generalization of weighted averaging. We call this new fuzzy inference scheme Choquet-TSK. A first draft of the method was presented by the authors in [4]. The motivation for this new method of aggregation derives from the fact that the rules of a FIS are not always independent, as it is generally assumed [5]. Furthermore, similarity between membership functions of antecedents relating to the same input variable (e.g. large overlap of membership functions pertaining to the same linguistic variable) will imply significant correlations between the rule activation patterns, hence it may bias the results produced by the TSK system. The Choquet-TSK aggregates the outputs taking into account positive and negative correlations between rules. A real application from the Space domain will be presented to clarify the approach and to compare it with the traditional TSK inference scheme.

[1] M. Grabisch, Fuzzy integral in multicriteria decision making, Fuzzy Sets and Systems 69 (1995) 279-298.
[2] M. Grabisch, The application of fuzzy integrals in multicriteria decision making, European Journal of Operational Research 89 (1996) 445-456.
[3] J.M. Mendel, Uncertain rule-based fuzzy inference systems: Introduction and new directions, Prentice-Hall (2001).
[4] R.A. Marques Pereira, P. Serra and R.A. Ribeiro, Proceedings of the 9th Fuzzy Days Conference, Dortmund, Germany, September 2006.
[5] T. Takagi and M. Sugeno, Fuzzy identification of systems and its application to modeling and control, IEEE Transactions on Systems, Man, and Cybernetics 15 (1985) 116-132.

Distribution problems in the real world raise some practical considerations that usually are not considered in theoretical studies, at least in a realistic way. One of these considerations is connected with the vehicle capacity, not only in terms of volume but also in terms of the cargo physical arrangement. The order by which the clients are visited and the way the cargo is packed in the vehicle are important issues for the quality and admissibility of distribution solutions. Under this perspective two optimization problems meet: the Vehicle Routing Problem with Time Windows (VRPTW) and the Container Loading Problem (CLP). There is an inverse dependency between these two problems. In order to plan the routes the maximum weight of the cargo, the total volume, the packing order and the cargo stability must be considered. To achieve a good distribution it is necessary to take into account each one of these considerations. The need to combine the VRPTW and CLP problems arises. This integration results in a new problem named by us Vehicle Routing and Loading Problem (VRLP). This work presents the VRLP mathematical formulation and two different heuristic approaches. The first approach deal simultaneously with the two sub problems and the other one use an hierarquical strategy. With the first approach three algorithms are developed, one based in the Monte Carlo method, the second one is a compound heuristic and the last one a GRASP algorithm. The second method is an integration of two algorithms previously developed by the author in order to solve the VRPTW and CLP problems. In short, four approaches are presented to solve the VRLP. Some test problems were created to evaluate the quality and efficiency of the VRLP approaches. Those test problems are based on Solomon and Bischoff and Ratcliff test problems. Finally the results obtained and the respective conclusions are presented.

Adelaide Cerveira
numero de especies: 1000 Univ. Trás-os-Montes e Alto Douro, Portugal

In this talk, we consider a truss topology design problem, where the cross-sectional area of the bars can have only a finite number of values. The goal is to find the stiffest truss, under a given load, with a maximum volume constraint. The model is a large-scale non-convex problem which can be formulated as a semidefinite problem with binary variables. To solve the problem exactly it is applied a branch and bound method. Computational results are presented.

Extended solutions and primal-dual stability in linear semi-infinite optimization

F. Javier Toledo-Melero
numero de especies: 1000 Miguel Hernández University of Elche, Spain

We consider linear optimization problems in R^n with infinitely many inequality constraints. It is well-known that, in this linear semi-infinite optimization setting, nonzero duality gaps may occur. These gaps may be avoided by considering a suitable notion of extended solutions. In this talk we show how extended solutions allow us to study some stability properties of a pair of dual problems. Specifically, the main results are concerned with the sensitivity of the dual optimal value and the stability of the feasible set under small perturbations of the problems data.

(Based on a joint work with María J. Cánovas, Marco A. López, and Juan Parra)

The multiobjective shortest path (MSPP) problem is defined in a vector valued network. As usually there is a conflict among the different criteria solving the MSPP turns into finding nondominated (ND) paths, that is, paths for which there is no other path with better values for all the criteria. In the proposed method, ranking shortest path is used to select new labels from which the search tree is then developed. The algorithm computes sequentially deviation shortest paths (following an utility function) until all ND paths are obtained. Consequently, it finds ND s-t paths at a very early stage. Computational results are presented comparing the performance of the new technique relatively to the classical ones.

(joint work with José Pinto Paixão)

Initial solutions and step-lengths used in the resolution of some classes of semidefinite programming problems with some versions of a predictor-corrector method variant that use the HKM direction

Ana Paula Teixeira
numero de especies: 1000 University of Trás-os-Montes e Alto Douro, Portugal

Using some versions of a variant of a predictor-corrector primal-dual interior point algorithm with the HKM direction, we present a study that aims to obtain suitable initial solutions and step-lengths to be used in the resolution of some classes of semidefinite programming problems. In that variant, the predictor is calculated as an iteration of the primal-dual algorithm and the corrector is calculated in the classical way. All the implementations were based on the source code of the package CSDP. We will present computational experience.

(joint work with Fernando Bastos)

Edite M. G. P. Fernandes
numero de especies: 1000 University of Minho, Portugal

In this talk we consider the problem of finding all the global solutions of a nonlinear optimization problem. We propose a new algorithm that combines the simulated annealing method with a function stretching technique in order to generate a sequence of global optimization problems that are defined whenever a new global solution is identified. Computational experiments with a set of well-known test problems show that the proposed method is effective.

Strengthened lower bounds for the part families with precedence constraints problem

Lídia Lampreia Lourenço
numero de especies: 1000 New University of Lisbon, Portugal

The part families with precedence constraints problem (PFP) consists of grouping parts into families, within flexible manufacturing systems, by imposing capacity constraints, concerning both the number of parts and processing times, besides precedence constraints in the building of families. An alternative to a natural formulation for this difficult NP-hard problem is an extended formulation. This mixed binary linear model enables one to develop different valid inequalities that dominate those previously deduced. Results of a computational experiment, using the CPLEX software applied to the linear relaxation of the extended formulation and including the valid inequalities, confirmed the strengthening of the lower bounds for most of the instances tested. Such bounds can be used to improve the performance of a specific branch-and-bound to be developed for the PFP.

Keywords: part families problem; precedence constraints; mixed binary linear formulation; valid inequalities.

With this talk we present the formalization for a new problem concerning the determination of a minimal spanning tree with minimal node degree constraints for a given graph, and show that it is, in fact, another NP-hard problem.

(joint work with Pedro Coimbra Martins and Maurício Souza)

An Efficient Simulated Annealing Algorithm for Regional Wastewater Systems Planning

Maria da Conceição Cunha
numero de especies: 1000 University of Coimbra, Portugal

At present, most wastewater systems are local, i.e., each city has its own system. However, in many cases, these systems could better both from the economic and the environmental viewpoints if they were regional. The search for the best regional wastewater systems can only be effective if it is made through an optimization model. In this article, we report a study made to develop an efficient simulated annealing algorithm for solving a regional wastewater systems planning model – that is, a model aimed at determining the minimum-cost configuration for the system needed to drain the wastewater generated by the population centers located within a region, while meeting the quality standards defined for the receiving water bodies and complying with all other relevant regulatory aspects. Because of their highly non-linear nature, even moderate-size instances of a model of this type must be handled through heuristic algorithms. The simulated annealing algorithm is termed efficient because its parameters were calibrated to ensure the best possible solutions to the optimization model. The calibration was made for a sample of test problems using a particle swarm algorithm.

(Joint work with António P. Antunes and João A. Zeferino)

Solving the capacitated median problem by a priori reformulation and branch-and-cut

António P. Antunes
numero de especies: 1000 University of Coimbra, Portugal

In the capacitated median model, the aim is to locate facilities and assign demand centers to the facilities so that the total assignment cost is minimized, each facility serves at least a given minimum amount of demand, and each center is fully served by the closest (or least cost) facility. This model is useful in the context of public facility location problems where facilities such as schools, hospitals or post offices should guarantee a minimum workload (e.g. a minimum number of users) in order to be economically feasible, and users minimize their costs by attending the closest facility. The capacitated median model is a variant of the well-known p-median problem in which the number of open facilities is a model output rather than a parameter, and the so-called single assignment and closest assignment properties of solutions must be enforced explicitly rather than being naturally guaranteed. In this talk, we present valid inequalities for the integer programming formulation of the capacitated median model, show how they can be exploited by an a priori reformulation of the model, and present computational results with a branch-and-cut algorithm.

(Joint work with João C. Teixeira)

Graph based approaches to solve non guillotinable two-dimensional rectangular cut and packing problems

Maria Eduarda Ferreira
numero de especies: 1000 Polytechnic Institute of Porto, Portugal

This work presents a set of graph based approaches to solve non guillotinable two-dimensional rectangular cut and packing problems. Building on the work of Fekete and Schepers, namely their graph based algorithm which uses the properties of visibility graphs (representing the projection of packing’ items on the coordinate axis) to generate a packing. In this work, we introduce new requirements into this algorithm, so that it is possible to establish an equivalence between a set of visibility graphs and a packing. Exact algorithm for the construction of two-dimensional cut and packing problems are extremely demanding, on the computational point of view, their application being thus limited to problems not exceeding a few tens of elements. A new multi-level non exact algorithm was therefore introduced to circumvent this problem. Results are presented for problems up to 15000 elements. A study about the use of visibility graphs based neighbourhood structures in two-dimensional rectangular cut and packing problems is also presented. Two of these structures were then used in the simulated annealing metaheuristic.

Keywords: graphs, cut and packing, neighbourhood structures, metaheuristics

Study of a Special Nonlinear Problem Arising in Convex Semi-Infinite Programming

We study convex Semi Infinite (SIP) problems using the Implicit Optimality Criterion suggested in our recent paper (see Kostyukova O.I., Tchemisova T.V., Yermalinskaya S.A., "Convex Semi-Infinite Programming: Implicit Optimality Criterion Based on the Concept of Immobile Points"), where we have formulated the optimality conditions for a SIP problem in terms of such the conditions for a special Nonlinear Programming (NLP) problem. In the paper, we study some specific properties of the latest problem and obtain the efficient optimality conditions for it. We show that in the case when the constraint function of the initial SIP problem is analytical, then the optimality conditions for it take the form of criterion.

Consider a body moving in R^2, in a very rare medium, with constant velocity. At the same time, the body uniformly rotates (around its center of masses, say). The force exerted by the medium on the body is due to elastic collisions of the medium’s particles with the body. This force is called resistance; it is a periodic vector-valued function of time, the period being equal to the period of rotation. The problem is: find the (convex) set of all values the resistance vector can take. We present analytical and numerical results for this problem in the class of bodies contained in a given circle. The solution depends on the angular velocity of rotation.

Discretized formulations and valid inequalities for the variable size bin packing problem

In the Variable Size Bin Packing Problem we have bins of different capacities and costs available for packing the items. The objective is to pack all the items minimizing the total cost associated with the bins. We propose and discuss several formulations. One of these formulations considers explicitly the class of the bins used. The other uses a so-called discretized model reformulation technique. New valid inequalities suggested by the discretized variables are proposed. Computational results are presented showing that the valid inequalities proposed not only enhance the linear programming relaxation bound but may also be extremely helpful when using a commercial package for solving the problem optimality.