We introduce an anti-matroid as a family $\cal F$ of subsets of a ground set $E$ for which there exists an assignment of weights to the elements of $E$ such that the greedy algorithm to compute a maximal set (with respect to inclusion) in $\cal F$ of minimum weight finds, instead, the unique maximal set … Read more
We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the … Read more
Motivated by telecommunication applications, we investigate the shortest path problem on directed acyclic graphs under arc length uncertainties represented as interval numbers. Using a minimax-regret criterion we define and identify robust paths via mixed-integer programming and exploiting interesting structural properties of the problem. Citation Bilkent University, Department of Industrial Engineering, Technical Report August 2001 Article … Read more
The paper proposes a constrained Nonlinear Programming methodology for volatility estimation with GARCH models. These models are usually developed and solved as unconstrained optimization problems whereas they actually fit into nonlinear, nonconvex problems. Computational results on FTSE 100 and S & P 500 indices with up to 1500 data points are given and contrasted to … Read more
Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the … Read more
This work reports the results of evaluating all computer codes submitted to the Seventh DIMACS Implementation Challenge on Semidefinite and Related Optimization Problems. The codes were run on a standard platform and on all the benchmark problems provided by the organizers of the challenge. A total of ten codes were tested on fifty problems in … Read more
We define a class of parabolic problems with control and state constraints and identify a problem within this class which possesses a locally unique critical point satisfying the second order sufficient optimality conditions. In this solution inequality constraints on the control are strongly active. The second derivative of the Lagrangian is not globally coercive. This … Read more
The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most $k$ edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits. Article Download View Facets of The Cardinality Constrained Circuit … Read more
We present new fixed parameter algorithms for feedback vertex set and disjoint cycles on planar graphs. We give an $O(c^{\sqrt{k}} + n)$ algorithm for $k$-feedback vertex set and an $O(c^{\sqrt{k}} n)$ algorithm for $k$-disjoint cycles on planar graphs. Citation Manuscript 4 July, 2001. Article Download View Feedback vertex sets and disjoint cycles in planar (di)graphs
Sherali and Adams \cite{SA90}, Lov\’asz and Schrijver \cite{LS91} and, recently, Lasserre \cite{Las01b} have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a $0-1$ polytope $P\subseteq \oR^n$ converging to $P$ in $n$ steps. Lasserre’s approach uses results about representations of positive polynomials as sums of squares and the dual … Read more