Cluster analysis of census data using the symbolic data approach

The aim of this paper is to investigate the economic specialization of the Italian local labor systems (sets of contiguous municipalities with a high degree of self-containment of daily commuter travel) by using the Symbolic Data approach, on the basis of data derived from the Census of Industrial and Service Activities. Specifically, the economic structure of a local labor system (LLS) is described by an interval-type variable, a special symbolic data type that allows for the fact that all municipalities within the same LLS do not have the same economic structure.     

Persistence in discrete optimization under data uncertainty

An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the network and determine a smaller set of arcs that will most probably be a part of the optimal solution under different realizations of the arc lengths. Building on a characterization of moment cones for single variate problems, and its associated semidefinite constraint representation, we develop a limited marginal moment model to compute the persistency of a decision variable. Under this model, we show that finding the persistency is tractable for zero-one optimization problems with a polynomial sized representation of the convex hull of the feasible region. Through extensive experiments, we show that the persistency computed under the limited marginal moment model is often close to the simulated persistency value under various distributions that satisfy the prescribed marginal moments and are generated independently.     

Balancing two-sided U-type assembly lines using modified particle swarm optimization algorithm

In this paper, a new two-sided U-type assembly line balancing (TUALB) procedure and a new algorithm based on the particle swarm optimization algorithm to solve the TUALB problem are proposed. The proposed approach minimizes the number of stations for a given cycle time as the primary objective and it minimizes the number of positions as a secondary objective. The proposed approach is illustrated with an example problem. In order to evaluate the efficiency of the proposed algorithm, the test problems available in the literature are used. The experimental results show that the proposed approach performs well.     

Solving discrete linear bilevel optimization problems using the optimal value reformulation

In this article, we consider two classes of discrete bilevel optimization problems which have the peculiarity that the lower level variables do not affect the upper level constraints. In the first case, the objective functions are linear and the variables are discrete at both levels, and in the second case only the lower level variables are discrete and the objective function of the lower level is linear while the one of the upper level can be nonlinear. Algorithms for computing global optimal solutions using Branch and Cut and approximation of the optimal value function of the lower level are suggested. Their convergence is shown and we illustrate each algorithm via an example.     

Laguerre polynomials and the inverse Laplace transform using discrete data

We consider the problem of finding a function defined on (0,∞) from a countable set of values of its Laplace transform. The problem is severely ill-posed. We shall use the expansion of the function in a series of Laguerre polynomials to convert the problem in an analytic interpolation problem. Then, using the coefficients of Lagrange polynomials we shall construct a stable approximation solution. Error estimate is given. Numerical results are produced.     

Some problems in discrete optimization

The present paper concentrates on several problems of network flows and discrete optimization. Progress has been made on some of the problems while little is known about others. Some of the problems discussed are shortest paths, multi-commodity flows, traveling salesman problems, m-center problem, telepak problems and binary trees.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.Sponsored by the United States Army under Contract No.: DA-31-124-ARO-D-462 and the National Science Foundation, GJ-28339.     

On discrete optimization with ordering

This paper studies discrete optimization problems with ordering requirements. These problems are formulated on general discrete sets in which there exists an ordering on their elements together with a cost function that evaluates each element of a given subset depending on its ordering relative to the remaining elements in the set. It is proven that ordered sequences over the original ground set define an independence system. The simplest such ordering problem, that consists of finding the ordered sequence of maximum weight, and its restriction to sets of a fixed cardinality are studied. In both cases, the polyhedral structure of the corresponding feasible sets is analyzed.     

A new discrete filled function algorithm for discrete global optimization

A definition of the discrete filled function is given in this paper. Based on the definition, a discrete filled function is proposed. Theoretical properties of the proposed discrete filled function are investigated, and an algorithm for discrete global optimization is developed from the new discrete filled function. The implementation of the algorithms on several test problems is reported with satisfactory numerical results.     

Evaluating the quality of online optimization algorithms by discrete event simulation

A key feature of dynamic problems which offer degrees of freedom to the decision maker is the necessity for a goal-oriented decision making routine which is employed every time the logic of the system requires a decision. In this paper, we look at optimization procedures which appear as subroutines in dynamic problems and show how discrete event simulation can be used to assess the quality of algorithms: after establishing a general link between online optimization and discrete event systems, we address performance measurement in dynamic settings and derive a corresponding tool kit. We then analyze several control strategies using the methodologies discussed previously in two real world examples of discrete event simulation models: a manual order picking system and a pickup and delivery service.     

A primogenitary linked quad tree data structure and its application to discrete multiple criteria optimization

A data structure called the primogenitary linked quad tree is developed. Each node in the data structure has a pointer to its parent, a pointer to its immediate existing younger sibling, a pointer to its eldest existing son, and an integer as its successorship to its parent. To access any other son of a node, the first-born existing son must be accessed first. The siblings of the same parent are managed as a linked list. This data structure is an extension or enhancement of the traditional quad tree data structure. The primogenitary linked quad tree is applied to discrete multiple criteria optimization for the identification, storage, and retrieval of nondominated criterion vectors. Algorithms managing this data structure are developed and implemented. Major advantages of using the primogenitary linked quad tree instead of the traditional quad tree are savings in memory or storage space and savings in execution time. Examples are provided to demonstrate the application. A computational experiment is conducted to test the performances of the data structure and the algorithms. Computational results show that this data structure uses only a small fraction of the CPU time used by the traditional quad tree to perform the same task. Using this data structure, the identification, storage and retrieval of nondominated criterion vectors become an easy task for discrete multiple criteria optimization problems with many criteria and hundreds of thousands criterion vectors. This data structure can also be used for storage and retrieval of data with composite keys in other applications.     

A discrete optimization method based on a parameterization of a Grassmannian in multidimensional dichotomous data structuring

An approach to reducing large computational time in the problem of multidimensional dichotomous data structuring based on algebraic properties of finite geometries is proposed. A vector parameterization of the Grassmannian Gr₂(k, n) reducing memory expenditures and the number of operations required to solve this problem is introduced. A parallelization algorithm based on this parameterization and Gray coding which further reduces computational time is constructed.     

Confidence sets for discrete stochastic optimization

Consider the problem of finding the points of maximum of an expectation functional over a finite setS. Based on statistical estimates at each point ofS, confidence sets for theargmax-set are constructed which guarantee a prespecified probability of correct selection. We review known selection methods and propose a new two-stage procedure that works well for largeS and few global maxima. The performance is compared in a simulation study.     

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

Approximation and optimization of discrete and differential inclusions described by inequality constraints

In the first part of this article optimization of polyhedral discrete and differential inclusions is considered, the problem is reduced to convex minimization problem and the necessary and sufficient condition for optimality is derived. The optimality conditions for polyhedral differential inclusions based on discrete-approximation problem according to continuous problems are formulated. In particular, boundedness of the set of adjoint discrete solutions and upper semi-continuity of the locally adjoint mapping are proved. In the second part of this article an optimization problem described by convex inequality constraint is studied. By using the equivalence theorem concerning the subdifferential calculus and approximating method necessary and sufficient condition for discrete-approximation problem with inequality constraint is established.     

Using matrix approximation for high-dimensional discrete optimization problems: Server consolidation based on cyclic time-series data

We consider the assignment of enterprise applications in virtual machines to physical servers, also known as server consolidation problem. Data center operators try to minimize the number of servers, but at the same time provide sufficient computing resources at each point in time. While historical workload data would allow for accurate workload forecasting and optimal allocation of enterprise applications to servers, the volume of data and the large number of resulting capacity constraints in a mathematical problem formulation renders this task impossible for any but small instances. We use singular value decomposition (SVD) to extract significant features from a large constraint matrix and provide a new geometric interpretation of these features, which allows for allocating large sets of applications efficiently to physical servers with this new formulation. While SVD is typically applied for purposes such as time series decomposition, noise filtering, or clustering, in this paper features are used to transform the original allocation problem into a low-dimensional integer program with only the extracted features in a much smaller constraint matrix. We evaluate the approach using workload data from a large data center and show that it leads to high solution quality, but at the same time allows for solving considerably larger problem instances than what would be possible without data reduction and model transform. The overall approach could also be applied to similar packing problems in service operations management.     

Unique discrete harmonic continuation and data completion problems using the fading regularization method

A data completion method is proposed for solving Cauchy problems for which the number of data is less than the number of unknowns. This method is presented on the Cauchy problem for the Laplace equation in 2D situations. The idea is to search the solution in a space of discrete harmonic functions for which the existence and the uniqueness of a discrete harmonic continuation are guaranteed. Many numerical simulations using the finite element method highlight the efficiency, accuracy, and stability of this method even when data are noisy.     

Portfolio optimization with early announced discrete dividends

In this article we include discrete dividends in the stock price model and solve the corresponding generalized portfolio optimization problem. For this, we develop a new discrete dividend model that allows for the possibility of early announcement and ensures that the drop of the stock price at the ex-dividend date equals the dividend. The resulting portfolio problem can be solved explicitly for both the wealth and the trading strategy. We find that the resulting optimal portfolio process differs from the Merton strategy.     

Distributionally robust discrete optimization with Entropic Value-at-Risk

We study the discrete optimization problem under the distributionally robust framework. We optimize the Entropic Value-at-Risk, which is a coherent risk measure and is also known as Bernstein approximation for the chance constraint. We propose an efficient approximation algorithm to resolve the problem via solving a sequence of nominal problems. The computational results show that the number of nominal problems required to be solved is small under various distributional information sets.