Counting and enumerating aggregate classifiers

in Discrete Applied Mathematics (2008), 156(3), 2459-2468

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct ... [more ▼]

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct aggregate classifiers that arise in this model. When there are only two classes in the classification problem, we show that a class of functions that arises from aggregate classifiers coincides with the class of self-dual positive threshold Boolean functions. [less ▲]

Geršgorin variations III: On a theme of Brualdi and Varga

in Journal of Linear Algebra and its Applications (2008), 428

Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the ... [more ▼]

Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the product of the diagonal entries exceeds the product of the row sums of the moduli of the off-diagonal entries, then the matrix is nonsingular. We will show how, in polynomial time, that condition can be tested and (if satisfied) produce a diagonal matrix D, with positive diagonal entries, such that AD (where A is any nonnnegative matrix satisfying the conditions) is strictly diagonally dominant (and so, A is nonsingular). The same D works for all matrices satisfying the conditions. Varga raised the question of whether Brualdi’s conditions are sharp. Improving Varga’s results, we show, if G is scwaltcy (strongly connected with at least two cycles), and if the Brualdi conditions do not hold, how to construct (again in polynomial time) a complex matrix whose moduli satisfy the given specifications, but is singular. [less ▲]

The tool switching problem revisited

in European Journal of Operational Research (2007), 182(2), 952-957

In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting ... [more ▼]

In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly N P-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem. (C) 2006 Elsevier B.V. All rights reserved. [less ▲]

A mixed-integer heuristic for the structural optimization of a cruise ship

in COMPIT 2007 , Cortona, Italy (2007, April 23)

A heuristic approach is proposed to solve the structural optimization problem of a cruise ship. The challenge of optimization is to define the scantling of the structure of a ship in order to minimize the ... [more ▼]

A heuristic approach is proposed to solve the structural optimization problem of a cruise ship. The challenge of optimization is to define the scantling of the structure of a ship in order to minimize the weight or the production cost. The variables are the dimensions and positions of the constitutive elements of the structure: they are discrete by nature. The objective functions are nonlinear functions. The structure is submitted to geometric constraints and to structural constraints. The geometric constraints are linear functions and the structural constraints are implicit functions requiring a high computation cost. The problem belongs to the class of mixed-integer nonlinear problems (MINLP). A local heuristic of the type “dive and fix” is combined with a solver based on approximation methods. The solver is used as a black-box tool to perform the structural analysis and solve the nonlinear optimization problems (NLP) defined by the heuristic. The heuristic is designed to always provide a discrete feasible solution. Experiments on a real-size structure demonstrate that the optimal value of the mixed-integer problem is of the same magnitude as the optimal value of the optimization problem for which all the variables can take continuous values. [less ▲]

Multiplicity and complexity issues in contemporary production scheduling

in Statistica Neerlandica (2007), 61(1), 75-91

High multiplicity scheduling problems arise naturally in contemporary production settings where manufacturers combine economies of scale with high product variety. Despite their frequent occurrence in ... [more ▼]

High multiplicity scheduling problems arise naturally in contemporary production settings where manufacturers combine economies of scale with high product variety. Despite their frequent occurrence in practice, the complexity of high multiplicity problems - as opposed to classical, single multiplicity problems - is in many cases not well understood. In this paper, we discuss various concepts and results that enable a better understanding of the nature and complexity of high multiplicity scheduling problems. The paper extends the framework presented in Brauner et al. [Journal of Combinatorial Optimization (2005) Vol. 9, pp. 313-323] for single machine, non-preemptive high multiplicity scheduling problems, to more general classes of problems. [less ▲]

Optimization of Surface Allocation using Heuristic Approaches

in COMPIT 2005 , Hambourg, Germany (2005, May)

In this paper, we present a scheduling problem that arises in factories producing large building blocks (in our case, a shipyard workshop producing prefabricated keel elements). The factory is divided in ... [more ▼]

In this paper, we present a scheduling problem that arises in factories producing large building blocks (in our case, a shipyard workshop producing prefabricated keel elements). The factory is divided in several equal size areas. The blocks produced in the factory are very large, and, once a building block is placed in the factory, it cannot be moved until all processes on the building block are finished. The blocks cannot overlap. The objective is to maximize the number of building blocks produced in the factory during a certain time window. To solve this problem, we propose heuristics inspired by techniques initially developed for the three-dimensional bin packing problem, e.g. Faroe and al. (2003), since constraints for both problems are quite similar. Starting from an unfeasible solution, where blocks can overlap, a Guided Local Search (GLS) heuristic is used to minimize the sum of total overlap. If a solution with zero overlap is found, then it is a feasible solution; otherwise the block with the biggest overlap is removed and the procedure is restarted. The GLS algorithm has been improved by Fast Local Search (FST) tech- niques in order to speed up convergence to a local minimum. Additionally, neighborhoods are restricted to their smallest size so as to allow their evaluation in polynomial-time. In a last step, we explain the additional real-life issues arising in the industrial application and how firm-specific constraints can be conveniently considered by the model. [less ▲]

Grafting Information in Scenario Trees: Application to Option Prices

E-print/Working paper (2005)

The high level of sophistication in portfolio management modeling techniques often goes along with very large output sensitivity to parameter choices. As a potential solution to this problem, this paper ... [more ▼]

The high level of sophistication in portfolio management modeling techniques often goes along with very large output sensitivity to parameter choices. As a potential solution to this problem, this paper proposes a consistent and flexible methodology to represent the distribution of future values of a portfolio through scenario trees. This methodology relies on the information contained in current option prices in order to generate the probability density function of future returns. This density function can be used, in turn, to generate scenario trees . As an illustration, a tree of scenarios based on S&P500 options is built and then used to compute arbitrage-free option prices. The approach preserves information embedded in options prices and is able to provide very accurate values for out-of-sample options. The high level of numerical accuracy of the framework is reproduced on different samples. The scenario tree approach also provides stable pricing results when confronted with the passage of time. The results derived from our model are comparable to those obtained from Rubinstein’s [1994] methodology, although both models fulfill different objectives. [less ▲]

Optimal procurement decisions in the presence of total quantity discounts and alternative product recipes

in European Journal of Operational Research (2004), 159(2), 364-378

We describe the purchasing decisions faced by a multi-plant company. The suppliers of this company offer complex discount schedules based on the total quantity (rather than cost) of ingredients purchased ... [more ▼]

We describe the purchasing decisions faced by a multi-plant company. The suppliers of this company offer complex discount schedules based on the total quantity (rather than cost) of ingredients purchased. The schedules simultaneously account both for corporate purchases and for purchases at the individual plant level. The complexity of the purchasing decisions is further increased due to the existence of alternative production recipes for each final product. We formulate the corresponding cost-minimization problem as a nonlinear mixed 0-1 programming problem. We propose various ways to linearize this formulation, and we evaluate the quality of the resulting models on real-world data. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]

Simulated annealing for complex portfolio selection problems

in European Journal of Operational Research (2003), 150(3), 546-571

This paper describes the application of a simulated annealing approach to the solution of a complex portfolio selection model. The model is a mixed integer quadratic programming problem which arises when ... [more ▼]

This paper describes the application of a simulated annealing approach to the solution of a complex portfolio selection model. The model is a mixed integer quadratic programming problem which arises when Markowitz' classical mean-variance model is enriched with additional realistic constraints. Exact optimization algorithms run into difficulties in this framework and this motivates the investigation of heuristic techniques. Computational experiments indicate that the approach is promising for this class of problems. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]

Production planning problems in printed circuit board assembly

in Discrete Applied Mathematics (2002), 123(1-3), 339-361

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical ... [more ▼]

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical decomposition of the planning process into distinct optimization subproblems, addressing issues such as the assignment of board types to machine groups, the allocation of component feeders to individual machines, the determination of optimal production sequences, etc, The paper reviews the literature on this topic with an emphasis on the most recent developments, on the fundamental structure of the mathematical models and on the relation between these models and some 'environmental' variables such as the layout of the shop or the product mix. (C) 2002 Elsevier Science B.V, All rights reserved. [less ▲]