Augmented Lagrangian dual augments the classical Lagrangian dual with a nonnegative nonlinear penalty function of the violation of the relaxed/dualized constraints in order to reduce the duality gap. We investigate th...
详细信息
Augmented Lagrangian dual augments the classical Lagrangian dual with a nonnegative nonlinear penalty function of the violation of the relaxed/dualized constraints in order to reduce the duality gap. We investigate the cases in which mixed integer convex optimization problems have an exact penalty representation using sharp augmenting functions (norms as augmenting penalty functions). We present a generalizable constructive proof technique for proving existence of exact penalty representations for mixedintegerconvex programs under specific conditions using the associated value functions. This generalizes the recent results for mixedinteger linear programming [M. J. Feizollahi, S. Ahmed, and A. Sun, Math. Program., 161 (2017), pp. 365--387] and mixedinteger quadratic progamming [X. Gu, S. Ahmed, and S. S. Dey, SIAM J. Optim., 30 (2020), pp. 781--797] while also providing an alternative proof for the aforementioned along with quantification of the finite penalty parameter in these cases.
In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust li...
详细信息
In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this end, a solution scheme based on a blending of three popular robust optimization techniques is proposed. For disjoint bilinear optimization problems with a polyhedral feasible region and a general convex feasible region, we show that, under mild regularity conditions, the convex relaxations of the original bilinear formulation and its two-stage robust reformulation obtained from a reformulation-linearization-based technique and linear decision rules, respectively, are equivalent. For generic bilinear optimization problems, the convex relaxations from the reformulation-linearization-based technique are generally tighter than the one from linear decision rules. Numerical experiments on bimatrix games, synthetic disjoint bilinear problem instances, and convex maximization problems demonstrate the efficiency and effectiveness of the proposed solution scheme.
Classic vehicle routing models usually treat fuel cost as input data, but fuel consumption heavily depends on the travel speed, which leads to the study of optimizing speeds over a route to improve fuel efficiency. In...
详细信息
Classic vehicle routing models usually treat fuel cost as input data, but fuel consumption heavily depends on the travel speed, which leads to the study of optimizing speeds over a route to improve fuel efficiency. In this paper, we propose a joint vehicle routing and speed optimization problem to minimize the total operating cost including fuel cost. The only assumption made on the dependence between fuel cost and travel speed is that it is a strictly convex differentiable function. This problem is very challenging, with medium-sized instances already difficult for a general mixed-integerconvexoptimization solver. We propose a novel set-partitioning formulation and a branch-cut-and-price algorithm to solve this problem. We introduce new dominance rules for the labeling algorithm so that the pricing problem can be solved efficiently. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time.
暂无评论