Source author record

Luze Xu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC Other Computer Science

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions

We study MINLO (mixed-integer nonlinear optimization) formulations of the disjunction $x\in\{0\}\cup[\ell,u]$ , where $z$ is a binary indicator of $x\in[\ell,u]$ ( $0 \leq \ell <u$ ), and $y$ "captures" $f(x)$ , which is assumed to be convex and positive on its domain $[\ell,u]$ , but otherwise $y=0$ when $x=0$ . This model is very useful in nonlinear combinatorial optimization, where there is a fixed cost of operating an activity at level $x$ in the operating range $[\ell,u]$ , and then there is a further (convex) variable cost $f(x)$ . In particular, we study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of $f$ , obtained by choosing linearization points for $f$ . Using 3-d volume (in $(x,y,z)$ ) as a measure of the tightness of a convex relaxation, we investigate relaxation quality as a function of $f$ , $\ell$ , $u$ , and the linearization points chosen. We make a detailed investigation for convex power functions $f(x):=x^p$ , $p>1$ .

preprint2020arXiv

Improving proximity bounds using sparsity

We refer to the distance between optimal solutions of integer programs and their linear relaxations as proximity. In 2018, Eisenbrand and Weismantel proved that proximity is independent of the dimension for programs in standard form. We improve their bounds using existing and novel results on the sparsity of integer solutions. We first bound proximity in terms of the largest absolute value of any full-dimensional minor in the constraint matrix, and this bound is tight up to a polynomial factor in the number of constraints. We also give an improved bound in terms of the largest absolute entry in the constraint matrix, after efficiently transforming the program into an equivalent one. Our results are stated in terms of general sparsity bounds, so any new results on sparse solutions immediately improves our work. Generalizations to mixed integer programs are also discussed.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.