A note on duality in disjunctive programming

We state a duality theorem for disjunctive programming, which generalizes to this class of problems the corresponding result for linear programming.This work was supported by the National Science Foundation under Grant No. MPS73-08534 A02 and by the US Office of Naval Research under Contract No. N00014-75-C-0621-NR047-048.     

A discussion of scalarization techniques for multiple objective integer programming

In this paper we consider solution methods for multiobjective integer programming (MOIP) problems based on scalarization. We define the MOIP, discuss some common scalarizations, and provide a general formulation that encompasses most scalarizations that have been applied in the MOIP context as special cases. We show that these methods suffer some drawbacks by either only being able to find supported efficient solutions or introducing constraints that can make the computational effort to solve the scalarization prohibitive. We show that Lagrangian duality applied to the general scalarization does not remedy the situation. We also introduce a new scalarization technique, the method of elastic constraints, which is shown to be able to find all efficient solutions and overcome the computational burden of the scalarizations that use constraints on objective values. Finally, we present some results from an application in airline crew scheduling as evidence. This research is partially supported by University of Auckland grant 3602178/9275 and by the Deutsche Forschungsgemeinschaft grant Ka 477/27-1.     

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.     

Symmetric duality for minimax multiobjective variational mixed integer programming problems with partial-invexity

A pair of symmetric dual multiobjective variational mixed integer programs for the polars of arbitrary cones are formulated, which some primal and dual variables are constrained to belong to the set of integers. Under the separability with respect to integer variables and partial-invexity assumptions on the functions involved, we prove the weak, strong, converse and self-duality theorems to related minimax efficient solution. These results include some of available results.     

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.     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

Strong duality for a special class of integer programs

A pair of primal-dual integer programs is constructed for a class of problems motivated by a generalization of the concept of greatest common divisor. The primal-dual formulation is based on a number-theoretic, rather than a Lagrangian, duality property; consequently, it avoids the dualitygap common to Lagrangian duals in integer programming.This research was partially supported by the National Science Foundation, Grant No. DCR-74-20584     

Generating functions and duality for integer programs

We consider the integer program P→max c^′x|Ax=y;xNⁿ . Using the generating function of an associated counting problem, and a generalized residue formula of Brion and Vergne, we explicitly relate P with its continuous linear programming (LP) analogue and provide a characterization of its optimal value. In particular, dual variables λR^m have discrete analogues zC^m, related in a simple manner. Moreover, both optimal values of P and the LP obey the same formula, using z for P and |z| for the LP. One retrieves (and refines) the so-called group-relaxations of Gomory which, in this dual approach, arise naturally from a detailed analysis of a generalized residue formula of Brion and Vergne. Finally, we also provide an explicit formulation of a dual problem P^*, the analogue of the dual LP in linear programming.     

An integer programming model for two- and three-stage two-dimensional cutting stock problems

In this paper, an integer programming model for two-dimensional cutting stock problems is proposed. In the problems addressed, it is intended to cut a set of small rectangular items of given sizes from a set of larger rectangular plates in such a way that the total number of used plates is minimized.     

Symmetric duality for minimax mixed integer programming problems with pseudo-invexity

In this paper, we consider the pair of symmetric dual multiobjective variational mixed integer programs proposed by Chen and Yang [X. Chen, J. Yang, Symmetric duality for minimax multiobjective variational mixed integer programming problems with partial-invexity, European Journal of Operational Research 181 (2007) 76-85.] and extend some of their results under the assumptions of partial-pseudo-invexity and separability on the functions involved. These results include several results available in literature as special cases.     

A duality theorem for a homogeneous fractional programming problem

The usual theory of duality for linear fractional programs is extended by replacing the linear functions in the numerator and denominator by arbitrary positively homogeneous convex functions. In the constraints, the positive orthant inR ⁿ is replaced by an arbitrary cone. The resultant duality theorem contains a recent result of Chandra and Gulati as a special case.The authors wish to thank the referee for a number of valuable suggestions, particularly improvements in Theorem 3.4 and Corollary 3.1.     

A mixed integer programming model for multiple stage adaptive testing

The last decade has seen paper-and-pencil (P&P) tests being replaced by computerized adaptive tests (CATs) within many testing programs. A CAT may yield several advantages relative to a conventional P&P test. A CAT can determine the questions or test items to administer, allowing each test form to be tailored to a test taker’s skill level. Subsequent items can be chosen to match the capability of the test taker. By adapting to a test taker’s ability, a CAT can acquire more information about a test taker while administering fewer items. A Multiple Stage Adaptive test (MST) provides a means to implement a CAT that allows review before the administration. The MST format is a hybrid between the conventional P&P and CAT formats. This paper presents mixed integer programming models for MST assembly problems. Computational results with commercial optimization software will be given and advantages of the models evaluated.     

Strong duality for robust minimax fractional programming problems

We develop a duality theory for minimax fractional programming problems in the face of data uncertainty both in the objective and constraints. Following the framework of robust optimization, we establish strong duality between the robust counterpart of an uncertain minimax convex–concave fractional program, termed as robust minimax fractional program, and the optimistic counterpart of its uncertain conventional dual program, called optimistic dual. In the case of a robust minimax linear fractional program with scenario uncertainty in the numerator of the objective function, we show that the optimistic dual is a simple linear program when the constraint uncertainty is expressed as bounded intervals. We also show that the dual can be reformulated as a second-order cone programming problem when the constraint uncertainty is given by ellipsoids. In these cases, the optimistic dual problems are computationally tractable and their solutions can be validated in polynomial time. We further show that, for robust minimax linear fractional programs with interval uncertainty, the conventional dual of its robust counterpart and the optimistic dual are equivalent.     

Second order duality for nondifferentiable minimax programming problems with generalized convexity

In this paper, we are concerned with a class of nondifferentiable minimax programming problem and its two types of second order dual models. Weak, strong and strict converse duality theorems from a view point of generalized convexity are established. Our study naturally unifies and extends some previously known results on minimax programming.     

Minimax mixed integer symmetric duality for multiobjective variational problems

A Mond–Weir type multiobjective variational mixed integer symmetric dual program over arbitrary cones is formulated. Applying the separability and generalized F-convexity on the functions involved, weak, strong and converse duality theorems are established. Self duality theorem is proved. A close relationship between these variational problems and static symmetric dual minimax mixed integer multiobjective programming problems is also presented.     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

Multi-objective integer programming: A general approach for generating all non-dominated solutions

In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical ε-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical ε-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with k objectives. A numerical example considering tri-objective assignment problem is also provided.     

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.     

Using duality to solve generalized fractional programming problems

In this paper we explore the relations between the standard dual problem of a convex generalized fractional programming problem and the partial dual problem proposed by Barros et al. (1994). Taking into account the similarities between these dual problems and using basic duality results we propose a new algorithm to directly solve the standard dual of a convex generalized fractional programming problem, and hence the original primal problem, if strong duality holds. This new algorithm works in a similar way as the algorithm proposed in Barros et al. (1994) to solve the partial dual problem. Although the convergence rates of both algorithms are similar, the new algorithm requires slightly more restrictive assumptions to ensure a superlinear convergence rate. An important characteristic of the new algorithm is that it extends to the nonlinear case the Dinkelbach-type algorithm of Crouzeix et al. (1985) applied to the standard dual problem of a generalized linear fractional program. Moreover, the general duality results derived for the nonlinear case, yield an alternative way to derive the standard dual of a generalized linear fractional program. The numerical results, in case of quadratic-linear ratios and linear constraints, show that solving the standard dual via the new algorithm is in most cases more efficient than applying directly the Dinkelbach-type algorithm to the original generalized fractional programming problem. However, the numerical results also indicate that solving the alternative dual (Barros et al., 1994) is in general more efficient than solving the standard dual.This research was carried out at the Econometric Institute, Erasmus University Rotterdam, the Netherlands and was supported by the Tinbergen Institute Rotterdam