We describe a learning procedure enhancing L1-penalized regression by adding dynamically generated rules describing multidimensional “box” sets. Our rule-adding procedure is based on the classical column generation method for high-dimensional linear programming. The pricing problem for our column generation procedure reduces to the NP-hard rectangular maximum agreement (RMA) problem of finding a box that best discriminates between two weighted datasets. We solve this problem exactly using a parallel branch-and-bound procedure. The resulting rule-enhanced regression procedure is computation-intensive, but has promising prediction performance.

Coherent risk measures have become a popular tool for incorporating risk aversion into stochastic optimization models. For dynamic models in which uncertainty is resolved at more than one stage, however, using coherent risk measures within a standard single-level optimization framework becomes problematic. To avoid severe time-consistency difficulties, the current state of the art is to employ risk measures of a specific nested form, which unfortunately have some undesirable and somewhat counterintuitive modeling properties. This paper summarizes the potential drawbacks of nested-form risk measure issues and then presents an alternative multilevel optimization modeling approach that enforces a form of time consistency through constraints rather than by restricting the modeler’s choice of objective function. This technique leads to models that are time consistent even while using time-inconsistent risk measures and can easily be formulated to be law invariant with respect to the final wealth if so desired. We argue that this approach should be the starting point for all multistage optimization modeling. When used with time-consistent objective functions, we show its multilevel optimization constraints become redundant, and the associated models thus simplify to a more familiar single-objective form. Unfortunately, we also show that our proposed approach leads to 𝒩𝒫-hard models, even in the simplest imaginable setting in which it would be needed: three-stage linear problems on a finite probability space, using the standard average value-at-risk and first-order mean-semideviation risk measures. Finally, we show that for a simple but reasonably realistic test application, the kind of models we propose, although drawn from an 𝒩𝒫-hard family and certainly more time consuming to solve than those obtained from the nested-objective approach, are readily solvable to global optimality using a standard commercial mixed-integer linear programming solver. Therefore, there seems some promise of our proposed modeling approach being useful despite its computational complexity properties.

The 𝒩𝒫-hard maximum monomial agreement problem consists of finding a single logical conjunction that is most consistent with or “best fits” a weighted data set of “positive” and “negative” binary vectors. Computing weighted voting classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved in practice by heuristic methods. Here, we describe an exact branch-and-bound method for maximum agreement over Boolean monomials, improving on the earlier work of Goldberg and Shan [Goldberg, N., C. Shan. 2007. Boosting optimal logical patterns. Proc. 7th SIAM Internat. Conf. Data Mining, SIAM, Philadelphia, 228–236]. Specifically, we develop a tighter upper bounding function and an improved branching procedure that exploits knowledge of the bound and the particular data set, while having a lower branching factor. Experimental results show that the new method is able to solve larger problem instances and runs faster within a linear programming boosting procedure applied to medium-sized data sets from the UCI Machine Learning Repository. The new algorithm also runs much faster than applying a commercial mixed-integer programming solver, which uses linear programming relaxation-based bounds, to an integer linear programming formulation of the problem.

We describe scheduling algorithms for monitoring a single information source whose contents change at times modeled by a nonhomogeneous Poisson process. In a given time period of length T, we enforce a server-side politeness constraint that we may only probe the source at most n times. This constraint, along with an optional constraint that no two probes may be spaced less than δ time units apart, is intended to prevent the monitor from being classified as a nuisance to be “locked out” of the information source. To develop our algorithms, we use a portion of the cost model developed in our earlier work. Our first algorithm assumes a discrete set of N > n possible update times, and uses dynamic programming to identify a provably optimal subset of n of these times at which to probe the server. Our second algorithm is a simple direct search for locally improving any continuous-time schedule with respect to the same cost model. In particular, this improvement procedure may be applied to the schedule obtained from our first algorithm. We evaluate our algorithms using real-world data feeds.

Recent trends in information management involve the periodic transcription of data onto secondary devices in a networked environment, and the proper scheduling of these transcriptions is critical for efficient data management. To assist in the scheduling process, we are interested in modeling data obsolescence , that is, the reduction of consistency over time between a relation and its replica. The modeling is based on techniques from the field of stochastic processes, and provides several stochastic models for content evolution in the base relations of a database, taking referential integrity constraints into account. These models are general enough to accommodate most of the common scenarios in databases, including batch insertions and lifespans both with and without memory. As an initial "proof of concept" of the applicability of our approach, we validate the insertion portion of our model framework via experiments with real data feeds. We also discuss a set of transcription protocols that make use of the proposed stochastic model.

This article applies splitting techniques developed for set-valued maximal monotone operators to monotone affine variational inequalities, including, as a special case, the classical linear complementarity problem. We give a unified presentation of several splitting algorithms for monotone operators, and then apply these results to obtain two classes of algorithms for affine variational inequalities. The second class resembles classical matrix splitting, but has a novel “under-relaxation” step, and converges under more general conditions. In particular, the convergence proofs do not require the affine operator to be symmetric. We specialize our matrix-splitting-like method to discrete-time optimal control problems formulated as extended linear-quadratic programs in the manner advocated by Rockafellar and Wets. The result is a highly parallel algorithm, which we implement and test on the Connection Machine CM-5 computer family.

Consider the classical branch and bound algorithm for mixed integer programming (MIP). Parallel implementations of this method are known to be viable and reasonably scalable on systems with sophisticated, high-performance interprocessor communication capabilities. But how parallel can the algorithm be when communication is more rudimentary? This article attempts to address this question by comparing two different implementations of MIP branch and bound on CM-5 systems with between 4 and 64 processors, using a selection of MIPLIB test problems. The first code, CMMIP, exploits many of the advanced features of the CM-5 network, whereas the second, called LCMIP, has a minimal, relatively infrequent communication pattern. Generally speaking, the performance of the low-communication code is competitive for relatively difficult problems and/or small processor configurations, but it appears that advanced communications features are essential to extract the maximum degree of parallelism from a given problem instance.

We describe three data-parallel implementations of the simplex method for dense linear programming problems. The first implementation uses a full tableau and the most-negative reduced cost pivot rule, the second uses a tableau and the steepest-edge pivot rule, and the third is a revised method with explicit inverse. All are implemented on a Connection Machine CM-2 massively parallel computer system, using a variant of Fortran 90. Using special data structures called stripe arrays, we produce efficient implementations. We compare the implementations to one another and to MINOS 5.4 on a Sun workstation. Test problems are from NETLIB, supplemented by a few additional, genuinely dense models from real applications. An appendix also gives recent results on the Connection Machine CM-5. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Mixed integer programs are numerical optimization problems that arise frequently in operations research, particularly in industrial logistics and tactical planning. Their classical solution method is a tree-search branch-and-bound algorithm in which each tree node represents a linear program. This paper describes an implementation of general mixed integer branch-and-bound algorithm that runs on the CM5 family of parallel processors. This code allows varying amounts of centralization, and combines the randomized work-distribution scheme of Karp and Zhang (1993) with a global load-balancing method based on SIMD algorithms. This combination proves effective in an asynchronous MIMD setting.>

The alternating step method is a massively parallel alternating direction method for monotropic programming, that is, convex programming with a separable objective function and linear constraints. This paper specializes the alternating step method to generalized network problems with positive semi-definite quadratic arc costs, and describes its implementation on a massively parallel computer, the Connection Machine CM-2. Extensive computational tests reveal that while the method is disappointingly slow for most problems with purely linear cost functions, it is competitive with dual relaxation methods on many problems having positive definite objectives. Furthermore, the algorithm continues to perform well even if a minority of arcs are given purely linear costs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.