# Solving a optimization problem

Here is the objective function of my optimization problem:

$$\min \left( \sum_{i=1}^{n}a_i(1 - X_i)\right), \qquad n = \arg \min(X_i = 1)$$ $$X_i = \{0,1\} \text{some other linear constraints}$$

Does anybody know:

1. Is it a linear programming?
2. If not, what kind of category this problem belongs to? Any reference paper?
3. How to put it into a optimization solver (such as Matlab or GLPK)? I don't know how to set the coefficient in this case.
• Because the variables $X_i$ are discrete (binary) values, (1) it is not a linear program. It's not clear to me what the argmin construct produces. It wouldn't make much sense to limit the summation to the first index $i$ where $X_i = 1$. Jul 16, 2014 at 14:43
• The number of items in this Sigma is decided by n while this n is the minimum index of Xi which equals to 1. For example, if x1 = 0, x2 = 1, x3 = 1,... then the result should be a1. if x1 = 0, x2 = 0, x3 = 1,...then the result should be a1 + a2 Jul 16, 2014 at 15:00
• How many $a_i$ are there? Jul 16, 2014 at 16:15
• If you have discrete sets you optimize over like $X_i=\{0,1\}$ it will be combinatorial optimization which is in general hard, but some such problems can be approximated by sparse $L_1$ penalized methods. Aug 29, 2018 at 18:11

I don't understand where $n$ comes from but this seems to be a binary programming problem.

http://www.mathworks.se/help/optim/ug/bintprog.html

As explained the problem is solved in linear time by forming a running sum of the $a_i$. Keep track of the minimum sum formed (starting with a zero initial sum). The location of the minimum running sum tells where the leading $X_i$ should be all zeros. After setting the next variable to 1, it doesn't matter how the rest get set. For the sake of specificity we can require the $X_i$ to be increasing.

The formulation would be a bit simpler if, instead of binary $X_i$, we used binary $Y_i = 1-X_i$ (then $Y_i$ are decreasing), but I'll stick to the notation used in the Question. We write:

$$min \sum_{i=1}^N a_i (1-X_i), \;\;\text{ where } \;\; X_i \in \{0,1\}$$

$$X_1 \leq X_2 \leq \ldots \leq X_N$$

The discrete binary values for $X_i$ make this a integer linear program (ILP), which are generically hard problems. The particular problem here though is easily solved in time linear with the number of available $X_i$.

A free and open source solver for such problems is lp_solve. For $N=3$ the lp_solve model can be written as a text file in this way, assuming coefficients $a_1 = 0.2, a_2 = -3, a_3 = 4.1$:

min: 0.2*(1 - x1) - 3*(1 - x2) + 4.1*(1 - x3);
x2 - x1 >= 0;
x3 - x2 >= 0;
bin: x1, x2, x3

• Yes, you are correct But I was wondering how to get this optimization result. Only if we set the coefficients in objective function explicitly, the ILP solver could get a result. If I use $\min \quad \sum_{i = 1}^N a_i(1-X_i)$ while N is the total number of ai, I could get an answer from solver but that is not what I want. Jul 16, 2014 at 18:57
• It sounds like you want to get the result from some Solver, as opposed to simply solving the problem. Note that you can impose a constraint $X_i \le X_j$ when $i \le j$ and force the selection of $a_i$ coefficients as a run of 1's followed by 0's in this fashion. Jul 16, 2014 at 19:08

Its binary programming, not linear programming. As for your third question, that is product-specific (I use Excel Solver or R)