Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

13
votes
0answers
334 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
10
votes
5answers
6k views

Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...
7
votes
2answers
304 views

Mean and Median in a Classic River Crossing Problem

Consider the following classic problem: Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the ...
7
votes
1answer
78 views

Integer programming feasibility is NP-what

What is the complexity class of the general problem of integer programming feasibility? The sources I've looked at are, in my opinion, very confusing. Some say NP-hard, some say NP-complete. Some ...
6
votes
3answers
277 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} ...
5
votes
1answer
619 views

Determining quickly whether this Integer Linear Program has any solution at all

I've got an integer linear program of the form $$ \begin{aligned} \text{Minimize}&& c &= x_1 + \cdots + x_m \\ \text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\ \text{where} ...
5
votes
2answers
161 views

Minimize sum of smallest and largest among integers on the real line.

Suppose there are 3 non-negative integers $x$, $y$ and $z$ on the real line. We are told that $x + y + z = 300$. Without loss of generality, assume $x$ to be the smallest integer, and $z$ to be the ...
5
votes
2answers
109 views

How to prove that this matrix is total unimodular

This matrix is total unimodular (tested by a computer program). ...
4
votes
1answer
132 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
1answer
54 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
4
votes
1answer
511 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 ...
4
votes
3answers
105 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$ ...
4
votes
0answers
45 views

Name for “Almost a vector space, but with $\mathbb{N}_0$ instead of a field”

I have a finite set of vectors $V\subset \mathbb{R}^n$ Let us enumerate $V = \{\tilde{v}_1, \tilde{v}_2,...,\tilde{v}_m\}$ I have some space that I want to talk about (I spend a lot of time talking ...
4
votes
0answers
118 views

ax+by+cz<=d, find the maximum value of ax+by+cz.

I am recently calculating that kind of questions as shown in title. And of course, I use a lot of time to find the answer. Therefore I would like to know how I can calculate faster. Q.: ax + by + ...
4
votes
1answer
207 views

Why calculating XOR of consecutive values can be simplified? [duplicate]

I was trying to calculate integer xor of 0..n. I named the function xored(n). Note that in examples below ^ does not mean power but integer xor (like in C or Java language) So, xored(0) = 0, ...
4
votes
0answers
91 views

How to minimize $\min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}$

This problem looks familiar, but I don't remember its solution: $$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/n \rfloor}k $$ subject to $$ b^k \ge n \\ b,n,k \in \mathbb{N} $$ Does it have a name? What's ...
4
votes
0answers
165 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$. ...
3
votes
2answers
274 views

For a fixed positive integer n, show that the determinant below is divisible by n

For a fixed positive integer n, if $D = \left|\begin{array}{ccc} n! & (n + 1)! & (n + 2)! \\ (n + 1)! & (n + 2)! & (n + 3)! \\ (n + 2)! & (n + 3)! & (n + 4)! ...
3
votes
3answers
435 views

How to divide natural number N into M nearly equal summands?

How to divide natural number N into M nearly equal summands? For example, to divide 20 by 13, in geometric representation, I should get How to generate the sequence above? What is the name of ...
3
votes
3answers
3k views

Double summation

I'm currently solving some Operations Research exercises related to Integer Programming. In one of the solutions of the exercises the author uses the following formula for the objective function: ...
3
votes
5answers
62 views

Why is my procedure misleading?

Max: $ z = 10( x_1 + x_2)$ subject to constraints: $$ 2x_1 + 5x_2 \leq 16 $$ $$ 6x_1 + 5x_2 \leq 30 $$ $$ x_1, x_2 \in \mathbb{Z^+} $$ I have the Integer Programming ...
3
votes
2answers
86 views

$ k x^2 +4x = n $, Algorithm or any other method needed

I want to find any $n < 10^{18} $ so that the equation below has at least two pairs of solutions $(k, x)$ $ k x^2 +4 x = n $ constraints: $x > 10^6; \; x > k ; \; k, x \in \mathbb{N}$ I ...
3
votes
2answers
432 views

How many solutions are there to $abc+def=ghi$, where $a,b,\ldots, h,i$ are distinct non-zero digits?

I saw this problem posted by Google. Those posting in the comments found solutions using computer programming. I would like to know if there is an easier solution than trying every single combination. ...
3
votes
1answer
42 views

solve $54 x + 16 y = 2400$ for integer values of x,y

How to get integer values for x and y that satisfy: $$54 x + 16 y = 2400$$ Someone told me that I can do it using Euclid-Wallis algorithm, but I don't understand it so, if there isn't any else ...
3
votes
1answer
113 views

XORing consecutive integers has an interesting property. Does anyone know why?

I hesitated to post on StackOverflow but I think the problem has little to do with programming and more to do with mathematics. So, here it is: I wanted to compute the function $ f(n) = 0 \oplus 1 ...
3
votes
2answers
103 views

How does one find the minimum of an equation of integers?

Going through a book of probability problems and am working on the Sock Drawer Problem: A drawer contains red socks and black socks. When two socks are drawn at random, the probability that both ...
3
votes
1answer
465 views

Determining Weights of Columns For A Prioritization Matrix

I'm trying to calculate the weight of various tasks. I have tasks that are daily, weekly, monthly, yearly. As a task gets closer to due date, I'd like it to be more important. For example, a weekly ...
3
votes
1answer
627 views

Connected graph solution from IP/LP

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties. I have problems formulating the connectedness condition in an IP/LP. The ...
3
votes
4answers
401 views

Combinatorial optimization - Bijections between duplicated numbers

English is not my native language: sorry for my mistakes. Thank you in advance for your answers. Two Bijections and an Array... Here is a 2D array (in this particular example: rows: 1 to 4; ...
3
votes
1answer
100 views

Software for Binary Integer Linear Programs

I am aware that there is good software out there to solve integer linear programs (ILPs). However, is there (preferably free or low cost) software I could use to solve large binary integer linear ...
3
votes
1answer
887 views

Linear programming problem with no objective function

I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize. I've been ...
3
votes
1answer
196 views

Efficiently solving a special integer linear programming with simple structure and known feasible solution

Consider an ILP of the following form: Minimize $\sum_{k=1}^N s_i$ where $\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of ...
3
votes
1answer
107 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence ...
3
votes
1answer
133 views

Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
3
votes
0answers
36 views

NP-hardness of solving congruence equations in several variables

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...
3
votes
0answers
158 views

Binary optimization

Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows: There are ...
3
votes
0answers
149 views

An optimization problem involving Latin Squares

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write ...
2
votes
3answers
143 views

Finding $a + b + c$ given that $\;a + \frac{1}{b+\large\frac 1c} = \frac{37}{16}$

Please help me to find the needed sum: If $a,b,c$ are positive integers such that $\;a + \dfrac{1}{b+\large \frac 1c} = \dfrac{37}{16},\;$ find the value of $\;(a+b+c)$. Thanks!
2
votes
2answers
205 views

Finding the index such that all partial sums are nonnegative

Given an array a[] of integers of arbitrary size N that sum to 0 (for example, a[] = {-1, 0, 5, 3, -9, 2}), does there always exists an index i ($0\le i\le N-1$) such that each partial sum $S_j = ...
2
votes
1answer
4k views

How to prove the matrix is totally unimodular

Is there any (theoretic) way I can prove the matrix is totally unimodular? I have tested it by Matlab and know it is TU, however I cannot prove it. ...
2
votes
3answers
775 views

Is there any methods to solve for integer solution of a quadratic equation like $ax^2 + bx + c = 0$

Is there any method to solve for integer solution of a quadratic equation like following: $$ax^2 + bx + c = 0$$ where $a, b, c \in \mathbb{Z}$ If not is it possible for the Special case: ? $$x^2 -x ...
2
votes
1answer
358 views

Maximizing the number of non-crossing lines between a number of points

Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross. Hoping for a polynomial time algorithm, I ...
2
votes
2answers
368 views

Prove or disprove a chessboard with diagonal corners removed, cannot be tiled with L shape pieces or size 2

I think this is impossible, but I don't know how to prove an integer solution doesn't exist for a given equation. Here's my approach: First, observations: The removed tile will be of the same color. ...
2
votes
1answer
886 views

Integer solutions to a hyperbola

Is there a way to find all integer solutions to a hyperbola equation? If it helps, I am specifically looking at "square" hyperbolas (i.e. of the form $\frac{x^2}{z} - \frac{y^2}{z}=1$), where z is an ...
2
votes
3answers
400 views

How to formulate Unique value constraint in Integer Programming?

Given the following integer programming formulation, how can I specify that the variables are unique and none of them has the same value as the other one. basically ...
2
votes
1answer
592 views

Unimodular matrix definition?

I'm a bit confused. Based on Wikipedia: In mathematics, a unimodular matrix M is a square integer matrix having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
2
votes
2answers
1k views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
2
votes
1answer
90 views

Prerequisite reading for Concrete Mathematics? [closed]

I'm a freshman computer science major who has just started reading Concrete Mathematics, mathematics for computer science. Is there any prerequisite reading or learning I should do before embarking on ...
2
votes
1answer
1k views

linear programming constraint for conditional

I having formulating the following (what should be fairly simple) ilp constraint. Basically let $p$ be a binary variable and $s$ be an integer that is greater than or equal to 0. The constraint is ...
2
votes
1answer
93 views

Help with Math software (macaulay 2)

I just started working with Macaulay 2 and need some help. I need to find the number of solutions of a system of equations. I am having difficulty imputing this into the software so please be specific ...