Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following constraint inequalities and equalities:

$$Ax \leq b$$ $$A_{eq}x = b_{eq}$$

The problem is that the objective function, which I am asked to minimized, is defined as

$$f=\sum\limits_{i=1}^{m}u([\sum\limits_{j=1}^{n}k_{ij}x_j]-c_{i})$$

where $u(x)$ is the Heaviside step function.

Strictly speaking, this is not a linear programming problem ( although quite close!), so it can't be attacked by the standard linear programming techniques.

I'm aware that I can approximate the step function into a smooth function, but this is not the route I plan to take now.

What are the techniques that are available for this kind of problem?

share|improve this question
1  
one choice is to replace the step function with a smooth approximation, and then to use some nonlinear solver. –  user1709 Jan 8 '11 at 17:28
    
@Slowsolver, is there another choice? –  Graviton Jan 9 '11 at 11:21
    
The objective should be to minimize $\sum_i u(t_i)$, not $\sum_i t_i$, right? I like Fanfan's approach though I'm not sure if it'll work in this case since if $\sum_j k_{ij} x_j - c_i \leq 0$, then $t_i$ is not necessarily 0 though it needs to be. –  user32021 May 23 '12 at 10:52
    
Strike that. It would still work because of the minimization objective. If the objective were to maximize, then it would not. –  user32021 May 23 '12 at 10:57
add comment

1 Answer

Your problem can be converted in a mixed-integer program in the following way: for each term in the objective function of the form $$u\Bigl(\sum_j k_{ij} x_j - c_i\Bigr) ,$$ introduce an auxiliary binary variable $t_i \in \{0,1\}$ and add the constraint $$\sum_j k_{ij} x_j - c_i \le M t_i$$ where $M$ is a sufficiently large constant (it has to be larger than all possible values for the argument of $u$). You can then replace the objective function by the sum of the binary variables, i.e. minimize $\sum_i t_i$ and check that the constraint ensures that the problem is equivalent to the original one (note that this assumes the convention $u(0)=0$).

Mixed-integer programs are harder to solve than linear programs, but you are guaranteed to find a globally optimal solution exactly.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.