Inverse optimization is the problem of determining the values of missing input parameters for an associated forward problem that are closest to given estimates and that will make a given target vector optimal. This study is concerned with the relationship of a particular inverse mixed integer linear optimization problem (MILP) to both the forward problem and the separation problem associated with its feasible region. We show that a decision version of the inverse MILP in which a primal bound is verified is coNP-complete, whereas primal bound verification for the associated forward problem is NP-complete, and that the optimal value verification problems for both the inverse problem and the associated forward problem are complete for the complexity class D^P. We also describe a cutting-plane algorithm for solving inverse MILPs that illustrates the close relationship between the separation problem for the convex hull of solutions to a given MILP and the associated inverse problem. The inverse problem is shown to be equivalent to the separation problem for the radial cone defined by all inequalities that are both valid for the convex hull of solutions to the forward problem and binding at the target vector. Thus, the inverse, forward, and separation problems can be said to be equivalent.
翻译:反向优化是确定一个相关前期问题缺失输入参数值的问题,这个问题最接近给定的估计数,并使给定的目标矢量最佳化。本研究涉及一个特殊的反双整线性线性优化问题(MILP)与与其可行区域相关的前期问题和分离问题之间的关系。我们显示,对准初线性约束进行核查的反向MILP的决定版本是完整的,而对相关前期问题的初步约束核查是完整的,而反向问题及相关前期问题的最佳价值核查问题对于复杂等级DP来说都是完整的。我们还描述了用于解决反向MILP的切片算法,该算法说明了对给定的MILP的解决方案的方形体的分离问题与与之相关的反向问题之间的密切关系。反面的问题与由所有不平等界定的对前向问题和对目标矢量的方形体的分离问题相等。因此,对前向、前向和分离问题可以这么说。