An efficient local search algorithm for the winner determination problem

Combinatorial auction, which allows bidders to bid on combinations of items, is an important type of market mechanism. The winner determination problem (WDP) has extensive applications in combinatorial auctions, and attracts more and more attention due to its strong relevance to business. However, this problem is intractable in theory as it has been proven to be NP-hard, and is also a challenging combinatorial optimization problem in practice. This paper is devoted to designing an efficient heuristic algorithm for solving the WDP. This proposed heuristic algorithm dubbed abcWDP is based on an effective yet simple local search framework, and equipped with three novel strategies, i.e., configuration checking, free-bid exploiting, and pseudo-tie mechanism. Extensive computational experiments on a broad range of benchmarks demonstrate that abcWDP performs much better than state-of-the-art algorithms and CPLEX in terms of both revenue and running time. More encouragingly, our abcWDP algorithm as a sequential algorithm even achieves better computational results than the multi-thread implemented algorithm \(\hbox {CA}_\mathrm{RA}\), which confirms its efficiency.     

基于权值编码的组合拍卖竞胜标确定启发式算法研究

针对较大规模组合拍卖竞胜标确定问题(WDP),提出了基于权值编码的竞胜标确定启发式算法.改进了算法编码机制并嵌入基于WDP本质特点的启发式搜索规则,极大地提高了算法进化能力和求解效率.模拟实验结果表明该算法能够在较短时间内求出WDP最优解或满意近似解,为较大规模网上组合拍卖竞胜标确定问题提供了切实可行的求解算法.     

A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.     

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.     

Importance Sampling,Large Deviations,and Differential Games

A standard heuristic in the area of importance sampling is that the changes of measure used to prove large deviation lower bounds give good performance when used for importance sampling. Recent work, however, has shown that a naive implementation of the heuristic is incorrect in many situations. The present paper considers the simple setting of sums of independent and identically distributed (iid) random variables, and shows that under mild conditions asymptotically optimal changes of measure can be found if one considers dynamic importance sampling schemes. For such schemes, the change of measure applied to an individual summand can depend on the historical empirical mean of the simulation (i.e. the system state). In analyzing the asymptotic performance of importance sampling, we show that the value function of a differential game characterizes the optimal performance, with player A corresponding to the choice of change of measure and player B arising due to a large deviations analysis. From this perspective, the traditional implementation of the heuristic is shown to correspond to player A choosing a control that is fixed, regardless of the system state or player B's choice of control. This leads to an "open loop" control for player A, which is suboptimal except in special cases. Our final contribution is a method, based on the Isaacs equation associated with the differential game, for constructing dynamic schemes. Numerical examples are presented to illustrate the results.     

An analysis of approximations for maximizing submodular set functions—I

LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)z(ST)+z(ST) for allS, T inN. Such a function is called submodular. We consider the problem max_SN{a(S):|S|K,z(S) submodular}.Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a greedy heuristic always produces a solution whose value is at least 1 –[(K – 1)/K] ^K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e – 1)/e, where e is the base of the natural logarithm.On leave of absence from Cornell University and supported, in part, by NSF Grant ENG 75-00568.Supported, in part, by NSF Grant ENG 76-20274.     

Combinatorial auctions

Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research. An earlier version of this paper appeared in 4OR 2, 1–33, 2004.     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

Design issues for combinatorial auctions

Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research.Received: April 2003, Revised: July 2003, AMS classification: 91B26, 90BXX, 90C27All correspondence to:Jawad Abrache     

Restart strategies for GRASP with path-relinking heuristics

GRASP with path-relinking is a hybrid metaheuristic, or stochastic local search (Monte Carlo) method, for combinatorial optimization. A restart strategy in GRASP with path-relinking heuristics is a set of iterations {i ₁, i ₂, …} on which the heuristic is restarted from scratch using a new seed for the random number generator. Restart strategies have been shown to speed up stochastic local search algorithms. In this paper, we propose a new restart strategy for GRASP with path-relinking heuristics. We illustrate the speedup obtained with our restart strategy on GRASP with path-relinking heuristics for the maximum cut problem, the maximum weighted satisfiability problem, and the private virtual circuit routing problem.     

A combinatorial proof of the Dense Hindman’s Theorem

The Dense Hindman’s Theorem states that, in any finite coloring of the natural numbers, one may find a single color and a “dense” set B₁, for each b₁∈B₁ a “dense” set (depending on b₁), for each a “dense” set (depending on b₁,b₂), and so on, such that for any such sequence of b_i, all finite sums belong to the chosen color. (Here density is often taken to be “piecewise syndetic”, but the proof is unchanged for any notion of density satisfying certain properties.) This theorem is an example of a combinatorial statement for which the only known proof requires the use of ultrafilters or a similar infinitary formalism. Here we give a direct combinatorial proof of the theorem.     

Multiattribute electronic procurement using goal programming

One of the key challenges of current day electronic procurement systems is to enable procurement decisions transcend beyond a single attribute such as cost. Consequently, multiattribute procurement have emerged as an important research direction. In this paper, we develop a multiattribute e-procurement system for procuring large volume of a single item. Our system is motivated by an industrial procurement scenario for procuring raw material. The procurement scenario demands multiattribute bids, volume discount cost functions, inclusion of business constraints, and consideration of multiple criteria in bid evaluation. We develop a generic framework for an e-procurement system that meets the above requirements. The bid evaluation problem is formulated as a mixed linear integer multiple criteria optimization problem and goal programming is used as the solution technique. We present a case study for which we illustrate the proposed approach and a heuristic is proposed to handle the computational complexity arising out of the cost functions used in the bids.     

Covering continuous demand in the plane

Continuous demand is generated in a convex polygon. A facility located in the area covers demand within a given radius. The objective is to find the locations for p facilities that cover the maximum demand in the area. A procedure that calculates the total area covered by a set of facilities is developed. A multi start heuristic approach for solving this problem is proposed by applying a gradient search from a randomly generated set of p locations for the facilities. Computational experiments for covering a square area illustrate the effectiveness of the proposed algorithm.     

The simultaneous computation of a few of the algebraically largest and smallest eigenvalues of a large,sparse, symmetric matrix

A heuristic argument and supporting numerical results are given to demonstrate that a block Lanczos procedure can be used to compute simultaneously a few of the algebraically largest and smallest eigenvalues and a corresponding eigenspace of a large, sparse, symmetric matrixA. This block procedure can be used, for example, to compute appropriate parameters for iterative schemes used in solving the equationAx=b. Moreover, if there exists an efficient method for repeatedly solving the equation (A–I)X=B, this procedure can be used to determine the interior eigenvalues (and corresponding eigenvectors) ofA closest to .     

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r3 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r3 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.     

A fast meta-heuristic approach for the $$(\alpha ,\beta )-k$$-feature set problem

The feature selection problem aims to choose a subset of a given set of features that best represents the whole in a particular aspect, preserving the original semantics of the variables on the given samples and classes. In 2004, a new approach to perform feature selection was proposed. It was based on a NP-complete combinatorial optimisation problem called (\(\alpha ,\beta \))-k-feature set problem. Although effective for many practical cases, which made the approach an important feature selection tool, the only existing solution method, proposed on the original paper, was found not to work well for several instances. Our work aims to cover this gap found on the literature, quickly obtaining high quality solutions for the instances that existing approach can not solve. This work proposes a heuristic based on the greedy randomised adaptive search procedure and tabu search to address this problem; and benchmark instances to evaluate its performance. The computational results show that our method can obtain high quality solutions for both real and the proposed artificial instances and requires only a fraction of the computational resources required by the state of the art exact and heuristic approaches which use mixed integer programming models.     

An optimal algorithm for generating equivalence relations on a linear array of processors

We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B _n) time solution, whereB _n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (n) elements is also described.The research is partialy supported by NSERC operating grant OGPIN 007.     

A biased random-key genetic algorithm for the project scheduling problem with flexible resources

In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an \(\mathcal {NP}\)-hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions.     

Relating Subsets of a Poset,and a Partition Theorem for WQOs

We point out some basic properties of the partial ordering which a poset P induces on its power set, defining AB to mean that every element of A lies below some element of B. One result is that if P is a WQO then P decomposes uniquely into finitely many indivisible sets A ₁,...,A _n (that are essential parts of P in the sense that PP\A _i ).