For equality-constrained linear mixed-integer programs (MIP) defined by rational data, it is known that the subadditive dual is a strong dual and that there exists an optimal solution of a particular form, termed generator subadditive function. Motivated by these results, we explore the connection between Lagrangian duality, subadditive duality and generator subadditive functions for general … Read more
Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective func- tions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a … Read more
In transportation problems and in many other planning problems, there are important sources of uncertainty that must be addressed to find effective and efficient solutions. A common approach for solving these dynamic and stochastic problems is the Multiple Scenario Approach (MSA), that has been proved effective for transportation problems, but it does not provide flexibility … Read more
In this paper, we propose a novel decomposition approach for mixed-integer stochastic programming (SMIP) problems that is inspired by the combination of penalty-based Lagrangian and block Gauss-Seidel methods (PBGS). In this sense, PBGS is developed such that the inherent decomposable structure that SMIPs present can be exploited in a computationally efficient manner. The performance of … Read more
We present a new primal-dual algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. The algorithm relies on the well-known progressive hedging method, but unlike previous progressive hedging approaches for SMIP, our algorithm can be shown to converge to the optimal Lagrangian dual … Read more
We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation … Read more
In this paper, we apply the quadratic penalization technique to derive strong Lagrangian duality property for an inequality constrained invex program. Our results extend and improve the corresponding results in the literature. Citation Bazara, M. S. and Shetty, C. M., Nonlinear Programming Theory and Algorithms, John Wiley \& Sons, New York, 1979. Ben-Israel, A. and … Read more
For a particular class of minimax stochastic programming models, we show that the problem can be equivalently reformulated into a standard stochastic programming problem. This permits the direct use of standard decomposition and sampling methods developed for stochastic programming. We also show that this class of minimax stochastic programs subsumes a large family of mean-risk … Read more