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.