Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem

Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. In this paper, we investigate capacitated path substructures and derive strong and easy-to-compute \emph{path cover and path pack inequalities}. These inequalities are based on an explicit characterization of the submodular inequalities through a fast computation of parametric minimum cuts on a path, and they generalize the well-known flow cover and flow pack inequalities for the single-node relaxations of fixed-charge flow models. We provide necessary and sufficient facet conditions. Computational results demonstrate the effectiveness of the inequalities when used as cuts in a branch-and-cut algorithm.


Similar Publications

For multi-block alternating direction method of multipliers(ADMM), where the objective function can be decomposed into multiple block components, we show that with block symmetric Gauss-Seidel iteration, the algorithm will converge quickly. The method will apply a block symmetric Gauss-Seidel iteration in the primal update and a linear correction that can be derived in view of Richard iteration. We also establish the linear convergence rate for linear systems. Read More


We study the sensitivity of the expected utility maximization problem in a continuous semi-martingale market with respect to small changes in the market price of risk. Assuming that the preferences of a rational economic agent are modeled with a general utility function, we obtain a second-order expansion of the value function, a first-order approximation of the terminal wealth, and construct trading strategies that match the indirect utility function up to the second order. If a risk-tolerance wealth process exists, using it as a num\'eraire and under an appropriate change of measure, we reduce the approximation problem to a Kunita-Watanabe decomposition. Read More


For an arbitrary finite family of semi-algebraic/definable functions, we consider the corresponding constraint set and we study qualification conditions for perturbations of this set. In particular we prove that all positive diagonal perturbations, save perhaps a finite number of them, ensure that any point within the feasible set satisfies Mangasarian-Fromovitz constraint qualification. Using the Milnor-Thom theorem, we provide a bound for the number of singular perturbations when the constraints are polynomial functions. Read More


Real world networks are often subject to severe uncertainties which need to be addressed by any reliable prescriptive model. In the context of the maximum flow problem subject to arc failure, robust models have gained particular attention. For a path-based model, the resulting optimization problem is assumed to be difficult in the literature, yet the complexity status is widely unknown. Read More


We study the fragmentation-coagulation (or merging and splitting) evolutionary control model as introduced recently by one of the authors, where $N$ small players can form coalitions to resist to the pressure exerted by the principal. It is a Markov chain in continuous time and the players have a common reward to optimize. We study the behavior as $N$ grows and show that the problem converges to a (one player) deterministic optimization problem in continuous time, in the infinite dimensional state space. Read More


We establish a stochastic maximum principle for mean-field stochastic differential equations with jumps and corresponding cost functionals, both of whose coefficients involve not only the solution, but also the law of the solution. The control domain does not need to be convex. Our work heavily depends on the derivatives of a stochastic process with respect to a measure as well as the duality method. Read More


Several theorems on the volume computing of the polyhedron spanned by a n-dimensional vector set with the finite-interval parameters are presented and proved firstly, and then are used in the analysis of the controllable regions of the linear discrete time-invariant systems with saturated inputs. A new concept and continuous measure on the control ability, control efficiency of the input variables, and the diversity of the control laws, named as the controllable abundance, is proposed based on the volume computing of the regions and is applied to the actuator placing and configuring problems, the optimizing problems of dynamics and kinematics of the controlled plants, etc.. Read More


We consider nonlinear scalar-input differential control systems in the vicinity of an equilibrium. When the linearized system at the equilibrium is controllable, the nonlinear system is smoothly small-time locally controllable, i.e. Read More


In this paper, we address the Bounded Cardinality Hub Location Routing with Route Capacity wherein each hub acts as a transshipment node for one directed route. The number of hubs lies between a minimum and a maximum and the hub-level network is a complete subgraph. The transshipment operations take place at the hub nodes and flow transfer time from a hub-level transporter to a spoke-level vehicle influences spoke- to-hub allocations. Read More


We consider large scale empirical risk minimization (ERM) problems, where both the problem dimension and variable size is large. In these cases, most second order methods are infeasible due to the high cost in both computing the Hessian over all samples and computing its inverse in high dimensions. In this paper, we propose a novel adaptive sample size second-order method, which reduces the cost of computing the Hessian by solving a sequence of ERM problems corresponding to a subset of samples and lowers the cost of computing the Hessian inverse using a truncated eigenvalue decomposition. Read More