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.     

Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results

Given a (combinatorial) optimization problem and a feasible solution to it, the corresponding inverse optimization problem is to find a minimal adjustment of the cost function such that the given solution becomes optimum.Several such problems have been studied in the last twelve years. After formalizing the notion of an inverse problem and its variants, we present various methods for solving them. Then we discuss the problems considered in the literature and the results that have been obtained. Finally, we formulate some open problems.     

On Approximability of Boolean Formula Minimization

For a Boolean function given by a Boolean formula (or a binary circuit) S we discuss the problem of building a Boolean formula (binary circuit) of minimal size, which computes the function g equivalent to , or -equivalent to , i.e., . In this paper we prove that if P NP then this problem can not be approximated with a good approximation ratio by a polynomial time algorithm.     

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.     

Optimizing the Collections Process in Consumer Credit

This paper builds a dynamic programming model to optimize the collections process in consumer credit. It determines which collections actions should be undertaken and how long they should be performed, including theoretical results about the form of the optimal policy under certain conditions. Finally, a case study is described based on data from the collections department of a European bank.     

An Optimization‐Based Framework for the Identification of Vulnerabilities in Electric Power Grids Exposed to Natural Hazards

This article proposes a novel mathematical optimization framework for the identification of the vulnerabilities of electric power infrastructure systems (which is a paramount example of critical infrastructure) due to natural hazards. In this framework, the potential impacts of a specific natural hazard on an infrastructure are first evaluated in terms of failure and recovery probabilities of system components. Then, these are fed into a bi‐level attacker–defender interdiction model to determine the critical components whose failures lead to the largest system functionality loss. The proposed framework bridges the gap between the difficulties of accurately predicting the hazard information in classical probability‐based analyses and the over conservatism of the pure attacker–defender interdiction models. Mathematically, the proposed model configures a bi‐level max‐min mixed integer linear programming (MILP) that is challenging to solve. For its solution, the problem is casted into an equivalent one‐level MILP that can be solved by efficient global solvers. The approach is applied to a case study concerning the vulnerability identification of the georeferenced RTS24 test system under simulated wind storms. The numerical results demonstrate the effectiveness of the proposed framework for identifying critical locations under multiple hazard events and, thus, for providing a useful tool to help decisionmakers in making more‐informed prehazard preparation decisions.     

Integrating Operational and Organizational Aspects in Interdependent Infrastructure Network Recovery

Managing risk in infrastructure systems implies dealing with interdependent physical networks and their relationships with the natural and societal contexts. Computational tools are often used to support operational decisions aimed at improving resilience, whereas economics‐related tools tend to be used to address broader societal and policy issues in infrastructure management. We propose an optimization‐based framework for infrastructure resilience analysis that incorporates organizational and socioeconomic aspects into operational problems, allowing to understand relationships between decisions at the policy level (e.g., regulation) and the technical level (e.g., optimal infrastructure restoration). We focus on three issues that arise when integrating such levels. First, optimal restoration strategies driven by financial and operational factors evolve differently compared to those driven by socioeconomic and humanitarian factors. Second, regulatory aspects have a significant impact on recovery dynamics (e.g., effective recovery is most challenging in societies with weak institutions and regulation, where individual interests may compromise societal well‐being). And third, the decision space (i.e., available actions) in postdisaster phases is strongly determined by predisaster decisions (e.g., resource allocation). The proposed optimization framework addresses these issues by using: (1) parametric analyses to test the influence of operational and socioeconomic factors on optimization outcomes, (2) regulatory constraints to model and assess the cost and benefit (for a variety of actors) of enforcing specific policy‐related conditions for the recovery process, and (3) sensitivity analyses to capture the effect of predisaster decisions on recovery. We illustrate our methodology with an example regarding the recovery of interdependent water, power, and gas networks in Shelby County, TN (USA), with exposure to natural hazards.     

基于波动持续性的最优组合构建与分散化研究

构建恰当资产组合来减少风险, 是投资组合理论研究的重要目标.由于金融时间序列的波动往往会伴随着持续性特征, 该种特性会增大组合未来收益的风险.本文通过构建随机波动模型序列持续性最优投资组合模型, 以降低金融资产波动的持续性特征对组合收益波动的影响;并通过研究其分散化水平, 考察该投资组合构建方法的有效性与稳健性.研究发现:与均值方差的组合模型相比较, 序列持续性组合的风险分散化水平更好.此研究在资产组合选择方面, 具有较为重要的理论价值及实践意义.     

社区应急疏散动态协作调度优化研究

针对灾民数量和路网通行时间的动态性以及灾民疏散反应系数的随机性,本文提出了社区应急疏散协作调度优化流程,并以疏散灾民数量最大化和疏散成本最小化为目标,构建了社区应急疏散多种运输方式协作调度优化模型,并给出了求解该模型的改进多目标遗传算法。然后,论文使用Tansmodeler模拟社区应急疏散协作调度优化过程,加载疏散灾民动态需求和历史出行时间表,并对模型和算法进行验证。结果表明,该模型和算法可以在有效刻画疏散灾民数量和路网通行时间的基础上,为不同时刻的交通工具配置及疏散路径选取提供决策。     

数据驱动下收货方质量偏好与电商配送服务质量优化

针对"互联网+大数据"优化电商配送服务质量问题,明确不同收货方的质量需求稳定性,引导电商根据收货方不同质量敏感性提供相对精准服务,提升配送服务质量。模拟投票结果的形成过程聚类得到收货方对服务质量偏好的记忆性特征：（1）"无记忆"型收货方;（2）"记忆"型收货方;（3）"不确定"型收货方;（4）收货方总体。进一步推导不同规划类型求解空间,设计得到"无记忆"型收货方动态规划精确求解方法,及其他三种类型近似求解粒子群算法。研究过程中,配送资源质量感知度被嵌入到模型约束;"无记忆"型收货方的质量需求规划问题转化为零库存策略最优解问题,进而证明存在精确解;"记忆"型收货方呈现出对质量感知的累积;"不确定"型收货方模型通过赋值即可得总体收货方表达式。结果表明：数据驱动研究框架借助大数据资源,使得电商更易通过收货方的质量偏好设计更加匹配的配送方案;不确定服务需求得到有效满足,投入成本的利用率更高;通过特征分类的方式,尽可能地抽取能够精确最优化的部分,缩小NP范围,提高整体求解的精确度。