3
$\begingroup$

Mixed Integer Conic Programs is a family of Mixed Integer Programs which are convex in all non integer variables. I am giving presentation on Mixed Integer technology. A large part of the presentation will be about MILP, it's tricks and common problem structures. I will also make people aware of MINLP by giving a practical non-convex MINLP. I aim to do the same with a convex MINLP. Is someone aware of an easy to explain[1] MIP using a Second-order, Rotated second-order, Positive semidefinite or Primal exponential which has a practical application?

[1] It should not involve power networks, trajectory optimisation and ideally fit on a slide. Why the cone is needed should be obvious from the problem description.

$\endgroup$

1 Answer 1

8
$\begingroup$

Your opening sentence could be more accurately written as Mixed Integer Conic Programs are a family of Mixed Integer Programs whose continuous relaxations are (convex) conic programs.

One easy to understand example is best variable subset selection by Mixed-Integer Least Squares, as presented in BEST SUBSET SELECTION VIA A MODERN OPTIMIZATION LENS, D IMITRIS B ERTSIMAS, ANGELA K ING AND R AHUL M AZUMDER,The Annals of Statistics, 2016, Vol. 44, No. 2, 813–852

The Mosek Modeling Cookbook version 3.2.3 Section 9.2 Mixed integer conic case studies has examples

  • Wireless network design
  • Portfolio optimization subject to transaction costs, cardinality constraints, and/or trading size constraints
  • Convex piecewise linear regression

The YALMIP wiki has an example of nonconvex regression arising from non-convex penalty function, which is handled as MISOCP.

Applications and Solution Approaches for Mixed-Integer Semidefinite Programming, Tristan Gally, joint work with Marc E. Pfetsch and Stefan Ulbrich has MISDP examples for

  • Max-Cut (very cleverly, the non-convex rank constraint for the SDP can be relaxed (omitted) with no effect on optimal solution because every integer solution satisfies the omitted rank constraint; therefore the non-convexity has been moved from the rank constraint entirely to the integer (binary) constraints)
  • Compressed Sensing
  • Truss Topology Design.

Section 9.2 of A Tutorial on Geometric Programming, S. Boyd, S.-J. Kim, L. Vandenberghe, and A. Hassibi has a Mixed-Integer Geometric Programming example for Digital Circuit Gate Scaling in which the scale factors must take integer values. So this would be a Mixed-Integer Exponential Cone problem.

You may also find the video, The conic advantage in MINLP, Henrik A. Friberg: to be of interest.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.