Downloads & Free Reading Options - Results

This volume was digitized and made accessible online due to deterioration of the original print copy.

This volume was digitized and made accessible online due to deterioration of the original print copy.

The development is documented of a heuristic method for the solution of pure integer linear programming problems. The procedure draws its methodology from the ideas of Hooke and Jeeves type 1 and 2 exploratory searches, greedy procedures, and neighborhood searches. It uses an efficient rounding method to obtain its first feasible integer point from the optimal continuous solution obtained via the simplex method. Since this method is based entirely on simple addition or subtraction of one to each variable of a point in n-space and the subsequent comparison of candidate solutions to a given set of constraints, it facilitates significant complexity improvements over existing techniques. It also obtains the same optimal solution found by the branch-and-bound technique in 44 of 45 small to moderate size test problems. Two example problems are worked in detail to show the inner workings of the method. Furthermore, using an established weighted scheme for comparing computational effort involved in an algorithm, a comparison of this algorithm is made to the more established and rigorous branch-and-bound method. A computer implementation of the procedure, in PC compatible Pascal, is also presented and discussed.

The Marine Corps has long been successful in assigning its available personnel to vacant billets. However, by our research, the Marine Corps has not been as successful in minimizing assignment costs when moving a Marine to another permanent duty station. With increased pressure on cost savings due to shrinking budgets, the importance of cost minimizing efforts is becoming more significant. This thesis examines the Marine Corps personnel assignment process and proposes a methodology for optimizing the allocation of Marine Corps personnel that minimizes assignment costs while taking into account constraints such as military occupational specialty, billet vacancies, duty station preference, and seniority. Optimization is achieved by incorporating an integer programming model into the personnel assignment process. The model is tested by contrasting the results of the actual assignments of a 15-Marine sample with the results of simulated optimization assignments of the same sample. The findings of this thesis show that the proposed methodology is both valid and feasible, and that it could yield significant monetary savings for the Marine Corps.

Journal of Research of the National Bureau of Standards

Detection of an Unmanned Air Vehicle by radar is dependent on many variables including range, altitude, and relative orientation. Given a radar location and appropriate model for the likelihood of detection, a path plan can be created for an Unmanned Air Vehicle which constrains the probability of detection. In this paper such an approach is taken using a linearized detection model. The detection model and the Unmanned Air Vehicle's dynamics are represented as a linear program subject to mixed integer constraints. This mixed integer linear program (MILP) is then solved with commercial software which has been traditionally used by the Operations Research community. This approach searches for all feasible solutions and produces the best path plan based on the user specified parameters.

Contents: Resource Decomposition: A Conceptual Outline; Branching in the Rudimentary Branch-and-Bound Algorithm; Computing Bounds: Single Linking Constraint Case; Computing Bounds: Multiple Linking Constraints Case; Computational Results; and Conclusions, Extensions, and Areas for Future Research.

Thesis advisor(s): Dell, Robert F

This thesis details an integer programming model to aid in the modernization of the Navy's Maritime Patrol Aviation fleet. Over a user specified time horizon, the model provides a schedule for when to retire, perform avionics upgrades, or transfer current inventory aircraft from the USN to the USNR. Additionally, the model determines when to open a new aircraft production line and the number of aircraft to procure each year. The model optimizes the modernization schedule while taking into consideration required inventory, minimum required percentage of aircraft containing modern avionics, maximum desired mean aircraft age, budgetary limitations, and production line restrictions. The model minimizes the procurement, operating and maintenance costs using the X-System solver.

Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic. The primary goal is a study of a simple version of general nonlinear integer problems, where all constraints are still linear. Our focus is on the computational complexity of the problem, which varies significantly with the type of nonlinear objective function in combination with the underlying combinatorial structure. Numerous boundary cases of complexity emerge, which sometimes surprisingly lead even to polynomial time algorithms. We also cover recent successful approaches for more general classes of problems. Though no positive theoretical efficiency results are available, nor are they likely to ever be available, these seem to be the currently most successful and interesting approaches for solving practical problems. It is our belief that the study of algorithms motivated by theoretical considerations and those motivated by our desire to solve practical instances should and do inform one another. So it is with this viewpoint that we present the subject, and it is in this direction that we hope to spark further research.

Load disaggregation based on aided linear integer programming (ALIP) is proposed. We start with a conventional linear integer programming (IP) based disaggregation and enhance it in several ways. The enhancements include additional constraints, correction based on a state diagram, median filtering, and linear programming-based refinement. With the aid of these enhancements, the performance of IP-based disaggregation is significantly improved. The proposed ALIP system relies only on the instantaneous load samples instead of waveform signatures, and hence does not crucially depend on high sampling frequency. Experimental results show that the proposed ALIP system performs better than the conventional IP-based load disaggregation system.

In the Integer Quadratic Programming problem input is an n*n integer matrix Q, an m*n integer matrix A and an m-dimensional integer vector b. The task is to find a vector x in Z^n, minimizing x^TQx, subject to Ax

This paper introduces an improved recursive algorithm to generate the set of all nondominated objective vectors for the Multi-Objective Integer Programming (MOIP) problem. We significantly improve the earlier recursive algorithm of \"Ozlen and Azizo\u{g}lu by using the set of already solved subproblems and their solutions to avoid solving a large number of IPs. A numerical example is presented to explain the workings of the algorithm, and we conduct a series of computational experiments to show the savings that can be obtained. As our experiments show, the improvement becomes more significant as the problems grow larger in terms of the number of objectives.

We transform join ordering into a mixed integer linear program (MILP). This allows to address query optimization by mature MILP solver implementations that have evolved over decades and steadily improved their performance. They offer features such as anytime optimization and parallel search that are highly relevant for query optimization. We present a MILP formulation for searching left-deep query plans. We use sets of binary variables to represent join operands and intermediate results, operator implementation choices or the presence of interesting orders. Linear constraints restrict value assignments to the ones representing valid query plans. We approximate the cost of scan and join operations via linear functions, allowing to increase approximation precision up to arbitrary degrees. Our experimental results are encouraging: we are able to find optimal plans for joins between 60 tables; a query size that is beyond the capabilities of prior exhaustive query optimization methods.

In this paper, an integer programming approach is introduced to construct Unequal Error Protection (UEP) codes for multiuser broadcast channels. We show that the optimal codes can be constructed that satisfy the integer programming bound. Based on the bound, we compute asymptotic code rate and perform throughput analysis for the degraded broadcast channel.

Answering science questions posed in natural language is an important AI challenge. Answering such questions often requires non-trivial inference and knowledge that goes beyond factoid retrieval. Yet, most systems for this task are based on relatively shallow Information Retrieval (IR) and statistical correlation techniques operating on large unstructured corpora. We propose a structured inference system for this task, formulated as an Integer Linear Program (ILP), that answers natural language questions using a semi-structured knowledge base derived from text, including questions requiring multi-step inference and a combination of multiple facts. On a dataset of real, unseen science questions, our system significantly outperforms (+14%) the best previous attempt at structured reasoning for this task, which used Markov Logic Networks (MLNs). It also improves upon a previous ILP formulation by 17.7%. When combined with unstructured inference methods, the ILP system significantly boosts overall performance (+10%). Finally, we show our approach is substantially more robust to a simple answer perturbation compared to statistical correlation methods.

Answering science questions posed in natural language is an important AI challenge. Answering such questions often requires non-trivial inference and knowledge that goes beyond factoid retrieval. Yet, most systems for this task are based on relatively shallow Information Retrieval (IR) and statistical correlation techniques operating on large unstructured corpora. We propose a structured inference system for this task, formulated as an Integer Linear Program (ILP), that answers natural language questions using a semi-structured knowledge base derived from text, including questions requiring multi-step inference and a combination of multiple facts. On a dataset of real, unseen science questions, our system significantly outperforms (+14%) the best previous attempt at structured reasoning for this task, which used Markov Logic Networks (MLNs). It also improves upon a previous ILP formulation by 17.7%. When combined with unstructured inference methods, the ILP system significantly boosts overall performance (+10%). Finally, we show our approach is substantially more robust to a simple answer perturbation compared to statistical correlation methods.

Considering the intermittency of renewable energy systems, a sizing and scheduling model is proposed for a finite number of static electric loads. The model objective is to maximize solar energy utilization with and without storage. For the application of optimal load size selection, the energy production of a solar photovoltaic is assumed to be consumed by a finite number of discrete loads in an off-grid system using mixed-integer linear programming. Additional constraints are battery charge and discharge limitations and minimum uptime and downtime for each unit. For a certain solar power profile the model outputs optimal unit size as well as the optimal scheduling for both units and battery charge and discharge (if applicable). The impact of different solar power profiles and minimum up and down time constraints on the optimal unit and battery sizes are studied. The battery size required to achieve full solar energy utilization decreases with the number of units and with increased flexibility of the units (shorter on and off-time). A novel formulation is introduced to model quasi-dynamic units that gradually start and stop and the quasi-dynamic units increase solar energy utilization. The model can also be applied to search for the optimal number of units for a given cost function.

Considering the intermittency of renewable energy systems, a sizing and scheduling model is proposed for a finite number of static electric loads. The model objective is to maximize solar energy utilization with and without storage. For the application of optimal load size selection, the energy production of a solar photovoltaic is assumed to be consumed by a finite number of discrete loads in an off-grid system using mixed-integer linear programming. Additional constraints are battery charge and discharge limitations and minimum uptime and downtime for each unit. For a certain solar power profile the model outputs optimal unit size as well as the optimal scheduling for both units and battery charge and discharge (if applicable). The impact of different solar power profiles and minimum up and down time constraints on the optimal unit and battery sizes are studied. The battery size required to achieve full solar energy utilization decreases with the number of units and with increased flexibility of the units (shorter on and off-time). A novel formulation is introduced to model quasi-dynamic units that gradually start and stop and the quasi-dynamic units increase solar energy utilization. The model can also be applied to search for the optimal number of units for a given cost function.

Considering the intermittency of renewable energy systems, a sizing and scheduling model is proposed for a finite number of static electric loads. The model objective is to maximize solar energy utilization with and without storage. For the application of optimal load size selection, the energy production of a solar photovoltaic is assumed to be consumed by a finite number of discrete loads in an off-grid system using mixed-integer linear programming. Additional constraints are battery charge and discharge limitations and minimum uptime and downtime for each unit. For a certain solar power profile the model outputs optimal unit size as well as the optimal scheduling for both units and battery charge and discharge (if applicable). The impact of different solar power profiles and minimum up and down time constraints on the optimal unit and battery sizes are studied. The battery size required to achieve full solar energy utilization decreases with the number of units and with increased flexibility of the units (shorter on and off-time). A novel formulation is introduced to model quasi-dynamic units that gradually start and stop and the quasi-dynamic units increase solar energy utilization. The model can also be applied to search for the optimal number of units for a given cost function.

This dissertation considers optimization problems in which similar decisions need to be made repeatedly over many successive periods. These problems have wide applications including manpower planning, scheduling, production planning and control, capacity expansion, and equipment replacement/modemization. In reality these decision problems usually extend over an indeterminate horizon, but it is common practice to model them using a finite horizon. Unfortunately, an artificial finite horizon may adversely influence optimal decisions, a difficulty commonly referred to as the end effects problem. Past research into end effects has focused on theoretical issues associated with solving (or approximately solving) infinite-horizon extensions of finite-horizon problems. This dissertation derives equivalent finite-horizon formulations for a small class of infinite-horizon problem structures. For a larger class of problems, it also develops finite-horizon approximations which bound the infinite- horizon optimal solution, thereby quantifying the influence of end effects. For linear programs, extensions of these approximations quantify the end effects of fixed initial period decisions over a functional range of future infinite-horizon conditions.

We consider the following problem: Given a rational matrix $A \in \setQ^{m \times n}$ and a rational polyhedron $Q \subseteq\setR^{m+p}$, decide if for all vectors $b \in \setR^m$, for which there exists an integral $z \in \setZ^p$ such that $(b, z) \in Q$, the system of linear inequalities $A x \leq b$ has an integral solution. We show that there exists an algorithm that solves this problem in polynomial time if $p$ and $n$ are fixed. This extends a result of Kannan (1990) who established such an algorithm for the case when, in addition to $p$ and $n$, the affine dimension of $Q$ is fixed. As an application of this result, we describe an algorithm to find the maximum difference between the optimum values of an integer program $\max \{c x : A x \leq b, x \in \setZ^n \}$ and its linear programming relaxation over all right-hand sides $b$, for which the integer program is feasible. The algorithm is polynomial if $n$ is fixed. This is an extension of a recent result of Ho\c{s}ten and Sturmfels (2003) who presented such an algorithm for integer programs in standard form.

We consider the following problem: Given a rational matrix $A \in \setQ^{m \times n}$ and a rational polyhedron $Q \subseteq\setR^{m+p}$, decide if for all vectors $b \in \setR^m$, for which there exists an integral $z \in \setZ^p$ such that $(b, z) \in Q$, the system of linear inequalities $A x \leq b$ has an integral solution. We show that there exists an algorithm that solves this problem in polynomial time if $p$ and $n$ are fixed. This extends a result of Kannan (1990) who established such an algorithm for the case when, in addition to $p$ and $n$, the affine dimension of $Q$ is fixed. As an application of this result, we describe an algorithm to find the maximum difference between the optimum values of an integer program $\max \{c x : A x \leq b, x \in \setZ^n \}$ and its linear programming relaxation over all right-hand sides $b$, for which the integer program is feasible. The algorithm is polynomial if $n$ is fixed. This is an extension of a recent result of Ho\c{s}ten and Sturmfels (2003) who presented such an algorithm for integer programs in standard form.

"NPS-55-82-009"--Cover

"NPS-55-82-009"--Cover

"NPS-55-82-009"--Cover

The Defense Language Institute (DLI) offers 23 beginning language courses and in 2004 began to provide a smaller class size for these courses. Restrictions on when classes can begin and a limited number of instructors prevent all students from being trained in a smaller class. This thesis develops integer linear programs (ILPs) that generate schedules for all student classes and maximize the number of smaller class starts for a given number of instructors. Secondary scheduling goals include avoiding weekly changes to instructor levels and scheduling preferences such as the number of classes to start simultaneously. The ILPs solve in less than one minute and offer a significant improvement in the number of students that may be trained in the smaller class size. Computational results using real data for the Arabic, Chinese-Mandarin, and Persian-Farsi courses verify the ILPs find feasible multiyear schedules that incorporate the DLI's scheduling preferences while exceeding the DLI's published schedule results. For example, the ILPs find schedules for Arabic that train 8%, 34% and 76% of students in the smaller class in 2006, 2007, and 2008, whereas DLI's manual schedules at best can train 8%, 7% and 64%.

Advances in the field of integer programming have recently been made by Young and Glover, who have developed primal all integer integer programming alorithms. It is the purpose of this paper to gain computational experience and suggest techniques to improve the efficiency of the algorithm. A first phase procedure is developed to obtain an initial feasible integer solution.

Slides used for group presentation.

Slides used for group presentation.

Slides used for group presentation.

Slides used for group presentation.

In recent years, the embedding approach for switched optimal control problems has been developed in a series of papers. However, the embedding approach, which advantageously converts the hybrid optimal control problem to a classical nonlinear optimization, has not been extensively compared to alternative approaches. The goal of this paper is thus to compare the embedding approach to multi-parametric programming, mixed-integer programming, gradient-descent based methods, and CPLEX in the context of five recently published examples. A sixth example, an autonomous switched 11-region linear system, is used to compare a hybrid minimum principle method and traditional numerical programming. For a given performance index for each case, cost and solution times are presented. It is shown that there are numerical advantages of the embedding approach: lower performance index cost (except in some instances when autonomous switches are present), generally faster solution time, and convergence to a solution when other methods may fail. In addition, the embedding method requires no ad hoc assumptions (e.g., predetermined mode sequences) or specialized control models. Theoretical advantages of the embedding approach over the other methods are also described: guaranteed existence of a solution under mild conditions, convexity of the embedded hybrid optimization problem (under the customary conditions on the performance index), solvability with traditional techniques (e.g., sequential quadratic programming) avoiding the combinatorial complexity in the number of modes/discrete variables of mixed-integer programming, applicability to affine nonlinear systems, and no need to explicitly assign discrete/mode variables to autonomous switches.

Inspired by a paper of R. W. Rosenthal, we investigate generalized Nash-equilibria of integer programming games. We show that generalized Nash-equilibria always exist and are related to an optimal solution of a so-called N-fold integer program. This link allows us to establish some polynomial time complexity results about solving this optimization problem and its inverse counter-part.

This paper addresses the single-item single-stocking location stochastic lot sizing problem under the $(s, S) $ policy. We first present a mixed integer non-linear programming (MINLP) formulation for determining near-optimal $(s, S)$ policy parameters. To tackle larger instances, we then combine the previously introduced MINLP model and a binary search approach. These models can be reformulated as mixed integer linear programming (MILP) models which can be easily implemented and solved by using off-the-shelf optimisation software. Computational experiments demonstrate that optimality gaps of these models are around $0.3\%$ of the optimal policy cost and computational times are reasonable.

Lecture from a Business Mathematics course (2005 - 6) by KIT

This research develops a mixed integer linear programming (MILP) model that considers simultaneously both the traditional reservoir rule curves and the hedging rules to manage and operate a multipurpose, multireservoir system. During normal periods of operation, when inflows are plentiful, this optimization model efficiently distributes the available stored water from different reservoirs to meet the planned demands imposed by competing users. However, during periods of drought, or when anticipating a drought, the planned demands cannot be fully met, and a water shortage occurs. By considering the hedging rules along with the rule curves, guidelines are provided for reservoir releases. To minimize the impact of drought, the hedging rules effectively reduce the ongoing water supply to balance with the target storage requirement. The MILP model is applied to a multireservoir system in the southern region of Taiwan, where the results obtained demonstrate the applicability and utility of the model. Read More: http://ascelibrary.org/action/showAbstract?page=86&volume=129&issue=2&journalCode=jwrmd5

Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In 2014, Mnich and Wiese initiated a systematic study in this direction. In this paper we continue this study and show that several additional cases of fundamental scheduling problems are fixed parameter tractable for some natural parameters. Our main tool is n-fold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique. Specifically, we show the following four scheduling problems to be fixed-parameter tractable, where p max is the maximum processing time of a job and w max is the maximum weight of a job: - Makespan minimization on uniformly related machines $(Q||C_{max} )$ parameterized by $p_{max}$, - Makespan minimization on unrelated machines $(R||C_{max} )$ parameterized by $p_{max}$ and the number of kinds of machines, - Sum of weighted completion times minimization on unrelated machines $(R|| \sum w_i C_i )$ parameterized by $p_{max} + w_{max}$ and the number of kinds of machines, - The same problem, $(R|| \sum w_i C_i),$ parameterized by the number of distinct job times and the number of machines.

This paper presents Multi-Objective Integer Non-Linear Programming (MOINLP) involving Negative Total Float (NTF) for improving the basic model of Multi-Objective Programming (MOP) in case the optimization of the additional cost for Project Scheduling Compression (PSC). Using the basic MOP to solve the more complex problems is a challenging task. We suspect that Negative Total Float (NTF) having an indication to make the basic MOP to solve the more general case, both simple and complex of PSC. The purpose of this research is identifying the conflicting objectives in PSC problem using NTF and improving MOINLP by involving the NTF parameter to solve the PSC problem. The Solver Application, which is an add-in of MS Excel, is used to perform optimization process to the model developed. The results show that NTF has an important role to identify the conflicting objectives in PSC. We define NTF is an automatic maximum value of the activity duration reduction to achieve due date of PSC. Furthermore, the use of NTF as a constraint in MOINLP can solve the more general case for both simple and complex PSC problem. Base on the condition, we state that the basic MOP is still significant to solve the PSC complex problems using MOINLP as a sophisticated MOP technique. 

This paper presents Multi-Objective Integer Non-Linear Programming (MOINLP) involving Negative Total Float (NTF) for improving the basic model of Multi-Objective Programming (MOP) in case the optimization of the additional cost for Project Scheduling Compression (PSC). Using the basic MOP to solve the more complex problems is a challenging task. We suspect that Negative Total Float (NTF) having an indication to make the basic MOP to solve the more general case, both simple and complex of PSC. The purpose of this research is identifying the conflicting objectives in PSC problem using NTF and improving MOINLP by involving the NTF parameter to solve the PSC problem. The Solver Application, which is an add-in of MS Excel, is used to perform optimization process to the model developed. The results show that NTF has an important role to identify the conflicting objectives in PSC. We define NTF is an automatic maximum value of the activity duration reduction to achieve due date of PSC. Furthermore, the use of NTF as a constraint in MOINLP can solve the more general case for both simple and complex PSC problem. Base on the condition, we state that the basic MOP is still significant to solve the PSC complex problems using MOINLP as a sophisticated MOP technique. 

Thesis advisor, Richard E. Rosenthal

Thesis advisor, Richard E. Rosenthal

In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma, Ahmed and Nemhauser (2008) and Hijazi, Bonami and Ouorou (2013) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.

A nonlinear integer programming model for expanding the transportation system of an underdeveloped country is presented. The model uses integer 0-1 decision variables. The basic model has linear constraints and a nonlinear objective function. Some special situations and extensions to the model are presented. The benefits being maximized in the objective function are discussed, as are the problems of parameterization and suboptimization. A solution procedure for the model is suggested, but an efficient algorithm is not available for solving the model. Some areas for future research are also suggested.

To obtain a better understanding of the trade-offs between various objectives, Bi-Objective Integer Programming (BOIP) algorithms calculate the set of all non-dominated vectors and present these as the solution to a BOIP problem. Historically, these algorithms have been compared in terms of the number of single-objective IPs solved and total CPU time taken to produce the solution to a problem. This is equitable, as researchers can often have access to widely differing amounts of computing power. However, the real world has recently seen a large uptake of multi-core processors in computers, laptops, tablets and even mobile phones. With this in mind, we look at how to best utilise parallel processing to improve the elapsed time of optimisation algorithms. We present two methods of parallelising the recursive algorithm presented by Ozlen, Burton and MacRae. Both new methods utilise two threads and improve running times. One of the new methods, the Meeting algorithm, halves running time to achieve near-perfect parallelisation. The results are compared with the efficiency of parallelisation within the commercial IP solver IBM ILOG CPLEX, and the new methods are both shown to perform better.

To obtain a better understanding of the trade-offs between various objectives, Bi-Objective Integer Programming (BOIP) algorithms calculate the set of all non-dominated vectors and present these as the solution to a BOIP problem. Historically, these algorithms have been compared in terms of the number of single-objective IPs solved and total CPU time taken to produce the solution to a problem. This is equitable, as researchers can often have access to widely differing amounts of computing power. However, the real world has recently seen a large uptake of multi-core processors in computers, laptops, tablets and even mobile phones. With this in mind, we look at how to best utilise parallel processing to improve the elapsed time of optimisation algorithms. We present two methods of parallelising the recursive algorithm presented by Ozlen, Burton and MacRae. Both new methods utilise two threads and improve running times. One of the new methods, the Meeting algorithm, halves running time to achieve near-perfect parallelisation. The results are compared with the efficiency of parallelisation within the commercial IP solver IBM ILOG CPLEX, and the new methods are both shown to perform better.

In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed {\em n-fold integer programming problems} are polynomial time solvable. Our proof involves two heavy ingredients discovered recently: the equivalence of linear optimization and so-called directed augmentation, and the stabilization of certain Graver bases. We discuss several applications of our algorithm to multiway transportation problems and to packing problems. One important consequence of our results is a polynomial time algorithm for the $d$-dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting stock problem.

In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed {\em n-fold integer programming problems} are polynomial time solvable. Our proof involves two heavy ingredients discovered recently: the equivalence of linear optimization and so-called directed augmentation, and the stabilization of certain Graver bases. We discuss several applications of our algorithm to multiway transportation problems and to packing problems. One important consequence of our results is a polynomial time algorithm for the $d$-dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting stock problem.