I would like to change the following linear programming model to restrict the decision variables to two integers, namely a and b (a -e
-(Y-Zx) > -e
where Y is a n-dimensional vector, Z is a n \times k matrix and x is a k-dimensional vector. e represents a n-dimensional vector of errors which need to be minimized. In order to make sure that x's only can have values equal to "a" or "b", I have added the following constraints keeping the original LP formulation:
-a/(b-a) - (1/2)' + I/(b-a) x > -(E/(b-a) +(1/2)')
-(-a/(b-a) - (1/2)' + I/(b-a) x ) > -(E/(b-a) +(1/2)')
where I stands for a k \times k identity matrix and E is a k-dimensional vector of deviations which needs to be minimized (subsequently, the objective would be minimize (1,1...,1)' (e; E)).
But, yet there is no guarantee that the resulting optimal vector only consists in a and b. Is there any way to fix this problem? Is there any way to give a higher level of importance to two latter constraints than to the two former's?
Hi, I agree with Iago, in case you want to limit the possible values of one variable you fall under the integer programming formulation.
Dear Iago,
Thanks for your reply.
Indeed, I am converting an instance of a 0-1 integer linear programming problem to an instance of another integer linear programming problem in which all variables are restricted to a finite set of integers. Therefore, I can not use an additional 0-1 variable. Besides, The formulation must be preserved.
Fatemeh, You need to have two set of variable (integer and continuous) and then have a dummy function as Iago suggested above.
Thank you Iago and Ganesh,
But my problem is that all the decision variables must be restricted to a finite set of integers, e.g, S = {s_1, s_2, ..., s_p}. I can't have any binary variable. I wish to restrict them to s_1 and s_2.
Dear Peter,
Thank you for your reply. I did this by adding the following constraints to my problem:
-a/(b-a) - (1/2)' + I/(b-a) x > -(E/(b-a) +(1/2)')
-(-a/(b-a) - (1/2)' + I/(b-a) x ) > -(E/(b-a) +(1/2)')
But, I don't know how to argue that by minimizing the positive errors (i.e, components of vector E) at the optimum all variables take extremal values which is either a or b. Could you please give me more details?
P.S: I don't wish to solve this optimization problem. I want to convert an instance of a problem (namely binary linear programming) to an instance of another problem (a linear programming in which the decision variables are restricted to a finite set, S = {s_1,s_2, ..., s_p}).
Dear F. H
U can use dynamic approache to solve the linear programming problem.
With best wishes
Dear Fatemeh,
Maybe I am getting too late into this discussion. What I would do is to solve the following problem P:
minimize (1,1,...,1)' e
(Y-Zx) > -e
-(Y-Zx) > -e
a -e
x_t = a
P2
minimize (1,1,...,1)' e
(Y-Zx) > -e
-(Y-Zx) > -e
x_t = b
4. Perform step 3 on the solutions of all problems you have.
5. (bounding) . Stop branching if:
- the solution of a problem is infeasible
- all variables in the solution have values either a or b ("integer" solution)
- the solution of the problem still contains variables with values different to a or b, but the objective is worse than a previously found "integer" solution.
I know it is brut force, but it will keep the structure of your problem and will guarantee what you want. And, it is very easy to program.
Hope it helps.
Vlad
- Badges
- Science topic
- Similar topics
- Computer Science