Subadditive approaches in integer programming

Linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory has been developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We present computational experiments, which show that the new algorithm is tractable.     

Integer programming, Barvinok's counting algorithm and Gomory relaxations

We propose an algorithm based on Barvinok's counting algorithm for . It runs in time polynomial in the input size of when n is fixed, and under a condition on c, provides the optimal value of . We also relate Barvinok's counting formula and Gomory relaxations.     

Integer programming models for the q-mode problem

The q-mode problem is a combinatorial optimization problem that requires partitioning of objects into clusters. We discuss theoretical properties of an existing mixed integer programming (MIP) model for this problem and offer alternative models and enhancements. Through a comprehensive experiment we investigate computational properties of these MIP models. This experiment reveals that, in practice, the MIP approach is more effective for instances containing strong natural clusters and it is not as effective for instances containing weak natural clusters. The experiment also reveals that one of the MIP models that we propose is more effective than the other models for solving larger instances of the problem.     

Integer linear programming models for grid-based light post location problem

Selecting optimal location is a key decision problem in business and engineering. This research focuses to develop mathematical models for a special type of location problems called grid-based location problems. It uses a real-world problem of placing lights in a park to minimize the amount of darkness and excess supply. The non-linear nature of the supply function (arising from the light physics) and heterogeneous demand distribution make this decision problem truly intractable to solve. We develop ILP models that are designed to provide the optimal solution for the light post problem: the total number of light posts, the location of each light post, and their capacities (i.e., brightness). Finally, the ILP models are implemented within a standard modeling language and solved with the CPLEX solver. Results show that the ILP models are quite efficient in solving moderately sized problems with a very small optimality gap.     

整数规划的渐进强对偶方法

虽然整数规划中经典的Lagrange对偶方法是一个有效的方法，但是由于对偶缝隙的原因它经常不能求出原问题的最优解。该文提出一个用于有界整数规划的指数对偶公式。此公式具有渐进强对偶的特性并且可以保证找到原问题的最优解。它的另一个特性是当参数选择的合适时不需要进行实际的对偶搜索。     

Integer programming approach to reactive scheduling in make-to-order manufacturing

New algorithms based on mixed integer programming formulations are proposed for reactive scheduling in a dynamic, make-to-order manufacturing environment. The problem objective is to update a long-term production schedule subject to service level and inventory constraints, whenever the customer orders are modified or new orders arrive. Different rescheduling policies are proposed, from a total reschedule of all remaining and unmodified customer orders to a non-reschedule of all such orders. In addition, a medium restrictive policy is considered for rescheduling only a subset of remaining customer orders awaiting material supplies. Numerical examples modeled after a real-world scheduling/rescheduling of customer orders in the electronics industry are presented and some results of computational experiments are reported.     

Integer programming duality: Price functions and sensitivity analysis

Recently a duality theory for integer programming has been developed. Here we examine some of the economic implications of this theory, in particular the necessity of using price functions in place of prices, and the possibility of carrying out sensitivity analysis of optimal solutions. In addition we consider the form of price functions that are generated by known algorithms for integer programming.This research was supported in part by a Senior Visiting Research Fellowship from the Science Research Council at the London School of Economics while the author was on leave from CORE, Université Catholique de Louvain, at Louvain-la-Neuve.     

Integer linear programming formulation of the material requirements planning problem

Lot sizing procedures for discrete and dynamic demand form a distinct class of inventory control problems, usually referred to asmaterial requirements planning. A general integer programming formulation is presented, covering an extensive range of problems: single-item, multi-item, and multi-level optimization; conditions on lot sizes and time phasing; conditions on storage and production capacities; and changes in production and storage costs per unit. The formulation serves as a uniform framework for presenting a problem and a starting point for developing and evaluating heuristic and tailor-made optimum-seeking techniques.     

Homogeneous programming

A duality theorem for homogeneous programming was established by Eisenberg. The purpose of this paper is to present another duality theory for a class of homogeneous programming. Our proof is simple and self contained.     

约束全局整数规划问题的填充函数法

本文给出了一类新的求解箱约束全局整数规划问题的填充函数，并讨论了其填充性质．基于提出的填充函数，设计了一个求解带等式约束、不等式约束、及箱约束的全局整数规划问题的算法．初步的数值试验结果表明提出的算法是可行的。     

Integer linear programming models for topology optimization in sheet metal design

The process of designing new industrial products is in many cases solely based on the intuition and experience of the responsible design engineer. The aid of computers is restricted to visualization and manual manipulation tools. We demonstrate that the design process for conduits, which are made out of sheet metal plates, can be supported by mathematical optimization models and solution techniques, leading to challenging optimization problems. The design goal is to find a topology that consists of several channels with a given cross section area using a minimum amount of sheet metal and, at the same time, maximizing its stiffness. We consider a mixed integer linear programming model to describe the topology of two dimensional slices of a three dimensional sheet metal product. We give different model formulations, based on cuts and on multicommodity flows. Numerical results for various test instances are presented.     

Integer programming models for hierarchical workforce scheduling problems including excess off-days and idle labour times

The decision problem considered in this paper is a hierarchical workforce scheduling problem in which a higher qualified worker can substitute for a lower qualified one, but not vice versa, labour requirements may vary, and each worker must receive n off-days a week. Within this context, five mathematical models are discussed. The first two of these five models are previously published. Both of them are for the case where the work is indivisible. The remaining three models are developed by the authors of this paper. One of these new models is for the case where the work is indivisible and the other two are for the case where the work is divisible. The three new models are proposed with the purpose of removing the shortcomings of the previously published two models. All of the five models are applied on the same illustrative example. Additionally, a total of 108 test problems are solved within the context of two computational experiments.     

On a class of iterative projection and contraction methods for linear programming

In this paper, based on the idea of a projection and contraction method for a class of linear complementarity problems (Refs. 1 and 2), we develop a class of iterative algorithms for linear programming with linear speed of convergence. The algorithms are used to solve transportation and network problems with up to 10,000 variables. Our experiments indicate that the algorithms are simple, easy to parallelize, and more efficient for some large practical problems.This research was done while the author was visiting the Department of Mathematics at the University of Würzburg, Würzburg, Germany.     

Exact Penalty Function and Asymptotic Strong Nonlinear Duality in Integer Programming

In this paper,a logarithmic-exponential penalty function with two parameters for integer program-ming is discussed.We obtain the exact penalty properties and then establish the asymptotic strong nonlinearduality in the corresponding logarithmic-exponential dual formulation by using the obtained exact penaltyproperties.The discussion is based on the logarithmic-exponential nonlinear dual formulation proposed in [6].     

An integer linear programming approach for bilinear integer programming

We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems.     

Some relationships between lagrangian and surrogate duality in integer programming

Lagrangian dual approaches have been employed successfully in a number of integer programming situations to provide bounds for branch-and-bound procedures. This paper investigates some relationship between bounds obtained from lagrangian duals and those derived from the lesser known, but theoretically more powerful surrogate duals. A generalization of Geoffrion's integrality property, some complementary slackness relationships between optimal solutions, and some empirical results are presented and used to argue for the relative value of surrogate duals in integer programming. These and other results are then shown to lead naturally to a two-phase algorithm which optimizes first the computationally easier lagrangian dual and then the surrogate dual.     

Smoothed analysis of integer programming

We present a probabilistic analysis of integer linear programs (ILPs). More specifically, we study ILPs in a so-called smoothed analysis in which it is assumed that first an adversary specifies the coefficients of an integer program and then (some of) these coefficients are randomly perturbed, e.g., using a Gaussian or a uniform distribution with small standard deviation. In this probabilistic model, we investigate structural properties of ILPs and apply them to the analysis of algorithms. For example, we prove a lower bound on the slack of the optimal solution. As a result of our analysis, we are able to specify the smoothed complexity of classes of ILPs in terms of their worst case complexity. This way, we obtain polynomial smoothed complexity for packing and covering problems with any fixed number of constraints. Previous results of this kind were restricted to the case of binary programs.      

Pseudo-invexity and duality in nonlinear programming

The purpose of this paper is to study various duality results in nonlinear programming for pseudo-invex functions. Such results were known in the literature for invex functions.     

Evaluating mixed-integer programming models over multiple right-hand sides

A critical measure of model quality for a mixed-integer program (MIP) is the difference, or gap, between its optimal objective value and that of its linear programming relaxation. In some cases, the right-hand side is not known exactly; however, there is no consensus metric for evaluating a MIP model when considering multiple right-hand sides. In this paper, we provide model formulations for the expectation and extrema of absolute and relative MIP gap functions over finite discrete sets.