Search

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. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a specific optimization problem that arises in the context of Balance Optimization Subset Selection (BOSS), which is an optimization framework for causal inference. Most BOSS problems can be formulated as mixed integer linear programs. By relaxing the integrality constraints so that fractional contributions of control units are permitted, a linear program (LP) is obtained. Properties of this LP and its dual are investigated and a sensitivity analysis is conducted to characterize how the objective value changes as the covariate values are perturbed. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

To make causal inferences from observational data, researchers have often turned to matching methods. These methods are variably successful. We address issues with matching methods by redefining the matching problem as a subset selection problem. Given a set of covariates, we seek to find two subsets, a control group and a treatment group, so that we obtain optimal balance, or, in other words, the minimum discrepancy between the distributions of these covariates in the control and treatment groups. Our formulation captures the key elements of the Rubin causal model and translates nicely into a discrete optimization framework. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]