Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case

We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function. Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported.     

Complexity of linear programming

The complexity of linear programming is discussed in the “integer” and “real number” models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation.Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all “reasonable” models of computation.     

Faces for a linear inequality in 0–1 variables

Given a linear inequality in 0–1 variables we attempt to obtain the faces of the integer hull of 0–1 feasible solutions. For the given inequality we specify how faces of a variety of lower-dimensional inequalities can be raised to give full-dimensional faces. In terms of a set, called a “strong cover”, we obtain necessary and sufficient conditions for any inequality with 0–1 coefficients to be a face, and characterize different forms that the integer hull must take. In general the suggested procedures fail to produce the complete integer hull. Special subclasses of inequalities for which all faces can be generated are demonstrated. These include the “matroidal” and “graphic” inequalities, where a count on the number of such inequalities is obtained, and inequalities where all faces can be derived from lower dimensional faces.     

Cutting plane algorithms for 0-1 programming based on cardinality cuts

We present new valid inequalities for 0-1 programming problems that work in similar ways to well known cover inequalities. Discussion and analysis of these cuts is followed by their revision and use in integer programming as a new generation of cuts that excludes not only portions of polyhedra containing noninteger points, also parts with some integer points that have been explored in search of an optimal solution. Our computational experimentations demonstrate that this new approach has significant potential for solving large scale integer programming problems.     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.     

Separable Relaxation for Nonconvex Quadratic Integer Programming: Integer Diagonalization Approach

We present in this paper an integer diagonalization approach for deriving new lower bounds for general quadratic integer programming problems. More specifically, we introduce a semiunimodular transformation in order to diagonalize a symmetric matrix and preserve integral property of the feasible set at the same time. Via the semiunimodular transformation, the resulting separable quadratic integer program is a relaxation of the nonseparable quadratic integer program. We further define the integer diagonalization dual problem to identify the best semiunimodular transformation and analyze some basic properties of the set of semiunimodular transformations for a rational symmetric matrix. In particular, we present a complete characterization of the set of all semiunimodular transformations for a nonsingular 2×2 symmetric matrix. We finally discuss Lagrangian relaxation and convex relaxation schemes for the resulting separable quadratic integer programming problem and compare the tightness of different relaxation schemes.     

Intelligent parking systems

The basic concepts of the parking reservation system and parking revenue management system are discussed in this paper. The proposed “intelligent” parking space inventory control system that is based on a combination of fuzzy logic and integer programming techniques makes “on line” decisions whether to accept or reject a new driver’s request for parking. In the first step of the proposed model, the best parking strategies are developed for many different patterns of vehicle arrivals. These parking strategies are developed using integer programming approach. In the second step, learning from the best strategies, specific rules are defined. The uniqueness of the proposed approach is that the rules are derived from the set of chosen examples assuming that the future traffic arrival patterns are known. The results were found to be close to the best solution assuming that the future arrival pattern is known.     

Intersection cuts for convex mixed integer programs from translated cones

We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions.     

On boundedness of (quasi-)convex integer optimization problems

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained integer optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or quasi-convex polynomial function over the feasible set contained in , and defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities. The conditions for boundedness are provided in the form of an implementable algorithm, terminating after a finite number of iterations, showing that for the considered class of functions, the integer programming problem with nonempty feasible region is unbounded if and only if the associated continuous optimization problem is unbounded. We also prove that for a broad class of objective functions (which in particular includes polynomials with integer coefficients), an optimal solution set of the constrained integer problem is nonempty over any subset of .     

On the facets of the mixed–integer knapsack polyhedron

We study the mixed–integer knapsack polyhedron, that is, the convex hull of the mixed–integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet–defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities for several special cases. We report computational results on using the inequalities as cutting planes for mixed–integer programming.Supported, in part, by NSF grants DMII–0070127 and DMII–0218265.Mathematics Subject Classification (2000): 90C10, 90C11, 90C57     

Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices

We present branching-on-hyperplane methods for solving mixed integer linear and mixed integer convex programs. In particular, we formulate the problem of finding a good branching hyperplane using a novel concept of adjoint lattice. We also reformulate the problem of rounding a continuous solution to a mixed integer solution. A worst case complexity of a Lenstra-type algorithm is established using an approximate log-barrier center to obtain an ellipsoidal rounding of the feasible set. The results for the mixed integer convex programming also establish a complexity result for the mixed integer second order cone programming and mixed integer semidefinite programming feasibility problems as a special case. Our results motivate an alternative reformulation technique and a branching heuristic using a generalized (e.g., ellipsoidal) norm reduced basis available at the root node.     

Unboundedness in reverse convex and concave integer programming

In this paper we are concerned with the problem of unboundedness and existence of an optimal solution in reverse convex and concave integer optimization problems. In particular, we present necessary and sufficient conditions for existence of an upper bound for a convex objective function defined over the feasible region contained in ${\mathbb{Z}^n}$ . The conditions for boundedness are provided in a form of an implementable algorithm, showing that for the considered class of functions, the integer programming problem is unbounded if and only if the associated continuous problem is unbounded. We also address the problem of boundedness in the global optimization problem of maximizing a convex function over a set of integers contained in a convex and unbounded region. It is shown in the paper that in both types of integer programming problems, the objective function is either unbounded from above, or it attains its maximum at a feasible integer point.     

An interior point algorithm to solve computationally difficult set covering problems

We present an interior point approach to the zero–one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interior points of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems.     

A separable integer programming problem equivalent to its continual version

The separable integer programming problem with so called nested constraints is shown to be equivalent to its continual version obtained by piecewise linear continuation of the cost functions. A new approach to solution of the latter based on its successive reduction in size is suggested. When applied to the problem with piecewise linear convex functions it leads to two algorithms for its solution applicable also to the similar integer problem. These algorithms turn out more efficient than those obtained by dynamic programming approach.     

Fixed-charge transportation on a path: optimization, LP formulations and separation

In the fixed-charge transportation problem, the goal is to optimally transport goods from depots to clients when there is a fixed cost associated to transportation or, equivalently, to opening an arc in the underlying bipartite graph. We further motivate its study by showing that it is both a special case and a strong relaxation of the big-bucket multi-item lot-sizing problem, and a generalization of a simple variant of the single-node flow set. This paper is essentially a polyhedral analysis of the polynomially solvable special case in which the associated bipartite graph is a path. We give a $\mathcal O (n^3)$ -time optimization algorithm and a $\mathcal O (n^2)$ -size linear programming extended formulation. We describe a new class of inequalities that we call “path-modular” inequalities. We give two distinct proofs of their validity. The first one is direct and crucially relies on sub- and super-modularity of an associated set function. The second proof is by showing that the projection of the extended linear programming formulations onto the original variable space yields exactly the polyhedron described by the path-modular inequalities. Thus we also show that these inequalities suffice to describe the convex hull of the set of feasible solutions.     

Strong-branching inequalities for convex mixed integer nonlinear programs

Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving mixed integer nonlinear programming (MINLP) problems. The focus of this paper is to demonstrate how to effectively use “discarded” information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various forms of disjunctive inequalities, and mixing-type inequalities are all discussed. The inequalities span a spectrum from those that require almost no extra effort to compute to those that require the solution of an additional linear program. In the end, we perform an extensive computational study to measure the impact of each of our proposed techniques. Computational results reveal that existing algorithms can be significantly improved by leveraging the information generated as a byproduct of strong branching in the form of valid inequalities.     

Limit vector variational inequality problems via scalarization

This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively.     

Second-order cover inequalities

We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives. Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities that limit sums over disjoint subsets of variables to be at most one.