Mixed-integer linear programming for resource leveling problems

We consider project scheduling problems subject to general temporal constraints, where the utilization of a set of renewable resources has to be smoothed over a prescribed planning horizon. In particular, we consider the classical resource leveling problem, where the variation in resource utilization during project execution is to be minimized, and the so-called “overload problem”, where costs are incurred if a given resource-utilization threshold is exceeded. For both problems, we present new mixed-integer linear model formulations and domain-reducing preprocessing techniques. In order to strengthen the models, lower and upper bounds for resource requirements at particular points in time, as well as effective cutting planes, are outlined. We use CPLEX 12.1 to solve medium-scale instances, as well as instances of the well-known test set devised by Kolisch et al. (1999). Instances with up to 50 activities and tight project deadlines are solved to optimality for the first time.     

Fast neighborhood search for two- and three-dimensional nesting problems

In this paper we present a new heuristic solution method for two-dimensional nesting problems. It is based on a simple local search scheme in which the neighborhood is any horizontal or vertical translation of a given polygon from its current position. To escape local minima we apply the meta-heuristic method Guided Local Search.     

A skyline heuristic for the 2D rectangular packing and strip packing problems

In this paper, we propose a greedy heuristic for the 2D rectangular packing problem (2DRP) that represents packings using a skyline; the use of this heuristic in a simple tabu search approach outperforms the best existing approach for the 2DRP on benchmark test cases. We then make use of this 2DRP approach as a subroutine in an “iterative doubling” binary search on the height of the packing to solve the 2D rectangular strip packing problem (2DSP). This approach outperforms all existing approaches on standard benchmark test cases for the 2DSP.     

A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering

The nesting problem is commonly encountered in sheet metal, clothing and shoe-making industries. The nesting problem is a combinatorial optimization problem in which a given set of irregular polygons is required to be placed on a rectangular sheet. The objective is to minimize the length of the sheet while having all polygons inside the sheet without overlap. In this study, a methodology that hybridizes cuckoo search and guided local search optimization techniques is proposed.     

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.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems

Cutting and packing problems have been extensively studied in the literature in recent decades, mainly due to their numerous real-world applications while at the same time exhibiting intrinsic computational complexity. However, a major limitation has been the lack of problem generators that can be widely and commonly used by all researchers in their computational experiments. In this paper, a problem generator for every type of two-dimensional rectangular cutting and packing problems is proposed. The problems are defined according to the recent typology for cutting and packing problems proposed by Wäscher, Haußner, and Schumann (2007) and the relevant problem parameters are identified. The proposed problem generator can significantly contribute to the quality of the computational experiments run with cutting and packing problems and therefore will help improve the quality of the papers published in this field.     

A geometric proof of the combinatorial bounds for the number of optimal solutions for the Euclidean 2-center problem

We provide lower and upper bounds for γ(n), the number of optimal solutions for the two-center problem: “Given a set S of n points in the real plane, find two closed discs whose union contains all of the points such that the radius of the larger disc is minimized.”The main result of the paper shows the matching upper and lower bounds for the two-center problem and demonstrates that γ(n)=n.     

Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations

This paper is concerned with the problem of assigning employees to gas stations owned by the Kuwait National Petroleum Corporation (KNPC), which hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. Although similar employee scheduling problems have been addressed in the literature, certain peculiarities of the problem require novel mathematical models and algorithms to deal with the specific nature and size of this problem. The problem is modeled as a mixed-integer program, and a problem size analysis based on real data reveals that the formulation is too complex to solve directly. Hence, a two-stage approach is proposed, where the first stage assigns employees to stations, and the second stage specifies shifts and off-days for each employee. Computational results related to solving the two-stage models directly via CPLEX and by specialized heuristics are reported. The two-stage approach provides daily schedules for employees for a given time horizon in a timely fashion, taking into consideration the employees’ expressed preferences. This proposed modeling approach can be incorporated within a decision support system to replace the current manual scheduling practice that is often chaotic and has led to feelings of bias and job dissatisfaction among employees.     

A geometric approach for solving fuzzy linear programming problems

In this paper we first recall some definitions and results of fuzzy plane geometry, and then introduce some definitions in the geometry of two-dimensional fuzzy linear programming (FLP). After defining the optimal solution based on these definitions, we use the geometric approach for obtaining optimal solution(s) and show that the algebraic solutions obtained by Zimmermann method (ZM) and our geometric solutions are the same. Finally, numerical examples are solved by these two methods.     

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.     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

Mathematical programming models for some smallest-world problems

Given a weighted graph G, in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph G. Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0–1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the “small-worldness” of graphs.     

Approximations for chance-constrained programming problems

This paper proposes an approximation approach to the solution of chance-constrained stochastic programming problems. The results rely in a fundamental way on the theory of convergence of sequences of measurable multifunctions. Particular results are presented for stochastic linear programming problems.