Proposal

Main paper can be found here.

Summary

The problem and its notation

  • MIP (Mixed Integer Programming) is an optimization problem of the form
    • minimize ΣjϵNcjxj\Sigma_{j \epsilon N} c_j x_j
    • subject to
      • ΣjϵNaijxj≤bi(iϵM)\Sigma_{j \epsilon N} a_{ij} x_j \le b_i \qquad (i \epsilon M)
      • lj≤xj≤uj(jϵN)l_j \le x_j \le u_j \qquad (j \epsilon N)
      • xjϵZ(jϵI)x_j \epsilon Z \qquad (j \epsilon I)
  • where
    • NN = number of variables
    • MM = number of constraints
    • ZZ = set of integers
    • II = set of variables that can only take integer values

Algorithm

  • Lagrangian relaxation
    • Relax all the constraints (except the variable bounds and integrality constraints)
    • Penalize the relaxed ones, when they violate the constraints, in the objective function
  • IOW
    • minimize Oq(x)+Fw(x)O^q(x) + F^w(x)
    • subject to
      • lj≤xj≤uj(jϵN)l_j \le x_j \le u_j \qquad (j \epsilon N)
      • xjϵZ(jϵI)x_j \epsilon Z \qquad (j \epsilon I)
    • where
      • Oq(x)=qΣjϵNcjxjO^q(x) = q \Sigma_{j \epsilon N} c_j x_j = original objective weighted by qq
      • Fw(x)=ΣiϵMwifi(x)F^w(x) = \Sigma_{i \epsilon M} w_i f_i(x) = total infeasibility penalty
      • wiw_i = weight for each constraint
      • fi(x)=max(0,ΣjϵNaijxj−bi)f_i(x) = max(0, \Sigma_{j \epsilon N} a_{ij} x_j - b_i)
      • using 'max' function means we are interested in the solutions that live on the edge rather than interior of the feasibility region.
  • this doesn't minimize the langrangian function directly, but instead looks for a local minimum in the feasible neighborhoods where only variable is varied.

jump value

  • current assignment assumed to be x=x‾x = \overline{x} and only one variable xjx_j is allowed to change with the rest of them fixed.
  • However, we expect the resultant value of xjx_j to not be xj‾\overline{x_j}
  • Let's say rij=bi−Σk≠jaikxk‾aijr_{ij} = \frac{b_i - \Sigma_{k \ne j} a_{ik} \overline{x_k}}{a_{ij}}
  • Thus, if xjx_j is integer variable, we have
    • tij(xk≠j‾)=⌊rij⌋ifaij>0t_{ij}(\overline{x_{k \ne j}}) = \lfloor r_{ij} \rfloor \qquad if \qquad a_{ij} > 0
    • tij(xk≠j‾)=⌈rij⌉ifaij<0t_{ij}(\overline{x_{k \ne j}}) = \lceil r_{ij} \rceil \qquad if \qquad a_{ij} < 0
  • else, if xjx_j is fractional, we have: tij(xk≠j‾)=rijt_{ij}(\overline{x_{k \ne j}}) = r_{ij}
  • We'll get a piecewise linear convex function:
    • gij(t∣xk≠j‾)=max(0,wi(t−tij(xk≠j‾)))ifaij>0g_{ij}(t|\overline{x_{k \ne j}}) = max(0, w_i(t - t_{ij}(\overline{x_{k \ne j}}))) \qquad if \qquad a_{ij} > 0
    • gij(t∣xk≠j‾)=max(0,−wi(t−tij(xk≠j‾)))ifaij<0g_{ij}(t|\overline{x_{k \ne j}}) = max(0, -w_i(t - t_{ij}(\overline{x_{k \ne j}}))) \qquad if \qquad a_{ij} < 0
  • constraint violation penalty then is: Gj(t∣xk≠j‾)=ΣiϵMgij(t∣xk≠j‾)aij≠0G_j(t|\overline{x_{k \ne j}}) = \Sigma_{i \epsilon M} g_{ij}(t|\overline{x_{k \ne j}}) \qquad a_{ij} \ne 0
  • jump for this variable would then become
    • Jj(xk≠j‾)=argmintϵ[lj,uj]−xj‾Gj(t∣xk≠j‾)J_j(\overline{x_{k \ne j}}) = argmin_{t \epsilon [l_j, u_j] - \overline{x_j}} G_j(t|\overline{x_{k \ne j}})
    • this means, it can only be one of: Jj(xk≠j‾)={lj,uj,tij(xk≠j‾)}J_j(\overline{x_{k \ne j}}) = \text{\textbraceleft} l_j, u_j, t_{ij}(\overline{x_{k \ne j}}) \text{\textbraceright}