tag:blogger.com,1999:blog-593563533834706486.post8991468706024527791..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: Scheduling as non-convex MIQPErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-593563533834706486.post-68464831736699771652015-01-13T08:53:07.856-05:002015-01-13T08:53:07.856-05:00I wish I could edit my message, it's either &q...I wish I could edit my message, it's either "the maximum of a convex function over a convex set" or "the minimum of a concave function over a convex set".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-67657653268934218692015-01-13T08:51:21.634-05:002015-01-13T08:51:21.634-05:00One more thought: the maximum of a concave functio...One more thought: the maximum of a concave function over a convex set is attained at an extreme point of the feasible set. You therefore do not need to specify x_{jk} as binary. It will be interesting to see how this affects the running time of all methods.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-89902265552973564482015-01-13T08:34:54.882-05:002015-01-13T08:34:54.882-05:00>> MIP with binaries exploiting integer data...>> MIP with binaries exploiting integer data for capacity and job spans<br />There are (at least) two ways to do this: using that z_k can take any integer value between 0 and N := max_k cap_k:<br /><br />1. using binary variables y_{ik} that take the value 1 only if z_k = i. The objective becomes sum_k sum_i i^2 y_{ik}; the extra constraints are 1 - y_{ik} >= (i - z_k)/N and 1 - y_{ik} >= (z_k - i)/N.<br /><br />2. using binary variables y_{ik} that sum to z_k. The expression (sum_i y_{ik})^2 contains products of binary variables, which can be linearized in an exact reformulation.<br /><br />Both have a weak LP relaxation; the first because it is a big-M formulation, the second because for each k, all y_{ik} are symmetric and you may need to fix many values before it has any effect on the solution.Anonymousnoreply@blogger.com