Semi-continuous network flow problems

We consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are restricted to be semi-continuous. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present … Read more

A Polyhedral Study of the Semi-Continuous Knapsack Problem

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem arises in a number of other contexts, e.g. it is a relaxation of general mixed-integer programming. We show how … Read more

Branch-and-Cut for Separable Piecewise Linear Optimization: New Inequalities and Intersection with Semi-Continuous Constraints

We give new facets and valid inequalities for the separable piecewise linear optimization knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. In a companion paper (de Farias, Gupta, Kozyreff, Zhao, 2011) we demonstrate the efficiency of the inequalities when used as cuts in a branch-and-cut … Read more

Semi-Continuous Cuts for Mixed-Integer Programming

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integer programming. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can … Read more