Solving structured 0/1 integer programs arising from truck dispatching scheduling problems

A branch-and-cut IP solver is developed for a class of structured 0/1 integer programs arising from a truck dispatching scheduling problem. This problem is characterized by a group of set partitioning constraints and a group of knapsack equality constraints of a specific form. Families of facets for the polytopes associated with individual knapsack constraints are identified, and in some cases, a complete characterization of a polytope is obtained. In addition, a notion of "conflict graph" is introduced and utilized to obtain an approximating node-packing polytope for the convex hull of all 0/1 solutions. The branch-and-cut solver generates cuts based on both the knapsack constraints and the approximating node-packing polytope, and incorporates these cuts into a tree-search algorithm that uses problem reformulation and linear programming-based heuristics at each node in the search tree to assist in the solution process. Numerical experiments are performed on large-scale real instances supplied by Texaco Trading & Transportation, Inc. The optimal schedules obtained correspond to cost savings for the company and greater job satisfaction for drivers due to more balanced work schedules and income distribution. It is noteworthy that this is apparently the first time that branch-and-cut has been applied to an equality constrained problem in which the entries in the constraint matrix and right hand side are not purely 0/1