随机P矩阵和随机P0矩阵线性互补问题

定义了随机P矩阵和随机P0矩阵,给出了矩阵为随机P矩阵或随机P0矩阵的充要条件.研究了随机线性互补问题(SLCP)的矩阵为随机P矩阵时,期望残差方法(ERM)解集的有界性.得到了期望矩阵为P矩阵时,(ERM)解集非空有界.并且研究离散情形(ERM)与期望值方法(EV)解的关系,给出了(ERM)解唯一的条件.     

Facet of regular 0–1 polytopes

The role of 0–1 programming problems having monotone or regular feasible sets was pointed out in [6]. The solution sets of covering and of knapsack problems are examples of monotone and of regular sets respectively. Some connections are established between prime implicants of a monotone or a regular Boolean function on the one hand, and facets of the convex hullH of the zeros of on the other. In particular (Corollary 2) a necessary and sufficient condition is given for a constraint of a covering problem to be a facet of the corresponding integer polyhedron. For any prime implicantP of, a nonempty familyF(P) of facets ofH is constructed. Proposition 17 gives easy-to-determine sharp upper bounds for the coefficients of these facets when is regular. A special class of prime implicants is described for regular functions and it is shown that for anyP in this class,F(P) consists of one facet ofH, and this facet has 0–1 coefficients. Every nontrivial facet ofH with 0–1 coefficients is obtained from this class.     

The Collapsing 0–1 Knapsack Problem

The Collapsing 0–1 Knapsack Problem is a type of non-linear knapsack problem in which the knapsack size is a non-increasing function of the number of items included.An algorithm is developed and computational results included.     

On surrogating 0–1 knapsack constraints

In this note, we present a scheme for tightening 0–1 knapsack constraints based on other knapsack constraints surrogating. The preparation of this paper was partially supported by DGICYT through grant N. PB95-0407     

Persistency in quadratic 0–1 optimization

This paper is concerned with persistency properties which allow the evaluation of some variables at all maximizing points of a quadratic pseudo-Boolean function. Hammer, Hansen and Simeone (1984) have proposed to determine these variables using a procedure described by Balinski for computing a strongly complementary pair of optimal primal and dual solutions for arbitrary linear programs. We propose a linear time algorithm for determining these variables from a best roof off, i.e. from a lowest upper linear bound off.     

P型NFDE的(h_0,h,M_0)稳定性

本文将M0稳定性结合欢度量的概念推广到P型NFDE，并给出了稳定性的几个定理．     

A note for tightening 0–1 models

We describe two approaches for 0–1 program model tightening that are based on the coefficient increasing and reduction methods proposed in Dietrich, Escudero and Chance (1993). We present some characterizations for the new formulations to be tighter than the original model. It can be shown that tighter models can be obtained even when applying any of both approaches to a redundant constraint; see Escudero and Muñoz (1998). We also present some situations where these approaches cannot be applied.     

Concave extensions for nonlinear 0–1 maximization problems

A well-known linearization technique for nonlinear 0–1 maximization problems can be viewed as extending any polynomial in 0–1 variables to a concave function defined on [0, 1] ⁿ . Some properties of this standard concave extension are investigated. Polynomials for which the standard extension coincides with the concave envelope are characterized in terms of integrality of a certain polyhedron or balancedness of a certain matrix. The standard extension is proved to be identical to another type of concave extension, defined as the lower envelope of a class of affine functions majorizing the given polynomial.     

On characterizing tighter formulations for 0–1 programs

We present two approaches for 0–1 program model tightening. They are based on increasing and reducing knapsack constraint coefficients, respectively. Both approaches make use of information from cover structures implied by the original constraint system. The formulations that they provide are 0–1 equivalent and as tight as the original model. We also present some characterizations for the new formulations to be tighter than the original model.     

Large-scale 0–1 linear programming on distributed workstations

We present a methodology which uses a collection of workstations connected by an Ethernet network as a parallel processor for solving large-scale linear programming problems. On the largest problems we tested, linear and super-linear speedups have been achieved. Using the branch-and-cut approach of Hoffman, Padberg and Rinaldi, eight workstations connected in parallel solve problems from the test set documented in the Crowder, Johnson and Padberg 1983Operations Research article. Very inexpensive, networked workstations are now solving in minutes problems which were once considered not solvable in economically feasible times. In this peer-to-peer (as opposed to master-worker) implementation, interprocess communication was accomplished by using shared files and resource locks. Effective communication between processes was accomplished with a minimum of overhead (never more than 8% of total processing time). The implementation procedures and computational results will be presented.Supported in part by a grant from the Digital Equipment Corporation.Supported in part by grants from the Office of Naval Research and the National Science Foundation (ECS-8615438).     

Testing optimality for quadratic 0–1 unconstrained problems

This paper analyses a necessary and sufficient optimality condition for quadratic pseudo-Boolean unconstrained problems. It is proved that in general testing any necessary and sufficient optimality condition is a difficult task for anyNP-hard problem. An-optimality condition is derived together with an approximation scheme to test it.This work has been supported by the Progetto Finalizzato Trasporti 2, 93.01799.PF74.Professor Paolo Carraresi died unexpectedly on March 5, 1994. At the time of his death this paper had been completed. While undertaking the final revision, the other two authors were reminded just how much they were indebted to Professor Carraresi after many years of common work together.     

All 0–1 polytopes are traveling salesman polytopes

We study the facial structure of two important permutation polytopes in , theBirkhoff orassignment polytopeB _n , defined as the convex hull of alln×n permutation matrices, and theasymmetric traveling salesman polytopeT _n , defined as the convex hull of thosen×n permutation matrices corresponding ton-cycles. Using an isomorphism between the face lattice ofB _n and the lattice of elementary bipartite graphs, we show, for example, that every pair of vertices ofB _n is contained in a cubical face, showing faces ofB _n to be fairly special 0–1 polytopes. On the other hand, we show thatevery 0–1d-polytope is affinely equivalent to a face ofT _n , fordlogn, by showing that every 0–1d-polytope is affinely equivalent to the asymmetric traveling salesman polytope of some directed graph withn nodes. The latter class of polytopes is shown to have maximum diameter [n/3].Partially supported by NSF grant DMS-9207700.     

Fractional 0–1 programming: applications and algorithms

We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.     

Bregman Proximal Relaxation of Large-Scale 0–1 Problems

We apply a recent extension of the Bregman proximal method for convex programming to LP relaxations of 0–1 problems. We allow inexact subproblem solutions obtained via dual ascent, increasing their accuracy successively to retain global convergence. Our framework is applied to relaxations of large-scale set covering problems that arise in airline crew scheduling. Approximate relaxed solutions are used to construct primal feasible solutions via a randomized heuristic. Encouraging preliminary experience is reported.     

An evolutionary heuristic for quadratic 0–1 programming

In this paper we present a heuristic algorithm for the well-known Unconstrained Quadratic 0–1 Programming Problem. The approach is based on combining solutions in a genetic paradigm and incorporates intensification algorithms used to improve solutions and speed up the method. Extensive computational experiments on instances with up to 500 variables are presented and we compare our approach both with powerful heuristic and exact algorithms from the literature establishing the effectiveness of the method in terms of solutions quality and computing time.     

Supplement to the Pál type (0; 0, 1) lacunary interpolation

Letx ₁, …,x _n be givenn distinct positive nodal points which generate the polynomial $$\omega _n (x) = \prod\limits_{i = 1}^n {(x - x_i )} .$$ Letx*₁, …,x* _n?1 be the roots of the derivativeω′ _n (x) and putx ₀=0. In this paper, the following theorem is proved: Ify ₀, …,y _n andy′₁, …,y′ _n?1 are arbitrary real numbers, then there exists a unique polynomialP _2n?1(x) of degree 2n?1 having the following interpolation properties: $$P_{2n - 1} (x_j ) = y_j (j = 0,...,n),$$ , $$P_{2n - 1}^\prime (x_j^* ) = y_j^\prime (j = 1,...,n - 1).$$ . This result gives the theoretical completion of the original Pál type interpolation process, since it ensures uniqueness without assuming any additional condition.     

On One Generalization of the Hardy–Littlewood–Pólya Inequality

We generalize the Hardy–Littlewood–Pólya inequality for numerical sets to certain sets of vectors on a plane.     

Type II bivariate Pólya–Aeppli distribution

In this paper, we introduce the Type II bivariate Pólya–Aeppli distribution as a compound Poisson distribution with bivariate geometric compounding distribution. The probability mass function, recursion formulas, conditional distributions and some other properties are then derived for this distribution.