0
votes
1answer
29 views

Can there be a unique natural number vector solution to $Ax =b$ where $A$ is not a specific type of square matrix?

Let $A$ be $(n-1) \times n$ matrix that is of the following form: $$\left( \begin{array}{ccc} n-1 & 1 & 0 &.... & ....\\ 0 & n-2 & 2 & .... & ....\\ 0 & 0 & n-3 ...
0
votes
0answers
19 views

Name search for special Linear Mixed Integer Programm

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you ...
0
votes
0answers
31 views

Mixed Interprogramm remodeling

for example i have the following problem min z 5 x_1a + 6 x_1b - 3 x_2a + 0 x_2b <= z -3 x_1a + 0 x_1b - 1 x_2a + 2 x_2b <= z x_1a + x_1b = 1 (Constraint say of this group only one variable ...
0
votes
1answer
47 views

Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements ...
0
votes
0answers
21 views

Binary IP - Binari-zed result of negative value to 0, and positive value to 1

I have a set of variables $T_i = \{22, 23.6, 24, 24.2, 25\}$ and a constant value $C=24$. Given $$ a =T_i - C $$ I'd like to turn the result of subtraction a to binary value $\{0,1\}$, such that if ...
6
votes
3answers
233 views

Integer Programming problem

I have an integer programming problem with $L$ variables $x_1, x_2, x_{L}$ which all assume integer values and the following constraints must stand: $x_i \geq 0$ $x_1 = 10$ $x_2 + x_3 + ... + x_{L} ...
0
votes
1answer
212 views

general formula for an orthogonal projection of a point onto a line

Could someone confirm this or correct the mistakes because this seems somehow wrong although I doublechecked it. Mx,My are coordinates of a point and Px,Py,Kx,Ky are coordinates of a line on a ...
1
vote
0answers
38 views

Regression/compressive sensing with non-linear constrains where the coefficients are assumed to be integer or binary {0,1}

The following regression problem $$ \mathbf{y} = \mathbf{A}\mathbf{x} $$ where $\mathbf{y}$ is a $N\times 1$ column real vector, $\mathbf{A}$ is a $N\times M$ real matrix where each column ...
1
vote
2answers
91 views

Checking inequality without actually calculating LHS and RHS

How to check whether the following inequality is true or not without actually calculating the values of $x^y $ and $y^x $: $$ x^y > y^x$$ (x and y are integers)
0
votes
2answers
1k views

Integer Solutions for linear equation

What are the different methods for solving a linear equation with integral Solutions? Which one is preferred over other? What is the best method? For example, 3x + 5y = 12309834576, How do I find ...
2
votes
0answers
57 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
1
vote
1answer
66 views

Quadratic integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
0
votes
0answers
52 views

Minimizing an expression with linear constraints

Given a system of under-constrained (i.e. infinite solutions) linear equations (all values will be integers, all coefficients will be 0, 1, or -1), I want to pick values for the variables to minimize ...
1
vote
0answers
30 views

If the following LP has an integral solution

I know the constraints matrix A of a linear program "Min cx such that Ax>=b" is totally unimodular. So, the program has integral solutions for integral vector b. If this is also the case for the ...
3
votes
3answers
93 views

How do one solve a nonlinear combinatoric problem?

I am an undergraduate CS student and I am struggling with a problem. $Qx = b$ where $Q$ is a constant $m \times n$ matrix (with $m>n$), $x$ is a $n \times 1$ vector and $b$ is a $m\times 1$ ...
1
vote
1answer
156 views

How tell if a polyhedron contains a lattice point

So given a polyhedron $Ax \le b$ Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point) I was thinking a couple things: brute force ...
4
votes
1answer
269 views

Is the inverse of an invertible totally unimodular matrix also totally unimodular?

My question is learned from here. Let me restate it as follows: A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
1
vote
1answer
149 views

Linear Programming for Integer Solutions

Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer. How would one manipulate the resources so that the ...
1
vote
1answer
147 views

Are there 0-1-matrices that are not unimodular?

I am just wondering if there are matrices that only consists of $0$s and a few $1$s that are not totally unimodular (TU)? I cannot come up with an example but I am not very experienced with this ...
3
votes
1answer
93 views

A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately. I am ...
4
votes
0answers
154 views

On the integer feasibility of polytopes defined by idempotent integer matrices

EDIT: I realized that while writing this question, I was reasoning about orthogonal projections. Thus, I forgot to transpose when forming the projection on to the space orthogonal to the image of $P$. ...
1
vote
4answers
83 views

Procedures to find solution to $a_1x_1+\cdots+a_nx_n = 0$

Suppose that $x_1, \dots,x_n$ are given as an input. Then we want to find $a_1,\ldots,a_n$ that satisfy $a_1x_1 + a_2x_2+a_3x_3 + a_4x_4+\cdots +a_nx_n =0$. (including the case where such $a$ set does ...
0
votes
1answer
108 views

Approximate rational number of radical combination

Suppose that there is a radical combination $a\sqrt{b}+c\sqrt{d}$ where a,b,c,d are natural. Each term part $\sqrt{b}$ cannot be transformed into the form of $s\sqrt{q}$. The question is, 1) Suppose ...
1
vote
1answer
154 views

way of converting an approximate rational number of radical combination into original form

Suppose that there is a radical combination $a\sqrt{b}+c\sqrt{d} ...$. where $a,b,c,d\in \mathbb{N}$, for which each term part $\sqrt{b}$ cannot be transformed into the form of $s\sqrt{q}$. The ...
2
votes
1answer
220 views

Is there a formula for nCr that considers a min/max range? (restricted composition estimation)

I'm bad at math and hope I explain this right(please don't be upset if I don't, I'm not trying to be lazy or a jerk, I really don't understand what information is sometimes required and focus on the ...
2
votes
3answers
181 views

Linear inequalities to make a specific solution infeasible

Say we have a binary linear programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & c\cdot\mathbf{x} \\ & \text{subject to} & ...