Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
0answers
31 views

How to find nonnegative solutions of a linear system?

I have a $M$ equation and $N$ variables like this : $ \begin{bmatrix} 3 & 0 & 1 & 0 & -1 & -3 & 2\\ 1 & 2 & 0 & 4 & 0 & 0 & -1\\ 1 & 1 & 0 ...
0
votes
0answers
7 views

In the problem below, what is the right mix of drugs to maximize the expected revenue without exceeding R&D resources?

This is not a homework question. It's a question for a class I have yet to take that my friend gave me. I haven't been able to figure it out. Help is appreciated because it's driving me crazy. A ...
2
votes
1answer
306 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 ...
0
votes
0answers
8 views

Favorable probability(part 2)

After condition in Favorable probability . i should make an program in Python. I started in the next way: from random import randint import math MembersInBand = 50 ArrayOfMembers = [] for i in ...
0
votes
0answers
13 views

Why in the Uncapacitated Facility Location problem does each client not order all their goods from one location?

Here is the problem: A set of potential depot locations N = {1, . . . , n} has been identified. A set of clients M = {1, . . . , m} is known, each of which buys products that could be delivered from ...
0
votes
0answers
7 views

Ways to deal with Boolean constraint in optimization

For the optimization of $\text{min}_\alpha Q(\alpha)$, such that $\alpha_i \in \{0,1\}$, what will be popular way to deal with the Boolean constraint? Is there any methods to approximate the Boolean ...
2
votes
0answers
48 views

Algorithm to reduce expressions to canonical form

I'm writing a small computer algebra system that only knows rational numbers and all expressions that you can get from them by using basic arithmetic operations and powers. So the expressions are ...
0
votes
1answer
246 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
26 views

fill up a square with rectanagles

I have a square 46*46, I want to fill this up with three types of rectangles of size 29*20, 21*5, 10*4 such that the free space can be minimized? any rectangles can't be overlapped and they can be ...
1
vote
1answer
44 views

Integer Optimization

I have an integer optimization problem that I've been pondering for the last several days. Here's an abbreviated version: I have several wav song files with variable sizes (601201 kilobytes for ...
2
votes
2answers
259 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
28 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
1
vote
0answers
14 views

Find relationships between events

I have a set of Events $(E_i)_i$ which have a probability $(P_i)_i$. I am able to write each event as a sum of distinct events that form a partition of the space. My goal is to find all the ...
2
votes
4answers
287 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; ...
0
votes
0answers
16 views

Devising objective function for integer linear programming

I am working to devise a objective function for a integer linear programming model. The goal is to determine the copy number of two genes as well as if a gene conversion event has happened (where one ...
0
votes
1answer
89 views

Formulating a bilinear optimization problem as an integer linear program

In my work, I came across the following problem: Given a similarity matrix D, where $d_{i,j} \in \Re$ represents the similarity between objects $i$ and $j$, I would like to select $k$ objects, for $k ...
0
votes
0answers
31 views

Finding the optimal solution to an ILP, when feasibility is not ultimately required

I have the following problem: I would like to solve an ILP with binary variables, i.e. I have a set of possible items, each having properties like "size" "weight" "value" "age" and so on, in total, ...
1
vote
2answers
48 views

$a^2-b^2 = k$, $ab = l$ for fixed integer $k,l$ when $a,b$ are both integers

Let us fix integers $k,l$. Let all numbers be integers. Now we want integer $a,b$ to satisfy: $$a^2-b^2 = k, \,\,\,2ab = l.$$ We want to maximize the number of possible $(a,b)$. In order to do ...
0
votes
1answer
47 views

How to minimize the square of $\sum b_i x_i$ where each $b_i$ can be either $0$ or $1$?

Would you please help me solve the following problem where $b_{ij}$ is my decision variable that must be determined and all other parameters are known. $$\min \left(\sum_{i=1}^n b_i x_i\right)^2$$ ...
0
votes
1answer
30 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
2answers
21 views

Determine page number for question based on count of questions and number of questions per page

I'm trying to build a simple quiz, and I want to split up the questions into pages. However, the number of questions and pages can change based on a few parameters, most important is a variable number ...
1
vote
2answers
72 views

Free solvers in C/C++ for convex integer programming

I need to solve the following integer program: $\text{minimize } \sum_{i=1}^n(a_{i0} x_i + \sum_{k=1}^3 a_{ik}w_i^k + \sum_{j=1}^m d_{ij}y_{ij})$ $\text{subject to}$ $$ \sum_{i=1}^n y_{ij}=1, \quad ...
2
votes
1answer
39 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 ...
1
vote
0answers
65 views

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
0
votes
1answer
55 views

Shortest path problem: dual formulation and proof of total unimodularity

The IP formulation of the shortest path problem looks as follows: \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
63 views

Minimize the following function with integer values with the given constraint. [closed]

$$f(b_1,b_2,\ldots,b_m)=(b_1)^2+(b_2)^2+\cdots+(b_m)^2$$ such that $$ b_1+b_2+\cdots+b_m=l$$ m is fixed and all values are positive integers including zero. We want to minimize this function with ...
0
votes
1answer
39 views

Almost linear programming problem

I have a problem that is almost the typical in linear programming, but not quite. All variables take real non-negative values. Certain simple linear inequalities and equalities should hold. But what ...
0
votes
1answer
40 views

Disjunction of conjunction in linear programming

I'm trying to get my model working with less variable/constraints possible. I want the binary variable $R$ to store the result of this Boolean expression: R = (a1 and b1) or (a2 and b2) or (a3 and ...
1
vote
2answers
288 views

Optimization problem: Maximize the sum of minimum.

Given positive integers $L$ and a set of non-negative integers $N$. Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$ with $c \in \{1, 2,\dots ...
0
votes
0answers
25 views

Finding integer vectors in the column space of a matrix

Consider a given set $S \subset Z$. $S$ is a finite set. Matrix $A \in S^{N \times M}$ is also given. Does there exist an algorithm to find all the vectors belonging to the space Col$(A)\cap S^N$ ...
6
votes
1answer
36 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 ...
0
votes
1answer
15 views

Global consistency of constraints in a MIP program

How does a Mixed Integer Programming (MIP) solver ensure global consistency of constraints while adding an additional constraint (during branch and bound). A naive method would be to add the ...
-1
votes
1answer
142 views

Finding sum of all integral parts

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 can be calculated in $O(M)$. Can this be done in less time, ...
0
votes
0answers
22 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
33 views

Good MIP formulation of a timetabling problem

I am trying to formulate a university timetabling problem as a mixed-integer program. The choice variables are binary variables of the form $x(c,s,r)$ which is $1$ if a class of course $c$ is held in ...
0
votes
0answers
32 views

Finding the largest $3^k$ number less than the natural number

Given the natural number $N$ in binary representation (computer memory). How to obtain the representation of the $N\rightarrow\sum^{M}_{k=0}(a_k\cdot(3^k+1))$ form or, at least, how to find the $M$? ...
1
vote
1answer
145 views

Integer linear programming, energy constrained max-flow problem, column generation

We have graph $(V,A)$, $V$ is teh set of nodes, $A$ is the set of arcs. There is a source node $s \in V$ and a sink $t \in V$. Each node $i$ has a battery with capacity $E_i$. Sending flow on arc ...
0
votes
0answers
2 views

Multiplying separately the different units,(other multiplication methods)

Is there any technique that performs multiplications taking into account the units separately? For example when you have to multiply 15*13 how can you process the tens separately? In general are there ...
1
vote
0answers
37 views

Prove this statement about inequalities

Can someone help to prove this. For $n$ and $\{a_{11},\dots,a_{nn}\}$, if we know that $a_{ij}$ is either $0$ or $1$ or $-1$, and further assume that the following inequality system on $\{b_n|b_n\in ...
0
votes
1answer
63 views

Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?

Consider the assignment problem: $$ Z = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} $$ s.t. $$ \sum_i x_{ij} = 1 \quad\forall j $$ $$ a \leq \sum_j x_{ij} \leq b \quad\forall i $$ $$ ...
1
vote
2answers
464 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 ...
3
votes
1answer
39 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 ...
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 ...
2
votes
1answer
28 views

How is the upper bound of a minimisation IP determined during branch-and-bound?

When using the branch-and-bound algorithm to solve an Integer Programming (IP) problem, the entire enumeration tree doesn't need to be evaluated and that's where the speed-up is achieved. Suppose the ...
1
vote
0answers
45 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
1
vote
1answer
156 views

Ordered pair of positive integers

One holiday, I gave each of my 3 grandsons x coins and each of my 4 granddaughters y coins. The total number of coins that I gave to my grandchildren will allow for only one ordered pair of positive ...
1
vote
2answers
82 views

Why do Integer Relation Algorithms (e.g. PSLQ) not solve the subset sum problem?

I'm trying to understand what mistake I'm making or what incorrect information I fail to recognize as such. The subset sum problem (given distinct $a_i$ and $A$, does any subset of ${ a_i }$ sum to ...
1
vote
0answers
41 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
1
vote
1answer
53 views

Why optimization problems cannot be solved by simple derivative?

Let $f(\cdot)$ be a linear function. $f:\mathbb{R}^n\rightarrow\mathbb{R}$ $\;\quad\;\mathbf{x}\;\rightarrow f(\mathbf{x})$. Let $\mathbf{A}$ be a matrix in $\mathbb{R}^{m\times ...
2
votes
0answers
32 views

Find bounded integers $x, y$ minimizing $| t - x * y |$

How do I find the integers $x$ and $y$ minimizing $| t - x \cdot y |$ with $1 \leq x < N$ and $1 \leq y < M$ ? Background: A clock signal is divided by two hardware prescalers (with a limited ...