Concentration inequalities for nonlinear matroid intersection

In this work we propose new randomized rounding algorithms for matroid intersection and matroid base polytopes. We prove concentration inequalities for polynomial objective functions and constraints that has numerous applications and can be used in approximation algorithms for Minimum Quadratic Spanning Tree, Unrelated Parallel Machines Scheduling and scheduling with time windows and nonlinear objectives. We also show applications related to Constraint Satisfaction and dense polynomial optimization. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 541–571, 2015     

取整函数及其生成的数列

讨论三类整数列，这些数列的后项均是由前项与非整数乘积再取整后得到的，对应的取整函数分别为四舍五入取整函数、下取整函数、上取整函数．结果表明这三类整数列均为二阶线性递归数列．     

On the L<Subscript>∞</Subscript>-norm of extreme points for crossing supermodular directed network LPs

We discuss extensions of Jain’s framework for network design [8] that go beyond undirected graphs. The main problem is approximating a minimum cost set of directed edges that covers a crossing supermodular function. We show that iterated rounding gives a factor 3 approximation, where factor 4 was previously known and factor 2 was conjectured. Our bound is tight for the simplest interpretation of iterated rounding. We also show that (the simplest version of) iterated rounding has unbounded approximation ratio when the problem is extended to mixed graphs.      

A simple plant-location model for quantity-setting firms subject to price uncertainty

The uncapacitated plant location problem under uncertainty is formulated in a mean-variance framework with prices in various markets correlated via their response to a common random factor. This formulation results in a mixed-integer quadratic programming problem. However, for a given integer solution, the resulting quadratic programming problem is amenable to a very simple solution procedure. The simplicity of this algorithm means that reasonably large problems should be solvable using existing branch-and-bound techniques.     

Generating facets for finite master cyclic group polyhedra using n-step mixed integer rounding functions

The n-step mixed integer rounding (MIR) functions generate n-step MIR inequalities for MIP problems and are facets for the infinite group problems. We show that the n-step MIR functions also directly generate facets for the finite master cyclic group polyhedra especially in many cases where the breakpoints of the n-step MIR function are not necessarily at the elements of the group (hence the linear interpolation of the facet coefficients obtained has more than two slopes).     

Solving the Unit Commitment Problem by a Unit Decommitment Method

In this paper, we present a unified decommitment method to solve the unit commitment problem. This method starts with a solution having all available units online at all hours in the planning horizon and determines an optimal strategy for decommitting units one at a time. We show that the proposed method may be viewed as an approximate implementation of the Lagrangian relaxation approach and that the number of iterations is bounded by the number of units. Numerical tests suggest that the proposed method is a reliable, efficient, and robust approach for solving the unit commitment problem.     

On the existence of solutions to the quadratic mixed-integer mean–variance portfolio selection problem

In the standard mean–variance portfolio selection approach, several operative features are not taken into account. Among these neglected aspects, one of particular interest is the finite divisibility of the (stock) assets, i.e. the obligation to buy/sell only integer quantities of asset lots whose number is pre-established. In order to consider such a feature, we deal with a suitably defined quadratic mixed-integer programming problem. In particular, we formulate this problem in terms of quantities of asset lots (instead of, as usual, in terms of capital per cent quotas). Secondly, we provide necessary and sufficient conditions for the existence of a non-empty mixed-integer feasible set of the considered programming problem. Thirdly, we present some rounding procedures for finding, in a finite number of steps, a feasible mixed-integer solution which is better than the one detected by the necessary and sufficient conditions in terms of the value assumed by the portfolio variance. Finally, we perform an extensive computational experiment by means of which we verify the goodness of our approach.     

A comparative study of decomposition algorithms for stochastic combinatorial optimization

This paper presents comparative computational results using three decomposition algorithms on a battery of instances drawn from two different applications. In order to preserve the commonalities among the algorithms in our experiments, we have designed a testbed which is used to study instances arising in server location under uncertainty and strategic supply chain planning under uncertainty. Insights related to alternative implementation issues leading to more efficient implementations, benchmarks for serial processing, and scalability of the methods are also presented. The computational experience demonstrates the promising potential of the disjunctive decomposition (D ²) approach towards solving several large-scale problem instances from the two application areas. Furthermore, the study shows that convergence of the D ² methods for stochastic combinatorial optimization (SCO) is in fact attainable since the methods scale well with the number of scenarios.     

Iterated snap rounding with bounded drift

Snap Rounding and its variant, Iterated Snap Rounding, are methods for converting arbitrary-precision arrangements of segments into a fixed-precision representation (we call them SR and ISR for short). Both methods approximate each original segment by a polygonal chain, and both may lead, for certain inputs, to rounded arrangements with undesirable properties: in SR the distance between a vertex and a non-incident edge of the rounded arrangement can be extremely small, inducing potential degeneracies. In ISR, a vertex and a non-incident edge are well separated, but the approximating chain may drift far away from the original segment it approximates. We propose a new variant, Iterated Snap Rounding with Bounded Drift, which overcomes these two shortcomings of the earlier methods. The new solution augments ISR with simple and efficient procedures that guarantee the quality of the geometric approximation of the original segments, while still maintaining the property that a vertex and a non-incident edge in the rounded arrangement are well separated. We investigate the properties of the new method and compare it with the earlier variants. We have implemented the new scheme on top of CGAL, the Computational Geometry Algorithms Library, and report on experimental results.     

基于价格歧视策略的多单元逆向多属性英式拍卖机制

针对现有的多单元逆向多属性拍卖机制的市场分配效率都比较低,不利于社会效益最大化和采购双方长期合作等问题,设计了高效率的基于价格歧视策略的多单元逆向多属性英式拍卖机制,利用线性混合整数规划建立了赢者确定模型,并基于新建立的拍卖机制给出了拍卖流程和投标策略,为供应商提供投标决策支持。然后通过设计数值实例和对比模拟实验收集数据,采取统计分析的方法验证了新设计的拍卖机制市场分配效率和采购方的效益都比较高。上述研究结果适用于通过逆向多属性拍卖与信息技术相结合的网上自动化多单元商品采购。