Finding a representative nondominated set for multi-objective mixed integer programs

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.     

Finding all efficient extreme points for multiple objective linear programs

In this paper we develop a method for finding all efficient extreme points for multiple objective linear programs. Simple characterizations of the efficiency of an edge incident to a nondegenerate or a degenerate efficient vertex are given. These characterizations form the basis of an algorithm for enumerating all efficient vertices. The algorithm appears to have definite computational advantages over other methods. Some illustrative examples are included.     

Finding multiple solutions to general integer linear programs

Integer linear programming (ILP) problems occur frequently in many applications. In practice, alternative optima are useful since they allow the decision maker to choose from multiple solutions without experiencing any deterioration in the objective function. This study proposes a general integer cut to exclude the previous solution and presents an algorithm to identify all alternative optimal solutions of an ILP problem. Numerical examples in real applications are presented to demonstrate the usefulness of the proposed method.     

Finding all solutions of separable systems of piecewise-linear equations using integer programming

Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time.     

Generation of all integer points for given sets of linear inequalities

We propose to give a computationally feasible procedure for the generation of all the integer points satisfying a given set of inequalities. Five different systems of inequalities will be considered. In order to generate all of these integer points, one requires a particular set of integer points, called fundamental points, and a set of linearly independent vectors with integer components. The number of these fundamental points is given by a simple formula. We show how to generate the fundamental points and the required vectors. We give an application concerning the localization of the integer optimum of a linear objective function subject to constraints which geometrically define a cone or a parallelotope.This paper was presented at the 7th Mathematical Programming Symposium, 1970, The Hague, The Netherlands, under the title Some linear inequalities in Z ⁿ .     

An interactive algorithm to find the most preferred solution of multi-objective integer programs

In this paper, we develop an interactive algorithm that finds the most preferred solution of a decision maker (DM) for multi-objective integer programming problems. We assume that the DM’s preferences are consistent with a quasiconcave value function unknown to us. Based on the properties of quasiconcave value functions and pairwise preference information obtained from the DM, we generate constraints to restrict the implied inferior regions. The algorithm continues iteratively and guarantees to find the most preferred solution for integer programs. We test the performance of the algorithm on multi-objective assignment, knapsack, and shortest path problems and show that it works well.     

On the computation of all supported efficient solutions in multi-objective integer network flow problems

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.     

Gomory integer programs

 The set of all group relaxations of an integer program contains certain special members called Gomory relaxations. A family of integer programs with a fixed coefficient matrix and cost vector but varying right hand sides is a Gomory family if every program in the family can be solved by one of its Gomory relaxations. In this paper, we characterize Gomory families. Every TDI system gives a Gomory family, and we construct Gomory families from matrices whose columns form a Hilbert basis for the cone they generate. The existence of Gomory families is related to the Hilbert covering problems that arose from the conjectures of Seb?. Connections to commutative algebra are outlined at the end. Received: May 17, 2001 / Accepted: February 7, 2002 Published online: April 24, 2003 RID="⋆" ID="⋆" Research partially supported by NSF grant DMS-0100141.     

A recursive procedure to generate all cuts for 0–1 mixed integer programs

We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.The research of this author was supported by NSF Contract No. ECS-8540898.     

Test sets of integer programs

This article is a survey about recent developments in the area of test sets of families of linear integer programs. Test sets are finite subsets of the integer lattice that allow to improve any given feasible non-optimal point of an integer program by one element in the set. There are various possible ways of defining test sets depending on the view that one takes: theGraver test set is naturally derived from a study of the integral vectors in cones; theScarf test set (neighbors of the origin) is strongly connected to the study of lattice point free convex bodies; the so-calledreduced Gröbner basis of an integer program is obtained from a study of generators of polynomial ideals. This explains why the study of test sets connects various branches of mathematics. We introduce in this paper these three kinds of test sets and discuss relations between them. We also illustrate on various examples such as the minimum cost flow problem, the knapsack problem and the matroid optimization problem how these test sets may be interpreted combinatorially. From the viewpoint of integer programming a major interest in test sets is their relation to the augmentation problem. This is discussed here in detail. In particular, we derive a complexity result of the augmentation problem, we discuss an algorithm for solving the augmentation problem by computing the Graver test set and show that, in the special case of an integer knapsack problem with 3 coefficients, the augmentation problem can be solved in polynomial time.Supported by a Gerhard-Hess-Forschungsförderpreis of the German Science Foundation (DFG).     

Enhancing computations of nondominated solutions in MOLFP via reference points

In previous work, Costa and Alves (J Math Sci 161:(6)820–831, 2009; 2011) have presented Branch & Bound and Branch & Cut techniques that allow for the effective computation of nondominated solutions, associated with reference points, of multi-objective linear fractional programming (MOLFP) problems of medium dimensions (ten objective functions, hundreds of variables and constraints). In this paper we present some results that enhance those computations. Firstly, it is proved that the use of a special kind of achievement scalarizing function guarantees that the computation error does not depend on the dimension of the problem. Secondly, a new cut for the Branch & Cut technique is presented. The proof that this new cut is better than the one in Costa and Alves (2011) is presented, guaranteeing that it reduces the region to explore. Some computational tests to assess the impact of the new cut on the performance of the Branch & Cut technique are presented.     

On integer points in polyhedra

We give an upper bound on the number of vertices ofP _I , the integer hull of a polyhedronP, in terms of the dimensionn of the space, the numberm of inequalities required to describeP, and the size of these inequalities. For fixedn the bound isO(m ^{n n–} ). We also describe an algorithm which determines the number of integer points in a polyhedron to within a multiplicative factor of 1+ in time polynomial inm, and 1/ when the dimensionn is fixed.Supported by Sonderfschungsbereich 303 (DFG) and NSF grant ECS-8611841.Partially supported by NSF grant DMS-8905645.Supported by NSF grants ECS-8418392 and CCR-8805199.mcd%vax.oxford.ac.uk     

Cutting planes for integer programs with general integer variables

We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was partly performed when the author was affiliated with CORE, Université Catholique de Louvain.     

Test sets for integer programs

In this paper I discuss various properties of the simplicial complex of maximal lattice free bodies associated with a matrixA. If the matrix satisfies some mild conditions, and isgeneric, the edges of the complex form the minimal test set for the family of integer programs obtained by selecting a particular row ofA as the objective function, and using the remaining rows to impose constraints on the integer variables.     

Optima of dual integer linear programs

We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions.     

Alternative formulations of mixed integer programs

We study the formation of mixed-integer programming (MIP) constraints through the development of constructions which syntactically parallel the set operations of union, intersection, Cartesian product, and linear affine transformation. In this manner, we are able to both modularize the work of constructing representations (as the representations for base sets of a composite construction need not be disjunctively derived) and to make connections to certain of the logic-based approaches to artificial intelligence which utilize the intersection (and) and union (or) operations. We provide results which allow one to calculate the linear relaxation of a composite construction, in terms of set operations on the relaxation of the base sets. We are also able to compare the size of the relaxations for different formulations of the same MIP set, when these different formulations arise from one another through distributive laws. Utilizing these results, we generalize the Davis-Putnam algorithm of propositional logic to an MIP form, and answer a question regarding the relative efficiency of two versions of this algorithm. In this context, the subroutines of the logic algorithm correspond to list processing subroutines for MIP to be used prior to running linear programs. They are similar in nature to preprocessing routines, wherein entire MIP constraint sets are manipulated as formal symbols of logic.This work has been partially supported by National Science Foundation Grant MCS-8304075.