Simple and Fast Interval Assignment Using Nonlinear and Piecewise Linear Objectives
Mitchell, Scott A.
22nd International Meshing Roundtable, Springer-Verlag, pp.203-221, October 13-16 2013
22nd International Meshing Roundtable
Sandia National Laboratories, Albuquerque, NM, U.S.A.
Interval Assignment (IA) is the problem of assigning an integer
number of mesh edges, intervals, to each curve so that the assigned value
is close to the goal value, and all containing surfaces and volumes may be
meshed independently and compatibly. Sum-even constraints are modeled
by an integer variable with no goal. My new method NLIA solves IA more
quickly than the prior lexicographic min-max approach. A problem with one
thousand faces and ten thousand curves can be solved in one second. I still
achieve good compromises when the assigned intervals must deviate a large
amount from their goals. The constraints are the same as in prior approaches,
but I define a new objective function, the sum of cubes of the weighted deviations
from the goals. I solve the relaxed (non-integer) problem with this
cubic objective. I adaptively bend the objective into a piecewise linear function,
which has a nearby mostly-integer optimum. I randomize and rescale
weights. For variables stuck at non-integer values, I tilt their objective. As a
last resort, I introduce wave-like nonlinear constraints to force integrality. In
short, I relax, bend, tilt, and wave.
Download Full Paper (PDF Format)
Contact author(s) or publisher for availability and copyright information on above referenced article