Description of 2-integer continuous knapsack polyhedra

In this paper we discuss the polyhedral structure of several mixed integer sets involving two integer variables. We show that the number of the corresponding facet-defining inequalities is polynomial on the size of the input data and their coefficients can also be computed in polynomial time using a known algorithm [D. Hirschberg, C. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the Association for Computing Machinery 23 (1) (1976) 147–154] for the two integer knapsack problem. These mixed integer sets may arise as substructures of more complex mixed integer sets that model the feasible solutions of real application problems.     

Maximum Feasibility Problem for Continuous Linear Inequalities with Applications to Fuzzy Linear Programming

Systems of linear inequalities are important tools to formulate optimization problems. However, the feasibility of the whole system was often presumed true in most models. Even if an infeasible system could be detected, it is in general not easy to tell which part of the system caused it. This motivates the study of continuous linear inequalities, given no information whether it is feasible or not, what is the largest possible portion of the system that can be remained in consistency? We first propose a bisection-based algorithm which comes with an auxiliary program to answer the question. For further accelerating the algorithm, several novel concepts, one called “constraint weighting” and the other called “shooting technique”, are introduced to explore intrinsic problem structures. This new scheme eventually replaces the bisection method and its validity can be justified via a solid probabilistic analysis. Numerical examples and applications to fuzzy inequalities are reported to illustrate the robustness of our algorithm.     

A Refined Model of Computation for Continuous Problems

The real-number model of computation is used in computational geometry, in the approach suggested by Blum, Shub, and Smale and in information based complexity. In this paper we propose a refinement of this model, the TTE-model of computation. In contrast to the real-number model, which is unrealistic or at least too optimistic, the TTE-model is very realistic; i.e., for TTE-algorithms there are digital computers, which behave exactly the same way as predicted by the theoretical model. We start with a detailed discussion of some objections to the real-number model. We introduce the refined model by adding the condition “every partial input or output information of an algorithm is finite” to the assumptions of the IBC-model of computation. First, we explain computability and computational complexity in TTE for the simple case of real functions. Then we apply the refined model to two typical IBC-problems, integration and zero-finding on the spaceC[0; 1] of continuous real functions. We study computability and computational complexity and compare TTE-results with IBC-results. Finally, we briefly discuss the computation of discontinuous problems. This paper does not present new technical results but should be considered as a fresh impetus to reflect on models of computation for numerical analysis and as an invitation to try out the TTE-model of computation in information based complexity.     

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.     

框式线性规划的多项式预估校正内点算法

本文研究带线性约束的框式线性规划问题,给出了一个预估校正内点算法,分析了该算法的多项式计算复杂性,并证明其迭代复杂度为Ο(nL).     

Algorithmic complexity of Greenberg’s conjecture

Archiv der Mathematik - Let k be a totally real number field and p a prime. We show that the “complexity” of Greenberg’s conjecture ( $$\lambda = \mu = 0$$ ) is governed (under...     

A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem

One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by Christofides in 1976 and is well known as “the Christofides algorithm”. Recently, some authors started calling it “Christofides-Serdyukov algorithm”, pointing out that it was published independently in the USSR in 1978. We provide some historic background on Serdyukov's findings and a translation of his article from Russian into English.     

Deepest point of a polyhedron and linear programming

Abstract

The problem of finding a deepest point (a ball centre) of a polyhedron is studied. A finite combinatorial interior point method is presented for this problem which yields an algorithm for linear programming. We conjecture that this is a strongly polynomial algorithm. Meanwhile developing the algorithm, several auxiliary results were found; among others, Gorokh and Werner’s algorithm for linear inequalities is slightly extended. Our numerical experiments with the problem detected bugs in a linear interior point solver used in MATLAB 6 Optimization Toolbox.     

Interior-Point Methods with Decomposition for Solving Large-Scale Linear Programs

This paper deals with an algorithm incorporating the interior-point method into the Dantzig–Wolfe decomposition technique for solving large-scale linear programming problems. The algorithm decomposes a linear program into a main problem and a subproblem. The subproblem is solved approximately. Hence, inexact Newton directions are used in solving the main problem. We show that the algorithm is globally linearly convergent and has polynomial-time complexity.     

Polyhedral annexation in mixed integer and combinatorial programming

Polyhedral annexation is a new approach for generating all valid inequalities in mixed integer and combinatorial programming. These include the facets of the convex hull of feasible integer solutions. The approach is capable of exploiting the characteristics of the feasible solution space in regions both “adjacent to” and “distant from” the linear programming vertex without resorting to specialized notions of group theory, convex analysis or projective geometry. The approach also provides new ways for exploiting the “branching inequalities” of branch and bound.     

Fast algorithms for determining the linear complexities of sequences over GF(p~m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p-1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(pm)(any positive integer m) with the period 3n (n and pm - 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-lmamura algorithm, we can determine the linear complexity of any sequence over GF(pm) with the period 3n (n and pm - 1 are coprime) more efficiently.     

Integer Optimization on Convex Semialgebraic Sets

Let Y be a convex set in \Re ^k defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min is not empty, then the problem has an optimal solution of binary length ld ^O(k4) . For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y ^* . In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming. Received August 3, 1998, and in revised form March 22, 1999.     

A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems

We show that the position of an input point in the Euclideand-dimensional space with respect to a given set of hyperplanes can be determined efficiently by linear decision trees. As an application, we prove that many concrete problems whose recognition versions are NP-complete, like the traveling salesman problem, many other shortest path problems, and integer programming, have polynomial-time upper bounds in the linear decision tree model of computation.     

0-1 reformulations of the multicommodity capacitated network design problem

We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ approximation algorithm for FLCNP, where ρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.     

Complexity of certain systems of monomials in calculation by composition circuits

The circuit complexity of monomial set computation is studied in the paper. In the model considered here, the complexity means the minimal number of composition operations sufficient for calculating the system from its variables. It is established that the considered complexity measure can be much less than known complexity measures corresponding to models admitting, for example, either multiplication operations only, or multiplication and division operations, or multiplication operations with the ability to use inverse variables. However, this feature of significant “computation strength” is not universal, which is confirmed by an appropriate example. Furthermore, for a system containing two monomials of two variables we obtained an exact complexity value. We have also established that duality reasons do not work (or work poorly) in calculations using composition operation.     

A primal-dual interior point method whose running time depends only on the constraint matrix

We propose a primal-dual “layered-step” interior point (LIP) algorithm for linear programming with data given by real numbers. This algorithm follows the central path, either with short steps or with a new type of step called a “layered least squares” (LLS) step. The algorithm returns an exact optimum after a finite number of steps—in particular, after O(n ^3.5 c(A)) iterations, wherec(A) is a function of the coefficient matrix. The LLS steps can be thought of as accelerating a classical path-following interior point method. One consequence of the new method is a new characterization of the central path: we show that it composed of at mostn ² alternating straight and curved segments. If the LIP algorithm is applied to integer data, we get as another corollary a new proof of a well-known theorem by Tardos that linear programming can be solved in strongly polynomial time provided thatA contains small-integer entries.     

A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality

Production lot sizing models are often used to decide the best lot size to minimize operation cost, inventory cost, and setup cost. Cellular manufacturing analyses mainly address how machines should be grouped and parts be produced. In this paper, a mathematical programming model is developed following an integrated approach for cell configuration and lot sizing in a dynamic manufacturing environment. The model development also considers the impact of lot sizes on product quality. Solution of the mathematical model is to minimize both production and quality related costs. The proposed model, with nonlinear terms and integer variables, cannot be solved for real size problems efficiently due to its NP-complexity. To solve the model for practical purposes, a linear programming embedded genetic algorithm was developed. The algorithm searches over the integer variables and for each integer solution visited the corresponding values of the continuous variables are determined by solving a linear programming subproblem using the simplex algorithm. Numerical examples showed that the proposed method is efficient and effective in searching for near optimal solutions.