Search

In an earlier paper 7, we suggested employing the sealed-bid auction as a format for modelling the marketing of a wide range of heterogeneous products, including the marketing of most brand names. The formation of prices in such markets is described as if it resulted from an actual sealed-bid auction, with buyers inspecting the goods offered by sale by the various manufacturers, and making sealed bids which later are opened by a hypothetical auctioneer. While surely putative, this model nevertheless seems superior to the standard assumptions of perfect competition where a homogeneous commodity is transacted and all buyers offer identical prices. Extending the use of the sealed bid auction, we here consider cases where the manufacturers or distributors promote their sales by advertising. While the maximum quantity demanded by each customer is fixed and given, his bids on the various brands are determined by the advertising and other promotional efforts. The bid response function for each consumer is supposed to be given and known. The preceding vertical production and distribution chain, from the supply of raw materials and primary commodities, via the successive processing, manufacturing and distribution of the product is described as a transshipment auction game. We formulate a complementarity model that in one step solves this entire logistics system, including a possible formation of coalitions between suppliers and/or distributors, the market prices of the various brands, the optimal distribution of the product, and the bids of the consumers. A numerical example is provided and the solution routine is discussed.

In this paper a local integral simplex method will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex method creates and solves a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc., and the solution to at least one of which is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is the optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n. Preliminary computational experience is given which indicates that global method has a low order polynomial empirical performance when solving such problems.

The purpose of this paper is to prove that the weighted uni- dimensional similarities problem with least absolute value metric (USPAM) is, in general, NP-Hard. In the first four sections of the paper, the USPAM problem and four lemmas are presented which will be used in Section 6 to prove the main theorem of this paper. It is shown that the simple max cut problem can, in a polynomial number of steps, be converted into a special case of the USPAM problem, which shows that the USPAM problem is NP-Hard. Finally, some special cases of the USPAM problem are described for which polynomial solutions exist.