Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
0answers
15 views

Integer linear programming - pythagorean theorem approximation

How would one approximate the pythagorean theorem (for cartesian coordinates) in ILP using a reasonable amount of variables and constraints? Basically, given points x1, y1 and x2, y2 $\in \mathbb{R}^...
1
vote
1answer
94 views

Efficient (time complexity) algorithm for Linear Programming problems

I have an inequality of the form: $$\sum_{i=1}^n a_i\cdot x_i \ge a_0$$ where $a_i\gt 0$ for all $i$. Subject to this and $x_i\ge 0$ for all $i$, I have to minimize the expression: $$\sum_{i=1}^n ...
0
votes
0answers
26 views

minimal number of sets of binary vectors

I have a set of binary vectors that I would like to group into a minimal number of sets. A set can be formed when it contains all combinations of elements that vary within that set. Example: for {...
0
votes
1answer
51 views

Minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k

For $k\in N, n-2\ge k\ge2$, and $n \in N, n\ge4$ minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k EDIT: Attempt to solve First I differentiated it partially w.r.t $k$ and ...
1
vote
0answers
52 views

Develop a model for determining the optimal production schedule in a manufacturing facility

I have to formulate (linearly) the following problem mathematically: What I tried: 1. Variables Let $x_{ijk} = 1$ if, in month k, product i should be made in production line j, where $i=...
1
vote
1answer
52 views

Is there any algorithm to find all the solutions of the following special linear Diophantine system?

Consider the following system. 1) $a_{11}x_1 + a_{21}x_2 + \cdots + a_{m1}x_m=d_1$ 2) $a_{12}x_1 + a_{22}x_2 + \cdots + a_{m2}x_m=d_2$ $\vdots$ n) $a_{1n}x_1 + a_{2n}x_2 + \cdots + a_{mn}x_m=d_n$ ...
0
votes
1answer
60 views

Packing three increasing integers into one

I have three integers representing positions on a board. Because all pieces are equal, the order does not matter, so it suffices to only consider increasing lists of three integers. However I am ...
0
votes
1answer
55 views

Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
0
votes
1answer
26 views

Octave false position

i'm try to write some code in octave based in false position method. So, here it is: And I get the follow error: "parse error near line 40 of file C:\Users\HP...falsa.m syntax error else" So, ...
1
vote
0answers
12 views

Maximizing iterations of finding circular successive differences

From a competition we had in comp sci: Given four integers, $a$, $b$, $c$, and $d$ take repeated absolute differences including $|a-d|$ until you reach all zeros. At each iteration, $a' \gets |b-a|...
4
votes
0answers
46 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 ...
1
vote
1answer
71 views

To show a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays.

I want to show that a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays. Where $r \in S$ is a ray of $S$ if $x \in S$ implies that $x+\mu r \in S$ for all $\mu \in R_{...
0
votes
1answer
40 views

How to solve mixed-integer problem?

I don't know how to solve this equation, $$\left\lceil\frac{x-A}{B}\right\rceil C + D x < E, \quad x\in \mathbb{Z}$$ In this equation, only $x$ is unknown and $x$ is integer, but $A,B,C,D,E$ are ...
2
votes
0answers
28 views

Discrete Optimization Problem (VRP)

Consider the following setting : We have two pickup nodes (a) and (b)and two delivery nodes (c) and (d). At each pickup node, there are entities to be picked up and delivered by cars (n cars) to ...
1
vote
1answer
35 views

Are there combinatorial problems that admit closed form solution? [closed]

I was wondering if there's some classes of combinatorial problems (specifically assignment problems) something like maximize: $$ f(\vec{x}) = \sum_{i,j} x_{i}x_{j}2^{i+j}, \;\; x_i \in {0,1} \;\;\...
0
votes
2answers
30 views

Writing conditional logic using mathematics forumla

I'm working on an application which has a specific function which receives 2 ints: x and y. If y > x then I would like the function to return y otherwise return x - y. Just a few examples: f(10, 12)...
1
vote
2answers
55 views

Boolean equation

$$\text{Solve for}\space{x, y}$$ $${a_1, a_2, a_3, a_4, b_1, b_2} \; \text{ - variables}$$ $$\left\{ \begin{aligned} {a_1}\&x \oplus {a_2}\&y &= {b_1} \\ {a_3}\&x \oplus {a_4}\&y ...
2
votes
0answers
34 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
-2
votes
2answers
81 views

Integer programming [closed]

Can anyone help me to find the right solution? How can integer programming be used to ensure that X takes on values 1,3, 5 or any even number less than 100? In practice we have a integer ...
0
votes
1answer
40 views

For any integer $n$ find $x<n$, and $y<n$ to minimize the natural number $z=xy-n$

I need to develop an algorithm for finding the optimal dimensions for setting a set of symbols on a grid (for a typesetting library I'm writing). I need to minimize the number of cells in my grid ...
0
votes
1answer
34 views

Modeling integers in NLP

I was wondering why it is not OK to model binary (integer) variables of an optimization problem, in the following form x(x-1) = 0 What are the consequences for ...
0
votes
0answers
29 views

Approximate ratio with a small fraction so that numerator multiplied by denominator give enough rectangular area?

I would like to layout given number of objects (like plots) into rectangular area (like computer operating system window on screen). I would like to calculate the width and height of the window (in ...
1
vote
1answer
62 views

Set up an integer programming problem so that all variables in the solution are different [closed]

I have a relatively simple minimisation problem. I have to minimise a linear function with many variables (more than 20), and I would like all the solutions to be different and in set $ x \in \{1,...,...
0
votes
0answers
31 views

Converting a linear-fractional program with an integer constraint to a linear program

Is it possible to convert the following linear-fractional program to a linear program ? $$ \max_x \frac{v\cdot x}{z \cdot x}\\s.t \\x_i \in \{0,1\}\\ \\ \sum_i x_i = k$$ where $v \in R^{d}$, $z \in R^...
0
votes
0answers
14 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
3
votes
1answer
44 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 ...
1
vote
1answer
60 views

What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically ...
2
votes
1answer
45 views

Solving integer programming problem using the graphical method

I have an integer programming problem I need to solve using the graphical method. Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ ...
3
votes
1answer
118 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 $...
0
votes
0answers
15 views

Reference Request For Hermite normal form of non full row rank matrix

Could someone recommend me some references which discuss the problem of the reduction of a matrix which is not full row rank into its Hermite normal form?
0
votes
0answers
39 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
1
vote
0answers
31 views

How to interpret this integer program

I'm having problem understanding the min weight st-cut integer programming in this wiki page: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem In the min-cut dual part, it has $$d_{ij}-p_i+p_i ...
0
votes
1answer
156 views

Normalized objective function in optimization problem

I have fairly standard linear optimization model with two objectives \begin{align*} \text{max}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 + 0x_2 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 &...
0
votes
0answers
101 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...
1
vote
1answer
69 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
0
votes
0answers
33 views

Mixed-integer (Linear) Programming (MILP) standard/canonical form

Is there a standard or canonical form for mixed-integer (linear) programming problems? For linear programms the standard form is sometimes given by: $$ \max_{\boldsymbol x} \boldsymbol c^T \boldsymbol ...
0
votes
0answers
23 views

All facets' coefficients contain only integers -1,0,1

Suppose a polytope $C\subset \mathbb R^{kl}$ is the $l$-product of $k-1$-simplex with extreme points containing coordinates $0$ or $1$ in each coordinate. A linear transformation is given by $L:\...
0
votes
1answer
26 views

integer valued outer normal vectors

Suppose a bounded polyhedra $C$ is given by $$x\in \mathbb R^n: Ax\leq b$$ The matrix $A\in\mathbb R^{m\times n}$ contains only elements from $\{-1,0,1\}$, which implies the outer normal vectors of ...
0
votes
2answers
43 views

Polynomial time solvable cases of the knapsack problem.

Is there some restricted version of the knapsack problem, which is not $Np$-complete and there is a polynomial time algorithm? In my cases the weights are all power of $2$, so $(1, 2, 4, 8, 16, \...
1
vote
3answers
286 views

What are common Mathematical Programming Languages out there?

I've seen the term used Mathematical Programming to describe a superset of: Linear programming Quadratic programming Nonlinear programming Mixed-integer programming Mixed-integer nonlinear ...
1
vote
1answer
76 views

MILP optimization constraint formulation

I'm trying to find a sensible way to add constraint for my optimization problem. Lets assume we have binary decision variables $x_i\in\{0,1\}$ and two constraints \begin{align*} \sum\limits_{i=1}^n ...
1
vote
0answers
40 views

Lenstra's integer programming algorithm: Finding a lattice point “near the center”

Preliminaries: As part of Lenstra's algorithm for integer programming (see here, page 4) we compute a linear transformation $\tau$ and a point $z \in \mathbb{R}^n$ which meet certain conditions (step ...
0
votes
1answer
79 views

Can the “goat cabbage wolf” problem be solved using integer programming?

Question: Can you solve the "goat cabbage wolf" problem using integer programming. If so could I get an outline of the solution or a reference to one?
0
votes
2answers
56 views

What method will work for this linear programming problem?

I just started studying linear programming and I have limited resources with which to work. I have to work on a number of exercises but the notes I have do not help much so I have to look online for ...
0
votes
1answer
58 views

Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
0
votes
1answer
20 views

Find the global/local minima of a quadratic function over the set of integer?

Sorry for my poor English, I'm trying to find the global and local minima of a quadratic function: $x^2 - 3x$, with $x \in Z $. Here is my solution: It is straightforward to find the global minima ...
0
votes
0answers
21 views

Multiple Choice Integer Program Special Ordered Set Naming

I have been given a problem, for which I have a hard time to find literature, since I'm unsure about the right name of the problem. The problem is defined as: We have given $k$ sets and we need to ...
1
vote
0answers
89 views

Shadow prices in assignment problems (and their relationship to Lagrange multipliers of LP-relaxation)

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given ...
1
vote
1answer
43 views

Binary variable in a constraint

I have the following optimization problem: Model I: $$f(x,y) \\ s.t., \\ y\leq x+M(1-V)\\ y \leq MV \\ x \geq 0, y \geq 0$$ where x and y are continuous variables whereas V is a binary variable. M ...
0
votes
1answer
47 views

How to formulate LP for shortest path problems?

I'm trying to understand how LP formulaton for shortest path problem. However I'm having trouble understanding constrains. Why this formulation work? http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf I'...