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, 2014 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, 2014 at 15:00
  • $\begingroup$ How many $a_i$ are there? $\endgroup$
    – hardmath
    Jul 16, 2014 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$
    – mathreadler
    Aug 29, 2018 at 18:11

3 Answers 3

Reset to default
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, 2014 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, 2014 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .