Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

11
votes
0answers
271 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 ...
9
votes
5answers
5k 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
298 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
68 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
256 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
2answers
147 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
1answer
39 views

How to prove that this matrix is total unimodular

This matrix is total unimodular (tested by a computer program). ...
4
votes
1answer
49 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
412 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
1answer
485 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} ...
4
votes
3answers
102 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
87 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
267 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
255 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
5answers
61 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
85 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
302 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
113 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 ...
3
votes
2answers
87 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
78 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
1answer
374 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
457 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
368 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
91 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
649 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
184 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
0answers
21 views

Why calculating XOR of consecutive values can be simplified?

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, ...
3
votes
0answers
23 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
153 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 ...
2
votes
3answers
137 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
3answers
2k 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: ...
2
votes
2answers
153 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
3answers
168 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
309 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
326 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
706 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
298 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
477 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
1answer
58 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
72 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 ...
2
votes
2answers
74 views

Integer Linear Programming

Without using a computer, I have to solve the following integer linear programming:$$\min \quad x_1+x_2+x_3$$ $$\operatorname{sub} ...
2
votes
1answer
302 views

Minimize $\|Ax-b\|$ where $x$ is a binary vector

For a software project I'm involved on, I have a situation where I have a large vector that is the sum of some smaller vectors. I know all the possible small vectors, and I know that no two of them ...
2
votes
2answers
54 views

Can one simplify a $3$-term max function, where one term is comprised of subterms from other two?

Is the expression $\max(a + b, b + c, c + d)$ in its simplest from? Assuming $a,b,c,d$ are positive integers. What I've Tried: I've tried several approaches but they all end up as either: ...
2
votes
1answer
243 views

Solving a knapsack-type problem

I'd like a good way to solve an optimization problem I came across. It's a constrained knapsack problem: I want to find integers $$1=a_1\le a_2\le\cdots\le a_t$$ $$a_1+a_2+\cdots+a_t=N$$ with $t$ ...
2
votes
1answer
50 views

Integer programming: if a or b then a, b, and c

I'm writing a mixed integer programming (MIP) constraint where my $\color{blue}{\texttt{binary variables}}$ are $a, b,$ and $c$ to meet the following condition: $$ (a \lor b) \to (a \land b \land c)$$ ...
2
votes
1answer
53 views

Chocolatier sampler boxes problem: applying goal programming and mixed-integer programing to optimally compromise goals.

QUESTION: A boutique chocolatier is planning to make a number of sampler boxes, each containing $36$ chocolates. (Therefore the total number of chocolates should be divisible by $36$.) The ...
2
votes
1answer
51 views

Description of a constraint for a mixed integer program.

Suppose we have 100 items that are labelled from the set $P = \{A, B, C, D, E\}$. My constraints are as follows: I want to choose exactly seven items. The choice should have at least one item of ...
2
votes
1answer
43 views

Question about making a custom 'formula'

I am working on some program for myself, and I am stuck on one thing, which I am not sure how to make exactly, I do know how to calculate it manually on paper, but I don't know any kind of formula or ...
2
votes
1answer
76 views

Non 0-1 integer programming

Many interesting combinatorial problems - graph coloring, maximal matching, set cover, and knapsack among others - can be reformulated as integer linear programs. One thing that all of these ...