A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to eigenvalue optimization. In our approach we utilize the method of analytic center to obtain the query points at each iteration. A restricted master problem in the primal space is formed corresponding to the relaxed dual problem. At each step of the algorithm, an oracle is … Read more

A hybrid bin-packing heuristic to multiprocessor scheduling

The multiprocessor scheduling problem consists in scheduling a set of tasks with known processing times into a set of identical processors so as to minimize their makespan, i.e., the maximum processing time over all processors. We propose a new heuristic for solving the multiprocessor scheduling problem, based on a hybrid heuristic to the bin packing … Read more

Solving diameter constrained minimum spanning tree problems in dense graphs

In this study, a lifting procedure is applied to some existing formulations of the Diameter Constrained Minimum Spanning Tree Problem. This problem typically models network design applications where all vertices must communicate with each other at minimum cost, while meeting or surpassing a given quality requirement. An alternative formulation is also proposed for instances of … Read more

Routing and wavelength assignment by partition coloring

We show in this work how the problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition coloring problem in a conflict graph. A new tabu search heuristic is also proposed for the … Read more

Heuristics for the mirrored traveling tournament problem

Professional sports leagues are a major economic activity around the world. Teams and leagues do not want to waste their investments in players and structure in consequence of poor schedules of games.Game scheduling is a difficult task, involving several decision makers, different types of constraints, and multiple objectives to optimize. The Traveling Tournament Problem abstracts … Read more

A randomized heuristic for scene recognition by graph matching

We propose a new strategy for solving the non-bijective graph matching problem in model-based pattern recognition. The search for the best correspondence between a model and an over-segmented image is formulated as a combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together … Read more

Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones

We establish polynomial-time convergence of infeasible-interior-point methods for conic programs over symmetric cones using a wide neighborhood of the central path. The convergence is shown for a commutative family of search directions used in Schmieta and Alizadeh. These conic programs include linear and semidefinite programs. This extends the work of Rangarajan and Todd, which established … Read more

Solving Nonlinear Portfolio Optimization Problems with the Primal-Dual Interior Point Method

Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear … Read more