This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more
Problem definition: Curb space has long been a scarce public resource in automobilized cities, serving competing uses for passenger parking and commercial activities. The rapid growth of e-commerce and home deliveries, combined with increasing urban density, has further intensified pressure on this already constrained resource, making effective curbspace management a critical policy challenge. Yet, in … Read more
We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly … Read more
The rapid growth of online meal delivery has introduced complex logistical challenges, where platforms must dynamically assign orders to couriers while accounting for demand uncertainty, courier autonomy, and service efficiency. Traditional dispatching methods, often focused on short-term cost minimization, fail to capture the long-term implications of assignment decisions on system-wide performance. This paper presents a … Read more
Abstract One approach to solving optimal control problems is Bock’s direct multiple shoot- ing method. This method yields lifted nonlinear optimization problems (NLPs) with a spe- cific block structure. Exploiting this structure via tailored optimization algorithms can be computationally beneficial. We propose such methods, primarily within the framework of fil- ter line search sequential quadratic … Read more
This paper introduces a generalized isotonic optimization framework over an arborescence graph, where each node incurs state-dependent convex costs and a fixed cost upon strict increases. We begin with the special case in which the arborescence is a path and develop a dynamic programming (DP) algorithm with an initial complexity of $O(n^3)$, which we improve … Read more
In this paper, we study a joint problem in which the Independent System Operator (ISO) intends to minimize the joint cost of operation and investment in a network structure. The problem is formulated through operational and investment control variables; we discuss the hierarchy between them and use the so-called Day Ahead Problem to find an … Read more
Stochastic Dual Dynamic Programming (SDDP) is widely recognized as the predominant methodology for solving large-scale multistage stochastic linear programming (MSLP) problems. This paper aims to contribute to the extant literature by conducting a comprehensive survey of the literature on SDDP within the realm of practical applications. We systematically identify and analyze the various domains where … Read more
We consider a dynamic lot sizing model in which end products to satisfy demands are obtained by remanufacturing m types of cores, where m ≥ 1, or manufacturing from raw materials, and in the model, we have separate setup costs for manufacturing and remanufacturing. As is widely known, remanufacturing is an environmental preferable choice compared … Read more
The Lovasz theta function is a semidefinite programming (SDP) relaxation for the maximum weighted stable set problem, which is tight for perfect graphs. However, even for perfect graphs, there is no known rounding method guaranteed to extract an optimal stable set from the SDP solution. In this paper, we develop a novel rounding scheme for … Read more