Note on fundamental operations

A new type of generalization of fundamental calculating operations is attempted. Instead of generalizing the nature of the elements upon which operations are acting, the nature of the operations themselves is changed. By iterating the step which leads from addition to multiplication, new types of operations are generated. Some of these operations are discussed briefly.     

An evaluation of semidefinite programming based approaches for discrete lot-sizing problems

The present work is intended as a first step towards applying semidefinite programming models and tools to discrete lot-sizing problems including sequence-dependent changeover costs and times. Such problems can be formulated as quadratically constrained quadratic binary programs. We investigate several semidefinite relaxations by combining known reformulation techniques recently proposed for generic quadratic binary problems with problem-specific strengthening procedures developed for lot-sizing problems. Our computational results show that the semidefinite relaxations consistently provide lower bounds of significantly improved quality as compared with those provided by the best previously published linear relaxations. In particular, the gap between the semidefinite relaxation and the optimal integer solution value can be closed for a significant proportion of the small-size instances, thus avoiding to resort to a tree search procedure. The reported computation times are significant. However improvements in SDP technology can still be expected in the future, making SDP based approaches to discrete lot-sizing more competitive.     

凸规划的新算法

对一般凸目标函数和一般凸集约束的凸规划问题新解法进行探讨,它是线性规划一种新算法的扩展和改进,此算法的基本思想是在规划问题的可行域中由所建－的一个切割面到另一个切割面的不断推进来求取最优的。文章对目标函数是二次的且约束是一般凸集和二次目标函数且约束是线性的情形,给出了更简单的算法。     

Symmetry-exploiting cuts for a class of mixed-0/1 second-order cone programs

We will analyze mixed-0/1 second-order cone programs where the continuous and binary variables are solely coupled via the conic constraints. We devise a cutting-plane framework based on an implicit Sherali–Adams reformulation. The resulting cuts are very effective as symmetric solutions are automatically cut off and each equivalence class of 0/1 solutions is visited at most once. Further, we present computational results showing the effectiveness of our method and briefly sketch an application in optimal pooling of securities.     

The one dimensional Compartmentalised Knapsack Problem: A case study

The Compartmentalised Knapsack Problem (CKP) is similar to the ordinary Knapsack Problem except that items to be packed belong to separate classes, and items can only be packed, in knapsack compartments, amongst items in their own class. This paper addresses a case study in the cutting of steel rolls in which the CKP arises. The rolls are cut in two-phases: the first phase produces sub-rolls (compartments) which are, after reducing the thickness, cut in a second phase to produce ribbons (a class consists of ordered items with the same thickness). Finally, two methods of solving CKP are presented, and these are used to generate columns in the classical linear optimisation model of Gilmore and Gomory. Results of computational experiments are presented.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

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.     

A constructive characterization of the split closure of a mixed integer linear program

Two independent proofs of the polyhedrality of the split closure of mixed integer linear program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Köppe and Weismantel.     

A polynomial algorithm for one problem of guillotine cutting

We consider the problem of guillotine cutting a rectangular sheet into two rectangular pieces without rotations. The question is whether there exists a cutting pattern with given numbers of occurrences of both rectangular pieces. A polynomial time algorithm is described to construct the convex hull of solutions to this problem.     

A two step algorithm for solving a large scale semi-definite logit model

This paper proposes a two step algorithm for solving a large scale semi-definite logit model, which is appreciated as a powerful model in failure discriminant analysis. This problem has been successfully solved by a cutting plane (outer approximation) algorithm. However, it requires much more computation time than the corresponding linear logit model. A two step algorithm to be proposed in this paper is intended to reduce the amount of computation time by eliminating a certain portion of the data based on the information obtained by solving an associated linear logit model. It will be shown that this algorithm can generate a solution with almost the same quality as the solution obtained by solving the original large scale semi-definite model within a fraction of computation time.