Extended Cutset Inequalities for the Network Power Consumption Problem

In this paper, we enhance the MIP formulation for the Network Power Consumption problem, proposed by Giroire et al. We derive cutting planes, extending the wellknown cutset inequalities, and report on preliminary computations.     

Alternative configurations for cutting machines in a tube cutting mill

In a steel tube mill where an endless stream of steel tube is supplied from a manufacturing facility, trim waste is never made regardless of cutting patterns used and the standard cutting stock problem seems meaningless. Therefore, the continuous stock cutting problem with setup is introduced to minimize the sum of cutting time and pattern changing time to meet the given demand. We propose a new configuration of cutting machines to achieve higher production efficiency, namely the open-ended configuration as opposed to the traditional closed-ended configuration, thereby two variants of the problem are defined. We propose linear formulations for both problems using binary expansion of the number of pieces of different types in a pattern. Furthermore, we define the time for pattern change as a linear function of the number of knives used in the pattern to be more realistic. Computational studies suggest that the open-ended cutting machine may improve the production time by up to 44% and that our linear formulations are more efficient than the existing ones.     

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented.     

Lower bounds and heuristics for the Windy Rural Postman Problem

In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.     

A new algorithm for the Integer Knapsack Problem and its parallelization

Summary A new sequential algorithm with complexityO(M ²+n) for an Integer Knapsack Problem with capacityM andn objects is proposed. The correspondentO(M ²/p+n) parallel algorithm runs on a ring machine withp processors. Computational results on both a local area network and a transputer network are reported.     

A Cutting Stock and Scheduling Problem in the Copper Industry

This case study was carried out for Thomas Bolton Ltd, a copper component manufacturer. The focus was on the first major production operation that is carried out in the foundry. This operation consists of three processes — melting scrap metal, casting it as ‘logs’ and cutting logs into ‘billets’. The timely production of the billets is essential as these feed a bottleneck process. The objective of the study was to investigate alternative methods of generating a production plan for the foundry that minimized costs whilst meeting the demand for billets at the bottleneck. The production plan was required to include a daily production schedule and a list of the cutting patterns to use when cutting the logs into billets. Thus, both the scheduling and cutting stock problems were addressed. A two-stage solution procedure was proposed. Alternative heuristic methods were investigated at the first stage and an optimal solution using Integer Programming (IP) was proposed for the second stage. It is shown that current performance could be improved using all of the heuristics considered at the first stage, but that using an IP-based heuristic method gives the best results.     

An Inverse Problem for the Heat Equation II

Completeness of the set of products of the derivatives of the solutions to the equation ( av ')' m u v = 0, v (0, u ) = 0 is proved. This property is used to prove the uniqueness of the solution to an inverse problem of finding conductivity in the heat equation $ \dot u = (a(x)u')' $ , u ( x , 0) = 0, u (0, t ) = 0, u (1, t ) = f ( t ) known for all t > 0, from the heat flux a (1) u '(1, t ) = g ( t ). Uniqueness of the solution to this problem is proved. The proof is based on Property C. It is proved the inverse that the inverse problem with the extra data (the flux) measured at the point, where the temperature is kept at zero, (point x = 0 in our case) does not have a unique solution, in general.     

Improving the efficiency of a best-first bottom-up approach for the Constrained 2D Cutting Problem

This work introduces several improvements in the solution of the Constrained 2D Cutting Problem. Such improvements combine the detection of dominated and duplicated cutting patterns with the implementation of parallel approaches for best-first search methods. The analysis of symmetries and dominances among the cutting patterns is able to discard some non-optimal or redundant builds, thus reducing the search space to be explored. The experimental evaluation demonstrates that when the domination/duplication rules are applied to an efficient parallel approach, the obtained reduction in the number of managed nodes involves a noticeable decrease in the computational effort associated with the final search process.     

Bounds and Heuristics for the Shortest Capacitated Paths Problem

Given a graph G, the Shortest Capacitated Paths Problem (SCPP) consists of determining a set of paths of least total length, linking given pairs of vertices in G, and satisfying capacity constraints on the arcs of G.We formulate the SCPP as a 0-1 linear program and study two Lagrangian relaxations for getting lower bounds on the optimal value. We then propose two heuristic methods. The first one is based on a greedy approach, while the second one is an adaptation of the tabu search meta-heuristic.     

我国汽车类样本上市公司股改事件窗中的风险与绩效评估

股权分置改革是中国股票市场的一场革命及重要的金融事件,它能够推动资本市场的改革,选取了两个具有代表性已实施股权分置改革的集团公司:上海汽车和宝利来.分别对两个集团公司在股改事件窗中的股票收益序列建立了合适的GARCH类模型.通过模型的实证结果得出股改后上海汽车和宝利来的收益水平均有很大的提高,而且股票价格波动对信息的反应更加灵敏,我国股票市场有效化程度显著提高.     

Models and algorithms for combinatorial optimization problems arising in railway applications

This is a summary of the author’s PhD thesis supervised by Alberto Caprara and Paolo Toth and defended on 29 May 2007 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work deals with Railway Optimization, and in particular it focuses on the Train Timetabling Problem (in the basic version on a corridor and in the extension to a railway network), and on the Train Unit Assignment Problem. Integer Linear Programming (ILP) formulations are proposed for both problems, and their continuous and Lagrangian relaxations are used to obtain optimal and heuristic solutions to real-world instances.      

The Diffraction Problem and Verigin Problem of Quasilinear Parabolic Equation in Divergence Form for the One-dimensional Case

In this paper, we consider the flow of two immiscible fluids in a onedimensional porous medium (the Verigin problem) and obtain a quasilinear parabolic equation in divergence form with the discontinuous coefficients. We prove first the existence and uniqueness of locally classical solution of the diffraction problem and then prove the existence of local solution of the Verigin problem.     

A simple and effective metaheuristic for the Minimum Latency Problem

The Minimum Latency Problem (MLP) is a variant of the Traveling Salesman Problem which aims to minimize the sum of arrival times at vertices. The problem arises in a number of practical applications such as logistics for relief supply, scheduling and data retrieval in computer networks. This paper introduces a simple metaheuristic for the MLP, based on a greedy randomized approach for solution construction and iterated variable neighborhood descent with random neighborhood ordering for solution improvement. Extensive computational experiments on nine sets of benchmark instances involving up to 1000 customers demonstrate the good performance of the method, which yields solutions of higher quality in less computational time when compared to the current best approaches from the literature. Optimal solutions, known for problems with up to 50 customers, are also systematically obtained in a fraction of seconds.     

A New Formulation and Computational Results for the Simple Cycle Problem

In this paper we propose a new formulation for the Simple Cycle Problem and conduct preliminary computational tests comparing it with a formulation that comes from the literature.     

股市中相互作用群体间出现无限集的一个必要条件

本文通过构造一个可逆马氏链模型 ,描述了股票市场中多组相互作用人群的进出与彼此间的转移 .我们推导出了人群大小的稳定分布 ;同时给出了人群中出现无限集 (指大量人群集中在一组或几组中 )的一个必要条件 ,无限集的出现可能对应于股市崩溃的情形     

A Cut and Branch Approach for the Capacitated <Emphasis Type="Italic">p</Emphasis>-Median Problem Based on Fenchel Cutting Planes

The capacitated p-median problem (CPMP) consists of finding p nodes (the median nodes) minimizing the total distance to the other nodes of the graph, with the constraint that the total demand of the nodes assigned to each median does not exceed its given capacity. In this paper we propose a cutting plane algorithm, based on Fenchel cuts, which allows us to considerably reduce the integrality gap of hard CPMP instances. The formulation strengthened with Fenchel cuts is solved by a commercial MIP solver. Computational results show that this approach is effective in solving hard instances or considerably reducing their integrality gap.      

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

Problem structuring methods ‘in the Dock’: Arguing the case for Soft OR

Problem structuring methods (‘soft’ OR) have been around for approximately 40 years and yet these methods are still very much overlooked in the OR world. Whilst there is almost certainly a number of explanations for this, two key stumbling blocks are: (1) the subjective nature of the modelling yielding insights rather than testable results, and (2) the demand on users to both manage content (through modelling) and processes (work with rather than ‘on behalf’ of groups). However, as evidenced from practice there are also a number of significant benefits. This paper therefore aims to examine the case of Soft OR through examining the case for and against problem structuring methods.