On the complexity of inverse mixed integer linear optimization
From MaRDI portal
Abstract: 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.
Recommendations
- The inverse optimal value problem
- Cutting plane algorithms for the inverse mixed integer linear programming problem
- Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem
- Inverse optimization: towards the optimal parameter set of inverse LP with interval coefficients
- Inverse Optimization
Cites work
- A note on the transaction backout problem
- Algorithmic Applications in Management
- Complexity classes of optimization functions
- Computational Complexity
- Convex Analysis
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Cutting plane algorithms for the inverse mixed integer linear programming problem
- Fenchel Cutting Planes for Integer Programs
- Geometric algorithms and combinatorial optimization.
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Inverse combinatorial optimization: a survey on problems, methods, and results
- Inverse integer programming
- Inverse Optimization
- Matroids and the greedy algorithm
- On Computable Numbers, with an Application to the Entscheidungsproblem
- On the complexity of integer programming
- Reducibility among combinatorial problems
- The complexity analysis of the inverse center location problem
- The complexity of facets (and some facets of complexity)
- The complexity of optimization problems
- The complexity of theorem-proving procedures
- The polynomial-time hierarchy
Cited in
(10)- A polyhedral characterization of the inverse-feasible region of a mixed-integer program
- Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem
- Inverse integer optimization with an imperfect observation
- Feasibility in reverse convex mixed-integer programming
- Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization
- Inverse Mixed Integer Optimization: Polyhedral Insights and Trust Region Methods
- A new mixed integer programming approach for inverse correspondence analysis
- Heuristic algorithms for the inverse mixed integer linear programming problem
- Fast numerical solver of Ising optimization problems via pruning and domain selection
- Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased
This page was built for publication: On the complexity of inverse mixed integer linear optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013588)
