Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
1answer
18 views

Solving an integer linear programming problem without a graph

I am new to linear prorgramming and so far I have been solving LP problems with the help of a graph solution. However, when there are more than 2 variables obviously I can't plot them on the graph. ...
0
votes
0answers
11 views

I want to find a maximum of a function by Maple. How to restrict the variables to be integers? [on hold]

For example, I want to find the maximum of $x^2+y^2$ with $0\le x,y\le 10$ in Maple. I can type $$maximize(x^2+y^2,x=0..10,y=0..10).$$ But if I restrict $x$ and $y$ to be both integers, then how can ...
2
votes
1answer
35 views

Chocolatier sampler boxes problem: applying goal programming and mixed-integer programing to optimally compromise goals.

QUESTION: A boutique chocolatier is planning to make a number of sampler boxes, each containing $36$ chocolates. (Therefore the total number of chocolates should be divisible by $36$.) The ...
2
votes
1answer
60 views

Help with Math software (macaulay 2)

I just started working with Macaulay 2 and need some help. I need to find the number of solutions of a system of equations. I am having difficulty imputing this into the software so please be specific ...
1
vote
0answers
15 views

Binary depending on the sign of another variable

I'm writing a mixed integer linear problem, where I have an indicator function in the objective function counting the instances of negative values of a decision variable. I thought of defining a ...
1
vote
0answers
15 views

Book recommendation on integer programming ? (in order to solve a set cover problem)

I'm trying to solve a set cover problem. To put it shortly, my problem is about covering a $N \times M$ grid, by using various rectangles which have associated cost depending on their shape and ...
1
vote
1answer
31 views

How do I convert a constraint with a product of two integer variables to a linear constraint?

I have a constraint of the form: $$\theta \leq a_1x_1 + a_2x_2 + a_3x_1x_2$$ where, $x_1$ and $x_2$ are integer variables with ranges $x_1 \in \{0, m\}$ and $x_2 \in \{0, n\}$. I would want to ...
0
votes
1answer
70 views

How to solve the coupled integer programming problem?

I have the following integer linear programming problem: $$\begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} && \sum_{k=1}^K\sum_{t=1}^Tx_{kt} \\ & \text{subject to} ...
0
votes
1answer
19 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
52 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
19 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
22 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
14 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
10 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
174 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
57 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
8 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
55 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
17 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
43 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
40 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
53 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
62 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
77 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
29 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
61 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
37 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
83 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
28 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
27 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
45 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
215 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
45 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
59 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
87 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
84 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
53 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
47 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.