Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

2
votes
1answer
37 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 ...
0
votes
1answer
14 views

matlab MINLP optimization with ga

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. There are additional constraints but ...
0
votes
1answer
21 views

integer linear programing in matlab with the symbolic toolbox

I am writing a program to optimize a set of generators. I have hourly data and but dont want to necessarily optimize the whole time series. For a similar problem in the past I used the symbolic ...
0
votes
1answer
74 views

A binary min-max optimization problem

I encountered a very special optimization problem for a practical application. We have a variable $$\mathbf{s}=(s_1,s_2,s_3, s_4)^T$$, where $s_i$ can only take $1$ or $-1$, and we also have a ...
0
votes
0answers
24 views

Solution existence on $ax + by = c$

I have to produce an program which resolve the following equation: $ax + by = c$ With the following condition: $a$, $b$ and $c$ are known positive integer. $x$ and $y$ are positive ...
0
votes
1answer
37 views

Which algorithms are commonly used to solve this kind of Binary Integer Programming problem?

I want to solve the problem of minimizing $$\mathbf{c}^T\mathbf{x}$$ subject to the condition that $$A\mathbf{x} = \mathbf{b}\text{,}$$ where $\mathbf{b},\mathbf{c}$ are given vectors in ...
1
vote
2answers
26 views

How to find smallest integer which is greater than N positive primes

I know this can't be computed exactly, but I just need a rough estimate. I know one can compute a rough estimate of the number of primes less than N using the famous formula: ...
1
vote
2answers
46 views

Escaping from a point in linear programming

Is there a trick for explaining the following constraint as a set of linear (in)equalities? $$ \sum_{i=1}^n|x_i-a_i|>0, $$ where $a_i$'s are real constants.
0
votes
1answer
21 views

One solution of a diophantine system

How to find one solution of $Ax = b$, where $A$ is a $(m, n)$ matrix and $x$ a vector of size $(n, 1)$. $A$, $x$ and $b$ are matrices of integers entries. How to check whether is a solution exists?
0
votes
1answer
18 views

Determine largest possible position for integers

I'm sorry if I'm not using the proper terminology but here's my question. When two numbers are multiplied, the position of the largest number can only be at the position of the sum of their operands. ...
1
vote
3answers
54 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 ...
0
votes
0answers
14 views

Replace BigM by SOS sets?

is there any way to get rid of Big-M when forming Mccormick envelopes by SOS sets ? eg x1 >= x2 - BigM*(1-w) x1 <= x2 x1 <= BigM*(w) where ...
1
vote
2answers
40 views

Combinations of fruits and their “nutrients”

As a computer scientist and not a mathematician, I know not some of the formal language to describe my problem, so I'll present it in a word problem form. Maybe someone can help me hone my search and ...
1
vote
1answer
44 views

If-Then Constraint: If X < 4 Then T = 4 -X

All the generic If-then constraints do not seem to be gaining me any insight into this. I would like to form a mixed-integer program with Lingo which can minimize cost given that a series of: When ...
0
votes
1answer
32 views

Finding a sequences so the image approximates integers

$x$ is fixed in $[0,1]$, $a_n,b_n,c_n$ are integers and not all of them are $0$ $y(a_n,b_n,c_n) = a_n x^3 + b_n x^2 + c_n x = Y_n$ Find an algorithm to go from $(a_n,b_n,c_n)$ to ...
1
vote
1answer
57 views

Existence of graphs when given the degrees of all vertices

My question is: How to decide whether a graph is exist when given the degree sequence of all vertices? This question can be easily reduced to the {0,1}-solutions of integer linear equation ...
1
vote
0answers
49 views

Mixed-Integer Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using Mixed-Integer Linear Programing ? I would like to get the variable $a$ in this description : $$ i = 1,\ldots,m ...
1
vote
0answers
18 views

Can this specific Linear Program constraint be expressed? [duplicate]

Thanks for your time. I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution. A company assembly and sells a ...
1
vote
1answer
16 views

Some operation like determinant

we have determinant operation that is like below: $ det(\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \\ \end{bmatrix}) $= $ (-1)^{1+1}a(ei-fh)+ ...
2
votes
0answers
50 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
9 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
18 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
8 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
55 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 ...
1
vote
0answers
28 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 ...
1
vote
1answer
29 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 ...
0
votes
0answers
27 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
0answers
39 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
49 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
49 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
22 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
85 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
67 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
87 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
42 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
66 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
46 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 ...
2
votes
4answers
303 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
26 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
40 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 ...
1
vote
2answers
310 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
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
47 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
35 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$? ...
0
votes
0answers
4 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 ...
3
votes
1answer
72 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 ...