Search

The field of statistical disclosure control aims to reduce the risk of re-identifying an individual from disseminated data, a major concern among national statistical agencies. Operations Research (OR) techniques have been widely used in the past for protecting tabular data, but not microdata (i.e., files of individuals and attributes). Few papers apply OR techniques to the microaggregation problem, which is considered one of the best methods for microdata protection and is known to be NP-hard. The new heuristic approach is based on a column generation scheme and, unlike previous (primal) heuristics for microaggregation, it also provides a lower bound on the optimal microaggregation. Using real data that is typically used in the literature, our computational results show, first, that solutions with small gaps are often achieved and, second, that dramatic improvements are obtained relative to the literature’s most popular heuristics. Author Enric Spagnolo-Arrizabalaga was supported by the ERASMUS+ Traineeship Program with a visiting period at CNR-IASI. Author Claudio Gentile was partly supported by the project PRIN 2015B5F27W funded by the Italian Ministry for Education, University, and Research; by the ITN 764759 “MINOA: Mixed-Integer Nonlinear Optimization Applications” of the European Union; and by the CNR Short-Term Mobility program CNRSTM14-PROT26328. Authors Jordi Castro and Claudio Gentile were supported by the MCIU/AEI/FEDER RTI2018-097580-B-I00 project of the Spanish Ministry of Science, Innovation and Universities.

In (Bacci et al. New MINLP formulations for the single-unit commitment problems with ramping constraints, 2019) the first MIP exact formulation was provided that describes the convex hull of the solutions satisfying all the standard operational constraints for the thermal units: minimum up- and down-time, minimum and maximum power output, ramp (including start-up and shut-down) limits, general history-dependent start-up costs, and nonlinear convex power production costs. That formulation contains a polynomial, but large, number of variables and constraints. We present two new formulations with fewer variables defined on the shut-down period and computationally test the trade-off between reduced size and possibly weaker bounds.

The paper reports on some preliminary results obtained by using polynomial time algorithms to solve max-cut on some special graphs within a heuristic scheme known as subgraph sampling. Computational results are reported on toroidal graphs of about 100 000 nodes with edge weights generated from both a Gaussian and a bivariate uniform distribution.

The authors investigate the application of deep convolutional neural networks (CNNs) to the problem of radiometric identification, i.e. the task of authenticating wireless devices on the basis of their radio frequency (RF) emissions, which contain features directly related to the physical properties of the wireless devices. They collected digitised RF from 12 wireless devices, and used various techniques to transform the time series derived from the RF to images. A deep CNN is then applied to the images. The authors' results show that the identification performance of the combination of deep CNN with an image representation significantly outperforms conventional methods based on dissimilarity on the original time series. Moreover, a specific comparison among RF-to-image techniques show that on their datasets the wavelet-based approach outperforms other approaches, also in the presence of white Gaussian noise.

Recently, Guan, Pan, and Zohu presented a MIP model for the thermal single-unit commitment claiming that provides an integer feasible solution for any convex cost function. In this note we provide a counterexample to this statement and we produce evindence that the perspective function is needed for this aim.

The ability to identify mobile phones through their built-in components has been demonstrated in the literature for various types of sensors including charge coupled devices (CCD)/complementary metal–oxide semiconductors (CMOS), accelerometers, magnetometers, and microphones. The identification is performed by exploiting small but significant differences in the electronic circuits generated during the manufacturing process. Thus, these distinctive traces become an intrinsic property of the electronic components, which can be detected and exploited as a unique fingerprints associated with the mobile phone. Such fingerprints can be used in various scenarios, especially in security and forensics related applications. In this article, the identification of mobile phones through their built-in microphone by means of convolutional neural networks (CNNs) is investigated. In this specific context, CNNs have received very limited attention by the research community so far. An experimental dataset is created by collecting microphone responses from 34 different mobile phones. These responses are then used to perform classification through CNNs. On different experiments, the proposed CNN is able to provide encouraging results; in particular, the achieved identification accuracy of CNNs is superior to the one obtained with more conventional machine learning algorithms like the K -nearest neighbor and support vector machine, also in the presence of additive white Gaussian noise.

We study the problem of decomposing the Hessian matrix of a mixed integer convex quadratic program (MICQP) into the sum of positive semidefinite 2 × 2 matrices. Solving this problem enables the use of perspective reformulation techniques for obtaining strong lower bounds for MICQPs with semicontinuous variables but a nonseparable objective function. An explicit formula is derived for constructing 2 × 2 decompositions when the underlying matrix is weakly scaled diagonally dominant, and necessary and sufficient conditions are given for the decomposition to be unique. For matrices lying outside this class, two exact semidefinite programming approaches and an efficient heuristic are developed for finding approximate decompositions. We present preliminary results on the bound strength of a 2 × 2 perspective reformulation for the portfolio optimization problem, showing that, for some classes of instances, the use of 2 × 2 matrices can significantly improve the quality of the bound with respect to the best previously known approach, although at a possibly high computational cost.

The sequential convex MINLP (SC-MINLP) technique is a solution method for nonconvex mixed-integer nonlinear problems (MINLPs) where the nonconvexities are separable. It is based on solving a sequence of convex MINLPs which trade a better and better relaxation of the nonconvex part of the problem with the introduction of more and more piecewise-linear nonconvex terms, and therefore binary variables. The convex MINLPs are obtained by partitioning the domain of each separable nonconvex term in the intervals in which it is convex and those in which it is concave. In the former, the term is left in its original form, while in the latter it is piecewise-linearized. Since each interval corresponds to a semi-continuous variable, we propose to modify the convex terms using the Perspective Reformulation technique to strengthen the bounds. We show by means of experimental results on different classes of instances that doing so significantly decreases the solution time of the convex MINLPs, which is the most time consuming part of the approach, and has therefore the potential to improving the overall effectiveness of SC-MINLP.

The Unit Commitment (UC) problem in electrical power production requires to optimally operate a set of power generation units over a short time horizon (one day to a week). Operational constraints of each unit depend on its type (e.g., thermal, hydro, nuclear, \ldots), and can be rather complex; typical ones concern minimum and maximum power output, minimum up- and down-time, start-up and shut-down limits, ramp-up and ramp-down limits. Also, the objective function is often nonlinear. Thus, even the Single-Unit Commitment (1UC) problem, in which only one unit is present, has a rich combinatorial structure. In this work we present the first MINLP formulation that describes the convex hull of the feasible solutions of (1UC) comprising all the above constraints, and Second-Order Cone representable power generation costs. The new formulation has a polynomial number of both variables and constraints, and it is based on the efficient Dynamic Programming algorithm proposed in~\cite{FG06} together with the \emph{perspective reformulation} technique proposed in~\cite{FG06a}. We then analyze the effect of using it to develop tight formulations for the more general (UC). Since the formulation, despite being polynomial-size, is rather large, we also propose two new formulations, based on partial aggregations of variables, with different trade-offs between quality of the obtained bound and cost of the solving the corresponding continuous relaxation. Our results show that navigating these trade-offs may lead to improved performances for the partial enumeration approach used to solve the problem.

The Sequential Convex MINLP (SC-MINLP) technique is a global optimization algorithm aimed at solving NonConvex Mixed-Integer NonLinear Problems with separable nonconvexities. At each iteration, it provides a lower and an upper bound by solving a Convex MINLP and a NonConvex NLP, respectively. The convex MINLPs are iteratively improved by adding breakpoints to the linearization of the concave parts of the problem. We propose to strengthen the convex MINLPs by exploiting its structure and modifying the convex terms using the Perspective Reformulation technique to strengthen the bounds. Experimental results on different classes of instances show a significant decrease of the solution time of the Convex MINLPs, i.e., the most time-consuming part of SC-MINLP, and has, therefore the potential to improving its overall effectiveness.

In this work we address, from a user perspective, the problem to define optimal itineraries for visiting scheduled events in an urban environment. The problem is modeled as an orienteering problem with time windows. Real-case instances are difficult to solve by means of commercial solvers. We propose a matheuristic approach which is compared against the exact solver by using a real-case instance derived by a big Italian furniture fair. Test results show clear effectiveness of the proposed approach.

Intelligent mobility entails the integration of key enabling technologies, such as sensor networks and data mining with innovative organization models and decision support systems. In these settings, we study an application of intelligent mobility for supporting the visit of organized events. In the analyzed scenario users plan visits of events "maximizing" their utility defined according their preferences. The aim of the proposed solution approach is to develop a tool able to be responsive and to provide near-optimal solutions in short time.

International audience; The alternating current optimal power flow problem is a fundamental problem in the management of smart grids. In this paper we consider a variant which includes activation/deactivation of generators at some of the grid sites. We formulate the problem as a mathematical program, prove its NP-hardness w.r.t. ac-tivation/deactivation, and derive two perspective reformulations.

Public use of microdata files requires preprocessing to protect privacy. Microaggre- gation consists in aggregating data into clusters of size at least k such that the spread between individuals' and centroid cluster values is minimized. This paper proposes an algorithm based on Column Generation to compute lower bounds on the spread.

The Sequential Convex MINLP (SC-MINLP) technique is a solution method for NonConvex Mixed-Integer NonLinear Problems where the nonconvexities are separable. It is based on solving a sequence of Convex MINLPs which trade a better and better relaxation of the nonlinear nonconvex part of the problem with the introduction of more and more piecewise-linear nonconvex terms, and therefore binary variables. The Convex MINLPs are obtained by separately considering each separable nonconvex term in the intervals in which it is convex and those in which it is concave, where the former are left in their original form while the latter are piecewise-linearized. Because each interval corresponds to a semi-continuous variable, we rather propose to modify the convex terms using the Perspective Reformulation technique to strengthen the bounds. We show by means of experimental results on different classes of instances that doing so significantly decreases the solution time of the Convex MINLPs, which is the most time consuming part of the approach, and has therefore the potential to improving the overall effectiveness of SC-MINLP.

We propose an improvement of the Approximated Projected Perspective Reformulation (AP 2 R) for dealing with constraints linking the binary variables. The new approach solves the Perspective Reformulation (PR) once, and then use the corresponding dual information to reformulate the problem prior to applying AP 2 R, thereby combining the root bound quality of the PR with the reduced relaxation computing time of AP 2 R. Computational results for the cardinality-constrained Mean–Variance portfolio optimization problem show that the new approach is competitive with state-of-the-art ones.

The problem of finding a complete linear description of the stable set polytope of claw-free graphs has been a major topic in combinatorial optimization in the last decades and it is still not completely solved. While it is known that this linear description contains facet defining inequalities with arbitrarily many and arbitrarily high coefficients, the set of claw-free graphs whose stable set polytope is described only by inequalities with { 0 , 1 , 2 } -valued coefficients is considerably large. In fact Galluccio et?al. (2014) proved that this set contains almost all claw-free graphs with stability number greater than three plus some of the building blocks with stability number smaller than or equal to three, identified by Chudnovsky and Seymour in their Structure Theorem.Here we show that another important class of claw-free graphs with stability number three belongs to this set: the class of icosahedral graphs, named S 1 by Chudnovsky and Seymour (2008). In particular, we prove that the stable set polytope of icosahedral graphs is described by: rank, lifted 5-wheel and lifted wedge inequalities, and all these linear inequalities have coefficients in { 0 , 1 , 2 } .

In this work we focus on methods for solving mixed integer non linear programming problems with separable non convexities. In particular, we propose a strengthening of a convex mixed integer non linear programming relaxation based on perspective reformulations. The relaxation is a subproblem of an iterative global optimization algorithm and it is solved at each iteration. Computational results confirm that the perspective reformulation outperforms the standard solution approaches.

We study the problem of (approximately) decomposing the hessian matrix of a Mixed-Integer Convex Quadratic Program with semicontinuous variables as the sum of positive semidefinite 2x2 matrices. Solving this problem can enable the use of Perspective Reformulation techniques for obtaining strong lower bounds for the MICQP. We discuss two exact SDP approaches for finding an approximate decomposition, we characterize the set of matrices that have an exact decomposition, and we use the characterization to devise efficient heuristics for obtaining 2x2 decompositions. We present preliminary results on the bound strength for Portfolio Optimization problems, showing that for some classes of problems the use of 2x2 matrices can significantly improve the quality of the bound w.r.t.~the best previously known approach, although at a possibly high computational cost.

Any institution that disseminates data in aggregated form has the duty to ensure that individual confidential information is not disclosed, either by not releasing data or by perturbing the released data while maintaining data utility. Controlled tabular adjustment (CTA) is a promising technique of the second type where a protected table that is close to the original one in some chosen distance is constructed. The choice of the specific distance shows a trade-off: although the Euclidean distance has been shown (and is confirmed here) to produce tables with greater “utility,” it gives rise to mixed integer quadratic problems (MIQPs) with pairs of linked semi-continuous variables that are more difficult to solve than the mixed integer linear problems corresponding to linear norms. We provide a novel analysis of perspective reformulations (PRs) for this special structure; in particular, we devise a projected PR (P2R), which is piecewise-conic but simplifies to a (nonseparable) MIQP when the instance is symmetric. We then compare different formulations of the CTA problem, showing that the ones based on P2R most often obtain better computational results.

The short-term Unit Commitment (UC) problem in hydro-thermal power generation is a fundamental problem in short-term electrical generation scheduling. Historically, Lagrangian techniques have been used to tackle this large-scale, difficult Mixed-Integer NonLinear Program (MINLP); this requires being able to efficiently solve the Lagrangian subproblems, which has only recently become possible (efficiently enough) for units subject to significant ramp constraints. In the last years, alternative approaches have been devised where the nonlinearities in the problem are approximated by means of piecewise-linear functions, so that UC can be approximated by a Mixed-Integer Linear Program (MILP); in particular, using a recently developed class of \emph{valid inequalities} for the problem, called ``Perspective Cuts'', significant improvements have been obtained in the efficiency and effectiveness of the solution algorithms. These two different approaches have complementary strengths; Lagrangian ones provide very good lower bounds quickly, but they require sophisticated heuristics---which may need to be changed every time that the mathematical model changes---for producing actual feasible solutions. MILP approaches have been shown to be able to provide very good feasible solutions quickly, but their lower bound is significantly worse. We present a sequential approach which combines the two methods, trying to exploit each one's strengths; we show, by means of extensive computational experiments on realistic instances, that the sequential approach may exhibit significantly better efficiency than either of the two basic ones, depending on the degree of accuracy requested to the feasible solutions.

The Perspective Reformulation is a general approach for constructing tight approximations to MINLP problems with semicontinuous variables. Two different reformulations have been proposed for solving it, one resulting in a Second-Order Cone Program, the other based on representing the perspective function by (an infinite number of) cutting planes. We compare the two reformulations on two sets of MIQPs to determine which one is most effective in the context of exact or approximate Branch-and-Cut algorithms.

Lagrangian relaxation (LR) algorithms are among the most successful approaches for solving large-scale hydro-thermal unit commitment (UC) problems; this is largely due to the fact that the single-unit commitment (1UC) problems resulting from the decomposition, incorporating many kinds of technical constraints such as minimum up- and down-time requirements and time-dependent startup costs, can be efficiently solved by dynamic programming (DP) techniques. Ramp constraints have historically eluded efficient exact DP approaches; however, this has recently changed [Frangioni A, Gentile C. Solving nonlinear single-unit commitment problems with ramping constraints. Oper Res 2006;54(4):767–75]. We show that the newly proposed DP algorithm for ramp-constrained (1UC) problems allows to extend existing LR approaches to ramp-constrained (UC); this is not obvious since the heuristic procedures typically used to recover a primal feasible solution are not easily extended to take ramp limits into account. However, dealing with ramp constraints in the subproblems turns out to be sufficient to provide the LR heuristic enough guidance to produce good feasible solutions even with no other modification of the approach; this is due to the fact that (sophisticated) LR algorithms to (UC) duly exploit the primal information computed by the Lagrangian Dual, which in the proposed approach is ramp feasible. We also show by computational experiments that the LR [approach] is competitive with those based on general-purpose mixed-integer program (MIP) solvers for large-scale instances, especially hydro-thermal ones.

We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of$STAB(G) when G is claw-free.

Support-graph preconditioners have been shown to be a valuable tool for the iterative solution, via a Preconditioned Conjugate Gradient method, of the KKT systems that must be solved at each iteration of an Interior Point algorithm for the solution of Min Cost Flow problems. These preconditioners extract a proper triangulated subgraph, with ``large'' weight, of the original graph: in practice, trees and Brother-Connected Trees (BCTs) of depth two have been shown to be the most computationally efficient families of subgraphs. In the literature, approximate versions of the Kruskal algorithm for maximum-weight spanning trees have most often been used for choosing the subgraphs; Prim-based approaches have been used for trees, but no comparison have ever been reported. We propose Prim-based heuristics for BCTs, which require nontrivial modifications w.r.t. the previously proposed Kruskal-based approaches, and present a computational comparison of the different approaches, which shows that Prim-based heuristics are most often preferable to Kruskal-based ones.

We present a new approach, requiring the solution of a SemiDefinite Program, for decomposing the Hessian of a nonseparable mixed-integer quadratic problem to permit using perspective cuts to improve its continuous relaxation bound. The new method favorably compares with a previously proposed one requiring a minimum eigenvalue computation.

Interior point (IP) algorithms for Min Cost Flow (MCF) problems have been shown to be competitive with combinatorial approaches, at least on some problem classes and for very large instances. This is in part due to availability of specialized crossover routines for MCF; these allow early termination of the IP approach, sparing it with the final iterations where the Karush Kuhn-Tucker (KKT) systems become more difficult to solve. As the crossover procedures are nothing but combinatorial approaches to MCF that are only allowed to perform few iterations, the IP algorithm can be seen as a complex 'multiple crash start' routine for the combinatorial ones. We report our experiments of allowing one primal-dual combinatorial algorithm to MCF to perform as many iterations as required to solve the problem after being warm-started by an IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the original combinatorial algorithm, at least on some 'difficult' instances.

We show that the convex envelope of the objective function of Mixed-Integer Programming problems with a specific structure is the perspective function of the continuous part of the objective function. Using a characterization of the subdifferential of the perspective function, we derive ``perspective cuts'', a family of valid inequalities for the problem. Perspective cuts can be shown to belong to the general family of disjunctive cuts, but they do not require the solution of a potentially costly nonlinear programming problem to be separated. Using perspective cuts substantially improves the performance of Branch \& Cut approaches for at least two models that, either ``naturally'' or after a proper reformulation, have the required structure: the Unit Commitment problem in electrical power production and the Mean-Variance problem in portfolio optimization.

Working in the framework of PAC-learning theory, we present special statistics for accomplishing in polynomial time proper learning of DNF boolean formulas having a fixed number of monomials. Our statistics turn out to be near sufficient for a large family of distribution laws – that we call butterfly distributions. We develop a theory of most powerful learning for analyzing the performance of learning algorithms, with particular reference to trade-offs between power and computational costs. Focusing attention on sample and time complexity, we prove that our algorithm works as efficiently as the best algorithms existing in the literature – while the latter only take care of subclasses of our family of distributions.

We study on-line learning in the linear regression framework. Most of the performance bounds for on-line algorithms in this framework assume a constant learning rate. To achieve these bounds the learning rate must be optimized based on a posteriori information. This information depends on the whole sequence of examples and thus it is not available to any strictly on-line algorithm. We introduce new techniques for adaptively tuning the learning rate as the data sequence is progressively revealed. Our techniques allow us to prove essentially the same bounds as if we knew the optimal learning rate in advance. Moreover, such techniques apply to a wide class of on-line algorithms, including p -norm algorithms for generalized linear regression and Weighted Majority for linear regression with absolute loss. Our adaptive tunings are radically different from previous techniques, such as the so-called doubling trick. Whereas the doubling trick restarts the on-line algorithm several times using a constant learning rate for each run, our methods save information by changing the value of the learning rate very smoothly. In fact, for Weighted Majority over a finite set of experts our analysis provides a better leading constant than the doubling trick.

Motivated by a problem of targeted advertising in social networks, we introduce a new model of online learning on labeled graphs where the graph is initially unknown and the algorithm is free to choose which vertex to predict next. For this learning model, we define an appropriate measure of regularity of a graph labeling called the merging degree. In general, the merging degree of a graph is small when its vertices can be partitioned into a few well-separated clusters within which labels are roughly constant. For the special case of binary labeled graphs, the merging degree is a more refined measure than the cutsize. After observing that natural nonadaptive exploration/prediction strategies, like depth-first with majority vote, do not behave satisfactorily on graphs with small merging degree, we introduce an efficiently implementable adaptive strategy whose cumulative loss is controlled by the merging degree. A matching lower bound shows that in the case of binary labels our analysis cannot be improved.

Radio Frequency (RF) wireless devices can be identified by the RF emissions they produce when transmitting. The reason is that such emissions contain intrinsic features originating from the physical structure and the materials used to build the wireless device itself. These features are usually called RF fingerprints in the literature, and they can be used to uniquely identify a wireless device through a process called radiometric identification. RF fingerprinting can support multifactor authentication of wireless devices in security applications. One of the main unresolved issues in radiometric identification is the lack of portability of the RF fingerprints. The RF emissions are collected by a RF receiver converting them into digital format, from which the fingerprints are extracted. The lack of portability issue is due to the fact that each RF receiver introduces a bias, which degrades the RF fingerprints of the emitting device. As a consequence, RF emissions of the same wireless device collected by different RF receivers will generate different fingerprints for the same wireless device. This issue strongly limits the applicability of RF fingerprinting for security purposes, since we are not afforded to use different RF receivers to perform identification, and the fingerprints are not portable from one receiver to another. In this paper, we propose a novel approach that helps mitigating this portability issue. Our approach is based on the removal of the bias introduced by RF receivers in the frequency domain through the use of one golden reference. The golden reference is used to generate a calibration function, which is then applied to the RF emissions collected by different RF receivers from any other wireless device. The specific approach is empirically validated against a set of ten Internet of Things (IoT) wireless devices (plus the golden reference), and three RF receivers. Our experimental evidence demostrates that our method is able to alleviate the portability issue at the cost of a minor degradation in identification accuracy.

Radio Frequency (RF) fingerprinting is the problem of identifying and authenticating an electronic device through its radio frequency emissions. These emissions contain intrinsic features of the device itself. RF fingerprinting can be used to enhance the security of wireless networks since the fingerprints provide a form of authentication complementing other measures. RF-based authentication turns out to be of practical use in security applications as long as the RF fingerprinting delivers high identification and verification accuracy, and the whole process is computationally efficient. In this paper, we investigate a novel approach to RF fingerprinting based on the application to time series of the Symbolic Aggregate Approximation algorithm (SAX). This is a compression scheme known to be time efficient and, although it has been applied to many domains, it has so far never been investigated in the problem of RF fingerprinting. We demonstrate that a SAX-based approach provides a very high identification accuracy (over 99%), and turns out to be attractive, as compared to classification without SAX, from both a computational standpoint and its robustness to noise.

This paper provides the convex hull description for the basic operation of slow- and quick-start units in power-based unit commitment (UC) problems. The basic operating constraints that are modeled for both types of units are (1) generation limits and (2) minimum up and down times. Apart from this, the startup and shutdown processes are also modeled, using (3) startup and shutdown power trajectories for slow-start units, and (4) startup and shutdown capabilities for quick-start units. In the conventional UC problem, power schedules are used to represent the staircase energy schedule; however, this simplification leads to infeasible energy delivery, as stated in the literature. To overcome this drawback, this paper provides a power-based UC formulation drawing a clear distinction between power and energy. The proposed constraints can be used as the core of any power-based UC formulation, thus tightening the final mixed-integer programming UC problem. We provide evidence that dramatic improvements in computational time are obtained by solving different case studies, for self-UC and network-constrained UC problems.

submitted to COLT; We derive non-asymptotic confidence regions for the mean of a random vector whose coordinates have an unknown dependence structure. The random vector is supposed to be either Gaussian or to have a symmetric bounded distribution, and we observe $n$ i.i.d copies of it. The confidence regions are built using a data-dependent threshold based on a weighted bootstrap procedure. We consider two approaches, the first based on a concentration approach and the second on a direct boostrapped quantile approach. The first one allows to deal with a very large class of resampling weights while our results for the second are restricted to Rademacher weights. However, the second method seems more accurate in practice. Our results are motivated by multiple testing problems, and we show on simulations that our procedures are better than the Bonferroni procedure (union bound) as soon as the observed vector has sufficiently correlated coordinates.