Linear Programming: Integer and non-integer decision variables

Question

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?

Answer 1

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.