We consider a class of fixed-charge transportation problems over graphs. We show that this problem is strongly NP-hard, but solvable in pseudo-polynomial time over trees using dynamic programming. We also show that the LP formulation associated to the dynamic program can be obtained from extended formulations of single-node flow polytopes. Given these results, we present … Read more
The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances … Read more
We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, … Read more
We study a class of bilevel binary linear programs with lower level variables in the upper-level constraints. Under certain assumptions, we prove that the problem can be reformulated as a single-level binary linear program, and propose a finitely terminating cut generation algorithm to solve it. We then relax the assumptions by means of a general … Read more
The handling of symmetries in mixed integer programs in order to speed up the solution process of branch-and-cut solvers has recently received significant attention, both in theory and practice. This paper compares different methods for handling symmetries using a common implementation framework. We start by investigating the computation of symmetries and analyze the symmetries present … Read more
Dantzig-Wolfe reformulation of an integer program convexifies a subset of the constraints, which yields an extended formulation with a potentially stronger linear programming (LP) relaxation. We would like to better understand the strength of such reformulations in general. As a first step we investigate the classical edge formulation for the stable set problem. We characterize … Read more
We discuss a Lagrangian-relaxation-based heuristics for dealing with feature selection in a standard L1 norm Support Vector Machine (SVM) framework for binary classification. The feature selection model we adopt is a Mixed Binary Linear Programming problem and it is suitable for a Lagrangian relaxation approach. Based on a property of the optimal multiplier setting, we … Read more
Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization ... Read more
We consider the problem of computing optimal traffic light programs for urban road intersections using traffic flow conservation laws on networks. Based on a Partial Outer Convexification approach, which has been successfully applied in the area of mixed-integer optimal control for systems of ordinary or differential algebraic equations, we develop a computationally tractable two-stage solution … Read more
The flow refueling location problem (FRLP) locates $p$ stations in order to maximize the flow volume that can be accommodated in a road network respecting the range limitations of the vehicles. This paper introduces the charging station location problem with plug-in hybrid electric vehicles (CSLP-PHEV) as a generalization of the FRLP. We consider not only … Read more