On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover

The problems dealt with in this paper are generalizations of the set cover problem, min{cx | Ax b, x {0,1}ⁿ}, where c Q₊ⁿ, A {0,1}^{m × n}, b 1. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m–K constrains (or more) in Ax b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover, partial set cover, and further generalizations.     

Comments on the Paper: Attacking the Market Split Problem with Lattice Point Enumeration

We present a few comments on the paper Attacking the market split problem with lattice point enumeration by A. Wasserman, published in Journal of Combinatorial Optimization, vol. 6, pp. 5–16, 2002.     

Intelligent Procedures for Intra‐Day Updating of Call Center Agent Schedules

For nearly all call centers, agent schedules are typically created several days or weeks before the time that agents report to work. After schedules are created, call center resource managers receive additional information that can affect forecasted workload and resource availability. In particular, there is significant evidence, both among practitioners and in the research literature, suggesting that actual call arrival volumes early in a scheduling period (typically an individual day or week) can provide valuable information about the call arrival pattern later in the same scheduling period. In this paper, we develop a flexible and powerful heuristic framework for managers to make intra‐day resource adjustment decisions that take into account updated call forecasts, updated agent requirements, existing agent schedules, agents' schedule flexibility, and associated incremental labor costs. We demonstrate the value of this methodology in managing the trade‐off between labor costs and service levels to best meet variable rates of demand for service, using data from an actual call center.     

技术创新对企业集团能量效率的影响与对策

引用动物捕食的最优方法的进化论观点研究了技术创新对企业集团能量效率的影响 ,提出了相应的对策 .首先 ,描述了一类企业集团的能量效率的基本模型 ,给出了一个关于技术与市场需求关系的假设 .接着 ,研究了技术创新对横向型企业集团能量效率的影响 ,在建立起模型之后 ,证明了提高核心企业的能量效率的充分性定理 ,为核心企业提供了对策方法 .然后 ,研究了核心企业是下游企业的纵向型企业集团 ,建立了模型 ,并获得了类似的结论 .最后 ,举例说明了核心企业应该怎样根据能量效率进行决策的思想 .总之 ,把一个企业集团的成长看成一群动物的进化 ,并且试图将进化论的思想应用到经济研究中     

Sequence Independent Lifting in Mixed Integer Programming

We investigate lifting, i.e., the process of taking a valid inequality for a polyhedron and extending it to a valid inequality in a higher dimensional space. Lifting is usually applied sequentially, that is, variables in a set are lifted one after the other. This may be computationally unattractive since it involves the solution of an optimization problem to compute a lifting coefficient for each variable. To relieve this computational burden, we study sequence independent lifting, which only involves the solution of one optimization problem. We show that if a certain lifting function is superadditive, then the lifting coefficients are independent of the lifting sequence. We introduce the idea of valid superadditive lifting functions to obtain good aproximations to maximum lifting. We apply these results to strengthen Balas' lifting theorem for cover inequalities and to produce lifted flow cover inequalities for a single node flow problem.     

Simplicial Pivoting Algorithms for a Tractable Class of Integer Programs

We present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart known as the class of Horn formulas. First we modify the existing algorithms in order to avoid the related recognition problem. Then we show that in order to solve these max-closed IP problems, simplicial path following methods can be used. This is important because these methods are flexible with respect to starting conditions, which make them more suitable than the top-down truncation algorithms that have been suggested.     

一类两层规划问题模糊满意解的遗传算法

在现有两层规划问题求解方法的基础上,提出用浮点数编码的遗传算法求解该问题模糊满意解的新方法．这种方法每次提供给决策者一组近似最优解,通过决策者的比较、评价和选择,在交互过程中得到各决策者都满意的解．该方法不仅可以给决策者提供更多的决策环境信息,而且可以适应决策者偏好的变化,使得决策过程更合理,更符合人的认识过程．     

带有交易费用的证券投资最优策略

在假设证券价格服从几何布朗运动的基础上,运用随机最优控制理论,研究了在ｎ 个风险证券金融市场中带有交易费用的证券投资问题,建立了带有交易费用的证券投资最优控制问题的数学模型．首先,简述了文中所涉及的随机最优控制理论,给出了值函数、效用函数和粘性解的定义．然后,在粘性解的意义下,推导出了交易策略有限和交易策略无限两种情况下值函数所满足的偏微分方程,该偏微分方程是由变分不等式描述的自由边值问题．最后,给出了两种情况下基于最优控制问题值函数的证券投资最优策略．本文得到的结果可以用于投资基金管理、金融风险管理等实际工作中,提高决策的科学性     

Fused least absolute shrinkage and selection operator for credit scoring

Credit scoring can be defined as the set of statistical models and techniques that help financial institutions in their credit decision makings. In this paper, we consider a coarse classification method based on fused least absolute shrinkage and selection operator (LASSO) penalization. By adopting fused LASSO, one can deal continuous as well as discrete variables in a unified framework. For computational efficiency, we develop a penalization path algorithm. Through numerical examples, we compare the performances of fused LASSO and LASSO with dummy variable coding.