On the Moreau-Yosida regularization of the vector k-norm related functions

In this paper, we conduct a thorough study on the first and second order properties of the Moreau-Yosida regularization of the vector $k$-norm function, the indicator function of its epigraph, and the indicator function of the vector $k$-norm ball. We start with settling the vector $k$-norm case via applying the existing breakpoint searching algorithms to … Read more

Job-Shop Scheduling in a Body Shop

We study a generalized job-shop problem called the body shop scheduling problem (bssp). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. bssp corresponds to a job-shop problem where the operations of a job have to follow … Read more

Branch-and-Cut for Separable Piecewise Linear Optimization: Computation

We report and analyze the results of our extensive computational testing of branch-and-cut for piecewise linear optimization using the cutting planes given recently by Zhao and de Farias. Besides analysis of the performance of the cuts, we also analyze the effect of formulation on the performance of branch-and-cut. Finally, we report and analyze initial results … Read more

Branch-and-Cut for Separable Piecewise Linear Optimization: New Inequalities and Intersection with Semi-Continuous Constraints

We give new facets and valid inequalities for the separable piecewise linear optimization knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. In a companion paper (de Farias, Gupta, Kozyreff, Zhao, 2011) we demonstrate the efficiency of the inequalities when used as cuts in a branch-and-cut … Read more

Finding largest small polygons with GloptiPoly

A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices $n$. Many instances are already solved in the literature, namely for all odd $n$, and for $n=4, 6$ and $8$. Thus, for even $n\geq 10$, instances of this … Read more


In this paper we study constrained eigenvalue optimization of noncommutative (nc) polynomials, focusing on the polydisc and the ball. Our three main results are as follows: (1) an nc polynomial is nonnegative if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using … Read more

Inverse polynomial optimization

We consider the inverse optimization problem associated with the polynomial program $f^*=\min \{f(x):x\inK\}$ and a given current feasible solution $y\in K$. We provide a numerical scheme to compute an inverse optimal solution. That is, we compute a polynomial $\tilde{f}$ (which may be of same degree as $f$ if desired) with the following properties: (a) $y$ … Read more

SDDP for some interstage dependent risk averse problems and application to hydro-thermal planning

We consider interstage dependent stochastic linear programs where both the random right-hand side and the model of the underlying stochastic process have a special structure. Namely, for stage $t$, the right-hand side of the equality constraints (resp. the inequality constraints) is an affine function (resp. a given function $b_t$) of the process value for this … Read more

Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of … Read more