Equivalence of permutation polytopes corresponding to strictly supermodular functions

This paper demonstrates a strong equivalence of all permutation polytopes corresponding to strictly supermodular functions.     

Q-matrix recognition via secondary and universal polytopes

T (Mx+q)=0, Mx+q≥0, x≥0 has a solution. We explain how one can use the polyhedral structure of the set of all triangulations of a finite point set to determine if an n×n matrix M is a Q-matrix. Our implementation of the algorithm is practical for deciding the Q-nature for all M with n≤8. Received May 30, 1997 / Revised version received June 12, 1998 Published online November 24, 1998     

Intersection theorems on polytopes

Received June 6, 1995 / Revised version received May 26, 1998 Published online October 9, 1998     

Residue formulae, vector partition functions and lattice points in rational polytopes

We obtain residue formulae for certain functions of several variables. As an application, we obtain closed formulae for vector partition functions and for their continuous analogs. They imply an Euler-MacLaurin summation formula for vector partition functions, and for rational convex polytopes as well: we express the sum of values of a polynomial function at all lattice points of a rational convex polytope in terms of the variation of the integral of the function over the deformed polytope.

     

Box-inequalities for quadratic assignment polytopes

Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope. Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001     

Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control

Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions, tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational effort. We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct, at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the basic subgradient scheme. Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999     

Notes on L-/M-convex functions and the separation theorems

The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis. Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000     

The stable admissions polytope

The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities. It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been fruitful in the analysis of the stable marriage problem. Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000     

On the Asymptotic Behaviour of General Partition Functions

For A = {a₁, a₂,...} N, let p_A(n) denote the number of partitions of n into a's and let q_A(n) denote the number of partitions of n into distinct a's. The asymptotic behaviour of the quotient is studied.     

Exceptional Congruences for Powers of the Partition Function

In Journal of London Math. Soc. 31 (1956), 350–359, Morris Newman studied vector spaces of functions arising from lifts to ₀(p) of certain eta-products on the group ₀(pQ), Q = p ⁿ. In this paper, the author considers vector spaces of modular functions obtained as lifts of more general eta-products from ₀(pQ) to ₀(p), (Q, p) = 1. Specifically considered are functions arising as lifts of functions of the form

On the convexity of the multiplicative potential and penalty functions and related topics

It is well known that a function f of the real variable x is convex if and only if (x,y)→yf(y ^-1 x),y>0 is convex. This is used to derive a recursive proof of the convexity of the multiplicative potential function. In this paper, we obtain a conjugacy formula which gives rise, as a corollary, to a new rule for generating new convex functions from old ones. In particular, it allows to extend the aforementioned property to functions of the form (x,y)→g(y)f(g(y)^-1 x) and provides a new tool for the study of the multiplicative potential and penalty functions. Received: June 3, 1999 / Accepted: September 29, 2000?Published online January 17, 2001     

Trees and Keislers problem

We give a new negative solution to Keisler's problem regarding Skolem functions and elementary extensions. In contrast to existing ad hoc solutions due to Payne, Knight, and Lachlan, our solution uses well-known models. Received: 20 September 1999 / Published online: 21 March 2001     

A production-transportation problem with stochastic demand and concave production costs

Well known extensions of the classical transportation problem are obtained by including fixed costs for the production of goods at the supply points (facility location) and/or by introducing stochastic demand, modeled by convex nonlinear costs, at the demand points (the stochastic transportation problem, [STP]). However, the simultaneous use of concave and convex costs is not very well treated in the literature. Economies of scale often yield concave cost functions other than fixed charges, so in this paper we consider a problem with general concave costs at the supply points, as well as convex costs at the demand points. The objective function can then be represented as the difference of two convex functions, and is therefore called a d.c. function. We propose a solution method which reduces the problem to a d.c. optimization problem in a much smaller space, then solves the latter by a branch and bound procedure in which bounding is based on solving subproblems of the form of [STP]. We prove convergence of the method and report computational tests that indicate that quite large problems can be solved efficiently. Problems up to the size of 100 supply points and 500 demand points are solved. Received October 11, 1993 / Revised version received July 31, 1995 Published online November 24, 1998     

Ideal polytopes and face structures of some combinatorial optimization problems

Given a finite setX and a family of feasible subsetsF ofX, the 0–1 polytope P (F is defined as the convex hull of all the characteristic vectors of members ofF We show that under a certain assumption a special type of face ofP(F) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, we propose a new heuristic for such problems and give results of our preliminary computational experiments for the maximum stable set problem.Supported by a JSPS Fellowship for Young Scientists.Supported by Grant-in-Aids for Co-operative Research (06740147) of the Ministry of Education, Science and Culture.     

On existence and uniqueness of stationary points in semi-infinite optimization

The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied. Received June 30, 1995 / Revised version received October 9, 1998? Published online June 11, 1999     

Properties of the Moreau-Yosida regularization of a piecewise C2 convex function

Received December 14, 1995 / Revised version received May 7, 1998 Published online October 21, 1998     

Multisided matching games with complementarities

The paper considers multisided matching games with transfereable utility using the approach of cooperative game theory. Stable matchings are shown to exist when characteristic functions are supermodular, i.e., agents' abilities to contribute to the value of a coalition are complementary across types. We analyze the structure of the core of supermodular matching games and suggest an algorithm for constructing its extreme payoff vectors. Received February 1997/Final version September 1998