Solving L 1-CTA in 3D tables by an interior-point method for primal block-angular problems

The purpose of the field of statistical disclosure control is to avoid that confidential information could be derived from statistical data released by, mainly, national statistical agencies. Controlled tabular adjustment (CTA) is an emerging technique for the protection of statistical tabular data. Given a table with sensitive information, CTA looks for the closest safe table. In this work we focus on CTA for three-dimensional tables using the L ₁ norm for the distance between the original and protected tables. Three L ₁-CTA models are presented, giving rise to six different primal block-angular structures of the constraint matrices. The resulting linear programming problems are solved by a specialized interior-point algorithm for this constraints structure which solves the normal equations by a combination of Cholesky factorization and preconditioned conjugate gradients (PCG). In the past this algorithm was shown to be one of the most efficient approaches for some classes of block-angular problems. The effect of quadratic regularizations is also analyzed, showing that for three of the six primal block-angular structures the performance of PCG is guaranteed to improve. Computational results are reported for a set of large instances, which provide linear optimization problems of up to 50 million variables and 25 million constraints. The specialized interior-point algorithm is compared with the state-of-the-art barrier solver of the CPLEX 12.1 package, showing to be a more efficient choice for very large L ₁-CTA instances.     

Minimum-distance controlled perturbation methods for large-scale tabular data protection

National Statistical Agencies routinely release large amounts of tabular information. Prior to dissemination, tabular data needs to be processed to avoid the disclosure of individual confidential information. One widely used class of methods is based on the modification of the table cells values. However, previous approaches were not able to preserve the values of the marginal cells and the additivity relations for a general table of any dimension, size and structure. This void was recently filled by the controlled tabular adjustment and one of its variants, the quadratic minimum-distance controlled perturbation method. Although independently developed, both approaches rely on the same strategy: given a set of tables to be protected, they find the minimum-distance values to the original cells that make the released information safe. Controlled tabular adjustment uses the L₁ distance; the quadratic minimum-distance variant considers L₂. This work presents both approaches within an unified framework, and includes a new variant based on L_∞. Among other benefits, the unified framework permits the simple comparison of the three distances, and a single general result about their disclosure risk. The three distances are evaluated with the unique standard library for tabular data protection currently available. Some of the complex instances were contributed by National Statistical Agencies, and, therefore, are good representatives of theirs real needs. Unlike alternative methods, the three distances were able to solve all the instances, requiring only few seconds for each of them on a personal computer using a general purpose solver. The results show that this class of methods are an effective and promising tool for the protection of large volumes of tabular data. All the linear and quadratic problems solved in the paper are delivered to the optimization community in MPS format.     

A piecewise linearization framework for retail shelf space management models

Managing shelf space is critical for retailers to attract customers and optimize profits. This article develops a shelf-space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. A piecewise linearization technique is used to approximate the complicated nonlinear space-allocation model. The approximation reformulates the non-convex optimization problem into a linear mixed integer programming (MIP) problem. The MIP solution not only generates near-optimal solutions for large scale optimization problems, but also provides an error bound to evaluate the solution quality. Consequently, the proposed approach can solve single category-shelf space management problems with as many products as are typically encountered in practice and with more complicated cost and profit structures than currently possible by existing methods. Numerical experiments show the competitive accuracy of the proposed method compared with the mixed integer nonlinear programming shelf-space model. Several extensions of the main model are discussed to illustrate the flexibility of the proposed methodology.     

Integrated exact,hybrid and metaheuristic learning methods for confidentiality protection

A vital task facing government agencies and commercial organizations that report data is to represent the data in a meaningful way and simultaneously to protect the confidentiality of critical components of this data. The challenge is to organize and disseminate data in a form that prevents such critical components from being inferred by groups bent on corporate espionage, to gain competitive advantages, or having a desire to penetrate the security of the information underlying the data. Controlled tabular adjustment is a recently developed approach for protecting sensitive information by imposing a special form of statistical disclosure limitation on tabular data. The underlying model gives rise to a mixed integer linear programming problem involving both continuous and discrete (zero-one) variables. We develop stratified ordered (s-ordered) heuristics and a new meta-heuristic learning approach for solving this model, and compare their performance to previous heuristics and to an exact algorithm embodied in the state-of-the-art ILOG- CPLEX software. Our new approaches are based on partitioning the problem into its discrete and continuous components, first creating an s-ordered heuristic that reduces the number of binary variables through a grouping procedure that combines an exact mathematical programming model with constructive heuristics. To gain further advantages we then replace the mathematical programming model with an evolutionary scatter search approach that makes it possible to extend the method to large problems with over 9000 entries. Finally, we introduce a new metaheuristic learning method that significantly improves the quality of solutions obtained.     

Quadratic interior-point methods in statistical disclosure control

The safe dissemination of statistical tabular data is one of the main concerns of National Statistical Institutes (NSIs). Although each cell of the tables is made up of the aggregated information of several individuals, the statistical confidentiality can be violated. NSIs must guarantee that no individual information can be derived from the released tables. One widely used type of methods to reduce the disclosure risk is based on the perturbation of the cell values. We consider a new controlled perturbation method which, given a set of tables to be protected, finds the closest safe ones - thus reducing the information loss while preserving confidentiality. This approach means solving a quadratic optimization problem with a much larger number of variables than constraints. Real instances can provide problems with millions of variables. We show that interior-point methods are an effective choice for that model, and, also, that specialized algorithms which exploit the problem structure can be faster than state-of-the art general solvers. Computational results are presented for instances of up to 1000000 variables.AMS Subject Classification: 90C06, 90C20, 90C51, 90C90Jordi Castro: Partially supported by the EU IST-2000-25069 CASC project and by the Spanish MCyT project TIC2003-00997.     

Clique inference process for solving Max-CSP

Few works on problems CSP, Max-CSP and weighted CSP was carried out in the field of Combinatorial Optimization, whereas this field contains many algorithmic tools which can be used for the resolution of these problems.In this paper, we introduce the binary clique concept: clique which expresses incompatibilities between values of two CSP variables. We propose a linear formulation for any binary clique and we present several ways to exploit it in order to compute lower bounds or to solve Max-CSP. We also show that the binary clique concept can be exploited in the weighted CSP framework.The obtained theoretical and experimental results are very interesting and they open new prospects to exploit the Combinatorial Optimization algorithmic tools for the resolution of CSP, Max-CSP and weighted CSP.     

Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization

This is an overview of the significance and main uses of projection, lifting and extended formulation in integer and combinatorial optimization. Its first two sections deal with those basic properties of projection that make it such an effective and useful bridge between problem formulations in different spaces, i.e. different sets of variables. They discuss topics like projection and restriction, the integrality-preserving property of projection, the dimension of projected polyhedra, conditions for facets of a polyhedron to project into facets of its projections, and so on. The next two sections describe the use of projection for comparing the strength of different formulations of the same problem, and for proving the integrality of polyhedra by using extended formulations or lifting. Section 5 deals with disjunctive programming, or optimization over unions of polyhedra, whose most important incarnation are mixed 0-1 programs and their partial relaxations. It discusses the compact representation of the convex hull of a union of polyhedra through extended formulation, the connection between the projection of the latter and the polar of the convex hull, as well as the sequential convexification of facial disjunctive programs, among them mixed 0-1 programs, with the related concept of disjunctive rank. Section 6 reviews lift-and-project cuts, the construction of cut generating linear programs, and techniques for lifting and for strengthening disjunctive cuts. Section 7 discusses the recently discovered possibility of solving the higher dimensional cut generating linear program without explicitly constructing it, by a sequence of properly chosen pivots in the simplex tableau of the linear programming relaxation. Finally, section 8 deals with different ways of combining cuts with branch and bound, and briefly discusses computational experience with lift-and-project cuts. This is an updated and extended version of the paper published in LNCS 2241, Springer, 2001 (as given in Balas, 2001). Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

Zur kepplimg eines exakten verfahrens mit einem heuristiscieb verfahren für die lösung ganzzahliger linearer optimierungsprobleme

Combining an exact method with a heuristic approach possibilities for solving linear mixed integer optimization problems are investigated. For the considered exact method numerical results with problems from the practice are given. Proper heuristic methods are the interior path methods [2] for which numerical experiences are well-known or the so-called geometric approach [8], Deriving of sufficient conditions for the existence of feasible solutions is possible.     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

A three-phase algorithm for the cell suppression problem in two-dimensional statistical tables

To obtain full cooperation from respondents, statistical offices must guarantee that confidential data will not be disclosed when their reports are published. For tabular data, cell suppression is one of the preferred techniques to control statistical disclosure. When suppressing only confidential values does not guarantee the desired data protection, it is also necessary to suppress the values in some non-confidential cells. The problem of finding an optimal set of complementary suppressions—the cell suppression problem (CSP)—is NP-hard. We present a three-phase algorithm for the CSP based on a binary relaxation derived from row and column protection conditions. To enforce violated single cell conditions, integer cuts are added to the CSP relaxation. The numerical results obtained in 1410 instances with up to more than 250?000 cells, which were generated to reproduce two classes of real-world data, indicate that the algorithm is quite effective for both classes of instances and that it outperforms state-of-the-art algorithms for one of them.     

Quadratic convex reformulations for quadratic 0–1 programming

This is a summary of the author’s PhD thesis supervised by A. Billionnet and S. Elloumi and defended on November 2006 at the CNAM, Paris (Conservatoire National des Arts et Métiers). The thesis is written in French and is available from http://www.cedric.cnam.fr/PUBLIS/RC1115. This work deals with exact solution methods based on reformulations for quadratic 0–1 programs under linear constraints. These problems are generally not convex; more precisely, the associated continuous relaxation is not a convex problem. We developed approaches with the aim of making the initial problem convex and of obtaining a good lower bound by continuous relaxation. The main contribution is a general method (called QCR) that we implemented and applied to classical combinatorial optimization problems.      

The capacitated multiple allocation hub location problem: Formulations and algorithms

In this paper we consider and present formulations and solution approaches for the capacitated multiple allocation hub location problem. We present a new mixed integer linear programming formulation for the problem. We also construct an efficient heuristic algorithm, using shortest paths. We incorporate the upper bound obtained from this heuristic in a linear-programming-based branch-and-bound solution procedure. We present the results of extensive computational experience with both the heuristic and the exact methods.     

Efficient decomposition and linearization methods for the stochastic transportation problem

The stochastic transportation problem can be formulated as a convex transportation problem with nonlinear objective function and linear constraints. We compare several different methods based on decomposition techniques and linearization techniques for this problem, trying to find the most efficient method or combination of methods. We discuss and test a separable programming approach, the Frank-Wolfe method with and without modifications, the new technique of mean value cross decomposition and the more well known Lagrangean relaxation with subgradient optimization, as well as combinations of these approaches. Computational tests are presented, indicating that some new combination methods are quite efficient for large scale problems.     

Valuating residential real estate using parametric programming

When the estimation of the single equation multiple linear regression model is looked upon as an optimization problem, we show how the principles and methods of optimization can assist the analyst in finding an attractive prediction model. We illustrate this with the estimation of a linear prediction model for valuating residential property using regression quantiles. We make use of the linear parametric programming formulation to obtain the family of regression quantile models associated with a data set. We use the principle of dominance to reduce the number of models for consideration in the search for the most preferred property valuation model (s). We also provide useful displays that assist the analyst and the decision maker in selecting the final model (s). The approach is an interface between data analysis and operations research.     

Application of lower bound direct method to engineering structures

Direct methods provide elegant and efficient approaches for the prediction of the long-term behaviour of engineering structures under arbitrary complex loading independent of the number of loading cycles. The lower bound direct method leads to a constrained non-linear convex problem in conjunction with finite element methods, which necessitates a very large number of optimization variables and a large amount of computer memory. To solve this large-scale optimization problem, we first reformulate it in a simpler equivalent convex program with easily exploitable sparsity structure. The interior point with DC regularization algorithm (IPDCA) using quasi definite matrix techniques is then used for its solution. The numerical results obtained by this algorithm will be compared with those obtained by general standard code Lancelot. They show the robustness, the efficiency of IPDCA and in particular its great superiority with respect to Lancelot.     

Pessimistic,optimistic, and minimax regret approaches for linear programs under uncertainty

Uncertain data appearing as parameters in linear programs can be categorized variously. This paper deals with merely probability, belief (necessity), plausibility (possibility), and random set information of uncertainties. However, most theoretical approaches and models limit themselves to the analysis involving merely one kind of uncertainty within a problem. Moreover, none of the approaches concerns itself with the fact that random set, belief (necessity), and plausibility (possibility) convey the same information. This paper presents comprehensive methods for handling linear programs with mixed uncertainties which also preserve all details about uncertain data. We handle mixed uncertainties as sets of probabilities which lead to optimistic, pessimistic, and minimax regret in optimization criteria.     

Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithms

The dual simplex algorithm has become a strong contender in solving large scale LP problems. One key problem of any dual simplex algorithm is to obtain a dual feasible basis as a starting point. We give an overview of methods which have been proposed in the literature and present new stable and efficient ways to combine them within a state-of-the-art optimization system for solving real world linear and mixed integer programs. Furthermore, we address implementation aspects and the connection between dual feasibility and LP-preprocessing. Computational results are given for a large set of large scale LP problems, which show our dual simplex implementation to be superior to the best existing research and open-source codes and competitive to the leading commercial code on many of our most difficult problem instances.     

Cone contraction and reference point methods for multi-criteria mixed integer optimization

Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).     

Simple solution methods for separable mixed linear and quadratic knapsack problem

Quadratic knapsack problem has a central role in integer and nonlinear optimization, which has been intensively studied due to its immediate applications in many fields and theoretical reasons. Although quadratic knapsack problem can be solved using traditional nonlinear optimization methods, specialized algorithms are much faster and more reliable than the nonlinear programming solvers. In this paper, we study a mixed linear and quadratic knapsack with a convex separable objective function subject to a single linear constraint and box constraints. We investigate the structural properties of the studied problem, and develop a simple method for solving the continuous version of the problem based on bi-section search, and then we present heuristics for solving the integer version of the problem. Numerical experiments are conducted to show the effectiveness of the proposed solution methods by comparing our methods with some state of the art linear and quadratic convex solvers.     

Solving non-linear portfolio optimization problems with the primal-dual interior point method

Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear or quadratic models due to the inability of currently available solvers to solve NLP problems of typical sizes. However stochastic programming problems are highly structured. The key to the efficient solution of such problems is therefore the ability to exploit their structure. Interior point methods are well-suited to the solution of very large non-linear optimization problems. In this paper we exploit this feature and show how portfolio optimization problems with sizes measured in millions of constraints and decision variables, featuring constraints on semi-variance, skewness or non-linear utility functions in the objective, can be solved with the state-of-the-art solver.