
One option of the Math Programming
addin is to create a linear network flow model. By selecting
Math Program from the Optimize menu when a
network model is on the active worksheet, the Optimize addin
constructs a form for discrete variables that can interact with
the linear network model. When all the variables are specified
as the combinatorial variables in the dialog, the network flow
variables are manipulated directly by the search process. A
more interesting case is illustrated here in which the combinatorial
problem involves a selection of arcs that are to be excluded
or included in the network. In this example, we manually link
the combinatorial variables to the network model. For this example,
three addins must be installed, the Math Programming addin,
the Network Solver addin and the Optimize
addin.
Consider a telecommunications network in which traffic flows
between various origins and destinations. The figure shows a
case with three source nodes S = {1, 3, 7}, four destination
nodes D = {2, 4, 5, 8}, and one transshipment node T = {6}.
The arcs drawn with solid lines represent existing communication
links while those drawn with dashed lines are proposed links.
The complete set of arcs is denoted by A = {1,…,17}.
Associated with each link is an upper bound on flow and a unit
flow cost shown as the two numbers on each arc. If one of the
proposed links is constructed, it will have the capacity and
cost indicated on the arc. Let A' = { 1,…,5} be the set
of proposed links with corresponding construction costs f1 =
8, f2 = 6, f3 = 9, f4 = 7 and f5 = 7. These costs are independent
of size. The problem is to determine which links to build, if
any, and how much traffic to put on each link in the network
so that the sum of the flow costs and construction costs is
minimized. For a solution to be feasible, it must satisfy flow
balance at each node and arc flows must stay within the arc
capacities. 

We choose Math
Program from the Optimize menu to construct an
combinatorial form on the worksheet. There is a variable for
each fixed charge arc.
The form is placed to the right of the network
model. The two arrays in columns T and U measure the infeasibility
of the current flow solution. With all 0 arc flows, the flows
satisfy the arc capacity constraints, but the balance at the
nodes is not feasible. Infeasibility is indicated by a positive
numbers in the feasibility arrays. Formulas are placed in cells
AB2 and AB3 to indicate feasibility of the flow solution. The
data form in row 13 holds the fixed costs, and the contribution
to the objective is computed in row 11 and totaled with the
network cost in cell Z3. The requisite formulas in the yellow
cells are inserted by the addin.
It is necessarily to automatically link the network
model with the combinatorial variables representing the fixed
charges. We do this by placing formulas in the upper bound column
for each of the first five arcs. For example in cell I9 we insert
the formula:
=10*X7
Here X7 holds the value of y1. When X7 is 1, the
bound on flow is 10 and the arc is included in the model. When
X7 is 0 the bound on flow is 0 and the arc is excluded.
We have chosen to exhaustively enumerate the 32
solutions for the 5 combinatorial variables and the optimum
result is shown below. It is optimal to open arcs 1, 3 and 4.
The value in Z3 is the total of the fixed costs and the cost
of the network flow solution.


This problem could have been solved
as a mixedintegerlinear program since adjusting the upper
bounds on an arc can be implemented with a linear constraint.
The adjusted network model has side constraints and integer
variables and it is no longer possible to solve the embedded
network problem with a network solver.
The models shown here are much more intuitive and easy to implement
in Excel. The resulting combinatorial problem is easy to solve
by enumeration for this small case and the network flow models
are solved with the Network Solver. For larger problems, exhaustive
enumeration would not be possible and one of the approximate
solution methods would have to be used. 

When a transportation model constructed
by the Math Programming addin is on the worksheet
when Math Program is selected from the Optimize
menu, a form is created that allows manual linking of combinatorial
variables to elements of the transportation model. As an illustration
we consider a small warehouse location problem with data shown
below. There are five customers and five locations where warehouses
can be located. The customer demand must be served, but all
the warehouses need not be constructed. Unit shipping costs
between the customers and the potential warehouse locations
are given. The fixed and variable costs associated with each
warehouse are in the table at the right. An open warehouse can
serve up to 80 units of demand.


Given the set of open warehouses,
the optimum shipping pattern can be determined by a linear transportation
model. We model the combinatorial problem of selecting the warehouses
separately from the problem of distributing the product. The
combinatorial form with the optimum solution is shown below.
It is optimum to open warehouses at locations 1, 3 and 4.
