Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean space

Under study are the two problems of choosing a subset of m vectors with the maximum norm of the sum of the elements from a set of n vectors in Euclidean space ℝ ^k . The vectors are assumed to have integer coordinates. Using the dynamic programming technique, some new optimal algorithms are suggested for solving the problems; these algorithms have pseudopolynomial time when the dimension of the space is fixed. The new algorithms have certain advantages over the availables: the vector subset problem can be solved faster for m < (k/2) ^k , while, after taking into account an additional restriction on the order of the vectors, the time complexity is k ^k−1 times less independently on m.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer linear minimization problems inn variables subject tom linear constraints with at most two variables per inequality, and with all variables bounded between 0 andU. For such systems, a 2-approximation algorithm is presented that runs in time O(mnU ² log(Un ² m)), so it is polynomial in the input size if the upper boundU is polynomially bounded. The algorithm works by finding first a super-optimal feasible solution that consists of integer multiples of 1/2. That solution gives a tight bound on the value of the minimum. It furthermore has an identifiable subset of integer components that retain their value in an integer optimal solution of the problem. These properties are a generalization of the properties of the vertex cover problem. The algorithm described is, in particular, a 2-approximation algorithm for the problem of minimizing the total weight of true variables, among all truth assignments to the 2-satisfiability problem.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported in part by ONR contracts N00014-88-K-0377 and N00014-91-J-1241.Research supported in part by ONR contract N00014-91-C-0026.Part of this work was done while the author was visiting the International Computer Science Institute in Berkeley, CA and DIMACS, Rutgers University, New Brunswick, NJ.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k₁, k₂, is there a vertex cover taking at most k₁ vertices from one and at most k₂ vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999^{k₁ + k₂} + (k₁ + k₂)n) time. Our algorithm is efficient and practical for small values of k₁ and k₂, as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed; nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths (and hence the depth of the search tree as a whole) by a sort of bonus points.     

Capacitated dynamic lot-sizing problem with delivery/production time windows

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT⁴) time, where n is the number of demands and T is the length of the planning horizon.     

Choosing the best set of variables in regression analysis using integer programming

This paper is concerned with an algorithm for selecting the best set of s variables out of k(> s) candidate variables in a multiple linear regression model. We employ absolute deviation as the measure of deviation and solve the resulting optimization problem by using 0-1 integer programming methodologies. In addition, we will propose a heuristic algorithm to obtain a close to optimal set of variables in terms of squared deviation. Computational results show that this method is practical and reliable for determining the best set of variables.     

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002     

Smooth Solution of the Compressible Navier–Stokes Equations in an Unbounded Domain with Inflow Boundary Condition

The barotropic compressible Navier–Stokes equations in an unbounded domain are studied. We prove the unique existence of the solution (u, p) of the system (1.1) in the Sobolev spaceH^{k + 3} × H^{k + 2}provided that the derivatives of the data of the problem are sufficiently small, wherek ≥ 0 is any integer. The proof follows from an analysis of the linearized problem, the solvability of the continuity equation, and the Schauder fixed point theory. Similar smoothness results are obtained for a linearized form of (1.1).     

Optimising a nonlinear utility function in multi-objective integer programming

In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective integer programming problem.     

On binary signed digit representations of integers

Applications of signed digit representations of an integer include computer arithmetic, cryptography, and digital signal processing. An integer of length n bits can have several binary signed digit (BSD) representations and their number depends on its value and varies with its length. In this paper, we present an algorithm that calculates the exact number of BSDR of an integer of a certain length. We formulate the integer that has the maximum number of BSDR among all integers of the same length. We also present an algorithm to generate a random BSD representation for an integer starting from the most significant end and its modified version which generates all possible BSDR. We show how the number of BSD representations of k increases as we prepend 0s to its binary representation.     

New formulations of the multiple sequence alignment problem

A well known formulation of the multiple sequence alignment (MSA) problem is the maximum weight trace (MWT), a 0–1 linear programming problem. In this paper, we propose a new integer quadratic programming formulation of the MSA. The number of constraints and variables in the problem are only of the order of kL ², where, k is the number of sequences and L is the total length of the sequences, that is, L = ?_i=1^kl_i{L= \sum_{i=1}^{k}l_{i}} , where l _i is the length of sequence i. Based on this formulation we introduce an equivalent linear constrained 0–1 quadratic programming problem. We also propose a 0–1 linear programming formulation of the MWT problem, with polynomially many constraints. Our formulation provides the first direct compact formulation that ensures that the critical circuit inequalities (which are exponentially many) are all met.     

Exploring the constrained maximum edge-weight connected graph problem

Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.     

A Dynamic Programming Algorithm for the κ-Haplotyping Problem

The Minimum Fragments Removal （MFR） problem is one of the haplotyping problems： given a set of fragments, remove the minimum number of fragments so that the resulting fragments can be partitioned into k classes of non-conflicting subsets. In this paper, we formulate the κ-MFR problem as an integer linear programming problem, and develop a dynamic programming approach to solve the κ-MFR problem for both the gapless and gap eases.     

Approximation of RNA multiple structural alignment

In the context of non-coding RNA (ncRNA) multiple structural alignment, Davydov and Batzoglou (2006) introduced in [7] the problem of finding the largest nested linear graph that occurs in a set G of linear graphs, the so-called Max-NLS problem. This problem generalizes both the longest common subsequence problem and the maximum common homeomorphic subtree problem for rooted ordered trees.In the present paper, we give a fast algorithm for finding the largest nested linear subgraph of a linear graph and a polynomial-time algorithm for a fixed number (k) of linear graphs. Also, we strongly strengthen the result of Davydov and Batzoglou (2006) [7] by proving that the problem is NP-complete even if G is composed of nested linear graphs of height at most 2, thereby precisely defining the borderline between tractable and intractable instances of the problem. Of particular importance, we improve the result of Davydov and Batzoglou (2006) [7] by showing that the Max-NLS problem is approximable within ratio in O(kn²) running time, where mopt is the size of an optimal solution. We also present O(1)-approximation of Max-NLS problem running in O(kn) time for restricted linear graphs. In particular, for ncRNA derived linear graphs, a -approximation is presented.     

Success Guarantee of Dual Search in Integer Programming: p-th Power Lagrangian Method

Although the Lagrangian method is a powerful dual search approach in integer programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two key transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search within [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.     

Persistency of linear programming relaxations for the stable set problem

The Nemhauser–Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of other LP formulations have been studied and one may wonder whether any of them has this property as well. We show that any other formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable set polytope.

     

Benders's method revisited

The master problem in Benders's partitioning method is an integer program with a very large number of constraints, each of which is usually generated by solving the integer program with the constraints generated earlier. Computational experience shows that the subset B of those constraints of the master problem that are satisfied with equality at the linear programming optimum often play a crucial role in determining the integer optimum, in the sense that only a few of the remaining inequalities are needed. We characterize this subset B of inequalities. If an optimal basic solution to the linear program is nondegenerate in the continuous variables and has p integer-constrained basic variables, then the corresponding set B contains at most 2^p inequalities, none of which is implied by the others. We give an efficient procedure for generating an appropriate subset of the inequalities in B, which leads to a considerably improved version of Benders's method.     

Stability in convex semi-infinite programming and rates of convergence of optimal solutions of discretized finite subproblems

We consider convex semiinfinite programming (SIP) problems with an arbitrary fixed index set T. The article analyzes the relationship between the upper and lower semicontinuity (lsc) of the optimal value function and the optimal set mapping, and the so-called Hadamard well-posedness property (allowing for more than one optimal solution). We consider the family of all functions involved in some fixed optimization problem as one element of a space of data equipped with some topology, and arbitrary perturbations are premitted as long as the perturbed problem continues to be convex semiinfinite. Since no structure is required for T, our results apply to the ordinary convex programming case. We also provide conditions, not involving any second order optimality one, guaranteeing that the distance between optimal solutions of the discretized subproblems and the optimal set of the original problem decreases by a rate which is linear with respect to the discretization mesh-size.