A nonlinear approach to a class of combinatorial optimization problems

A special class of combinatorial optimization problems is considered. We develop a compact nonconvex quadratic model for these problems that incorporates all inequality constraints in the objective function, and discuss two approximation algorithms for solving this model. One is inspired by Karmarkar's potential reduction algorithm for solving combinatorial optimization problems; the other is a variant of the reduced gradient method. The paper concludes with computational experiences with both real-life and randomly generated instances of the frequency assignment problem. Large problems are satisfactorily solved in reasonable computation times.     

THE JOINT ARRIVAL AND DEPARTURE PROCESS FOR THE M/M/l QUEUE

We consider the M/M/1-queue and derive an explicit expression for the joint distribution of the number of arrivals and the number of departures in [0, t), given the number of customers initially present. The derivation is almost purely combinatorial, it avoids the use of generating functions, and immediately yields a simple probabilistic interpretation of the result.     

User acceptance of complex electronic market mechanisms: Role of information feedback

This paper broadens the scope of evaluating the design of economic mechanisms that is traditionally done solely from an economic perspective. We introduce and demonstrate the application of acceptability to evaluate complex economic mechanisms. In particular, we apply our approach to the evaluation of continuous combinatorial auctions, which represent a complex, sophisticated market mechanism that has not been generally available in the online marketplace but has the potential to enhance the economic efficiency of trade for assets with interdependent values. Such auctions are being increasingly used in industry, e.g., to procure logistical services. Intuitively, acceptance and usage of a complex mechanism can be fostered by a design that provides information and tools that meet the users’ task demands. Based on prior research and an analysis of the auction tasks, we discuss practical and innovative information feedback schemes for reducing the cognitive burden of formulating bids in combinatorial auctions. Then, we use constructs from the technology acceptance model (TAM) – which have been consistently shown to be key determinants of technology acceptance in the extant literature – to compare the acceptability of the mechanism under three different information regimes. In addition, we borrow constructs from marketing theory to assess the potential growth in adoption of the mechanism. We compare user perceptions of the three alternative designs in a laboratory experiment with over 130 subjects. Our study constitutes a complementary and novel approach in evaluating the design of complex economic mechanisms. Results indicate a higher adoption and usage potential of the mechanism with advanced information feedback, supporting the potential of combinatorial auctions as a user-acceptable market mechanism with appropriate feedback.     

Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem

The introduction of Karmarkar's polynomial algorithm for linear programming (LP) in 1984 has influenced wide areas in the field of optimization. While in the 1980s emphasis was on developing and implementing efficient variants of interior point methods for LP, the 1990s have shown applicability to certain structured nonlinear programming and combinatorial problems. We will give a historical account of the developments and illustrate the typical results by analyzing a new method for computing the smallest eigenvalue of a matrix. We formulate this latter problem as a so-called semidefinite optimization problem. Semidefinite optimization has recently gained much attention since it has a lot of applications in various fields (like control and system theory, combinatorial optimization, algebra, statistics, structural design) and semidefinite problems can be efficiently solved with interior point methods.     

A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem

We describe a genetic algorithm for the partial constraint satisfaction problem. The typical elements of a genetic algorithm, selection, mutation and cross-over, are filled in with combinatorial ideas. For instance, cross-over of two solutions is performed by taking the one or two domain elements in the solutions of each of the variables as the complete domain of the variable. Then a branch-and-bound method is used for solving this small instance. When tested on a class of frequency assignment problems this genetic algorithm produced the best known solutions for all test problems. This feeds the idea that combinatorial ideas may well be useful in genetic algorithms.     

Capability-based governance patterns over the product life-cycle: an agent-based model

In recent literature, there is disagreement over the temporal pattern of vertical governance of firms over the product life-cycle. We use a novel neo-Schumpeterian agent-based simulation model to investigate emerging patterns of vertical governance for different levels of imitability and substitutability of capabilities. We find that, in the mature phase of the product life-cycle, firms generally prefer vertical specialization. However, in the early phase, imitability and substitutability, in interplay, determine the governance form preferred. High imitability frustrates appropriation and thereby discourages integration for synergistic advantages. However, firms need not vertically specialize: under low substitutability, incompatibilities reduce the advantages of specialization. When both substitutability and imitability are low, firms can appropriate the value of their inventions and there is no combinatorial advantage of specialization, so firms predominantly integrate. If substitutability is high and imitability is low, the combinatorial advantage of specialization balances with the synergistic advantage of integration.     

Computation of robust estimates of multivariate location and shape

This paper reviews the state of the art in the computation of robust estimates of multivariate location and shape using combinatorial estimators such as the minimum volume ellipsoid (MVE) and iterative M- and S-estimators. We also present new results on the behavior of M- and S-estimators in the presence of different types of outliers, and give the first computational evidence on compound estimators that use the MVE as a starting point for an S-estimator. Problems with too many data points in too many dimensions cannot be handled by any available technology; however, the methods presented in this paper substantially extend the size of problem that can be successfully handled.     

Polyhedral Combinatorics in Combinatorial Optimization

Polyhedral combinatorics is a subarea of combinatorial optimization of increasing practical importance. It deals with the application of the theory of linear systems and linear algebra to combinatorial problems. The paper is not intended as a survey on polyhedral combinatorics but it reviews some of the main concepts and proof techniques.     

基于IOWA-FAHP的物流需求组合预测模型

面向物流需求的预测问题,提出了一种基于诱导有序加权平均算子和模糊层次分析法相结合的组合预测模型。首先,采用诱导有序加权平均算子建立组合预测模型,并基于历史数据解算各单项预测模型的加权系数;然后,针对组合预测模型中各单项模型的加权系数确定问题,引入模糊层次分析法,得到各单项预测模型的公平排序,进而确定各单项预测模型在预测年的诱导值序列,从而预测出相应物流需求量;最后通过应用算例验证了该模型的正确性和可靠性。     

Simultaneous optimization of land use and transportation: A synthesis of the quadratic assignment problem and the optimal network problem

The problem of designing jointly a land use plan and a transportation network for a new town is formalized as a combinatorial programming problem which can be considered as an extension of the Koopmans-Beckmann problem. Accessibility and capital costs are the criteria taken into account to evaluate a plan. One exact technique and several heuristic techniques are reported and evaluated.     

三维装箱问题的启发式算法

三维装箱问题是一类典型的NP-hard组合优化问题。在一维、二维装箱问题基础上,设计了一种启发式算法,借以克服一般启发式算法依赖"经验"的不足,该算法结构简单,实验表明算法收敛速度快。     

个性化服务能力测评

对个性化服务能力的概念进行界定,并借鉴GAP差距模型,对个性化服务能力测评思路和测评指标进行了系统分析和梳理,形成了7大类22个具体指标;并通过主成分分析法和熵值法相结合的方法,对个性化服务能力进行测评,对具体的测评步骤进行了说明;并以LJ烟草公司与中国邮政的物流服务供应链为例进行了说明。     

Fast movement strategies for a step-and-scan wafer stepper

We describe algorithms for the determination of fast movement strategies for a step-and-scan wafer stepper, a device that is used for the photolithographic processing of integrated circuits. The proposed solution strategy consists of two parts. First, we determine the maximum number of congruent rectangular chips that can be packed on a wafer, subject to the restriction that the chips are placed in a rectangular grid. Second, we find fast movement strategies for scanning all chips of a given packing, given the mechanical restrictions of the wafer stepper. The corresponding combinatorial optimization problem is formulated as a generalized asymmetric traveling salesman problem. We show how feasible scan strategies are determined, and how these strategies are improved by local search techniques, such as iterative improvement based on 2- and 3-exchanges, and simulated annealing based on 2-exchanges.     

Experiments Testing Multiobject Allocation Mechanisms

This paper reports the results of over 130 auctions conducted under controlled conditions to examine the robustness of several auction mechanisms to allocate multiple objects. The simultaneous discrete auction process used by the Federal Communications Commission to allocate Personal Communications licenses was contrasted with a sequential auction and a combinatorial auction over a variety of demand conditions. In test environments created to check only the minimum competency of the procedures, the simultaneous discrete auction process produces highly efficient allocations, approaching levels similar to those found with a continuous form of the auction, and it outperforms a sequential auction. However, in environments created to stress test the procedures, a combinatorial auction outperforms the simultaneous discrete auction.     

JIT环境下多工序订单生产排序模型及改进蚁群算法应用研究

订单排序问题是一类典型的组合优化问题,采用改进蚁群算法对一种具有多生产工序和JIT交货的订单模型进行建模求解,给出了详细的算法步骤,通过仿真计算和结果分析,与模拟退火算法和基本蚁群算法进行对比,证明了本算法的有效性。     

基于组合权重的绿色度三角模糊函数模糊综合评价研究

首先建立了一套生产型节点企业绿色度综合评价指标体系,然后综合运用熵权值法、德尔菲法、层次分析法、三角模糊函数法形成的模糊综合评价方法对绿色度的评价问题进行研究,提出了基于组合权重的三角模糊函数模糊综合评价方法及其完整的评价过程,最后以供应链上多家企业的实际数据为例进行了实证研究。     

EQUILIBRIA EXISTENCE AND CHARACTERIZATION IN AUCTIONS: ACHIEVEMENTS AND OPEN QUESTIONS

Abstract Establishing existence and characterizing equilibria are both important achievements in the study of auctions. However, we recognize that equilibria existence results form the basis for well accepted characterizations. In this survey, we review the landmark results and highlight open questions regarding equilibria existence and characterizations in auctions. In addition, we review the standard assumptions underlying these results, and discuss the suitability of the Nash equilibrium solution concept. We focus our review on single‐object auctions, but also review results in multi‐unit, divisible, combinatorial and double auctions.     

关于六边形数列的一些恒等式

研究了一些有趣的六边形数列的性质,同时给出了一些组合恒等式。