Branching is an important component of the branch-and-cut algorithm for solving mixed integer linear programs. Most solvers branch by imposing a disjunction of the form“$x_i \leq k \vee x_i \geq k+1$” for some integer $k$ and some integer-constrained variable $x_i$. A generalization of this branching scheme is to branch by imposing a more general disjunction … Read more
In this paper I investigate several offline and online data transfer scheduling problems and propose efficient algorithms and techniques for addressing them. In the offline case, I present a novel, heuristic, algorithm for scheduling files with divisible sizes on multiple disjoint paths, in order to maximize the total profit (the problem is equivalent to the … Read more
The space of linear programs (LP) can be partitioned into a finite number of sets, each corresponding to a basis. This partition is thus called the basis partition. The closed-form solution on the space of LP can be determined with the basis partition if we can characterize the basis partition. A differential equation on the … Read more
Euclidean Jordan-algebra is a commonly used tool in designing interior point algorithms for symmetric cone programs. T-algebra, on the other hand, has rarely been used in symmetric cone programming. In this paper, we use both algebraic characterizations of symmetric cones to extend the target-following framework of linear programming to symmetric cone programming. Within this framework, … Read more
Recently, Andersen et al.(2007), Borozan and Cornuejols (2007) and Cornuejols and Margot(2007) characterized extreme inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. These inequalities are either split cuts or intersection cuts (Balas (1971)) derived using maximal lattice-free convex sets. In order to use these inequalities to obtain … Read more
We study mixed integer nonlinear programs (MINLP)s that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is “turned off”, forces some of the decision variables to assume fixed values, and, when it is “turned on”, forces them to belong … Read more
Sequential quadratic programming (SQP) methods form a class of highly efficient algorithms for solving nonlinearly constrained optimization problems. Although second derivative information may often be calculated, there is little practical theory that justifies exact-Hessian SQP methods. In particular, the resulting quadratic programming (QP) subproblems are often nonconvex, and thus finding their global solutions may be … Read more
The problem of routing and wavelength assignment (RWA) in wavelength division multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned different wavelengths. This problem was shown to be NP-hard when the objective is to … Read more
A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which each GRASP iteration consists of two phases, a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed … Read more
A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which each GRASP iteration consists of two phases, a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed … Read more