Inverse Quadratic Transportation Problem

Afrooz Jalilzadeh, Erfan Yazdandoost HamedaniarXiv 2014 · DOI · arXiv

Abstract

While extensive research exists separately for quadratic programming and inverse optimization, this paper explores their intersection within the context of transportation logistics. We present a framework for the Inverse Quadratic Transportation Problem (IQTP), aiming to identify the minimal adjustments required for cost parameters to justify a pre-determined shipping pattern as optimal. By applying duality theory and Kuhn-Tucker (KKT) conditions, we derive solutions under both $L_1$ and $L_\infty$ norms. Our findings demonstrate that these complex inverse quadratic challenges can be effectively transformed into solvable linear programming problems, providing a robust methodology for parameter estimation in non-linear supply chain models.

Introduction

In a classical transportation problem, the objective is to determine the most cost-effective shipping route from $m$ origins to $n$ destinations given fixed supply, demand, and cost parameters. However, real-world logistics often involve quadratic costs, which account for variables like congestion, infrastructure wear, or economies of scale.

Inverse optimization flips the traditional perspective: rather than solving for the optimal flow given the costs, we observe a specific shipping pattern (a feasible solution $x^0$) and seek the cost structure that would make this pattern the mathematically optimal choice. This paper addresses the Inverse Quadratic Transportation Problem (IQTP) by providing a rigorous mathematical framework to find the smallest possible changes to the cost matrix ($Q$) and the cost vector ($c$) that justify a given shipping plan.

Methodology

The authors employ a multi-step mathematical approach to simplify and solve the IQTP, focusing on transforming the non-linear nature of the problem into a manageable format.

1. Duality and KKT Conditions

The foundation of the approach lies in the Kuhn-Tucker (KKT) optimality conditions and complementary slackness. By utilizing these, the authors transform the requirement "make $x^0$ optimal" into a set of linear constraints. This allows the researchers to treat the optimality of a solution as a boundary condition for the cost parameters.

2. Norm-Based Objectives

To define "minimal change," the paper evaluates adjustments using two distinct metrics:

  • $L_1$ Norm: This minimizes the sum of absolute differences between the original and adjusted parameters, which is particularly useful for identifying sparse adjustments where only a few costs are changed.
  • $L_\infty$ Norm: This minimizes the maximum absolute difference, ensuring that no single cost parameter is adjusted beyond a specific bound, keeping the overall cost structure relatively stable.

3. Linearization and Simplification

A key contribution of this work is the linearization of the objective functions. By introducing clever substitutions for the absolute value terms, the authors transform the non-linear norm-based objectives into Linear Programming (LP) problems. This allows for the use of standard, highly efficient LP solvers to solve what initially appears to be a daunting quadratic inverse problem.

Key Insights and Results

The "Reduced Cost" Equivalent

The authors introduce the term $c_{ij}^\pi$, which functions similarly to the "reduced cost" found in linear programming. This value serves as a critical indicator, determining exactly how much a specific route's cost needs to be nudged to reach the threshold of optimality.

Complexity and Symmetry

The paper provides explicit, piecewise formulas for calculating the optimal adjusted cost vector $d^*$ and the adjusted quadratic matrix $H^*$. A significant finding is that while the general problem involves $2(mn)^2 + 3(mn) + m + n$ variables, the complexity drops significantly to $5(mn) + m + n$ variables if the quadratic matrix $Q$ is diagonal (meaning costs on one route are independent of others). Furthermore, the authors ensure that the adjusted matrix $H$ remains symmetric, a necessary condition for physical and economic consistency in quadratic models.

Norm Equivalence

Interestingly, the derivation shows that the optimal values for the parameters $d^*$ and $H^*$ follow a similar mathematical structure regardless of whether the $L_1$ or $L_\infty$ norm is applied. This provides a unified theoretical perspective on cost adjustments in transportation networks.

Limitations and Future Directions

While the paper establishes a strong theoretical foundation, it notes several areas for further development:

  • Computational Scale: For massive transportation networks with dense, non-diagonal cost matrices, the number of variables remains a challenge for standard solvers.
  • Diagonal Assumption: Much of the practical simplification relies on the assumption of a diagonal $Q$ matrix. Future research could investigate more efficient algorithms for dense, highly-correlated quadratic cost matrices.
  • Empirical Validation: As a methodological study, the paper does not apply these formulas to real-world supply chain data. Testing these models against actual market conditions remains a promising avenue for applied logistics research.

Summary updated

Abstract

Many research has been conducted about quadratic programming and inverse optimization. In this paper we present the combination aspect of these subjects, applying on transportation problem. First, we obtain the inverse form of quadratic tranportation problem under $L_1$ norm by using duality as well as introducing the optimal value. Then, we do the same process for inverse quadratic transportation problem (IQTP) under $L_\infty$ norm.
BibTeX
@misc{jalilzadeh2014inverse,
  author = {Afrooz Jalilzadeh and Erfan Yazdandoost Hamedani},
  title = {{Inverse Quadratic Transportation Problem}},
  year = {2014},
  eprint = {1409.6030},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.6030},
}
Figure