0
2

In one of my previous post, I mention a LP system with exponentially many constraints and variables. A more compact description of it would be:

given n, we construct a LP system with 2^n+n variables, and 2^(n-1)+n equality constraints, and each variable is larger than 0. Example, n=3:

min c[1xx]n[1xx]+c[11x]n[11x]+c[1x1]n[1x1]
n[1xx]=n[100]+n[101]+n[110]+n[111]
n[11x]=n[110]+n[111]
n[1x1]=n[101]+n[111]
n[000]+n[100]=n[000]+n[001]
n[001]+n[101]=n[010]+n[011]
n[010]+n[110]=n[100]+n[101]
n[011]+n[111]=n[110]+n[111]
n>=0

Notice, n[1xx] simply means all occurring probability of 100,101,110,111 with the shape "1XX". same analysis goes for 11x and 1x1... for the rest 2^(n-1) equality, we think in terms of connectivity. For example the n[x00]==n[000]+n[100]=n[000]+n[001]==n[00x], all terms on the left handside is in the shape of "X00" and everything on the right hand side is of the shape "00X". By "connectivity", they equal.

Row generation or column generation alone could not solve this system as far as I can think of. Afterwards I found one and only one paper mentioning something like simultaneous column and row generation. I wish to ask are there more reference tackling this type of problem (which requires column and row generation simultaneously). Did this kind of problem ever exist before and are there some standard names for it?

If you know of some other possibly methods to solve this, I would be very very appreciated if you could hint on me.... Thank you very much:)

EDIT:

" The problem is originated from solving the ground state of infinite 1D spin system. Consider an infinite 1D lattice, each spin site could be either 1 or 0, every 1 appeared in the 1D lattice would result in an energy of c[1xx]. so n[1xx], simply means the appearing frequency of "1" in the infinite 1D system. Same arguments goes for c[11x], corresponding to the energy for each existing "11" in the infinite system, and n[11x] is simply the appearing frequency of "11". For c[1x1], it is the energy for each occurrence of the "1?1"... As long as the first site and the third site is "1", regardless of what the second site, it would produce an energy of c[1x1]...

The rest of 2^(n-1) equality constraint is that: the appearing frequency of "ab" in the 1D lattice system is equal to the appearing frequency of "0ab"+"1ab", which means there must be something on "ab"'s left. And the appearing frequency of "ab" is also equal to the appearing frequency of "ab0"+"ab1", which simply means there is something on "ab"'s right hand side. So we term this type of equality as "connectivity equality". Note "ab" could choose as "00", "01", "10" or "11". So there are 2^(3-1)=4 such equalities. "

asked 12 Oct '14, 14:26

Chivalry's gravatar image

Chivalry
229117
accept rate: 0%

edited 12 Oct '14, 15:18


The definition of column-and-row generation is not fully clear. As mentioned in another answer, column-and-row generation can be another name for branch-cut-and-price. It can also mean the dynamic generation of columns which induces the dynamic generation of structural constraints. In regards to the latter, there have been a number of papers aimed at developing a general column-and-row generation framework.

To best of my knowledge, there are four main papers regarding a general column-and-row generation. These are:

  • A. Frangioni and B. Gendron (2013). A stabilized structured Dantzig-Wolfe decomposition method.
  • R. Sadykov and F. Vanderbeck (2013). Column generation for extended formulations.
  • I. Muter, S. I. Birbil, and K. Bulbul (2014). Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows.
  • S. J. Maher (2014). Solving the integrated recovery problem using column-and-row generation. (Sorry for the self reference).

Each of these has a different focus and they may not really fit with your needs. The paper by Avella et. al. was mentioned in another answer. This approach is slightly different since all variables and constraints are known a priori. However, it may be useful in your context.

link

answered 18 Oct '14, 02:36

Stephen%20J%20Maher's gravatar image

Stephen J Maher
2392
accept rate: 75%

This is very comprehensive and it removes my doubt about what is the difference the between them. Thank you:)

(18 Oct '14, 11:47) Chivalry

There exists "Branch and Price and Cut algorithms" for mixed integer problems (row and column generation are performed at every node of the branching tree).. I don't know if it will be useful for your LP system, but it may give you an idea.. Good luck.

link

answered 12 Oct '14, 19:45

Souha's gravatar image

Souha
513
accept rate: 0%

Thank you sooo much for hinting me.

(12 Oct '14, 19:46) Chivalry

Avella et al. published a paper some years ago entitled "Computational study of large-scale p-median problems" where they did simultaneous row and column generation. I do, however, not recall how general the proposed was.

link

answered 12 Oct '14, 15:00

Sune's gravatar image

Sune
958413
accept rate: 20%

Thank you for telling me:)

(12 Oct '14, 15:01) Chivalry
2

@Chivalry: by accident i stumbled over this article at optimization-online.org: http://www.optimization-online.org/DB_FILE/2010/11/2815.pdf . It might be of help

(13 Oct '14, 04:30) Sune

really, really thank you:)

(13 Oct '14, 09:51) Chivalry
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×18
×4

Asked: 12 Oct '14, 14:26

Seen: 1,282 times

Last updated: 18 Oct '14, 11:47

OR-Exchange! Your site for questions, answers, and announcements about operations research.