A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference
A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference
复制标题
DOI：
10.1287/ijoc.2022.1226
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Md Saiful Islam;M. Morshed;Md. Noor-E.-Alam
中科院分区：
文献类型：
--
作者：
Md Saiful Islam;M. Morshed;Md. Noor-E.-Alam
确定变量之间的因果关系是决策过程中的一个关键步骤。虽然因果推理需要随机实验，但由于数据的广泛可用性和实验的不可行性，研究人员和政策制定者越来越多地使用观察研究来测试因果假设。匹配方法是从观测数据中进行因果推断的最常用的技术。然而，在一对一配对中的配对分配过程中，由于实验者做出的不同选择，导致了推理的不确定性。最近，离散优化模型已被提出来解决这种不确定性，但它们产生0-1非线性问题，缺乏可扩展性。在这项工作中，我们研究了这个新兴的数据科学问题，并开发了一个独特的计算框架，以解决来自具有连续结果的观察数据的鲁棒因果推理测试实例。在该框架中，我们首先将非线性二元优化问题转化为可行性问题。通过利用可行性公式的结构，我们开发了贪婪的计划，有效地解决强大的测试问题。在许多情况下，所提出的算法实现了全局最优解。我们在真实世界的数据集上进行实验，以证明所提出的算法的有效性，并将我们的结果与最先进的求解器进行比较。我们的实验表明，所提出的算法显着优于精确的方法在计算时间方面，同时达到相同的结论，因果测试。数值实验和复杂性分析都表明，所提出的算法确保了在决策过程中利用大数据的力量所需的可扩展性。最后，所提出的框架不仅有利于通过大数据因果推理进行稳健的决策，而且还可以用于开发其他非线性优化问题（如二次分配问题）的有效算法。
Identifying cause-effect relations among variables is a key step in the decision-making process. Whereas causal inference requires randomized experiments, researchers and policy makers are increasingly using observational studies to test causal hypotheses due to the wide availability of data and the infeasibility of experiments. The matching method is the most used technique to make causal inference from observational data. However, the pair assignment process in one-to-one matching creates uncertainty in the inference because of different choices made by the experimenter. Recently, discrete optimization models have been proposed to tackle such uncertainty; however, they produce 0-1 nonlinear problems and lack scalability. In this work, we investigate this emerging data science problem and develop a unique computational framework to solve the robust causal inference test instances from observational data with continuous outcomes. In the proposed framework, we first reformulate the nonlinear binary optimization problems as feasibility problems. By leveraging the structure of the feasibility formulation, we develop greedy schemes that are efficient in solving robust test problems. In many cases, the proposed algorithms achieve a globally optimal solution. We perform experiments on real-world data sets to demonstrate the effectiveness of the proposed algorithms and compare our results with the state-of-the-art solver. Our experiments show that the proposed algorithms significantly outperform the exact method in terms of computation time while achieving the same conclusion for causal tests. Both numerical experiments and complexity analysis demonstrate that the proposed algorithms ensure the scalability required for harnessing the power of big data in the decision-making process. Finally, the proposed framework not only facilitates robust decision making through big-data causal inference, but it can also be utilized in developing efficient algorithms for other nonlinear optimization problems such as quadratic assignment problems.