A min-max theorem for plane bipartite graphs

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621-1625].     

关于矩形和斜带模型的反强迫数和反凯库勒数

在苯类化合物的凯库勒结构的研究中引入了反强迫数和反凯库勒数.通过分析矩形和斜带模型苯类化合物的分子图的结构,证明了具有k行l列的矩形R[k,l]和斜带模型Z[k,l]的反凯库勒数是2,R[k,l]的反强迫数是l,Z[k,l]的反强迫数不超过[(l+1)/2],其中[x]表示不超过x的最大整数.     

Balanced matrices

This paper studies some properties of hypergraphs in connection with a class of integer linear programming problems. The main result (theorem 3) states that the strong chromatic number of a balanced hypergraph is equal to its rank; this generalizes a result known for unimodular hypergraphs. Two applications of this result are given, the first one to Graph theory (theorem 5), the second one to integral linear programming (theorem 6).     

None of the coronoid systems can be isometrically embedded into a hypercube

A graph that can be isometrically embedded into a hypercube is called a partial cube (or binary Hamming graph). Klavžar, Gutman and Mohar [S. Klavžar, I. Gutman, B. Mohar, Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inf. Comput. Sci. 35 (1995) 590–593] showed that all benzenoid systems are partial cubes. In this article we show that none of the coronoid systems (benzenoid systems with “holes”) is a partial cube.     

The Clar formulas of a benzenoid system and the resonance graph

It is shown that the number of Clar formulas of a Kekuléan benzenoid system B is equal to the number of subgraphs of the resonance graph of B isomorphic to the Cl(B)-dimensional hypercube, where Cl(B) is the Clar number of B.     

Chaos, self-organized criticality, and SETAR nonlinearity: An analysis of purchasing power parity between Canada and the United States

This paper uses monthly observations for the real exchange rate between Canada and the United States over the recent flexible exchange rate period (from January 1, 1973 to August 1, 2004) to test purchasing power parity between Canada and the United States using unit root and stationarity tests. Moreover, given the apparent random walk behavior in the real exchange rate, various tests from dynamical systems theory, such as for example, the Nychka et al. [Nychka DW, Ellner S, Ronald GA, McCaffrey D. Finding chaos in noisy systems. J Roy Stat Soc B 1992;54:399–426] chaos test, the Li [Li W. Absence of 1/f spectra in Dow Jones average. Int J Bifurcat Chaos 1991;1:583–97] self-organized criticality test, and the Hansen [Hansen, B.E. Inference when a nuisance parameter is not identified under the null hypothesis. Econometrica 1996;64:413–30] threshold effects test are used to distinguish between stochastic and deterministic origin for the real exchange rate.     

Zero-one programming with many variables and few constraints

One of the more successful techniques for solving zero-one integer programs has been the implicit enumeration strategy first introduced by E. Balas. However, experience has shown that the efficiency of these enumerative techniques depends critically upon the bumber of variables. In this paper an algorithm is developed and computational experience provided for solving zero-one integer programs with many variables and few constraints. Sub-problems solved via implicit enumeration are generated from the linear programming relaxation and the variables in these sub-problems correspond to the fractional variables obtained in the linear program. Since the number of fractional variables in the linear program is bounded by the number of constraints in the linear program, the sub-problems will in general contain many fewer variables than the original zero-one integer program.     

An optimal solution to a three echelon supply chain network with multi-product and multi-period

Recently, Kadadevaramath et al. (2012) [1] presented a mathematical model for optimizing a three echelon supply chain network. Their model is an integer linear programming (ILP) model. In order to solve it, they developed five algorithms; four of them are based on a particle swarm optimization (PSO) method and the other is a genetic algorithm (GA). In this paper, we develop a more general mathematical model that contains the model developed by Kadadevaramath et al. (2012) [1]. Furthermore, we show that all instances proved in Kadadevaramath et al. (2012) [1] can easily be solved optimally by any integer linear programming solver.     

Determination of optimal vertices from feasible solutions in unimodular linear programming

In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.This author's research is partially supported by NSF grant DDM-8921835 and Airforce Grant AFSOR-88-0088.     

A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

Designing an optimal connected nature reserve

We consider a landscape divided into elementary cells, each of these cells containing some species to be protected. We search to select a set of cells to form a natural reserve in order to protect all the species present in the landscape. A species is considered protected if it is present in a certain number of cells of the reserve. There is an important spatial constraint concerning the set of selected cells: a species must be able to go from any cell to any cell without leaving the reserve. An integer linear programming model was proposed by Önal and Briers [2] for this reserve selection problem, but the size of the problems which can be handled by this model is limited: several hours of computation are required for solving instances with hundred of cells and hundred of species. Having proposed an improvement of this model which reduces appreciably the computation time, we propose another integer linear programming model, easy to carry out, which allows to obtain, in a few seconds of computation, optimal or near-optimal solutions for instances with hundred of cells and hundred of species. However, the computation time becomes prohibitive for instances with more than 200 cells and 100 species. But, this approach can be particularly useful to solve the problem, in an approximate way, by aggregation of cells as proposed by Önal and Briers [2].     

Alternatives for testing total dual integrality

In this paper we provide characterizing properties of totally dual integral (TDI) systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system’s dual integer programs where all test vectors have positive entries equal to 1. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick’s sufficient condition for the TDI property and Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. We also study the theoretical and practical efficiency and limits of the characterizations of the TDI property presented here. In the particular case of set packing polyhedra our results correspond to endowing the weak perfect graph theorem with an additional, computationally interesting, geometric feature: the normal fan of the stable set polytope of a perfect graph can be refined into a regular triangulation consisting only of unimodular cones.     

A Branch and Bound Algorithm for a Class of Asymmetrical Vehicle Routeing Problems

This paper describes a branch and bound algorithm for a general class of asymmetrical vehicle routeing problems. Vehicle routes start and end at a central depot. Visits are made to nodes grouped into clusters: every cluster must receive a minimum number of visits. But not all nodes must be visited: there are specified nodes and non-specified nodes. Vehicle routes are also constrained by capacity and distance restrictions. The problem is formulated as an integer linear program. It is then solved by a branch and bound algorithm which exploits the unimodular structure of the subproblems. Computational results are reported.     

Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching

The airline crew scheduling problem is the problem of assigning crew itineraries to flights. We develop a new approach for solving the problem that is based on enumerating hundreds of millions random pairings. The linear programming relaxation is solved first and then millions of columns with best reduced cost are selected for the integer program. The number of columns is further reduced by a linear programming based heuristic. Finally an integer solution is obtained with a commercial integer programming solver. The branching rule of the solver is enhanced with a combination of strong branching and a specialized branching rule. The algorithm produces solutions that are significantly better than ones found by current practice.     

奥运会临时超市网点的优化设计

在对[1]提供的问卷调查数据进行处理的基础上,运用商圈理论,就2008北京奥运会比赛主场馆周边地区临时超市网点(MS)的设计问题,在满足购物需求、分布基本均衡和商业上赢利三大基本要求上,建立起整数线性规划数学模型,并得到较为理想的优化设计结果.     

Phasing out Capital Equipment

A new formulation is proposed for the problem of the optimal phasing out over some time period of a group of similar items of capital equipment. The possibility of hiring items from an external source is explicitly considered, as are policy constraints which restrict the minimum number of items which may be held at any time. Initially formulated as an integer program, the problem is transformed to the familiar transportation form of linear programming.     

Computable numerical bounds for lagrange multipliers of stationary points of non-convex differentiable non-linear programs

It is shown that the satisfaction of a standard constraint qualification of mathematical programming [5] at a stationary point of a non-convex differentiable non-linear program provides explicit numerical bounds for the set of all Lagrange multipliers associated with the stationary point. Solution of a single linear program gives a sharper bound together with an achievable bound on the 1-norm of the multipliers associated with the inequality constraints. The simplicity of obtaining these bounds contrasts sharply with the intractable NP-complete problem of computing an achievable upper bound on the p-norm of the multipliers associated with the equality constraints for integer $\text{p ≧ 1}$.     

The problem of conflicting control with mixed constraints

The control problem for a linear dynamical system is considered at a minimax of the terminal quality index. Feasible controls are simultaneously restricted by geometrical constraints and by integrated momentum constraints, the latter being thought of as a store of control resources. The problem is formalized as a differential game [1–4] using concepts [5–8] developed at Ekaterinburg. Here, because of the geometrical constraints, the momentum formulation and its associated difficulties [2–4] do not appear. On the other hand the presence of the integral restrictions leads to the appearance of additional variables whose evolution describes the dynamics of the expenditure of the control resources. These variables are subject to phase restrictions, which is a peculiarity of the problem. A reasonably informative picture and a class of strategies for which the given game has a value and a saddle point are given. A constructive method for computing the value function of the game and constructing optimal strategies is presented. This method is conceptually related to the construction of a stochastic programming synthesis [5] and is based on the recursive construction of upper-convex envelopes for certain auxiliary functions. The possibility of exchanging the minimum and maximum operations over the resource parameters when calculating the value of the game using these procedure is established.     

Comments on “A bicriteria flowshop scheduling problem with setup times”

The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling problem with setup times, Appl. Math. Comput. 183 (2006) 1292-1300] is incorrect. We propose a new integer programming model for the same scheduling problem based on their model.