Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
1answer
14 views

Solution of the LP relaxation - always round to the nearest integer?

If an optimal solution to the LP relaxation of an IP is not integer, can we always get a feasible IP solution by rounding it to the nearest integer? Or can we generalize this process by saying, if we ...
1
vote
0answers
15 views

Is there any general algorithm to solve such a 3D cutting problem?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width ...
2
votes
1answer
50 views

On/off variables in MILPs with infinite bounds

I have an LP defined by $$A x = b$$ $$0 \leq x \leq U$$ and would like to extend it to an MILP through introduction of binary on/off variables $z$ such that $$z_i = 0 \implies x_i = 0.$$ This ...
0
votes
0answers
14 views

minimising multivariate quadratic function over integer variables

I have a quadratic function $x_1^2+x_2^2-(u_1x_1+u_2x_2)^2$ which I need to minimise over integer $x_1$ and $x_2$; also, the coefficients $u_1,u_2<1$. In other word, assuming coefficients ...
-1
votes
1answer
17 views

Linear Programming constraint equivalent of conditional

I would like to use the following conditional in my linear program: if(A == 1) then B = C + 1 A = binary, B and C are continuous. In the else case, any relation ...
0
votes
0answers
13 views

Binary variable and constraint help

Was trying to solve a Integer programming model that goes like this. A bread company is deciding whether to set up factories that cater to outlets. Each factory has a certain set up cost tagged to ...
0
votes
0answers
8 views

optimization of formulas involving binomial coefficients

I encountered such a problem. We need to find the min value and max value of $f(x,y)$. $x$ and $y$ are integers $\in[0,n]\times[0,n]$ and $(x,y)\neq (0,0)$ or $(n,n)$. $$ ...
1
vote
0answers
172 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters $\mathbf{x}$ $$\sum_{i} p_i \log( N + \sum_j x_j[B_j +(A_j-B_j)\delta_{ij} + min(A_j,B_j) ]) ...
1
vote
0answers
16 views

Linear Integer Optimzation Problem (scheduling problem)

Does any of you know how to get this done?
4
votes
1answer
46 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 ...
0
votes
1answer
56 views

convertion into integer linear program

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem) $$ maximise: ...
1
vote
1answer
6 views

How to think about minors of the rectangular matrix in the context of a system of Diophantine linear equations

My question is related to my previous question How to prove existence of solutions to the system of Diophantine linear equations. In particular, to the theorem which I've used to prove some subset of ...
1
vote
1answer
54 views

Can you generate math problems that are solveable?

If you take Linear Programming, it problems are formulated like this: You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. ...
1
vote
2answers
39 views

Fog of War Influence Map

I'm in the process of making an RTS game and I've ran into a problem I could use help with. I want to create a fog of war system that reveals an area around a unit that belongs to you like how it's ...
0
votes
1answer
16 views

Replacing a max constraint in a binary program

For $x \in \{0,1\}$, I want to express $x = 1 \Leftrightarrow \exists k: y_k = 2$ where $y_k \in \{0,1,2\}$, i.e. $x \leq 0.5\max_k\{y_k\}$ using binary decision variables but I can't figure out how ...
0
votes
1answer
22 views

Integer linear programming problem

There is an integer linear programming problem with this constraint: $$\left|X1 - X2\right|= 5\text{ or }10\text{ or }20$$ How it can be solved with adding auxiliary variable $y$? Main problem is ...
0
votes
1answer
40 views

Mixed Integer Linear Programming: Construction Rods

I have an interesting problem involving linear programming. The problem is the following, I have 4 different kinds of rods (rod sized found in the local market): 9m rod 11m rod 12m rod 15m rod ...
0
votes
0answers
29 views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
0
votes
1answer
52 views

Solution techniques for optimization problems

I am very new to solving such optimization problems. Following is the problem, I need to know the various methods (preferably advanced machine learning techniques) that I can use to solve this. ...
2
votes
2answers
55 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
74 views

What kind of algorithm might solve this type of optimization problem?

I am trading futures contracts in baskets at ratios that I compute by some method. Suppose there are $n$ contracts in a basket, and the ratio is given by $\mathbf{r}\in \mathbb{Z}^n$, so that the ...
0
votes
0answers
8 views

Number of satisfied constraints in unsolved ILP

I have ILP constraints as follow: $\forall l \in L_i \exists t \in T^l_i : \sum_j w_j(t) \geq r_i^l(t)$ For unsolved case, how can I compute the number satisfied $l$? Does it depend on the solver I ...
0
votes
0answers
25 views

A good enough solution for the 0-1 multiple knapsack problem

Can you please explain, or point to an easy explanation of a good enough solution to the 0-1 multiple knapsack problem? This is a single constraint problem so only one-dimensional weights are to be ...
-1
votes
4answers
59 views

Can I find solutions to $a^4 + a^2 + a = b^2 + b$, $a,b \in \mathbb{Z}$ and $ 1 < a < b$?

I was wondering if anyone could point me in the correct direction for either finding a solution to my problem or proving that it does not exist. $$a^4 + a^2 + a = b^2 + b \;\text{ for }\; a,b \in ...
0
votes
1answer
29 views

Wrong ILP solution with LPSolve (simple example)

I added the following example into LPSolve and found a strange issue. I don't want S1 and S2 to overlap within certain margins. ...
0
votes
1answer
79 views

Show both relaxations of boolean LP give equal lower bounds

Given the boolean LP: $$\text{Minimize}\;\; c^Tx$$ $$\text{Subject to}\;\; Ax \leq b$$ $$\hspace{57mm} x_i(1-x_i)=0\;\; i=1,...,n$$ Show that the LP relaxation: $$\text{Minimize}\;\; c^Tx$$ ...
0
votes
0answers
26 views

How is D.Knuth MMIX instruction MXOR useful for finite field multiplication?

Knuths TAOCP, Fascicle 1, exercise 37 (page 26) - http://mmix.cs.hm.edu/doc/fasc1.pdf: Explain how to use MXOR for arithmetic in a field of 256 elements; each element of the field should be ...
1
vote
0answers
26 views

How do you calculate Up and Down Penalties on a Branch and Bound algorithm of a MILP?

My notes really don't explain this clearly at all, so I have no idea what to do. If I have the following MILP: In which I've been told to solve it using: (a) Rule 1 (choose the variable with the ...
0
votes
0answers
9 views

Help on Binary Integer Programming

I am about to do a paper about distributing subjects to students with the constraints on: number of subjects that the student need, number of students whom these subjects will be distributed to, and ...
2
votes
0answers
23 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
0
votes
0answers
16 views

Linearization bounds on 0-1 quadratic problems

What are the best linearization methods for approximating the following constrained 0-1 Quadratic problem, where $Q \in \mathbb{R}^{n\times n}$ and $k$ is an integer $1\leq k \leq n$ $$ \max ...
0
votes
0answers
44 views

Solution of a linearly constrained quadratic programming problem

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
1
vote
1answer
24 views

Job scheduling to minimise squared completion times using mixed 0-1 quadratic program

I have come across an Optimization question as follows: There are $n$ jobs that have to be processed on a machine. The machine can process only one job at a time. The time taken to process job ...
3
votes
3answers
210 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 ...
2
votes
1answer
44 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
50 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
78 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
83 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
27 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
50 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
39 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
51 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.
11
votes
0answers
235 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 ...
0
votes
1answer
25 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
23 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
67 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 ...
1
vote
2answers
46 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
49 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 ...
1
vote
1answer
37 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
71 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 ...