carrier image

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
Orlando, FL
October 13-16,2013

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