This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders’ cuts that are valid for their ancestor nodes. In addition, we develop two closely … Read more
Directional sensors are gaining importance due to applications, in- cluding surveillance, detection, and tracking. Such sensors have a limited fi eld-of-view and a discrete set of directions they can be pointed to. The Directional Sensor Control problem (DSCP) consists in assigning a direction of view to each sensor. The location of the targets is known with … Read more
Given a double round-robin tournament, the traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team … Read more
In this paper we address a deterministic scheduling problem in which two agents compete for the usage of a single machine. Each agent decides on a fixed order to submit its tasks to an external coordination subject, who sequences them according to a known priority rule. We consider the problem from different perspectives. First, we … Read more
The restricted isometry constants (RICs) play an important role in exact recovery theory of sparse signals via l_q(0
In this paper branching for attacking MILP is investigated. Under certain circumstances branches can be done concurrently. By introducing a new calculus it is shown there are restrictions for dual values. As a second result of this study a new class of cuts for MILP is found, which are defined by those values. This class … Read more
We study approaches for the exact solution of the \NP–hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the … Read more
We present a framework for obtaining Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely the Calculus of K-approximation Functions and the Calculus of K-approximation Sets. Using our framework, we provide … Read more
We consider the problem of scheduling on uniform processors with nonsimultaneous machine available times with the purpose of mini\-mi\-zing the maximum completion time. We give a variant of the Multifit algorithm which generates schedules which end within $1.382$ times the optimal maximum completion times. This results from properties of the Multifit algorithm when used for … Read more
The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more