Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

-1
votes
1answer
128 views

Finding sum of all integral parts

Moderator Note: This is a question in a current contest. Given two numbers $M$ and $N$, Let $q_i$ be the integer part of $\frac{iN}{M}$. What is $$ \sum_{i=0}^{M-1} q_i? $$ The Sum is obviously ...
0
votes
1answer
57 views

Cutting plane in IP system

I am doing branch-and-bound for 5 decision binary variables. so Decision would be 0 and 1. and I found sub-problem node Q with optimal value 5.4 (0.3, 0.2, 1, 0.5, 0.1) my IP constraints are ...
1
vote
1answer
119 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 ...
0
votes
3answers
243 views

Binary Programming with nonlinear constraints

i have the following type of problem i'm interested to solve: Minimize the objective function: $f(x_1,\ldots, x_8) = \sum_{i=1}^8 a_i x_i$ with $a_i \in [0, \infty)$ and $x_i \in \{0,1\}$ and given ...
2
votes
1answer
330 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 ...
2
votes
0answers
96 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
1answer
194 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 ...
0
votes
1answer
194 views

Integrating the step-wise integer function 1/[x]

I'm trying to find the integral, respective to $x$, of a function that utilizes the step-wise integer (or floor) function. $$\displaystyle z = \int {1 \over [[x]*1.1^{[y]}]+1}$$ It's for modelling a ...
0
votes
1answer
99 views

integer programming formulation problem

Consider a problem with three variables: $u$, $\sigma_l$, and $\sigma_w$ where $\sigma_w > \sigma_l$. I want to represent the following relationship using integer programming. \begin{equation} u = ...
2
votes
3answers
151 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 ...
3
votes
1answer
83 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
228 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} ...
2
votes
1answer
170 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
1
vote
1answer
152 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
4
votes
0answers
142 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
1answer
64 views

$ A = x + y + z$, number of solutions in $Z$ if $x, y, z$ are bounded in intervals

For the equation $x + y = A$, it's easy, when you notice that when iterating over all possible $x$, the number of solutions for $y$ is $0$ at the beginning, then increases by $1$, then stays constant, ...
1
vote
0answers
88 views

Determining if data can be fit by a continuous piecewise integer-valued polynomial

This question concerns the sequence of integers which form the solution to a particular computational problem. See the bottom for the full formulation; basically, for some value n, $G(n)$ is the ...
1
vote
4answers
82 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 ...
2
votes
1answer
248 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
1
vote
1answer
77 views

Linear programming: expressing the fact that precisely $k$ variables are nonzero

Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero? I suspect this would already be enough to simulate ...
6
votes
5answers
2k 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 ...
0
votes
1answer
78 views

Converting loop to a closed form expression? [duplicate]

Possible Duplicate: How to convert this loop into a closed form expression? I have the following code in Python ...
2
votes
2answers
245 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. ...
0
votes
1answer
25 views

Finding the solutions of $ax+by\le D$

Given parameters $a,b,D$, all integers, I want to find all the integer solutions $(x,y)$ of $ax+by\le D$ Or at least a nice way to characterize them. Also, for a given $R$, it is actually enough for ...
2
votes
1answer
263 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 ...
0
votes
0answers
48 views

How to formulate or statment in integer programming

I need to formulate below statement in integer linear programming. if x+y=2 then (a+b<c or c+g<a) Can you help me please?
7
votes
2answers
263 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 ...
0
votes
1answer
99 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
145 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
186 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 ...
1
vote
1answer
118 views

For integers $a$ and $b \gt 0$, and $n^2$ a sum of two square integers, does this strategy find the largest integer $x | x^2 \lt n^2(a^2 + b^2)$?

Here is some background information on the problem I am trying to solve. I start with the following equation: $n^2(a^2 + b^2) = x^2 + y^2$, where $n, a, b, x, y \in \mathbb Z$, and $a \ge b \gt 0$, ...
1
vote
2answers
62 views

What's the relation between the non-convex sets and the hardness of ILP problems?

If some or all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. If understand ...
3
votes
0answers
102 views

Branch-and-Price algorithms for IP/MIP

I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
0
votes
2answers
188 views

What is the logic to calculate triangle-inequality-theorem

So I want to know is there any simple formula to get the result for the triangle-inequality-theorem I know what is the theorem but any formula rather than doing it the routine way of adding then ...
0
votes
0answers
173 views
0
votes
1answer
98 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
1
vote
1answer
383 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 ...
5
votes
2answers
135 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 ...
1
vote
0answers
71 views

Problem formulation for maximizing the number of smaller rectangle inside larger rectangle

I stumble upon a problem which i would like to pose it as "Optimization Problem". Given the dimension of larger and smaller rectangle, i would like to find the maximum number of smaller rectangle ...
1
vote
2answers
286 views

$\ell_0$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min:\|x\|_0$ subject to:$Ax=b$. $\|x\|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time has ...
1
vote
0answers
191 views

sum of maxima vs the maximum of the sum

Consider the following integer program $$ \begin{align} \max &\sum\nolimits_{i,j} U_i(j)\cdot x_{i,j}\\ \text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant c_j,& ...
1
vote
0answers
223 views

Book recommendation on Applied Integer Programming/Combinatorial Optimization/OR

Having some very basic and theoretical knowledge about these topics from my study, I'm looking for a book (or other good sources) that explains the stuff from a practical point of view. On the one ...
2
votes
1answer
193 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 ...
3
votes
2answers
71 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 ...
0
votes
1answer
64 views

Chaotic solutions to mixed integer linear problems

Is there a way to get the branch and bound algorithm to converge to a solution "close" to an initial value? One way I can think of, is to adding a "distance from initial value" term to the cost ...
0
votes
2answers
233 views

Minimising variance of the workload

A professor will assign research papers to his students as a partial fulfilment of the requirements of a graduate course. There are six students enrolled in the course and each student will be ...
-1
votes
1answer
167 views

How to express $y = x\ \mathrm{mod}\ 2$ as an ILP?

Using the signed modulo operation: $(x\ \mathrm{mod}\ 2) = \begin{cases} 0\ \mathrm{if}\ x\ \mathrm{is\ even} \\ 1\ \mathrm{if}\ x > 0\ \mathrm{and}\ x\ \mathrm{is\ odd} \\ -1\ \mathrm{if}\ x ...
3
votes
1answer
157 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 ...
1
vote
1answer
661 views

What are the algorithms for integer programming in which constraints are dependent?

What are some ways to deal with dependent constraints in integer programming? For example, suppose I want to maximize $x+3y+2z$ subject to (i) $x+y<=3$ and (ii) if $y+z>=2$ then $x+z<=6$. ...
0
votes
2answers
407 views

How many different Pairs are there?

Consider, F4(y) = the number of digits 4 in decimal representation of the positive integer y and F7(y)=the number of digits '7' in decimal representation of the positive integer y. For the given ...