# \[AMPL 24635\] Column generation with two types of variable using the column

**URL:** <https://discuss.ampl.com/t/ampl-24635-column-generation-with-two-types-of-variable-using-the-column/538>\
**Category:** Google Group Mirror\
**Created:** [May 4, 2023, 5:23am UTC](https://discuss.ampl.com/t/ampl-24635-column-generation-with-two-types-of-variable-using-the-column/538 "2023-05-04T05:23:57Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![qiaolu\_gmail.com](https://avatars.discourse-cdn.com/v4/letter/q/b9bd4f/32.png) [@qiaolu\_gmail.com](https://discuss.ampl.com/u/qiaolu_gmail.com)\
**Post date:** [May 4, 2023, 5:23am UTC](https://discuss.ampl.com/t/ampl-24635-column-generation-with-two-types-of-variable-using-the-column/538/1 "2023-05-04T05:23:57Z")

</div>

I want to model a Problem with column generation algorithm. I have two types of variables in the master problem, namely, x\_{i,j}^{a,k} and y\_{i,j}^{a,k}, where k belongs to the set of columns that we want to generate. In addition, x\_{i,j}^{a,k} equals to 1 if y\_{i,j}^{a,k} is greater than 0, and sum of x\_{i,j}^{a,k} over all possible a equals to 1. The reason why I want to put both x and y in the master problem rather than just use variable x and keep the value of y as a parameter related to columns is that I may have a more complex pricing problem and more columns.

I’m thinking of using two pricing problems for the variable x and y, respectively, when solving the pricing problem. Is it correct? Or are there any other approaches to address this problem?

Thank you so much!

---

<div class="post-metadata">

**Author:** ![AMPL\_Google\_Group](https://avatars.discourse-cdn.com/v4/letter/a/9dc877/32.png) [@AMPL\_Google\_Group](https://discuss.ampl.com/u/AMPL_Google_Group)\
**Post date:** [May 8, 2023, 5:24pm UTC](https://discuss.ampl.com/t/ampl-24635-column-generation-with-two-types-of-variable-using-the-column/538/2 "2023-05-08T17:24:32Z")

</div>

Is x\_{i,j}^{a,k} a binary (zero-one) variable? Then your master problem is a mixed-integer optimization problem, which does not normally give the dual values that you would need for the pricing problem of a column generation algorithm.

If you have found some way to do a pricing problem for your particular application, however, then you could experiment with solving only the pricing problem for the x-variables, or only the pricing problem for the y-variables, or both pricing problems. (There is no way to know which works best except to try them all.) Whenever you choose a new k, however, you will need to add both x\_{i,j}^{a,k} and y\_{i,j}^{a,k} to the master problem.

---

<div class="post-metadata">

**Author:** ![qiaolu\_gmail.com](https://avatars.discourse-cdn.com/v4/letter/q/b9bd4f/32.png) [@qiaolu\_gmail.com](https://discuss.ampl.com/u/qiaolu_gmail.com)\
**Post date:** [May 9, 2023, 7:12am UTC](https://discuss.ampl.com/t/ampl-24635-column-generation-with-two-types-of-variable-using-the-column/538/3 "2023-05-09T07:12:35Z")

</div>

Dear Robert,

Thank you so much for your answer! x\_{i,j}^{a,k} a binary (zero-one) variable before linear relaxation. We can relax the integer constraint of x.

Another concern is that we need another constraint as follows to make sure x and y are consistent.

_y\_{i,j}^{a,k} \<= **upperbound** \* x\_{i,j}^{a,k}_ _, \forall (i,j), a, k,_ where upperbound is a upper bound for y.

But in this way, the original master problem will have an exponential number of variables and constraints (as adding one column will add another constraint) if we put all the columns. It makes me think of one statement about column generation (the number of rows is much smaller than the number of columns). What do you think about the characteristic of such a formulation?

Thank you so much for your time and for the explanations!

Best regards,  
Qiaolun

---

<div class="post-metadata">

**Author:** ![AMPL\_Google\_Group](https://avatars.discourse-cdn.com/v4/letter/a/9dc877/32.png) [@AMPL\_Google\_Group](https://discuss.ampl.com/u/AMPL_Google_Group)\
**Post date:** [May 10, 2023, 2:36pm UTC](https://discuss.ampl.com/t/ampl-24635-column-generation-with-two-types-of-variable-using-the-column/538/4 "2023-05-10T14:36:38Z")

</div>

In your problem where the integer constraint is relaxed, you have

y\_{i,j}^{a,k} / upperbound \<= x\_{i,j}^{a,k}  
0 \<= x\_{i,j}^{a,k} \<= 1

In most applications that have these kinds of constraints, you can get the same optimal value when you replace them by

x\_{i,j}^{a,k} = y\_{i,j}^{a,k} / upperbound

where upperbound is some bound on y that is implied by other constraints of the problem. If this is true of your application, then you can eliminate these constraints from your formulation by substituting y\_{i,j}^{a,k} / upperbound wherever x\_{i,j}^{a,k} appears. Then your column-generation problem will be greatly simplified.

If setting x\_{i,j}^{a,k} = y\_{i,j}^{a,k} / upperbound sometimes gives a worse value for the optimal value of the relaxation, then further study will be needed. It might be that this problem is not easy to adapt to column generation.