[Math] how to model a linear program with step-like cost function in the objective

linear programming

I have a large linear program with the following details.

d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form

d1 < d3 < d7 < d23 (First set of constraints)
d2 < d3 < d8 < d49 (second set of constraints)
and so on.
d1 = 1 is given.

In my problem, there could be several hundred thousand such simple inequalities.

The objective function is to minimize the following

cost(d3 – d1) + cost(d7 – d3) + cost(d23 – d7) + cost(d3 – d2) + cost(d8 – d3) + cost(d49 – d8)

for this example. In this, cost(x) is a step function of the form
if x < k1, cost(x) = 1
k1 <= x < k2, cost(x) = 2
and so, where k1 and k2 are known constants.

I am looking for some guidance on modeling the step function in the objective.

Even though I state that di's are integers, I am thinking that I can relax that assumption to not being an integer (since solving large ILPs are tough). If I relax that and change the constraints as

d1 + 1 < d3
d3 + 1 < d7
d7 + 1 < d23
d2 + 1 < d3
d3 + 1 < d8
d8 + 1 < d49

and since I have a minimization problem, I am thinking that the di's will take distinct integer values. Can anybody help me with pointers on how to model this problem?

Best Answer

If i correctly understand you problem, it can't be transformed to LP in general. The reason is that LP is convex, and your objective function is not convex(even discontinues). So i suugest you to look at less general case.

Related Question