Search

In many statistical learning problems, it is desired that the optimal solution conform to an a priori known sparsity structure represented by a directed acyclic graph. Inducing such structures by means of convex regularizers requires nonsmooth penalty functions that exploit group overlapping. Our study focuses on evaluating the proximal operator of the latent overlapping group lasso developed by Jacob et al. in 2009 . We implemented an alternating direction method of multiplier with a sharing scheme to solve large-scale instances of the underlying optimization problem efficiently. In the absence of strong convexity, global linear convergence of the algorithm is established using the error bound theory. More specifically, the paper contributes to establishing primal and dual error bounds when the nonsmooth component in the objective function does not have a polyhedral epigraph. We also investigate the effect of the graph structure on the speed of convergence of the algorithm. Detailed numerical simulation studies over different graph structures supporting the proposed algorithm and two applications in learning are provided. Summary of Contribution: The paper proposes a computationally efficient optimization algorithm to evaluate the proximal operator of a nonsmooth hierarchical sparsity-inducing regularizer and establishes its convergence properties. The computationally intensive subproblem of the proposed algorithm can be fully parallelized, which allows solving large-scale instances of the underlying problem. Comprehensive numerical simulation studies benchmarking the proposed algorithm against five other methods on the speed of convergence to optimality are provided. Furthermore, performance of the algorithm is demonstrated on two statistical learning applications related to topic modeling and breast cancer classification. The code along with the simulation studies and benchmarks are available on the corresponding author’s GitHub website for evaluation and future use.

In this paper, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin-packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, a set of new 500 test instances were proposed for the 1D-BPP, and the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of 1 hour imposed on each execution of the algorithm. The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1DBPPs and the subset row inequalities. We describe an ad hoc label-setting algorithm to solve the pricing problem, dominance, and fathoming rules to speed up its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, such as the incompatibility between the items, and therefore, we also apply it to solve the one-dimensional bin-packing problem with conflicts (1D-BPPC). The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1,003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods and that it successfully closed several open 1D-BPPC instances.

The β-robust machine scheduling has attracted increasing attention as an effective method to hedge against uncertainty. However, existing β-robust scheduling models rely on the normality assumption of uncertain parameters, and existing solution methods are based on branch and bound, which cannot solve problems of 45 jobs within 3,600 seconds. This paper proposes distributionally β-robust scheduling (DRS) models to handle uncertain processing times. The DRS models only require the lower bound, mean, and covariance information of processing times, and have the capability of handling both single and parallel machine problems. Another key contribution of this paper is to devise efficient parametric search (PS) methods for the DRS models. Specifically, we show that there exists a parameterized assignment problem (PAP), such that its optimal solutions are also optimal for the original problem. The proposed methods only need to perform a one-dimensional PS and solve a series of PAPs. We further propose a bidirectional PS to reduce the number of PAPs needed to be solved, and we design a speedup shortest augmentation path algorithm for these PAPs. Experimental results on both single and identical parallel machine problems show that the improved PS method outperforms existing algorithms by more than three orders of magnitude improvement in computation time for problems of 45 jobs, and it is able to solve problems of 500 jobs within 0.5 seconds.

Recommendation stability measures the extent to which a recommendation algorithm provides predictions that are consistent with each other. Several approaches have been proposed in prior work to defining, measuring, and improving the stability of recommendation algorithms. Previous studies have focused primarily on understanding and evaluating recommendation stability in prediction-oriented settings, i.e., recommendation settings where it is crucial to provide the precise prediction of a user’s preference rating for an item. However, the research literature has been largely silent on the topic of recommendation stability in other important types of settings, such as classification-oriented (i.e., where it is important to accurately classify the item as relevant versus irrelevant, without having to quantify the user’s preference precisely), ranking-oriented (i.e., where it is important to provide accurate relative ranking of items to users), or top-K oriented (i.e., where it is important to suggest K items that are most appealing to the user). Therefore, this paper builds on prior work by generalizing the notion of stability to a broader set of recommendation settings and developing corresponding stability metrics. The paper also provides a comprehensive empirical analysis of classification, ranking, and top-K stability performance of popular recommender algorithms on real-world rating data sets under a variety of settings.

Models incorporating more realistic models of customer behavior, as customers choosing from an offer set, have recently become popular in assortment optimization and revenue management. The dynamic program for these models is intractable and approximated by a deterministic linear program called the choice deterministic linear program (CDLP), which has an exponential number of columns. Column generation has been proposed but finding an entering column is NP-hard when segment consideration sets overlap. In this paper we propose a new approach called segment-based deterministic concave program (SDCP) based on segments and their consideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound on the dynamic program, but coincides with CDLP for the case of nonoverlapping segments. If the number of elements in a consideration set for a segment is not very large, SDCP can be applied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by (i) simulations, called the randomized concave programming method, and (ii) by adding cuts to a recent compact formulation (SBLP) of the problem for a latent multinomial-choice model (MNL) of demand. This latter approach turns out to be very effective, essentially obtaining CDLP value, even for overlapping segments. By formulating the problem as a separation problem, we give insight into why CDLP is easy for the MNL with nonoverlapping consideration sets and why generalizations of MNL pose difficulties. Numerical conclusions that we derive from the present paper are the following: (a) The randomized linear programming approach that obtains significant tightening of the linear program upper bound under an older independent-class model seems to have relatively little effect for the choice case; (b) for the MNL choice model, the SBLP+ formulation we give here for overlapping segments is very fast and is potentially scalable to industrial-size problems.

Motivated by large-scale service systems with network structure, we introduced in a previous paper a time-varying open network of many-server fluid queues with customer abandonment from each queue and time-varying proportional routing among the queues, and showed how performance functions can be determined. The deterministic fluid model serves as an approximation for the corresponding non-Markovian stochastic network of many-server queues with Markovian routing, experiencing periods of overloading at the queues. In this paper we develop a new algorithm for the previous model and generalize the model to include non-exponential service-time distributions. In this paper we report results of implementing the algorithms and studying their computational complexity. We also conduct simulation experiments to confirm that the algorithms are effective in computing the performance functions and that these performance functions provide useful approximations for the corresponding stochastic models.

In this paper, we propose an algorithm to fit heavy-tailed (HT) distribution functions by generalized hyperexponential (GH) distribution functions. A discussion of the steps, usage, and accuracy of the GH algorithm is given. Several examples in this paper show that the proposed method can be applied to fit HT distributions with a completely monotone probability density function (pdf) very well, like the Pareto distribution and the Weibull distribution with the shape parameter less than one, as well as HT distributions whose pdf is not completely monotone, like the lognormal distribution. In addition, we provide an example that shows that the proposed method can be applied to density estimation of real data presenting a heavy tail.

In many fields, we come across problems where we want to optimize several conflicting objectives simultaneously. To find a good solution for such multi-objective optimization problems, an approximation of the Pareto set is often generated. In this paper, we con- sider the approximation of Pareto sets for problems with three or more convex objectives and with convex constraints. For these problems, sandwich algorithms can be used to de- termine an inner and outer approximation between which the Pareto set is 'sandwiched'. Using these two approximations, we can calculate an upper bound on the approximation error. This upper bound can be used to determine which parts of the approximations must be improved and to provide a quality guarantee to the decision maker. In this paper, we extend higher dimensional sandwich algorithms in three different ways. Firstly, we introduce the new concept of adding dummy points to the inner approx- imation of a Pareto set. By using these dummy points, we can determine accurate inner and outer approximations more e±ciently, i.e., using less time-consuming optimizations. Secondly, we introduce a new method for the calculation of an error measure which is easy to interpret. The combination of easy calculation and easy interpretation makes this measure very suitable for sandwich algorithms. Thirdly, we show how transforming cer- tain objective functions can improve the results of sandwich algorithms and extend their applicability to certain non-convex problems. The calculation of the introduced error measure when using transformations will also be discussed. To show the effect of these enhancements, we make a numerical comparison using four test cases, including a four-dimensional case from the field of intensity-modulated radiation therapy (IMRT). The results of the different cases show that we can indeed achieve an accurate approximation using significantly fewer optimizations by using the enhancements.

This paper develops algorithms for finding Coxian generators to phase-type (PH)-majorize a PH-generator T with only real eigenvalues. In the first part of this paper, we investigate matrices S and P satisfying TP = PS and Pe = e. Conditions on T are identified for S to be an ordered Coxian generator and for P to be nonnegative, which consequently implies that S PH-majorizes T. It is shown that every PH-generator with only real eigenvalues is PH-majorized by some Coxian generator. In the second part of this paper, the results on S and P and the conditions on T are used to develop efficient algorithms for Coxianization of PH-generators. Numerical examples are presented for a comparison between the developed algorithms.

This paper presents a parallel branch-and-bound method to address the two-dimensional rectangular guillotine strip cutting problem. Our paper focuses on a parallel branching schema. We present a series of computational experiments to evaluate the strength of the approach. Optimal solutions have been found for some benchmark instances that had unknown solutions until now. For many other instances, we demonstrate that the proposed approach is time effective. The efficiency of the parallel version of the algorithm is compared and the speedup, when increasing the number of processors, is clearly demonstrated with an upper bound calculated by a specialised heuristic procedure.

Controlled sequential bifurcation (CSB) is a factor-screening method for discrete-event simulations. It combines a multistage hypothesis testing procedure with the original sequential bifurcation procedure to control both the power for detecting important effects at each bifurcation step and the Type I error for each unimportant factor under heterogeneous variance conditions when a main-effects model applies. This paper improves the CSB procedure in two aspects. First, a new fully sequential hypothesis-testing procedure is introduced that greatly improves the efficiency of CSB. Moreover, this paper proposes CSB-X, a more general CSB procedure that has the same error control for screening main effects that CSB does, even when two-factor interactions are present. The performance of the new method is proven and compared with the original CSB procedure.

Problem-specific encodings can improve the performance of metaheuristics, such as genetic algorithms or simulated annealing. This paper studies the link-biased (LB) encoding, which is a tree representation, and applies metaheuristics using this encoding to the minimum communication spanning tree (MCST) problem. Given the communication requirements of the nodes, the MCST problem seeks a communication spanning tree with minimum total cost. Optimal solutions for MCST problems are similar to minimum spanning trees (MSTs), and the LB encoding exploits this property by encoding trees similar to MSTs with higher probability. The paper investigates how to systematically design problem-specific encodings for MCST problems and how to set the encoding-specific parameter that controls the bias of the LB encoding towards MSTs; it then presents performance results for various MCST problems.

This paper contains a complete and updated review of the literature for multiobjective flowshop problems, which are among the most studied environments in the scheduling research area. No previous comprehensive reviews exist in the literature. Papers about lexicographical, goal programming, objective weighting, and Pareto approaches have been reviewed. Exact, heuristic, and metaheuristic methods have been surveyed. Furthermore, a complete computational evaluation is also carried out. A total of 23 different algorithms including both flowshop-specific methods as well as general multiobjective optimization approaches have been tested under three different two-criteria combinations with a comprehensive benchmark. All methods have been studied under recent state-of-the-art quality measures. Parametric and nonparametric statistical testing is profusely employed to support the observed performance of the compared methods. As a result, we have identified the best-performing methods from the literature, which along with the review, constitutes a reference work for further research.

The introduction of edge-finding techniques was a significant development in constraint-based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge-finding algorithms for cumulative scheduling and shows that Nuijten's edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time O(n2k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge-finder specification. The paper also proposes the first extended edge-finding algorithms that run in time O(n2k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning.

This paper presents the spiral array model and its associated algorithms for tonal induction, approximation, and segmentation. The spiral array is a geometric model for tonality that clusters perceptually similar tonal entities. The model summarizes music information as interior points inside an array of spirals. Distances in the spiral array space are used to quantify tonal similarity. The paper traces the evolution, and presents general forms, of the existing algorithms for key finding, pitch spelling, and segmentation, and proposes a new O(n) algorithm, Argus, for tonal segmentation. The proposed algorithm computes a value that quantifies the discrepancy between the local contexts in the future and past at each point in time. Discrepancy values exceeding control thresholds are shown to mark the segmentation boundaries of the test set that concur with expert analyses. A number of window sizes and threshold settings are investigated. The algorithm is demonstrated using Edward MacDowell’s To A Wild Rose and tested on Franz Schubert’s Allegretto from Moment Musical D780 No. 6 and Thema from Impromptu D935 No. 4. The algorithm accurately locates tonal boundaries in all three case studies.

Modern integrated circuit design involves the layout of circuits consisting of millions of switching elements or transistors. Due to the sheer complexity of the problem, optimizing the connectivity between transistors is very difficult. The circuit interconnection is the single most important factor in performance criteria such as signal delay, power dissipation, circuit size, and cost. These factors dictate that interconnections, i.e., wires, be made as short as possible. The wire-minimization problem is generally formulated as a sequence of discrete optimization subproblems that are known to be NP-hard. Hence, they can only be solved approximately using meta-heuristics. These methods are computationally expensive and the quality of the solution depends to a great extent on an appropriate choice of starting configuration and modeling techniques. In this paper, new modeling techniques are used to solve the routing problem formulated as an integer programming problem. The main contribution of this paper is a proposed global routing heuristic that combines the wire length, channel congestion, and number of pins in routes to find the best wiring layout of a circuit. By adding information such as channel congestion and the number of pins in each route as well as the wire length, the quality of the solution is improved. In addition, the solutions of the large relaxed linear programming problems are skewed towards a zero-one solution, resulting in faster convergence. The developed LP models in this paper are useful when solving the global routing problem for two reasons; first, the new interior-point algorithms to solve the LP problem are polynomial in time. Second, “near optimal wiring” is obtained in polynomial time without performing randomized rounding.

In this paper, we study a new problem that we refer to as the multiple knapsack with color constraints (MKCP). Motivated by a real application from the steel industry, the MKCP can be formulated by generalizing the multiple knapsack problem. A real-life instance (called mkc) of this problem class is available through MIPLIB (Bixby 2004) and a larger instance (mkc7) is downloadable from the COIN site (IBM 2004). The focus of this paper is to present improved computational results for the two mentioned instances of this problem using a column-generation approach. We solve mkc to optimality and use Dantzig-Wolfe decomposition for upper bounding the other instance. Solving mkc to optimality took less time than it takes to solve the LP relaxation of the original formulation. The larger instance is solved to near optimality (within 0.5% of optimality) in a fraction of the time required to solve the original relaxed LP.

This paper introduces simultaneous generalized hill-climbing (SGHC) algorithms as a framework for simultaneously addressing a set of related discrete optimization problems using heuristics. Many well-known heuristics can be embedded within the SGHC algorithm framework, including simulated annealing, pure local search, and threshold accepting (among others). SGHC algorithms probabilistically move between a set of related discrete optimization problems during their execution according to a problem probability mass function. When an SGHC algorithm moves between discrete optimization problems, information gained while optimizing the current problem is used to set the initial solution in the subsequent problem. The information used is determined by the practitioner for the particular set of problems under study. However, effective strategies are often apparent based on the problem description. SGHC algorithms are motivated by a discrete manufacturing process design optimization problem (that is used throughout the paper to illustrate the concepts needed to implement a SGHC algorithm). This paper discusses effective strategies for three examples of sets of related discrete optimization problems (a set of traveling salesman problems, a set of permutation flow shop problems, and a set of MAX 3-satisfiability problems). Computational results using the SGHC algorithm for randomly generated problems for two of these examples are presented. For comparison purposes, the associated generalized hill-climbing (GHC) algorithms are applied to the individual discrete optimization problems in the sets. These computational results suggest that near-optimal solutions can be reached more effectively and efficiently using SGHC algorithms.

This paper proposes and tests variants of GRASP (greedy randomized adaptive search procedure) with path relinking for the three-index assignment problem (AP3). GRASP is a multistart metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and of a local search. Path relinking is an intensification strategy that explores trajectories that connect high-quality solutions. Several variants of the heuristic are proposed and tested. Computational results show clearly that this GRASP for AP3 benefits from path relinking and that the variants considered in this paper compare well with previously proposed heuristics for this problem. GRASP with path relinking was able to improve the solution quality of heuristics proposed by Balas and Saltzman (1991), Burkard et al. (1996), and Crama and Spieksma (1992) on all instances proposed in those papers. We show that the random variable “time to target solution,” for all proposed GRASP with path-relinking variants, fits a two-parameter exponential distribution. To illustrate the consequence of this, one of the variants of GRASP with path relinking is shown to benefit from parallelization.

In designing ideal multiple recursive random number (RN) generators (MRGs), the best set of multipliers, in terms of the lattice structure of the RNs produced, is sought. As the order of the MRG increases, the number of possible sets of multipliers to be examined grows exponentially. This paper proposes a genetic algorithm for designing good MRGs. The set of multipliers associated with the MRG is encoded as a binary string. Via the operations of reproduction, crossover, and mutation, new sets of multipliers are generated. The spectral values of the MRGs are calculated to guide the search process. As an illustration, the proposed algorithm is employed to find good sets of multipliers for MRGs of orders three and four. The results are better than those derived from other studies. To conclude, this paper not only finds better MRGs of orders three and four, but also develops an algorithm for designing MRGs of higher orders.

The purpose of this paper is to present a new deterministic metaheuristic based on a modification of the variable neighborhood search of Mladenovic and Hansen (1997) for solving the vehicle-routing problem with time windows. Results are reported for the standard 100, 200, and 400 customer data sets by Solomon (1987) and Gehring and Homberger (1999), and two real-life problems by Russell (1995). The findings indicate that the proposed procedure outperforms other recent local searches and metaheuristics. In addition, four new best-known solutions were obtained. The proposed procedure is based on a new four-phase approach. In this approach an initial solution is first created using new route-construction heuristics followed by a route-elimination procedure to improve the solutions regarding the number of vehicles. In the third phase the solutions are improved in terms of total traveled distance using four new local-search procedures proposed in this paper. Finally, in phase four, the best solution obtained is improved by modifying the objective function to escape from a local minimum.

The goal of this paper is to develop models and methods that use complementary strengths of Mixed Integer Linear Programming (MILP) and Constraint Programming (CP) techniques to solve problems that are otherwise intractable if solved using either of the two methods. The class of problems considered in this paper have the characteristic that only a subset of the binary variables have non-zero objective function coefficients if modeled as an MILP. This class of problems is formulated as a hybrid MILP/CP model that involves some of the MILP constraints, a reduced set of the CP constraints, and equivalence relations between the MILP and the CP variables. An MILP/CP based decomposition method and an LP/CP-based branch-and-bound algorithm are proposed to solve these hybrid models. Both these algorithms rely on the same relaxed MILP and feasibility CP problems. An application example is considered in which the least-cost schedule has to be derived for processing a set of orders with release and due dates using a set of dissimilar parallel machines. It is shown that this problem can be modeled as an MILP, a CP, a combined MILP-CP OPL model (Van Hentenryck 1999), and a hybrid MILP/CP model. The computational performance of these models for several sets shows that the hybrid MILP/CP model can achieve two to three orders of magnitude reduction in CPU time.

This paper is about modeling and solving mixed integer programming (MIP) problems. In the last decade, the use of mixed integer programming models has increased dramatically. Fifteen years ago, mainframe computers were required to solve problems with a hundred integer variables. Now it is possible to solve problems with thousands of integer variables on a personal computer and obtain provably good approximate solutions to problems such as set partitioning with millions of binary variables. These advances have been made possible by developments in modeling, algorithms, software, and hardware. This paper focuses on effective modeling, preprocessing, and the methodologies of branch-and-cut and branch-and-price, which are the techniques that make it possible to treat problems with either a very large number of constraints or a very large number of variables. We show how these techniques are useful in important application areas such as network design and crew scheduling. Finally, we discuss the relatively new research areas of parallel integer programming and stochastic integer programming.

In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties on the right-hand side of the constraints. Such a problem often arises in applications such as in systemic risk estimation in finance and stochastic optimization. We first show that the WCLO problem with the uncertainty set corresponding to the [Formula: see text]p-norm ((WCLOp)) is NP-hard for p ɛ (1,∞). Second, we combine several simple optimization techniques, such as the successive convex optimization method, quadratic convex relaxation, initialization, and branch-and-bound (B&B), to develop an algorithm for (WCLO2) that can find a globally optimal solution to (WCLO2) within a prespecified ε-tolerance. We establish the global convergence of the algorithm and estimate its complexity. We also develop a finite B&B algorithm for (WCLO∞) to identify a global optimal solution to the underlying problem, and establish the finite convergence of the algorithm. Numerical experiments are reported to illustrate the effectiveness of our proposed algorithms in finding globally optimal solutions to medium and large-scale WCLO instances.