Column generation with two types of variable using the column

[qiaolu...@gmail.com]

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!

[AMPL Google Group]

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.

--
Robert Fourer

We're switching to a new, enhanced user forum.
Join it now at discuss.ampl.com.

{#HS:2232649685-116690#}

[qiaolu...@gmail.com]

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

[AMPL Google Group]

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.

--
Robert Fourer

We're switching to a new, enhanced user forum.
Join it now at discuss.ampl.com.

{#HS:2232649685-116690#}

On Tue, May 9, 2023 at 7:12 AM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

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

On Mon, May 8, 2023 at 5:24 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

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.

--
Robert Fourer

We're switching to a new, enhanced user forum.
Join it now at discuss.ampl.com.