0
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – hardmath
    Jul 16 '14 at 14:43
  • $\begingroup$ 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 $\endgroup$
    – Wenjie
    Jul 16 '14 at 15:00
  • $\begingroup$ How many $a_i$ are there? $\endgroup$
    – hardmath
    Jul 16 '14 at 16:15
  • $\begingroup$ 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. $\endgroup$ Aug 29 '18 at 18:11
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Wenjie
    Jul 16 '14 at 18:57
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Jul 16 '14 at 19:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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