Robust strategic bidding in auction-based markets

In this paper, we propose an alternative methodology for devising revenue-maximizing strategic bids under uncertainty in the competitors’ bidding strategy. We focus on markets endowed with a sealed-bid uniform-price auction with multiple divisible products. On recognizing that the bids of competitors may deviate from equilibrium and are of difficult statistical characterization, we proposed a two-stage robust optimization model with equilibrium constraints aiming to devise risk-averse strategic bids. The proposed model is a trilevel optimization problem that can be recast as a particular instance of a bilevel program with equilibrium constraints. Reformulation procedures are proposed to find a single-level equivalent formulation suitable for column-and-constraint generation (CCG) algorithm. Results show that even for the case in which an imprecision of 1% is observed on the rivals’ bids in the equilibrium point, the robust solution provides a significant risk reduction (of 79.9%) in out-of-sample tests. They also indicate that the best strategy against high levels of uncertainty on competitors’ bid approaches to a price-taker offer, i.e., bid maximum capacity at marginal cost.     

MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem

In this paper we consider an integrated berth allocation and quay crane assignment and scheduling problem motivated by a real case where a heterogeneous set of cranes is considered. A first mathematical model based on the relative position formulation (RPF) for the berth allocation aspects is presented. Then, a new model is introduced to avoid the big-M constraints included in the RPF. This model results from a discretization of the time and space variables. For the new discretized model several enhancements, such as valid inequalities, are introduced. In order to derive good feasible solutions, a rolling horizon heuristic (RHH) is presented. A branch and cut approach that uses the enhanced discretized model and incorporates the upper bounds provided by the RHH solution is proposed. Computational tests are reported to show (i) the quality of the linear relaxation of the enhanced models; (ii) the effectiveness of the exact approach to solve to optimality a set of real instances; and (iii) the scalability of the RHH based on the enhanced mathematical model which is able to provide good feasible solutions for large size instances.     

Compact bidding languages and supplier selection for markets with economies of scale and scope

Combinatorial auctions have been used in procurement markets with economies of scope. Preference elicitation is already a problem in single-unit combinatorial auctions, but it becomes prohibitive even for small instances of multi-unit combinatorial auctions, as suppliers cannot be expected to enumerate a sufficient number of bids that would allow an auctioneer to find the efficient allocation. Auction design for markets with economies of scale and scope are much less well understood. They require more compact and yet expressive bidding languages, and the supplier selection typically is a hard computational problem. In this paper, we propose a compact bidding language to express the characteristics of a supplier’s cost function in markets with economies of scale and scope. Bidders in these auctions can specify various discounts and markups on overall spend on all items or selected item sets, and specify complex conditions for these pricing rules. We propose an optimization formulation to solve the resulting supplier selection problem and provide an extensive experimental evaluation. We also discuss the impact of different language features on the computational effort, on total spend, and the knowledge representation of the bids. Interestingly, while in most settings volume discount bids can lead to significant cost savings, some types of volume discount bids can be worse than split-award auctions in simple settings.     

Fuzzy Pattern Recognition Approach to Construction Contractor Selection

Contractor selection is a complex process crucial to ensuring the success of construction projects. Existing methods by which owners select a suitable contractor have been inadequate because it is difficult for decision-makers to evaluate contractor bids against inexact qualitative criteria. The purpose of this paper is to propose a Multiple-layer Fuzzy Pattern Recognition (MFPR) approach to solve contractor selection problem. Integrating judgments, experience and preferences of decision-makers, this paper uses the paired comparison method to decide relative membership degrees of qualitative criteria as well as weights of the criteria set, a case study for a channel construction project was used to demonstrate the feasibility of this approach. The findings clearly indicate that the techniques may successfully harmonize different opinions and reach a group consensus.     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.     

Reflections about pseudo-dual prices in combinatorial auctions

Combinatorial auctions permitting bids on bundles of items have been developed to remedy the exposure problem associated with single-item auctions. Given winning bundle prices, a set of item prices is called market clearing or equilibrium if all the winning (losing) bids are greater (less) than or equal to the total price of the bundle items. However, the prices for individual items are not readily computed once the winner determination problem is solved. This is due to the duality gap of integer programming caused by the indivisibility of the items. In this paper, we reflect on the calculation of approximate or pseudo-dual item prices. In particular, we present a novel scheme based on the aggregation of winning bids. Our analysis is illustrated by means of numerical examples.     

Using a DEA-cross efficiency approach in public procurement tenders

The paper addresses the topic of supplier selection in public procurement. According to European directives, when tenders are awarded through the “Most Economically Advantageous Tender” (MEAT) criterion, the awarding committee has to decide the tender evaluation criteria of the presented bids in advance. The authors propose a decision making tool that is aimed at helping the awarding committee in this difficult task and, at the same time, maintaining a transparent procedure in accordance with governmental procurement regulations and requirements as well as guaranteeing fair and equal evaluation of all bids. In this regard, the decision problem of supplier selection is addressed by applying an extension of the DEA (data envelopment analysis) methodology. The cross-efficiency evaluation is used for selecting the best supplier among the eligible candidates. The proposed technique allows the evaluation of quantitative data related to vendor selection and keeps the transparency features requested by public procurement. In addition, all bids are equally assessed according to the same objectively defined weights without any subjective setting by the public officers. The effectiveness and efficiency of the approach is supported by a case study that pertains to the tender of an Italian public agency.     

Spatial Instability Of Two-Phase Mixing Layers

The initial stage of liquid atomization by a fast gas stream is considered by means of spatial stability analysis of two–phase shear layers. We solve the viscous linear stability problem for parallel flow modelled by error–function profiles. The unstable modes known from temporal theory are recovered in the convectively unstable case for fluid properties close to the air/water system. The most unstable wavelength depends only weakly on the absolute velocity relative to the laboratory system. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Portfolio problems stopping at first hitting time with application to default risk

In this paper a portfolio problem is considered where trading in the risky asset is stopped if a state process hits a predefined barrier. This state process need not to be perfectly correlated with the risky asset. We give a representation result for the value function and provide a verification theorem. As an application, we explicitly solve the problem by assuming that the state process is an arithmetic Brownian motion. Then the result is used as a starting point to solve and analyze a portfolio problem with default risk modeled by the Black-Cox approach. Finally, we discuss how our results can be applied to a portfolio problem with stochastic interest rates and default risk modeled by the approach of Briys and de Varenne.     

A fast approximation algorithm for solving the complete set packing problem

We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.     

流面上的Navier-Stokes方程及其维数分裂方法

该文首先提出了流面和流层的概念,然后推导出了半测地坐标系下流层内的三维NS (Navier-Stokes)方程,以及流面上的二维NS方程.通过引入流面上的流函数,得到了流函数方程的非线性初边值问题,并讨论了方程解的存在性和唯一性.基于以上讨论,提出了求解三维NS方程的维数分裂方法, 并给出了算例.     

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.     

Multistage stochastic demand-side management for price-making major consumers of electricity in a co-optimized energy and reserve market

In this paper, we take an optimization-driven heuristic approach, motivated by dynamic programming, to solve a class of non-convex multistage stochastic optimization problems. We apply this to the problem of optimizing the timing of energy consumption for a large manufacturer who is a price-making major consumer of electricity. We introduce a mixed-integer program that co-optimizes consumption bids and interruptible load reserve offers, for such a major consumer over a finite time horizon. By utilizing Lagrangian methods, we decompose our model through approximately pricing the constraints that link the stages together. We construct look-up tables in the form of consumption-utility curves, and use these to determine optimal consumption levels. We also present heuristics, in order to tackle the non-convexities within our model, and improve the accuracy of our policies. In the second part of the paper, we present stochastic solution methods for our model in which, we reduce the size of the scenario tree by utilizing a tailor-made scenario clustering method. Furthermore, we report on a case study that implements our models for a major consumer in the (full) New Zealand Electricity Market and present numerical results.     

Explicit results for a class of asset-selling problems

We consider the following optimal selection problem: There are n identical assets which are to be sold, one at a time, to coming bidders. The bids are i.i.d. where there are only two possible bid-values, with known probabilities. The stream of bidders constitutes a general renewal process, and rewards are continuously discounted at a constant rate. The objective is to maximize the total expected discounted revenue from the sale of the n assets. The optimal policy here is stationary, where the decision in question is only whether to accept a low bid or not; the answer is affirmative depending on a critical number n^* of remaining assets. In this paper we derive an explicit formula for n^*, being a function of the Laplace transform of the renewal distribution evaluated at the discount rate, the probability for a low bid, and the ratio between the two bid-values. We also specify the pertinent value functions. Applications of the model are discussed in detail, and extensions are made to include holding costs and to allow for optimal pricing.     

The auction algorithm: A distributed relaxation method for the assignment problem

We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi — like relaxation method for solving a dual problem. Its (sequential) worst — case complexity, for a particular implementation that uses scaling, is O(NAlog(NC)), where N is the number of persons, A is the number of pairs of persons and objects that can be assigned to each other, and C is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.Work supported by Grant NSF-ECS-8217668. Thanks are due to J. Kennington and L. Hatay of Southern Methodist Univ. for contributing some of their computational experience.     

Optimization of discrete broadcast under uncertainty using conditional value-at-risk

The paper considers the problem of scheduling packets in wireless broadcast systems under uncertainty with the conditional value-at-risk (CVaR) constraints. In such systems, a server periodically transmits a stream of packets over a broadcast channel. The client that needs to access the data, tunes in to the channel and waits for the next packet. This allows one to serve a large number of clients in an efficient way and also keep clients’ location secret. We formulate and solve two alternative stochastic optimization problems that minimize the transmission time subject to CVaR constraints. Our results indicate that it is possible to derive an analytical solution to the problems in certain cases of practical interest. We also propose a methodology to obtain numerical solutions for the general case.     

面向电子逆向拍卖的多属性报价建议模型

针对多属性拍卖中报价的复杂性和现有报价指导模型的局限性,提出了一个以拍卖方的总价值提升为基本约束,以投标人的利润最大化为目标的多属性报价建议模型,并引入二元变量解决了定性属性的推荐问题。当投标人具有不同的投标能力和偏好时,模型可根据投标人的投标要求进行报价推荐;当存在单位价值相同的推荐报价时,模型设置了相应的约束以鼓励早投标行为。最后,还从理论上证明了该模型的稳定性,并通过算例说明了模型的可行性。     

Vortex generated fluid flows in multiply connected domains

A fluid flow in a multiply connected domain generated by an arbitrary number of point vortices is considered. A stream function for this flow is constructed as a limit of a certain functional sequence using the method of images. The convergence of this sequence is discussed, and the speed of convergence is determined explicitly. The presented formulas allow for an easy computation of the values of the stream function with arbitrary precision in the case of well-separated cylinders. The considered problem is important for applications such as eddy flows in oceans. Moreover, since finding the stream function of the flow is essentially identical to finding the modified Green’s function for Laplace’s equation, the presented method can be applied to a more general class of applied problems which involve solving the Dirichlet problem for Laplace’s equation.     

Asymptotic solutions of Fredholm integro-differential equations with rapidly varying kernels and irreversible limit operator

We consider a system of singularly perturbed integro-differential Fredholm equations with rapidly varying kernel in the case of irreversible operator of differential part. We develop an algorithm for constructing regularized asymptotic solutions. It is shown that in the presence of rapidly decreasing multiplier in the kernel the original problem is not on the spectrum (i.e, it is solvable for any right-hand side). We study the limit transition (with small parameter tending to zero), and solve the problem of initialization, i.e., the problem of extracting of the source data for which an exact solution to the system tends to the limit at all duration (including a zone of boundary layer).