Search

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

In this paper, we address an instance of the dynamic capacitated multi-item lot-sizing problem (CMILSP) typically encountered in steel rolling mills. Production planning is carried out at the master production schedule level, where the various end items lot sizes are determined such that the total cost is minimised. Through incorporating the various technological constraints associated with the manufacturing process, the integrated production-inventory problem is formulated as a mixed integer bilinear program (MIBLP). Typically, such class of mathematical models is solved via linearisation techniques which transform the model to an equivalent MILP (mixed integer linear program) at the expense of increased model dimensionality. This paper presents an alternative branch-and-bound based algorithm that exploits the special structure of the mathematical model to minimise the number of branches and obtain the bound at each node. The performance of our algorithm is benchmarked against that of a classical linearisation technique for several problem instances and the obtained results are reported. [ABSTRACT FROM AUTHOR]

The problem of optimal flow production planning at the operational scheduling stage is being studied, using the example of the out-of-furnace department of a converter-based steel-making production in the iron metallurgy industry. To solve this problem, a linear integer programming model is proposed, which fully describes the specifics of the investigated technological processes. A major advantage of this approach is its scalability for solving related optimization problems in the industry of plant logistics, as well as flexibility in adapting to changes and fine-tuning the system of constraints and objective function. The software implementation of the developed model forms the basis of the operational scheduling module of the optimal flow production planning system, which is used for a large-scale computational experiment on real-world data. [ABSTRACT FROM AUTHOR]

This paper studies the single-hoist cyclic scheduling problem in electroplating systems with two extended features. One extension is that the products must visit some processing tanks more than once (multi-function tanks). Another is that more than one identical tank is used at some stages. These extensions are common in practical electroplating lines and can increase the lines' processing capacity. However, they make the hoist scheduling problem more complicated and little research has been done to optimize the hoist moves in such extended practical systems. In this paper, we develop a comprehensive mixed integer linear programming model to find optimal solutions to the single-hoist cyclic scheduling problem for electroplating lines with these extensions. Examples are given to demonstrate the effectiveness of the model in different types of problems. [ABSTRACT FROM AUTHOR]

This paper presents an integer linear programming formulation for the problem of extracting a subset of stimuli from a confusion matrix. The objective is to select stimuli such that total confusion among the stimuli is minimized for a particular subset size. This formulation provides a drastic reduction in the number of variables and constraints relative to a previously proposed formulation for the same problem. An extension of the formulation is provided for a biobjective problem that considers both confusion and recognition in the objective function. Demonstrations using an empirical interletter confusion matrix from the psychological literature revealed that a commercial branch-and-bound integer programming code was always able to identify optimal solutions for both the single-objective and biobjective formulations within a matter of seconds. A further extension and demonstration of the model is provided for the extraction of multiple subsets of stimuli, wherein the objectives are to maximize similarity within subsets and minimize similarity between subsets. [ABSTRACT FROM AUTHOR]

At the heart of van der Linden's approach to automated test assembly ( ATA) is a linear programming/integer programming ( LP/ IP) problem. A variety of IP solvers are available, ranging in cost from free to hundreds of thousands of dollars. In this paper, I compare several approaches to solving the underlying IP problem. These approaches range from traditional computer programming, through LP/ IP-specific modeling languages, to plug-ins for common software such as Excel. The features of several of the major IP solvers are briefly reviewed, describing which of the features are more or less useful in the context of ATA. The appendices include a list of resources that I have found particularly useful. [ABSTRACT FROM AUTHOR]

The optimum coupon schedule for serial bonds issued by municipalities has been solved as a knapsack problem, and is widely implemented in bank and nonbank underwriting firms. A large subset of issues carries the additional requirement that limits the number of distinct coupons which the underwriters may assign to the issue. The paper formulates this problem as a dynamic programming model and discusses the computational aspects relating to this formulation by comparing it with a direct 0/1 integer programming model. Some computational experience is also provided. [ABSTRACT FROM AUTHOR]

This paper introduces two new one-dimensional cutting stock models: the generalized assortment problem (GAP) and the best cutting stock length (BSL) problem. These new models provide the potential to reduce waste to values lower than the optimum of current models, under the right management circumstances. In the GAP, management has a standard length and can select one or more of any additional custom stock lengths, and management wishes to minimize cutting stock waste. This model is different from existing models that assume that the selection is from a small fixed set of stock lengths. In the BSL problem, management chooses any number of custom stock lengths, but wishes to find the fewest custom stock lengths in order to have zero waste. Results show waste reductions of 80% with just one custom stock length compared with solutions from standard cutting stock formulations, when item lengths are long relative to the stock length. The models are most effective when the item lengths are nearly as long as the stock length. Solutions from the model have been implemented for a manufacturer. The model is easily generalized to allow multiple existing stock lengths and different costs. [ABSTRACT FROM AUTHOR]

Highlights • A new rigorous bilevel decomposition strategy for MILPs with strong linking constraints. • An extended cross decomposition method based on the bilevel decomposition strategy. • Application of the extended cross decomposition method to stochastic programming with CVaR constraints. • Case studies with a variety of scenario instances showing significant computational advantages of the proposed methods. Abstract Large-scale mixed-integer linear programming (MILP) problems, such as those from two-stage stochastic programming, usually have a decomposable structure that can be exploited to design efficient optimization methods. Classical Benders decomposition can solve MILPs with weak linking constraints (which are decomposable when linking variables are fixed) but not strong linking constraints (which are not decomposable even when linking variables are fixed). In this paper, we first propose a new rigorous bilevel decomposition strategy for solving MILPs with strong and weak linking constraints, then extend a recently developed cross decomposition method based on this strategy. We also show how to apply the extended cross decomposition method to two-stage stochastic programming problems with conditional-value-at-risk (CVaR) constraints. In the case studies, we demonstrate the significant computational advantage of the proposed extended cross decomposition method as well as the benefit of including CVaR constraints in stochastic programming. [ABSTRACT FROM AUTHOR]

Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically be solved in a reasonable amount of computing time. [ABSTRACT FROM AUTHOR]

As applied to mixed-integer programming, Benders' original work made two primary contributions: (1) development of a "pure integer" problem (Problem P) that is equivalent to the original mixed-integer problem, and (2) a relaxation algorithm for solving Problem P that works iteratively on an LP problem and a "pure integer" problem. In this paper a modified algorithm for solving Problem P is proposed, in which the solution of a sequence of integer programs is replaced by the solution of a sequence of linear programs plus some (hopefully few) integer programs. The modified algorithm will still allow for taking advantage of any special structures (e.g. an LP subproblem that is a "network problem") just as in Benders' original algorithm. The modified Benders' algorithm is explained and limited computational results are given. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of integrating the analysis of timber management, forest road building and maintenance, and transporting logs. The aim of such analysis is to provide tools for the decisionmaking process in long-range forest planning. A mixed integer linear programming model is developed to maximize discounted revenues from the sale of timber net of road construction and maintenance, timber management, and transport costs. The main complexity of this model, which precludes a straightforward formulation, arises from the need to gain access to an area before it can be managed. Artificial variables and relations are introduced to avoid an unmanageably large number of 0-1 integer variables. [ABSTRACT FROM AUTHOR]

In this paper we are concerned with imposing constraints directly on the admissible majority decisions so as to insure transitivity without restricting individual preference orderings. We demonstrate that this corresponds to requiring that majority decisions be confined to the extreme points of a convex polyhedron. Thus, transitive majority decisions can be characterized as basic solutions of a set of linear inequalities. Through the use of a majority decision function (which is not restricted to be linear) it is shown that constrained majority rule is equivalent to an integer programming problem. Some special forms of majority decision functions are studied ineluding the generalized lp norm and an indicator function. Implications of an integer programming solution, including alternate optima and post optimality analysis, are also discussed. [ABSTRACT FROM AUTHOR]

It has been established that integer programs with integral, recursive constraint matrices have integral extreme points for integral, nonnegative requirement vectors. In this paper, it is first shown that the assignment problem can be transformed to such a program, but with upper bounds on some variables. This equivalent program leads to additional results for solving the assignment problem. Algorithms are then delineated to transform matching, covering and travelling salesman problems to equivalent recursive programs of the aforementioned type, but with bounds on some variables. These results are extended to programs with special structure in their constraint matrices. [ABSTRACT FROM AUTHOR]

This article comments on the research paper "Management Decision and Integer Programming," which was used to illustrate the dangers of attempting to round a linear programming solution to obtain an integer answer. A number of examples have appeared in the literature to illustrate the dangers of rounding, the example in the paper is the only one that is not only small and easily understood but which illustrates a practical problem, contains a large number of rounding alternatives, and cannot be rounded to an optimal integer solution. By contrast, the previous examples which share property have been "textbook cases" involving few rounding possibilities, and thus may reasonably be questioned as to whether they truly illustrate that rounding can constitute a serious computational impediment in the real world. Nevertheless, it remains true that there are ways to round the LP solution to a feasible integer solution.

The optimal coupon schedule for municipal bonds with limits on the number of distinct coupons is formulated in terms of two different dynamic programming models which, in contrast to the companion paper, do guarantee an optimal solution, although at the cost of additional computational difficulty. [ABSTRACT FROM AUTHOR]

This article discusses two linear programming models used in capital budgeting. Many real-world optimization problems have the property that optimal decisions must be stated in terms of integers or whole numbers. This is the case, for example, in capital budgeting models where the integer 0 means that one does not undertake a project and the integer 1 indicates that one does. A model for many such problems is that of integer programming. The two models include a linear programming model without integer restrictions and the other the same linear programming model but with integer restrictions on the decision variables. The former, which is an approximation, is referred as the LP model, and the latter is referred as the IP model. There is no way to round an LP optimal solution to get an optimal solution to the IP model.

A recent article described a mathematical programming model and heuristic solution procedure to realign sales territories. This report presents two linear integer programming models for sales territory alignment to maximize profit. Emphasis is placed on the development of models which are easy to implement. [ABSTRACT FROM AUTHOR]

We give a branch-and-cut algorithm for finding the minimum distance of a binary linear block code. We give two integer programming (IP) models and study the convex hull of the single constraint relaxation of these IP models. We use the new inequalities as cuts in a branch-and-cut scheme. Finally, we report computational results based on turbo and low density parity check (LDPC) codes that demonstrate the effectiveness of our cuts. We demonstrate that our IP formulation and specific cuts are efficient tools for determining the minimum distance of moderate size linear block codes, specifically, they are very efficient for LDPC codes, and provide us with an additional tool for solving this important problem. [ABSTRACT FROM AUTHOR]

We apply to fixed charge network flow (FCNF) problems a general hybrid solution method that combines constraint programming and linear programming. FCNF problems test the hybrid approach on problems that are already rather well suited for a classical 0-1 model. They are solved by means of a global constraint that generates specialized constraint propagation algorithms and a projected relaxation that can be rapidly solved as a minimum cost network flow problem. The hybrid approach ran about twice as fast as a commercial mixed integer programming code on fixed charge transportation problems with its advantage increasing with problem size. For general fixed charge transshipment problems, however, it has no effect because the implemented propagation methods are weak. [ABSTRACT FROM AUTHOR]

A new hierarchy of relaxations is presented that provides a unifying framework for constructing a spectrum of continuous relaxations spanning from the linear programming relaxation to the convex hull representation for linear mixed integer 0-1 problems. This hierarchy is an extension of the Reformulation-Linearization Technique (RLT) of Sherali and Adams (1990, 1994a), and is particularly designed to exploit special structures. Specifically, inherent special structures are exploited by identifying particular classes of multiplicative factors that are applied to the original problem to reformulate it as an equivalent polynomial programming problem, and subsequently, this resulting problem is linearized to produce a tighter relaxation in a higher dimensional space. This general framework permits us to generate an explicit hierarchical sequence of tighter relaxations leading up to the convex hull representation. (A similar hierarchy can be constructed for polynomial mixed integer 0-1 problems.) Additional ideas for further strengthening RLT-based constraints by using conditional logical implications, as well as relationships with sequential lifting, are also explored. Several examples are presented to demonstrate how underlying special structures, including generalized and variable upper bounding, covering, partitioning, and packing constraints, as well as sparsity, can be exploited within this framework. For some types of structures, low level relaxations are exhibited to recover the convex hull of integer feasible solutions. [ABSTRACT FROM AUTHOR]

We describe a practical procedure for finding all solutions to a parametric family of nonseparable quadratic integer programs that differ in their resource availabilities. We outline a new method for optimizing these quadratic integer programs, and demonstrate how to solve a sequence of such problems parametrized against the right-hand-side of a single constraint. Several methods for accelerating the basic procedure are presented, and computational experience is provided. [ABSTRACT FROM AUTHOR]

Some easy postoptimality analysis for zero-one programming is developed. First, a procedure is presented for obtaining a set K of 0-1 solutions whose objective function values are within a specified tolerance of the optimum. Then sufficiency conditions for K to contain the optimum of a revised problem are derived. Computational experience with a number of test problems indicates that K can be economically obtained and that the sufficiency tests provide a significant postoptimization capability. [ABSTRACT FROM AUTHOR]

The early work done on the assortment problem assumed known demands and additive and proportional substitution cost functions for single period problems. The extension of this problem (to consider probabilistic demands and multiple periods) complicates the problem considerably. By making some assumptions about the pattern of demands and the form of a reasonable solution, the problem can be approached by using dynamic programming thus finding the shortest route through a network. [ABSTRACT FROM AUTHOR]

The usefulness of group theoretic methods in solving integer programming (IP) problems is extended by procedures for controlling the size of the groups. The main procedure given shows how an optimal linear programming basis can be altered to reduce the magnitude of its determinant thereby reducing the size of the group induced by the basis. An adaption of Benders' mixed IP algorithm is given which uses these methods. Some limited computational experience is given. [ABSTRACT FROM AUTHOR]

In this report, twenty-nine integer linear programming problems, ranging from very simple to apparently rather difficult, are introduced. The results of running these problems on four different computer codes, involving five distinct algorithms, are presented as both time and iteration data. A brief description of the codes used is also included. [ABSTRACT FROM AUTHOR]

This article presents comments from the author on the article "Preferences, Summations, and Social Welfare Function," by P. C. Fishburn. The author demonstrates the use of specific mathematical functions to solve a linear programming problem. The article presents the condition for the summable integer in the existence of real valued functions. Mathematical models extending Fishburn's analysis are presented and expanded upon, as well as the mathematical assumptions necessary to utilized this computational method.

An integer programming formulation for the problem of sequencing jobs on a single machine to minimize the number of late jobs is developed. The structure of the formulation is exploited to obtain the easily stated algorithm (previously developed by Moore [5]) for the solution of the problem and then to compare it to other similar allocation problems, among which is the Knapsack problem. [ABSTRACT FROM AUTHOR]