Types of integer problesm Flashcards

1
Q

Elaborate on knapsack problems

A

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}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Elaborate on facilituy location problems

A

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..

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

elaborate on assignment problems

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

elaborate on set covering

A

Set covering only care about covering all the objects. THerefore it is the same as set partitioning, but with >= constraint instead of =

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

elaborate on set partitioning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

elaborate on TSP

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

why is TSP so well studiuet?

A

Many planning problems can be formulated as a variation of it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Characteristics of TSP

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what types of TSP is there?

A

symmetric and asymmetric. Depends on whether the cost depend on direction or not

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

is TSP min or max?

A

min.

We minimize the cost of paths. There probably is nothing stopping us from maximizing it either?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

what is the problem with sub tour constraints?

A

requieres exponentail number of contraints

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

elaborate on branch and bound for TSP

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

elaborate on the assignment problem being unimodular (totally)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the VRP

A

Vehicle routing problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Elaborate on the VRP

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

in what ways can we mathematically describe VRP?

A

two ways
1) Arc flow
2) path flow

17
Q

elaborate on the mathematical formulation of VRP

A

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

18
Q

elaborate on the path flow variant of the VRP

A

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.

19
Q
A