We investigate the problem of sequencing jobs that have multiple components. Each component of the job needs to be processed independently on a specified machine. We derive approximate algorithms for the problem of scheduling such vector jobs to minimize their total completion time in the deterministic as well as stochastic setting. In particular, we propose … Read more
We present three new stopping rules for Multistart based methods. The first uses a device that enables the determination of the coverage of the bounded search domain. The second is based on the comparison of asymptotic expectation values of observable quantities to the actually measured ones. The third offers a probabilistic estimate for the number … Read more
We present a new matrix-free method for the trust region subproblem, assuming that the approximate Hessian is updated by the limited memory BFGS formula with m = 2. The resulting updating scheme, called 2-BFGS, give us the ability to determine via simple formulas the eigenvalues of the resulting approximation. Thus, at each iteration, we can … Read more
An algorithm for solving large-scale nonlinear optimization problems with simple bounds is described. The algorithm is an $\ell_\infty$-norm trust-region method that uses both active set identification techniques as well as limited memory BFGS updating for the Hessian approximation. The trust-region subproblems are solved using primal-dual interior point techniques that exploit the structure of the limited … Read more
We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered fixed constants. In particular we construct: 1. polynomial-time algorithms to exactly determine the number of Pareto optima and Pareto strategies; 2. a polynomial-space polynomial-delay prescribed-order enumeration algorithm … Read more
Yu and Liu’s strong duality theorem under the time-sharing property requires the Slater condition to hold for the considered general nonconvex problem, what is satisfied for the specific application. We further extend the scope of the theorem under Ky Fan convexity which is slightly weaker than Yu&Lui’s time-sharing property. ArticleDownload View PDF
We describe a version of randomization technique within a general framework of Euclidean Jordan algebras. It is shown how to use this technique to evaluate the quality of symmetric relaxations for several nonconvex optimization problems CitationPreprint, June 2007ArticleDownload View PDF
We propose a new gradient based scheme to approximate Nash equilibria of large sequential two-player, zero-sum games. The algorithm uses modern smoothing techniques for saddle-point problems tailored specifically for the polytopes used in the Nash equilibrium problem. CitationWorking Paper, Tepper School of Business, Carnegie Mellon UniversityArticleDownload View PDF
We present a new computer system, called GraPHedron, which uses a polyhedral approach to help the user to discover optimal conjectures in graph theory. We define what should be optimal conjectures and propose a formal framework allowing to identify them. Here, graphs with n nodes are viewed as points in the Euclidian space, whose coordinates … Read more
We present fourteen basic FORTRAN subroutines for large-scale unconstrained and box constrained optimization and large-scale systems of nonlinear equations. Subroutines {\tt PLIS} and {\tt PLIP}, intended for dense general optimization problems, are based on limited-memory variable metric methods. Subroutine {\tt PNET}, also intended for dense general optimization problems, is based on an inexact truncated Newton … Read more