6
$\begingroup$

I am looking for an answer to a question I can't quite get behind.

I am given the following mathematical optimization problem: \begin{align}\min&\quad\sum_{t\in T}s_t\cdot z_t+h_t\cdot i_t+p_t\cdot q_t\tag1\\\text{s.t.}&\quad i_0=0\tag2\\&\quad i_t=i_{t-1}+q_t-d_t&\forall t\in T\tag3\\&\quad q_t\le c_t\cdot z_t&\forall t\in T\tag4\\&\quad q_t,i_t\in\Bbb N_0&\forall t\in T\tag5\\&\quad z_t\in\{0,1\}&\forall t\in T\tag6\end{align}

Furthermore, the following table is given:

Period $t$ 1 2 3 4 5 6 7 8 9 10
demand $d_t$ 12 6 20 5 7 25 0 5 5 21
capacity $c_t$ 20 15 5 30 20 20 21 10 10 5
set-up costs $s_t$ 25 30 40 20 80 80 150 30 40 60
storage costs $h_t$ 6 5 4 5 6 9 9 6 5 4
production costs $p_t$ 5 3 7 2 1 10 15 2 1 5

Decision variables are:

  • $z_t$: Is day $t$ a production day?
  • $q_t$: Quantity in time $t$
  • $i_t$: Inventory in time $t$

If I implement this problem in Excel and solve it with the Excel Solver (setting $z_t$ binary and $q_t, i_t$ integers and using the Simplex-LP) I get an optimal solution.

So far so good. However, what I don't understand is the following. Out of interest, I decided to drop the constraint of $q_t$ and $i_t$ such that $q_t$ and $i_t$ can be real numbers. When I solve this problem with the Excel Solver again, I receive the exact (integer) solution as in the original model.

So my questions are the following:

First, why are both solutions described above exactly the same? Is that some sort of coincidence or can I conclude that for binary linear programming models with at least one continuous variable the optimal solution is an integer one? Or may the structure of the underlying problem be the reason for this observation?

Second, on a more general note, how does Excel Solver actually work with Mixed Integer Programming where not all decision variables are integer but some are continuous? Is the Excel Solver applying some sort of Branch and Bound to find the optimal solution to such problems or what kind of algorithm in addition to the Simplex-LP does Excel Solver use?

$\endgroup$
1
  • $\begingroup$ Welcome to OR.SE. Please try to avoid using images in future and instead use MathJax and/or Markdown to improve readability and searchability of posts. Thanks! $\endgroup$
    – TheSimpliFire
    Nov 14, 2021 at 21:56

1 Answer 1

7
$\begingroup$

For the first question, suppose you somehow knew which days would be production days and fixed the values of the $z_t$ variables accordingly, while allowing $q_t$ and $i_t$ to be continuous variables. You would be left with a "flow" type linear program. Since the capacities and demands are integer-valued, your flow LP would automatically produce integer values for production and inventory quantities. (This is proved in most textbooks on linear/integer programming. The phrase to look for is "totally unimodular", in reference to the constraint matrix.) So getting integrality automatically is a consequence of two things, the structure of your model and the fact that capacities and demands are integers. Try running an example where the capacity and demand date are not integers and see what happens.

For the second question, yes, Excel's Solver uses branch-and-bound for integer programs. As I understand it, Excel ships with a licensed copy of Frontline Solver.

$\endgroup$
3
  • $\begingroup$ Follow up question: when I assume that $z_t$ is fixed and only $q_t$ and $i_t$ are continous decision variables. In this case the "Totally Unimodular Theory (TU)" makes sense to me as you can transform every constraint in a form such that $Ax=b$ and then determine if A is totally unimodular and if b is a vector of integers. However, if $z_t$ is not fixed the constraints $q_t\leq c_t\cdot z_t$ can't be brought into the $Ax=b$ form and thus I can not determine if A is totally unimodular. However, when solved in Excel with $z_t$ is not fixed, the solution is again integer. Why does TU apply too? $\endgroup$
    – coar
    Nov 14, 2021 at 17:58
  • $\begingroup$ In branch-and-bound, the solver essentially develops a binary tree, with each node being split according to $z_t=0$ or $z_t=1$ for some $t$. At nodes in the tree where not all $z$ variables have been fixed, it's possible that the solution to the LP relaxation at the node could have fractional values for integer variables. That's not a concern, as the LP solution is providing a bound on the objective value. The final solution is obtained at a "leaf" node of the tree, where all $z$ variables are fixed to either 0 or 1. At that node, TUM applies and you get integer quantities. $\endgroup$
    – prubin
    Nov 14, 2021 at 19:03
  • 1
    $\begingroup$ In the solution where $z_j$ are relaxed, the matrix including the identity portion for the capacity constraints is still TU. The balance constraints have integer RHS and must be satisfied exactly with a basis made up of $i$ and $q$, so those have to be integer. Then $z$s are fractional, but the $c_jz_j$ right-hand sides of the capacity constraints are integer and equal to the $q_j$s on the left. $\endgroup$
    – mjsaltzman
    Nov 26, 2021 at 16:06

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.