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.     

Games in oriented matroids

We introduce a combinatorial abstraction of two person finite games in an oriented matroid. We also define a combinatorial version of Nash equilibrium and prove that an odd number of equilibria exists. The proof is a purely combinatorial rendition of the Lemke–Howson algorithm.     

Decomposing random mechanisms

Random mechanisms have been used in real-life situations for reasons such as fairness. Voting and matching are two examples of such situations. We investigate whether the desirable properties of a random mechanism survive decomposition of the mechanism as a lottery over deterministic mechanisms that also hold such properties. To this end, we represent properties of mechanisms–such as ordinal strategy-proofness or individual rationality–using linear constraints. Using the theory of totally unimodular matrices from combinatorial integer programming, we show that total unimodularity is a sufficient condition for the decomposability of linear constraints on random mechanisms. As two illustrative examples we show that individual rationality is totally unimodular in general, and that strategy-proofness is totally unimodular in some individual choice models. We also introduce a second, more constructive approach to decomposition problems, and prove that feasibility, strategy-proofness, and unanimity, with and without anonymity, are decomposable in non-dictatorial single-peaked voting domains. Just importantly, we establish that strategy-proofness is not decomposable in some natural problems.     

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.     

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.     

编码在大比例数字测图中的应用

使用全站仪野外数字测图是一项需要相互协作的团体作业过程,本文主要介绍一种编码的方法来解决这个问题。利用新方法采集外业数据的时候只需要两个人,不需要绘草图,不仅减少了外业的工作量,最重要的是内业基本实现全自动化,解决了高程点坐标、图层、线型及连接关系等问题,大大减轻了内业人员成图编辑的工作量。     

陕西省建筑行业总产值发展趋势预测研究

近十年,陕西省建筑行业稳步、快速、持续发展,为省内生产总值贡献重要力量。通过汇总陕西省2000-2011年建筑行业逐年总产值情况,利用线性回归分析法,针对"十二五"期间陕西省建筑行业的总产值情况进行定性与定量的综合分析,并做出初步预测,为"十二五"期间陕西省建筑行业的发展提供参考。     

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.     

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

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

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.     

差异演化算法求解集合划分问题

集合划分问题是组合优化中典型的NP难题,建立了集合划分问题模型,采用差异演化算法对其进行求解。通过对其它文献中仿真实例的计算和结果对比,表明了算法对求解集合划分问题的可行性和有效性。     

基于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.     

直线法线式方程在建筑施工放样中的应用

建筑物轴线的放样主要是计算出各轴线的交点的坐标,然后通过全站仪极坐标放样的方法定出轴线交点的位置。由于建筑物坐标系和测量坐标系不同,应先通过坐标转换将建筑物轴线交点转换为测量指标,本文提出无需进行坐标转换,而是通过建立建筑方格网主轴线法线式直线方程,并以此推求出建筑物轴线的法线式直线方程,进而通过解方程组求得交点坐标。     

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

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