Narrow Results

The CDT subproblem, which minimizes a quadratic function over the intersection of two ellipsoids, is a classical quadratic programming problem. In this paper, we study a method of solving CDT with a positive Lagrangian duality gap. An efficient splitting algorithm is proposed for finding the global optimal solutions. A cutting plane is firstly added to divide the feasible set of CDT into two subsets, and then two new quadratic programming problems with ellipsoidal and linear constraints are generated accordingly. Using the newly developed technique — second-order cone constraints to enhance the efficiencies of the SDP relaxation-based algorithms on the two subproblems, an optimal solution of CDT can be acquired by comparing the objective values of the two subproblems. Numerical experiments show that the new algorithm outperforms the two recent SDP relaxation-based algorithms, the two-parameter eigenvalue-based algorithm and the solver Gurobi 9.5 for certain types of CDT.

As minimally invasive surgical techniques become widely known to patients, medical training systems based on virtual simulation are highly desired. These systems help surgeon trainees to acquire, practice and evaluate their surgical skills. A key component in a virtual training system is to simulate the dynamics that occur in surgical procedures. Tissue cutting, as a common phenomenon during surgery, has attracted many research efforts in computer simulation. In this paper, we propose an approach to endoscopic image cutting simulation which is based on both mass-spring model and Computational Geometry. In the cutting simulation model, the springs to be cut off are imagined into line segments. In the calculation of the elastic force on mass points, we have found that whether some adjacent springs of a mass point to be eliminated or not during a cutting is critical. If a spring intersects the cutting plane, we set the elastic force of this spring to zero. We adopted properties of cross product and related algorithms (the rapid exclusion test, the crossover test) in Computational Geometry to determine the springs that are intersected with the cutting plane. And then, we utilized the bilinear interpolation and OpenGL techniques to render the cutting procedure of the soft tissue. The experimental results show that our cutting simulation is effective and practical.

From a practical perspective, mixed integer optimization represents a very powerful modeling paradigm. Its modeling power, however, comes with a price. The presence of both integer and continuous variables results in a significant increase in complexity over the pure integer case with respect to geometric, algebraic, combinatorial and algorithmic properties. Specifically, the theory of cutting planes for mixed integer linear optimization is not yet at a similar level of development as in the pure integer case. The goal of this paper is to discuss four research directions that are expected to contribute to the development of this field of optimization. In particular, we examine a new geometric approach based on lattice point free polyhedra and use it for developing a cutting plane theory for mixed integer sets. We expect that these novel developments will shed some light on the additional complexity that goes along with mixing discrete and continuous variables.