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

Question

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?

Answer 1

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.

Answer 2

I will not comment on the ilp to LP reduction, but the cost function is easy to deal with. The smallest cost (equal to 6) is had whe all of the terms at equal to 1. This is possible only when all of the arguments of cost() are smaller than $k_1.$ this means that you add six inequalities to your constraint set and check for feasibility. If the program is feasible, great. If not, you allow one of the terms to be between $k_1$ and $k_2$ and so on. You will have to solve 64 feasibility problems, but 64 is not such a big number.