Given $A \in Z^{m\times n}$, $b \in Z^m, c \in R^n$, we consider the integer program $P_d: \max \{c’x\vert Ax=b;x\in Z^n_+\}$ which has a well-known abstract dual optimization problem stated in terms of superadditive functions. Using a linear program $Q$ equivalent to $P_d$ that we have introduced recently, we show that its dual $Q^*$ can … Read more
In this paper we provide sufficient conditions for the existence of pair-wise envy free and stable matchings for two-sided systems with techniques. Article Download View Pair-wise envy free and stable matchings for two-sided systems with techniques
In this paper we show that the unconstrained continuous global minimization problem can not be solved by any algorithm. So without loss of generality we consider the box constrained continuous global minimization problem. We present a new globally convexized filled function method for the problem. The definition of globally convexized filled function is adapted from … Read more
We study the algebraic and facial structures of hyperbolic programs, and examine natural relaxations of hyperbolic programs, the relaxations themselves being hyperbolic programs. Citation TR 1406, School of Operations Research, Cornell University, Ithaca, NY 14853, U.S., 3/04 Article Download View Hyperbolic Programs, and Their Derivative Relaxations
The notion of weighted centers is essential in V-space interior-point algorithms for linear programming. Although there were some successes in generalizing this notion to semidefinite programming via weighted center equations, we still do not have a generalization that preserves two important properties — 1) each choice of weights uniquely determines a pair of primal-dual weighted … Read more
We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of master cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in … Read more
We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more
We describe a graph coloring problem associated with the determination of mathematical derivatives. The coloring instances are obtained as intersection graphs of row partitioned sparse derivative matrices. The size of the graph is dependent on the partition and can be varied between the number of columns and the number of nonzero entries. If solved exactly … Read more
Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more
Let $I=(g_1,…, g_n)$ be a zero-dimensional ideal of $ \R[x_1,…,x_n]$ such that its associated set $G$ of polynomial equations $g_i(x)=0$ for all $i=1,…,n$, is in triangular form. By introducing multivariate Newton sums we provide a numerical characterization of polynomials in the radical ideal of $I$. We also provide a necessary and sufficient (numerical) condition for … Read more