1
$\begingroup$

I have a model as below.

enter image description here

I have constructed the matrix of its constraints as below. I need to show the total unimodularity of its constraints matrix. However, the determinant of the below submatrix (specified by red line) is not equal to -1, 0, or 1. This means that the matrix of constraints is not totally unimodular. Can you please let me know whether I am making any mistakes?

enter image description here

$\endgroup$
5
  • $\begingroup$ It would help if you could confirm what's a variable and what's a constant and what the domain of those variables/ constants would be. I assume $x_{ij}$ are binary variables, $w_j$ are continuous variables and $g_j$ are constants? $\endgroup$ – Walter Sebastian Gisler May 29 at 7:18
  • $\begingroup$ It sounds like you have a business problem and want to come up with a mathematical optimization formulation that has a totally unimodular constraint matrix. What is the business problem? If it is what I think, you can model it as a shortest path problem in a directed acyclic network, and the corresponding constraint matrix will be TU. $\endgroup$ – RobPratt May 29 at 13:31
  • $\begingroup$ @RobPratt, could you please introduce me to a paper that proves the total unimodularity of a shortest path problem in a directed acyclic network? $\endgroup$ – mdslt Jun 12 at 23:50
  • $\begingroup$ See Theorem 11.12 in Ahuja, Magnanti, Orlin, Network Flows (1993). $\endgroup$ – RobPratt Jun 13 at 0:02
  • $\begingroup$ @RobPratt, thanks! $\endgroup$ – mdslt Jun 13 at 1:45
2
$\begingroup$

Your matrix seems to represent the given model. If you multiply any of the variables with $M$, $M$ will definitely be part of the matrix. Like RobPratt pointed out, that alone is sufficient to say that the matrix isn't totally unimodular.

However, assuming that $w_j$ are continuous variables and $g_j$ are constants (confirm please), I believe it is possible to set $M$ to 1 in this case. $M$ has to be a sufficiently large constant relative to the expected size of your $w_j$ and $g_j$. Assuming $w_j$ and $g_j$ would be quantities in kg, you could always change the constants such that $w_j$ and $g_j$ will be in tonnes or even larger units of weight.

With $M = 1$, you should be able to check whether the resulting matrix is unimodular or not.

$\endgroup$
4
  • $\begingroup$ This is amazing. I would like to confirm that w_j are continuous variables, g_j are constants. To make sure that I have understood your point, you meant that I can tentatively give relatively smaller values to my parameters (like g_j) such that I can set M = 1. Under this condition, I would be able to check the total unimodality. Is my understanding correct? $\endgroup$ – mdslt May 29 at 19:18
  • $\begingroup$ I would like to emphasize that M can certainly get values greater than 1 for many instances (where at least one g_j is greater than 1). However, you are telling me to assume that M=1 only for the sake of evaluating the total unimodality. Is that right? Many thanks. $\endgroup$ – mdslt May 29 at 19:26
  • $\begingroup$ Yes, that was my thought. Scale the inputs, such that you can solve the problem with M = 1. Nevertheless, this doesn't automatically mean that the matrix is totally unimodular, but at least you have a matrix consisting of only {-1,0,1} elements which is a prerequisite. $\endgroup$ – Walter Sebastian Gisler May 30 at 5:58
  • $\begingroup$ It is possible to show that if the matrix is totally unimodular, and all constants are integer values, the problem has integer basic solutions. Note the second part: all constants have integer values. It seems like that might not be the case when you scale the $g_j$ values, so even if it turns out that the matrix is totally unimodular, this might not help you for what you want to achieve. As RobPratt says in his comment, you might want to post what your problem is. There might be a more efficient formulation. $\endgroup$ – Walter Sebastian Gisler May 30 at 6:09
5
$\begingroup$

It is not totally unimodular. A necessary condition is that even the $1\times 1$ submatrices have determinant in $\{-1,0,1\}$. That is, individual entries must be in $\{-1,0,1\}$.

$\endgroup$
1
  • $\begingroup$ So, I should reformulate my question! Does the matrix I have constructed represent the constraints matrix of the given model? Many many thanks for your help. $\endgroup$ – mdslt May 28 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.