Contributed Session Wed.1.MA 042

Wednesday, 10:30 - 12:00 h, Room: MA 042

Cluster 14: Mixed-integer nonlinear programming [...]

Topics in mixed-integer nonlinear programming I


Chair: Anita Schöbel



Wednesday, 10:30 - 10:55 h, Room: MA 042, Talk 1

Laura Galli
Reformulating mixed-integer quadratically constrained quadratic programs

Coauthor: Adam N. Letchford


It is well known that semidefinite programming (SDP) can be used to derive useful relaxations for a variety of optimisation problems. Moreover, in the particular case of mixed-integer quadratic programs, SDP has been used to reformulate problems, rather than merely relax them. In two recent papers, Billionnet et al. (2009), (2012) present their reformulation method, which they call Quadratic Convex Reformulation (QCR), and apply it respectively to equality-constrained 0-1 QP and general mixed-integer QP (MIQP). In their second paper (2012), they use binary expansion to convert bounded integer quadratic instances into 0-1 QP. We show that binary expansion never causes the SDP bound to get any worse and sometimes can lead to an improvement. Then we show that, under certain conditions, the QCR method can be extended to the even more general case of mixed-integer quadratically constrained quadratic programming (MIQCQP). Handling quadratic constraints turns out to be a non-trivial exercise. In our computational results we implement different reformulation schemes and compare the corresponding bounds.



Wednesday, 11:00 - 11:25 h, Room: MA 042, Talk 2

Yi-Shuai Niu
On combination of DCA branch-and-bound and DC-Cut for solving mixed-01 linear programs

Coauthor: Tao Pham Dinh


We propose a new hybrid approach based on DC (Difference of convex functions) programming and DCA (DC algorithm) with combination of Branch-and-Bound (BB) framework and new local cutting plan technique (DC-Cut) for globally solving mixed-01 linear program. We will firstly reformulate a mixed-integer linear program as a DC program via exact penalty technique, then an efficient local optimization algorithm DCA is proposed for searching upper bound solutions. The new DC-Cut technique can construct cutting plans from some integer and non-integer local minimizers of DC program which helps to reduce the feasible set and accelerate the convergence of BB. This algorithm can be naturally extended for mixed-01 nonlinear program. Preliminary numerical results comparing with some existing methods will be reported.



Wednesday, 11:30 - 11:55 h, Room: MA 042, Talk 3

Anita Schöbel
A geometric branch and bound approach for nonlinear mixed-integer optimization

Coauthor: Daniel Scholz


Geometric branch-and-bound techniques are popular solution algorithms
for continuous, non-convex global optimization problems. The most important task throughout these algorithms is the calculation of good lower bounds on the objective function. Several techniques to do so exist. They can be compared theoretically by their rate of convergence.
The aim of this talk is to extend these geometric branch-and-bound methods to mixed integer nonlinear optimization problems, i.e. to objective functions with some continuous and some combinatorial variables. The idea is to do a geometric branching for the continuous variables and to approximate the remaining discrete problem in order to obtain the required bounds. This is in contrast to the classical integer branch-and-bound in which branching is done on the discrete variables.
We derive several bounding operations and theoretical results about
their rate of convergence. Moreover, we discuss an extension of the method which leads to exact optimal solutions under certain conditions.
The suggested techniques are applied to some mixed-integer facility location problems in which we succeed in finding exact optimal solutions.


  Florida Payday Loans can help you in trying times, but be sure to know the laws necessary for your loan application. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis is the one that definitely differs from all other products.