An outline of linear programming

Linear programming deals with the maximization or minimization of linear functions subject to linear inequality constraints. Definitions and practical examples are given in Section 2. Section 3 gives a geometric interpretation of the simplex algorithm. Section 4 develops the mathematical theory of duality and gives heuristic interpretations in terms of shadow prices. Section 5 studies those linear programs for which integer solutions are normally required and discusses those cases in which integer solutions arise naturally and those in which special techniques must be used.The preparation of this paper was supported in part by the Army Research Office under Contract No. DA-ARO-D-31-124-70-G42.     

Least-cost network topology design for a new service

We describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a centralized new service. Our results are compared to those of a greedy algorithm which applies corresponding decision rules, but without the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs that can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.This research was partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract No. F49629-90-C-0033.     

Hybrid genetic algorithms with selective crossover for the capacitated p-median problem

Central European Journal of Operations Research - The paper suggests two ways of combining a genetic algorithm with integer programming to improve the quality of the problem solution. The...     

Computational experience with a group theoretic integer programming algorithm

This paper gives specific computational details and experience with a group theoretic integer programming algorithm. Included among the subroutines are a matrix reduction scheme for obtaining group representations, network algorithms for solving group optimization problems, and a branch and bound search for finding optimal integer programming solutions. The innovative subroutines are shown to be efficient to compute and effective in finding good integer programming solutions and providing strong lower bounds for the branch and bound search.This research was supported in part by the U.S. Army Research Office (Durham) under contract no. DAHC04-70-C-0058. This paper is not an official National Bureau of Economic Research publication.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.     

A Feasibility Pump for mixed integer nonlinear programs

We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within an outer approximation scheme. We report computational results. P. Bonami is supported in part by a grant from IBM and by ANR grant BLAN06-1-138894. G. Cornuéjols is supported in part by NSF grant CMMI-0653419, ANR grant BLAN06-1-138894 and ONR grant N00014-03-1-0188. Part of this research was carried out when Andrea Lodi was Herman Goldstine Fellow of the IBM T.J. Watson Research Center whose support is gratefully acknowledged. F. Margot is supported in part by a grant from IBM and by ONR grant N00014-03-1-0188.     

A Simple Algorithm for Integer Programs Using Group Constraints

Journal of the Operational Research Society - This paper gives an algorithm for the solution of linear integer programs which is identical in spirit to Gomory's classic cutting plane procedure...     

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.     

The vertex separator problem: algorithms and computations

This is a companion paper to our polyhedral study [1] of the Vertex Separator (VS) Problem. Given an undirected graph G, the VS problem consists in identifying a minimum-weight vertex set whose removal disconnects G, subject to bounds on the size of the resulting components. In this paper, we describe versions of a branch-and-cut algorithm based on the results of that polyhedral study. It uses two families of cuts, symmetric and asymmetric, for which we develop polynomial-time greedy separation routines. A heuristic to generate feasible separators is also used. A computational experiment on several data sets from the literature compares the performance of three versions of our algorithm to that of the commercial MIP solver XPRESS. This experiment throws a sharp light on the role of cut density, known to software developers but never before documented in the literature. It convincingly shows that the practical usefulness of cuts in integer programming depends not only on their strength, but also on their sparsity: everything else being equal, the smaller the cut support, the better. The power of the inequalities proposed here is well illustrated by the computational tests on dense graphs. This is in accordance with the previous observation, since the support of these cuts tends to decrease with graph density.Research supported by the Brazilian agencies FAPESP (grant 01/14205–6), CAPES (grant BEX 04444/02–2) and CNPq (grants 302588/02–7 and Pronex 664107/97–4).Research supported by the National Science Foundation through grant #DMI-0098427 and by the Office of Naval Research through contract N00014-97-1-0196.     

Exact Algorithm for Concave Knapsack Problems: Linear Underestimation and Partition Method

Integer programming problems with a concave cost function are often encountered in optimization models involving economics of scale. In this paper, we propose an efficient exact algorithm for solving concave knapsack problems. The algorithm consists of an iterative process between finding lower and upper bounds by linearly underestimating the objective function and performing domain cut and partition by exploring the special structure of the problem. The lower bound is improved iteratively via cutting and partitioning the domain. This iteration process converges to the optimality in a finite number of steps. Promising computational results are reported for large-scale concave knapsack problems with up to 1200 integer variables. Comparison results with other existing methods in the literature are also presented. *Research supported by the National Natural Science Foundation of China under Grants 79970107 and 10271073,and the Research Grants Council of Hong Kong under Grant CUHK 4214/01E.     

整数线性规划投资组合模型的直接搜索算法求解

利用松弛最优邻近解临域整数点搜索法作过滤条件,建立求解整数规划的新方法——直接搜索算法,利用直接搜索算法并借助Matlab软件求解整数线性规划投资组合模型.数值结果表明了模型的建立与提出方法的有效性.     

A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated.     

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.     

Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts

In this paper, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the loqo algorithm and provide extensive numerical results on the CUTEr test set and on warmstarting in the context of quadratic, nonlinear, mixed integer nonlinear, and goal programming. Research of the first author is sponsored by ONR grant N00014-04-1-0145. Research of the second author is supported by NSF grant DMS-0107450.     

Global optimization of a quadratic function subject to a bounded mixed integer consraint set

In this paper we consider the optimization of a quadratic function subject to a linearly bounded mixed integer constraint set. We develop two types of piecewise affine convex underestimating functions for the objective function. These are used in a branch and bound algorithm for solving the original problem. We show finite convergence to a near optimal solution for this algorithm. We illustrate the algorithm with a small numerical example. Finally we discuss some modifications of the algorithm and address the question of extending the problem to include quadratic constraints.Supported by grants from the Danish Natural Science Research Council and the Danish Research Academy.     

An Improved Algorithm for the Capacitated Facility Location Problem

In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.     

A problem expanding parametric programming method for solving the job shop scheduling problem

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

A polynomial algorithm for an integer quadratic non-separable transportation problem

We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205.     

Small polynomials with integer coefficients

We study the problem of minimizing the supremum norm, on a segment of the real line or on a compact set in the plane, by polynomials with integer coefficients. The extremal polynomials are naturally called integer Chebyshev polynomials. Their factors, zero distribution and asymptotics are the main subjects of this paper. In particular, we show that the integer Chebyshev polynomials for any infinite subset of the real line must have infinitely many distinct factors, which answers a question of Borwein and Erdélyi. Furthermore, it is proved that the accumulation set for their zeros must be of positive capacity in this case. We also find the first nontrivial examples of explicit integer Chebyshev constants for certain classes of lemniscates. Since it is rarely possible to obtain an exact value of the integer Chebyshev constant, good estimates are of special importance. Introducing the methods of weighted potential theory, we generalize and improve the Hilbert-Fekete upper bound for the integer Chebyshev constant. These methods also give bounds for the multiplicities of factors of integer Chebyshev polynomials, and lower bounds for the integer Chebyshev constant. Moreover, all the bounds mentioned can be found numerically by using various extremal point techniques, such as the weighted Leja points algorithm. Applying our results in the classical case of the segment [0, 1], we improve the known bounds for the integer Chebyshev constant and the multiplicities of factors of the integer Chebyshev polynomials. Research supported in part by the National Security Agency under Grant No. MDA904-03-1-0081.     

Optimizing a multi-stage production/inventory system by DC programming based approaches

This paper deals with optimizing the cost of set up, transportation and inventory of a multi-stage production system in presence of bottleneck. The considered optimization model is a mixed integer nonlinear program. We propose two methods based on DC (Difference of Convex) programming and DCA (DC Algorithm)—an innovative approach in nonconvex programming framework. The mixed integer nonlinear problem is first reformulated as a DC program and then DCA is developed to solve the resulting problem. In order to globally solve the problem, we combine DCA with a Branch and Bound algorithm (BB-DCA). A convex minorant of the objective function is introduced. DCA is used to compute upper bounds while lower bounds are calculated from a convex relaxation problem. The numerical results compared with those of COUENNE (http://www.coin-or.org/download/binary/Couenne/), a solver for mixed integer nonconvex programming, show the rapidity and the ?-globality of DCA in almost cases, as well as the efficiency of the combined DCA-Branch and Bound algorithm. We also propose a simple heuristic algorithm which is proved by experimental results to be better than an existing heuristic in the literature for this problem.