In this paper, we discuss the one-machine scheduling problem with release and delivery times with the minimum makespan objective. Both heuristics and branch-and-bound algorithms have been formulated for the problem. One such branch-and-bound algorithm solves the problem and a variation that requires a delay between the completion of one job and the start of another (delayed precedence constraints). This paper analyzes key components of this branch-and-bound algorithm and proposes an improved heuristic to be used in conjunction with a different search strategy. Computational experiments demonstrate that the modifications lead to substantial improvements in running time and number of iterations on the one-machine problem instances both with and without delayed precedence constraints.

Branch-and-price algorithms for the graph coloring problem use an exponentially sized independent set-based integer programming formulation to produce usually tight lower bounds to enable more aggressive pruning in the branch-and-bound tree. One major problem inherent to any branch-and-price scheme for graph coloring is that to avoid destroying the pricing problem structure during column generation, difficult-to-implement branching rules that modify the underlying graph must be used. This paper proposes an alternative branching strategy that does not change the graph to solve the pricing problem but rather modifies the search tree to require fewer calls to difficult instances of the pricing problem. This approach, called wide branching, generates many subproblems at each node in the branch-and-price tree; this significantly reduces the length of any path through the search tree. In contrast, traditional deep branching only creates two subproblems per node, assigning a variable to either 0 or 1. A delayed branching procedure is introduced that prevents the branching factor at any particular node from growing too large in this scheme. Finally, computational results are presented that show the wide branching strategy to be competitive with state-of-the-art graph coloring solvers.

Matching is widely used in the estimation of treatment effects in observational studies. However, the matching paradigm may be too restrictive in many cases because exact matches often do not exist in the available data. One mechanism for overcoming this issue is to relax the requirement of exact matching on some or all of the covariates (attributes that may affect the response to treatment) to a requirement of balance on the covariate distributions for the treatment and control groups. The balance optimization subset selection (BOSS) model can be used to identify a control group featuring optimal covariate balance. This paper explores the relationship between the matching and BOSS models and shows how BOSS subsumes matching. Complexity and approximation results are presented for the resulting models. Computational results demonstrate some of the important trade-offs between matching and BOSS. Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2013.0583 . There is a video associated with this paper. Click here to view the Video Overview . To save the file, right click and choose “Save Link As” from the menu.

A network simplex algorithm is described for the minimum-cost network flow problem on a generalized network, with the additional constraint that there exist sets of arcs that must carry equal amounts of flow. This problem can be modeled as a linear programming problem and solved using the standard simplex algorithm. However, because of the structure of the problem, more efficient algorithms are possible that solve the problem by operating directly on the network itself. One such algorithm is described that leads to improved asymptotic performance per iteration over the standard simplex algorithm, as long as the number of side constraints is small relative to the size of the network. Computational results are given comparing this algorithm to CPLEX's primal simplex solver on randomly generated graphs.