Algorithms to Separate $\{0,\frac{1}{2}\}$ -Chvátal-Gomory Cuts

Chvátal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or , such cuts are known as -cuts. It has been proven by Caprara and Fischetti (Math. Program. 74:221–235, 1996) that separation of -cuts is -hard. In this paper, we study ways to separate -cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated -cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.     

Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions

We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our method to Viterbi’s decoding and training algorithms (IEEE Trans. Inform. Theory IT-13:260–269, 1967), as well as to the forward-backward and Baum-Welch (Inequalities 3:1–8, 1972) algorithms. Our approach is based on identifying repeated substrings in the observed input sequence. Initially, we show how to exploit repetitions of all sufficiently small substrings (this is similar to the Four Russians method). Then, we describe four algorithms based alternatively on run length encoding (RLE), Lempel-Ziv (LZ78) parsing, grammar-based compression (SLP), and byte pair encoding (BPE). Compared to Viterbi’s algorithm, we achieve speedups of Θ(log n) using the Four Russians method, using RLE, using LZ78, using SLP, and Ω(r) using BPE, where k is the number of hidden states, n is the length of the observed sequence and r is its compression ratio (under each compression scheme). Our experimental results demonstrate that our new algorithms are indeed faster in practice. We also discuss a parallel implementation of our algorithms. A preliminary version of this paper appeared in Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 4–15, 2007. Y. Lifshits’ research was supported by the Center for the Mathematics of Information and the Lee Center for Advanced Networking. S. Mozes’ work conducted while visiting MIT.     

模糊相关机会规划的蚁群优化算法及收敛性分析

模糊相关机会规划(Fuzzy dependent-chance programming, FDCP)因其非线性、非凸性及模糊性,对经典的优化理论提出了极大的挑战. 本文为解决复杂的模糊相关机会规划问题设计了一种基于模糊模拟的蚁群优化算法, 证明了该算法的收敛性,并通过估算期望收敛时间以分析蚁群优化算法的收敛速度. 数值案例研究验证了该算法的有效性、稳定性及准确性.     

The stochastic -hub center problem with service-level constraints

Small package delivery companies offer services where packages are guaranteed to be delivered within a given time-frame. With variability in travel time, the configuration on the hub-and-spoke delivery network is vital in ensuring a high probability of meeting the service-level guarantee. We present the stochastic p-hub center problem with chance constraints, which we use to model the service-level guarantees. We discuss analytical results, propose solution heuristics, and present the results from computational experiments.     

Using interactive multiobjective methods to solve DEA problems with value judgements

Data envelopment analysis (DEA) is a performance measurement tool that was initially developed without consideration of the decision maker (DM)'s preference structures. Ever since, there has been a wide literature incorporating DEA with value judgements such as the goal and target setting models. However, most of these models require prior judgements on target or weight setting. This paper will establish an equivalence model between DEA and multiple objective linear programming (MOLP) and show how a DEA problem can be solved interactively without any prior judgements by transforming it into an MOLP formulation. Various interactive multiobjective models would be used to solve DEA problems with the aid of PROMOIN, an interactive multiobjective programming software tool. The DM can then search along the efficient frontier to locate the most preferred solution where resource allocation and target levels based on the DM's value judgements can be set. An application on the efficiency analysis of retail banks in the UK is examined. Comparisons of the results among the interactive MOLP methods are investigated and recommendations on which method may best fit the data set and the DM's preferences will be made.     

Enhancements of two-stage stochastic decomposition

This paper presents some enhancements associated with stochastic decomposition (SD). Specifically, we study two issues: (a) Are there any conditions under which the regularized version of SD generates a unique solution? (b) Is there a way to modify the SD algorithm so that a user can trade-off solution times with solution quality? The second issue addresses the scalability of SD for very large scale problems for which computational resources may be limited and the user may be willing to accept solutions that are “nearly optimal”. We show that by using bootstrapping (re-sampling) the regularized SD algorithm can be accelerated without significant loss of optimality. We report computational results that demonstrate the viability of this approach.     

Several multi-criteria programming methods for classification

In this paper, we propose a general optimization-based model for classification. Then we show that some well-known optimization-based methods for classification, which were developed by Shi et al. [Data mining in credit card portfolio management: a multiple criteria decision making approac. In: Koksalan M, Zionts S, editors. Multiple criteria decision making in the new millennium. Berlin: Springer; 2001. p. 427–36] and Freed and Glover [A linear programming approach to the discriminant problem. Decision Sciences 1981; 12: 68–79; Simple but powerful goal programming models for discriminant problems. European Journal of Operational Research 1981; 7: 44–60], are special cases of our model. Moreover, three new models, MCQP (multi-criteria indefinite quadratic programming), MCCQP (multi-criteria concave quadratic programming) and MCVQP (multi-criteria convex programming), are developed based on the general model. We also propose algorithms for MCQP and MCCQP, respectively. Then we apply these models to three real-life problems: credit card accounts, VIP mail-box and social endowment insurance classification. Extensive experiments are done to compare the efficiency of these methods.     

The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach

In this paper, we consider the manpower allocation problem with time windows, job-teaming constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks. Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an integer programming model for the problem, which is decomposed using Dantzig–Wolfe decomposition. The problem is solved by column generation in a branch-and-price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context.     

Covering a line segment with variable radius discs

The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the disc covering problem on a line. The cost of each sensor includes a fixed component f, and a variable component that is a convex function of the diameter of the field-of-view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors, the problem becomes hard. A branch-and-bound algorithm as well as an efficient heuristic are developed for the special case in which the variable cost component of each sensor is proportional to the square of the measure of the field-of-view area. The heuristic very often obtains the optimal solution as shown in extensive computational testing.     

A new mixed integer linear programming model for product development using quality function deployment

Quality function deployment (QFD) is a product development process performed to maximize customer satisfaction. In the QFD, the design requirements (DRs) affecting the product performance are primarily identified, and product performance is improved to optimize customer needs (CNs). For product development, determining the fulfillment levels of design requirements (DRs) is crucial during QFD optimization. However, in real world applications, the values of DRs are often discrete instead of continuous. To the best of our knowledge, there is no mixed integer linear programming (MILP) model in which the discrete DRs values are considered. Therefore, in this paper, a new QFD optimization approach combining MILP model and Kano model is suggested to acquire the optimized solution from a limited number of alternative DRs, the values of which can be discrete. The proposed model can be used not only to optimize the product development but also in other applications of QFD such as quality management, planning, design, engineering and decision-making, on the condition that DR values are discrete. Additionally, the problem of lack of solutions in integer and linear programming in the QFD optimization is overcome. Finally, the model is illustrated through an example.