Types of integer problesm Flashcards
Elaborate on knapsack problems
Generally speaking:
Selecting the best object, projects, investments given one or several resource constraints. The resource is typically cash, weight, time, etc
The simplest variant have one constraint.
max z = ∑cj xj
s.t.
∑aj xj <= b
xj in {0,1}
Elaborate on facilituy location problems
Support a set of customer from a set of facilities.
We suppose we have m facilities to choose from, and we need to satisfy the demands of n customers.
Each specific facility typically has a fixed cost associated with it, as well as produciton varialbe cost, and maybe transportation cost.
The problem dinstinguish between product generated from a facility and shipped to a customer.
We use variable xij to indicate flow of product going from facility i to customer j.
I suppose we can extend to xsij to differ between products as well.
the simple problem consists of a unit cost for shipping + fixed cost of using facility.
There are 2 types of constraints:
1) Supply constraints, enforcing that the flow out from a facility is not larger than the capacity of the facility
2) Demand constraints, enforcing that the total amount of product shipped to eahc customer satisfy the customer’s needs..
elaborate on assignment problems
we have 2 sets of objects.
Objects in the first set is to be assigned to objects in the second set.
For instance, staff needs to be allocated to different tasks.
The important constriant is that each job should only be assigned to one machine.
elaborate on set covering
Set covering only care about covering all the objects. THerefore it is the same as set partitioning, but with >= constraint instead of =
elaborate on set partitioning
Suppose we have m objects(tasks) and that these objects should be partitioned into subsets. Assume there are n alternatieves in how the partitioning of objects can be made. Each partition consists of a a subset of objects.
The parameter aij is 1 if task/object “i” is included in alternative j.
The only constraint is that
∑aij xj =1 for all i
elaborate on TSP
variable:
xij = 1 if the arc between node i and j is included in the TSP tour, 0
otherwise
There is the symmetric and and assymetric problem
For the asymmetric problem:
We require 3 types of constraints:
1) Make sure that the sum of arcs leading into a specific node is 1
2) Make sure that the sum of arcs going out from a node is 1
3) make sure there are no sub tours going on
The elimination of sub tours is tricky.
∑∑xij [i in S][j in S] <= |S|-1, S subset of N, |S| >= 2
Basically, if we have n nodes in a set, there must be less than n arcs.
why is TSP so well studiuet?
Many planning problems can be formulated as a variation of it
Characteristics of TSP
Easy to understand, very hard to solve. Typically, the larger ones require heuristics (we dont discuss heuristics here i nthis course, only branch and bound)
what types of TSP is there?
symmetric and asymmetric. Depends on whether the cost depend on direction or not
is TSP min or max?
min.
We minimize the cost of paths. There probably is nothing stopping us from maximizing it either?
what is the problem with sub tour constraints?
requieres exponentail number of contraints
elaborate on branch and bound for TSP
Relax the subtour elim constraints, because this makes it totally unimodular.
When a subtour appears in the solution, we branch so that the sub tour is removed.
Branching does not split the feasible region in two.
The branching is done by selecting a sub tour, and choosing one arc to force equal to 0 to break it up.
Then we solve the original problem again, but with the sub tour constraint still in tact.
Of course, we get multiple new subproblems that are distinguished by having arc forced to 0.
elaborate on the assignment problem being unimodular (totally)
Although it is temping to say we get A matrix like this:
x11 + x12 + x13 = 1
x21 + x22 + x23 = 1
x31 + x32 + x33 = 1
this is wrong.
The matrix would not line these like this, because the variables in each column is not the same. I thought originally it was all 1’s because I pictured it like the matrix above without considering that this is not how the matrix-vector equation Ax=b works.
Of course, we’d get shifted positions:
x11 + x12 + x13 +0x21 + 0x22 + 0x23 + 0x31 + 0x32 + 0x33= 0
0x11 + 0x12 + 0*x13 + …
The same applies for the other constraint, but this one is different because of what it sums over. however, the result is a matrix that satisfy the conditions for being totally unimodular.
The important result of this is of course that the LP relaxation sovles the problem.
Also, as the TSP without the sub tour constraints become the assignment problem, we’re dealing with a totally unimodular matrix, and we know the LP relaxation is optimal.
What is the VRP
Vehicle routing problem
Elaborate on the VRP
Design routes for a given number of vehicles so that the customers’ demand is satisfied. Each route starts and ends at a given depot.
Each customer is visited by one vehicle and each vehicle has a cpaacity that must not be exceeded.
key points:
Each vehicle has a capacity
Each customer has a demand
The task is not to minimize time or length (in the standard VRP). The problem is about using capacity probably.
VRP is a generalization of TSP, because we get a TSP if the number if vehicles is 1 and capacity that exceeds demand of customers. However, TSP would never have crossing arcs.
in what ways can we mathematically describe VRP?
two ways
1) Arc flow
2) path flow
elaborate on the mathematical formulation of VRP
We have K vehicles and eahc have ther same capacity “b”. Let d_i denote the demand from customer i.
Let cij denote the cost of travel between customer i and j.
we use i=0 as the depot.
Variables:
y_ik = 1 if customer “i” is visited by vehicle k. 0 otherwise.
x_ijk = 1 if vehicle “k” travel directly between customer i and j. 0 otherwise.
Then we get the model:
min z = ∑∑∑cij xijk [k in K][i in n][j in n]
s.t.
∑di yik [i in n] <= b, for each k.
this constraint say that for each vehicle, we must not visit the list of customers if the sum of their demands exceed the capacity of the vehicle.
Then we must make sure that all the customers’ demand is satisifed by exactly one vehicle:
∑y_ik [k in K] = 1, for each customer
Then we need a constraint
there are so many constraints, there is no way we need to remember all of this
elaborate on the path flow variant of the VRP
The arc flow model leads to many constraints because of the sub tour elimination.
In this formulation, we hide this complexity.
We assume that we are able to generate a set of routes (up front typically) that vehicles can use.
Now, we have this:
“i” : customers
r: route
R : set of routes (assumed to satisfy the capacity restrictions)
A_ij : 1 if customer i is visited in route r, 0 otherwise
C_r : cost by driving route r
x_r : 1 if route r is used, 0 otherwise
Problem:
min z = ∑cj xj [j in J]
s.t.
∑xj [j in J] = K
∑aijxj = 1
xj in {0,1}
The benefit is that now, there is no reason to consider vehicle capacity.
Recall the aij. It is 1 if a specific route j has customer i visited.
The problem now really is to select a set of objects from subsets so that all are picked exactly once. However, we also have the ∑xj = K constraint that specified how the number of routes picked must be equal to K, and K is the number of vehicles.
