## mathematical optimization – NMinimize: How to avoid solutions that do not satisfy constraints within a certain tolerance?

Here’s how you can do it by adding some slack into the constraints and punishing slack in the objective:

SeedRandom(1);

(* the function you're trying to minimize *)
objective = ((e*(1 - Sqrt((g - e)^2 + (f - h)^2)) + (g - e)*(1 -
Sqrt(f^2 + e^2))) + (h*(1 -
Sqrt((g - e)^2 + (f - h)^2)) + (f - h)*(1 -
Sqrt(g^2 + h^2))))/((g + f)*
Max(1 - Sqrt((g - e)^2 + (f - h)^2), 1 - Sqrt(g^2 + h^2)));

(* these are the hard constraints *)
constraints = {
0 <= e <= 1,
0 <= f <= 1,
e^2 + f^2 == 1,
e <= g <= 1,
0 <= h <= f,
Sqrt((g - e)^2 + (f - h)^2) <= 1,
g^2 + h^2 <= 1
};

(* these constraints are softer and allow for a bit of slack *)
slackedConstraints = {
0 - se <= e <= 1 + se,
0 - sf <= f <= 1 - sf,
-sef1 < e^2 + f^2 - 1 < sef1,
e <= g <= 1,
0 - sh <= h <= f + sh,
Sqrt((g - e)^2 + (f - h)^2) <= 1,
g^2 + h^2 - 1 <= 0
};
variables = {e, f, g, h};
slackterms = {se, sf, sh, sef1};

(* solve it and harshly punish too much total squared slack *)
sol = Last(
NMinimize({objective + 10^10*Total(slackterms^2),
slackedConstraints}, Join(variables, slackterms)))

(* RESULT:
{e -> 0.25283, f -> 0.967511, g -> 0.944242, h -> 0.329154,
se -> 4.51664*10^-14, sf -> -2.52757*10^-13, sh -> 3.93093*10^-14,
sef1 -> 1.92914*10^-7} *)

objective /. sol
(* result: 0.304607 *)

(* Substitute back into the hard constraints to check if any violated *)
constraints /. sol
(* {True, True, False, True, True, True, True} *)

(* hard constraint #3 is violated, but only by a tiny amount: *)
e^2 + f^2 /. sol
(* result 1. *)

## mathematical optimization – Time computation problems with “Maximize” expression

I just started to use Mathematica a few weeks ago. I am afraid there is something that does not work on my laptop because, for the following simple command, it takes too much time. Do you know if there is a mistake in this command syntax? Thank you in advance for your help.

Maximize({(g/e)*Sqrt(((g – e)^2 + (f – h)^2)), 0 <= e <= 1,
0 <= f <= 1, e^2 + f^2 == 1, 0 <= g <= e, 0 <= h <= f}, {e, f, g, h})

## linear algebra – MaxMin of Sum of Fractionals Optimization Problem

Let $$mathbf{x}^{(1)},ldots,mathbf{x}^{(L)}$$ be $$L$$ vectors of $$N$$ variables. Then, how can I solve the following optimization problem?
begin{align} max_{mathbf{x}^{(1)},ldots,mathbf{x}^{(L)}}&min_nquad sum_{ell} frac{x_n^{(ell)}}{alpha+sum_{m}beta_m^{(n,ell)}x_m^{(ell)}}\ text{subject to}&quadsum_{ell=1}mathbf{A}^{(ell)}mathbf{x}^{(ell)}leq mathbf{1}. end{align}

## postgresql – Avoid duplicate WHERE clause on both sides of a LEFT JOIN, without changing semantics or impairing query optimization

I have a table recording the results of a web crawl. (Table
definition at the end of this question.) The relevant part of the data
stored in it looks like this:

experiment_id | url_id | redirect_num | full_url_id | has_blockpage_regex | blockpage_reason_id
---------------+--------+--------------+-------------+---------------------+---------------------
16 |   1312 |            0 |        1312 |                   f |
16 |   1312 |            1 |        2311 |                   f |
16 |   1312 |            2 |        2312 |                   f |
16 |   1312 |            3 |        2313 |                   f |
43 |   1320 |            0 |        1320 |                   f |
43 |   1320 |            2 |        2312 |                   f |
43 |   1320 |            1 |        2317 |                   t |                   1
43 |   1320 |            3 |        2318 |                   f |

For each (experiment_id, url_id) pair, from a small set of experiment IDs, I want to query the full_url_id associated with the largest value of redirect_num, and the blockpage_reason_id associated with the smallest value of redirect_num for which has_blockpage_regex is true. (If there is no row satisfying the latter condition, blockpage_reason_id should come out null.) For the data above, the desired results would be like this:

experiment_id | url_id | full_url_id | blockpage_reason_id
---------------+--------+-------------+---------------------
16 |   1312 |        2313 |
43 |   1320 |        2318 |                   1

I have a query that does what I want, but it’s extremely slow, involving multiple full table scans.
(EXPLAIN ANALYZE dump also at the end of the question.)

select x.experiment_id, x.url_id, x.full_url_id, y.blockpage_reason_id from (
select bm.experiment_id, bm.url_id, b.full_url_id
from blockpage b
join (select experiment_id, url_id, max(redirect_num) as redirect_num
from blockpage
group by experiment_id, url_id) bm
on b.experiment_id = bm.experiment_id
and b.url_id = bm.url_id
and b.redirect_num = bm.redirect_num
) x left join (
select bm.experiment_id, bm.url_id,
b.has_blockpage_regex, b.blockpage_reason_id
from blockpage b
join (select experiment_id, url_id, max(redirect_num) as redirect_num
from blockpage
where has_blockpage_regex
group by experiment_id, url_id) bm
on b.experiment_id = bm.experiment_id
and b.url_id = bm.url_id
and b.redirect_num = bm.redirect_num
) y on x.experiment_id = y.experiment_id
and x.url_id = y.url_id
where x.experiment_id in (16,43);

I can make it work efficiently by duplicating the WHERE clause at the very end into the subselects on both sides of the LEFT JOIN:

select x.experiment_id, x.url_id, x.full_url_id, y.blockpage_reason_id from (
select bm.experiment_id, bm.url_id, b.full_url_id
from blockpage b
join (select experiment_id, url_id, max(redirect_num) as redirect_num
from blockpage
group by experiment_id, url_id) bm
on b.experiment_id = bm.experiment_id
and b.url_id = bm.url_id
and b.redirect_num = bm.redirect_num
where bm.experiment_id in (16,43)         -- DUPLICATED
) x left join (
select bm.experiment_id, bm.url_id,
b.has_blockpage_regex, b.blockpage_reason_id
from blockpage b
join (select experiment_id, url_id, max(redirect_num) as redirect_num
from blockpage
where has_blockpage_regex
group by experiment_id, url_id) bm
on b.experiment_id = bm.experiment_id
and b.url_id = bm.url_id
and b.redirect_num = bm.redirect_num
where bm.experiment_id in (16,43)         -- DUPLICATED
) y on x.experiment_id = y.experiment_id
and x.url_id = y.url_id;

But this will not work in practice, because the query (without the WHERE) is going to be used as a view definition, and people will select with WHEREs from the view, which is equivalent to applying a single WHERE to the outermost SELECT.

So my question is, how do I rewrite this query so that WHEREs on the outermost SELECT will be executed as efficiently as they are if I push them inside the LEFT JOIN manually? Change it as much as you want, as long as it still produces the same results as the example at the top.

Database is Postgres 12.2.

### EXPLAIN ANALYZE for the original query:

Nested Loop Left Join  (cost=1315730.90..3856617.09 rows=20 width=16) (actual time=36112.365..55406.053 rows=501 loops=1)
Output: blockpage.experiment_id, blockpage.url_id, b.full_url_id, b_1.blockpage_reason_id
Join Filter: ((blockpage.experiment_id = blockpage_1.experiment_id) AND (blockpage.url_id = blockpage_1.url_id))
Rows Removed by Join Filter: 220714047
->  Nested Loop  (cost=1.14..88505.96 rows=20 width=12) (actual time=466.302..480.840 rows=501 loops=1)
Output: b.full_url_id, blockpage.experiment_id, blockpage.url_id
->  GroupAggregate  (cost=0.57..15442.73 rows=8543 width=12) (actual time=466.267..470.146 rows=501 loops=1)
Output: blockpage.experiment_id, blockpage.url_id, max(blockpage.redirect_num)
Group Key: blockpage.experiment_id, blockpage.url_id
->  Index Only Scan using blockpage_experiment_id_url_id_redirect_num_blockpage_reason__ on iclab.blockpage  (cost=0.57..15293.19 rows=8547 width=12) (actual time=0.048..1.662 rows=803 loops=1)
Output: blockpage.experiment_id, blockpage.url_id, blockpage.full_url_id, blockpage.redirect_num, blockpage.html_tag_id
Index Cond: (blockpage.experiment_id = ANY ('{16,43}'::integer()))
Heap Fetches: 803
->  Index Only Scan using blockpage_experiment_id_url_id_redirect_num_blockpage_reason__ on iclab.blockpage b  (cost=0.57..8.53 rows=1 width=16) (actual time=0.016..0.018 rows=1 loops=501)
Output: b.experiment_id, b.url_id, b.full_url_id, b.redirect_num, b.html_tag_id
Index Cond: ((b.experiment_id = blockpage.experiment_id) AND (b.url_id = blockpage.url_id) AND (b.redirect_num = (max(blockpage.redirect_num))))
Heap Fetches: 501
->  Materialize  (cost=1315729.77..3767691.70 rows=1207 width=12) (actual time=7.067..89.428 rows=440547 loops=501)
Output: b_1.blockpage_reason_id, blockpage_1.experiment_id, blockpage_1.url_id
->  Hash Join  (cost=1315729.77..3767685.66 rows=1207 width=12) (actual time=3540.653..35478.463 rows=440547 loops=1)
Output: b_1.blockpage_reason_id, blockpage_1.experiment_id, blockpage_1.url_id
Inner Unique: true
Hash Cond: ((b_1.experiment_id = blockpage_1.experiment_id) AND (b_1.url_id = blockpage_1.url_id) AND (b_1.redirect_num = (max(blockpage_1.redirect_num))))
->  Seq Scan on iclab.blockpage b_1  (cost=0.00..1757677.88 rows=88162288 width=16) (actual time=0.012..9535.931 rows=88164599 loops=1)
Output: b_1.id, b_1.url_id, b_1.full_url_id, b_1.experiment_id, b_1.blockpage_reason_id, b_1.html_tag_id, b_1.body_len, b_1.blockpage_diff, b_1.has_blockpage_regex, b_1.http_status, b_1.redirect_num, b_1.response_failure
->  Hash  (cost=1306621.31..1306621.31 rows=520483 width=12) (actual time=3538.005..3538.005 rows=440547 loops=1)
Output: blockpage_1.experiment_id, blockpage_1.url_id, (max(blockpage_1.redirect_num))
Buckets: 524288  Batches: 1  Memory Usage: 23026kB
->  Finalize HashAggregate  (cost=1296211.65..1301416.48 rows=520483 width=12) (actual time=3325.126..3427.920 rows=440547 loops=1)
Output: blockpage_1.experiment_id, blockpage_1.url_id, max(blockpage_1.redirect_num)
Group Key: blockpage_1.experiment_id, blockpage_1.url_id
->  Gather  (cost=1246069.28..1292868.83 rows=445710 width=12) (actual time=3029.657..3143.505 rows=441870 loops=1)
Output: blockpage_1.experiment_id, blockpage_1.url_id, (PARTIAL max(blockpage_1.redirect_num))
Workers Planned: 2
Workers Launched: 2
JIT for worker 0:
Functions: 9
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 1.136 ms, Inlining 51.049 ms, Optimization 73.089 ms, Emission 39.722 ms, Total 164.995 ms
JIT for worker 1:
Functions: 9
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 2.075 ms, Inlining 72.675 ms, Optimization 70.854 ms, Emission 39.490 ms, Total 185.093 ms
->  Partial HashAggregate  (cost=1245069.28..1247297.83 rows=222855 width=12) (actual time=3004.908..3047.674 rows=147290 loops=3)
Output: blockpage_1.experiment_id, blockpage_1.url_id, PARTIAL max(blockpage_1.redirect_num)
Group Key: blockpage_1.experiment_id, blockpage_1.url_id
Worker 0: actual time=2999.661..3042.358 rows=137916 loops=1
Worker 1: actual time=2985.698..3026.195 rows=144767 loops=1
->  Parallel Seq Scan on iclab.blockpage blockpage_1  (cost=0.00..1243397.87 rows=222855 width=12) (actual time=115.822..2924.688 rows=177783 loops=3)
Output: blockpage_1.id, blockpage_1.url_id, blockpage_1.full_url_id, blockpage_1.experiment_id, blockpage_1.blockpage_reason_id, blockpage_1.html_tag_id, blockpage_1.body_len, blockpage_1.blockpage_diff, blockpage_1.has_blockpage_regex, blockpage_1.http_status, blockpage_1.redirect_num, blockpage_1.response_failure
Filter: blockpage_1.has_blockpage_regex
Rows Removed by Filter: 29210417
Worker 0: actual time=164.165..2922.106 rows=165851 loops=1
Worker 1: actual time=183.286..2912.232 rows=173763 loops=1
Planning Time: 1.013 ms
JIT:
Functions: 60
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 11.387 ms, Inlining 132.486 ms, Optimization 415.860 ms, Emission 264.166 ms, Total 823.898 ms
Execution Time: 55458.769 ms

### EXPLAIN ANALYZE for the query with duplicate WHEREs:

Merge Left Join  (cost=2.27..104247.90 rows=20 width=16) (actual time=40.938..44.044 rows=501 loops=1)
Output: blockpage.experiment_id, blockpage.url_id, b.full_url_id, b_1.blockpage_reason_id
Merge Cond: ((blockpage.experiment_id = blockpage_1.experiment_id) AND (blockpage.url_id = blockpage_1.url_id))
->  Nested Loop  (cost=1.14..88505.96 rows=20 width=12) (actual time=40.603..43.615 rows=501 loops=1)
Output: b.full_url_id, blockpage.experiment_id, blockpage.url_id
->  GroupAggregate  (cost=0.57..15442.73 rows=8543 width=12) (actual time=40.561..41.298 rows=501 loops=1)
Output: blockpage.experiment_id, blockpage.url_id, max(blockpage.redirect_num)
Group Key: blockpage.experiment_id, blockpage.url_id
->  Index Only Scan using blockpage_experiment_id_url_id_redirect_num_blockpage_reason__ on iclab.blockpage  (cost=0.57..15293.19 rows=8547 width=12) (actual time=0.045..0.432 rows=803 loops=1)
Output: blockpage.experiment_id, blockpage.url_id, blockpage.full_url_id, blockpage.redirect_num, blockpage.html_tag_id
Index Cond: (blockpage.experiment_id = ANY ('{16,43}'::integer()))
Heap Fetches: 803
->  Index Only Scan using blockpage_experiment_id_url_id_redirect_num_blockpage_reason__ on iclab.blockpage b  (cost=0.57..8.53 rows=1 width=16) (actual time=0.004..0.004 rows=1 loops=501)
Output: b.experiment_id, b.url_id, b.full_url_id, b.redirect_num, b.html_tag_id
Index Cond: ((b.experiment_id = blockpage.experiment_id) AND (b.url_id = blockpage.url_id) AND (b.redirect_num = (max(blockpage.redirect_num))))
Heap Fetches: 501
->  Materialize  (cost=1.14..15741.83 rows=1 width=12) (actual time=0.329..0.329 rows=0 loops=1)
Output: b_1.blockpage_reason_id, blockpage_1.experiment_id, blockpage_1.url_id
->  Nested Loop  (cost=1.14..15741.82 rows=1 width=12) (actual time=0.326..0.326 rows=0 loops=1)
Output: b_1.blockpage_reason_id, blockpage_1.experiment_id, blockpage_1.url_id
->  GroupAggregate  (cost=0.57..15294.10 rows=52 width=12) (actual time=0.325..0.325 rows=0 loops=1)
Output: blockpage_1.experiment_id, blockpage_1.url_id, max(blockpage_1.redirect_num)
Group Key: blockpage_1.experiment_id, blockpage_1.url_id
->  Index Scan using blockpage_experiment_id_url_id_redirect_num_blockpage_reason__ on iclab.blockpage blockpage_1  (cost=0.57..15293.19 rows=52 width=12) (actual time=0.324..0.325 rows=0 loops=1)
Output: blockpage_1.id, blockpage_1.url_id, blockpage_1.full_url_id, blockpage_1.experiment_id, blockpage_1.blockpage_reason_id, blockpage_1.html_tag_id, blockpage_1.body_len, blockpage_1.blockpage_diff, blockpage_1.has_blockpage_regex, blockpage_1.http_status, blockpage_1.redirect_num, blockpage_1.response_failure
Index Cond: (blockpage_1.experiment_id = ANY ('{16,43}'::integer()))
Filter: blockpage_1.has_blockpage_regex
Rows Removed by Filter: 803
->  Index Scan using blockpage_experiment_id_url_id_redirect_num_blockpage_reason__ on iclab.blockpage b_1  (cost=0.57..8.59 rows=1 width=16) (never executed)
Output: b_1.id, b_1.url_id, b_1.full_url_id, b_1.experiment_id, b_1.blockpage_reason_id, b_1.html_tag_id, b_1.body_len, b_1.blockpage_diff, b_1.has_blockpage_regex, b_1.http_status, b_1.redirect_num, b_1.response_failure
Index Cond: ((b_1.experiment_id = blockpage_1.experiment_id) AND (b_1.url_id = blockpage_1.url_id) AND (b_1.redirect_num = (max(blockpage_1.redirect_num))))
Planning Time: 1.004 ms
JIT:
Functions: 33
Options: Inlining false, Optimization false, Expressions true, Deforming true
Timing: Generation 6.438 ms, Inlining 0.000 ms, Optimization 1.856 ms, Emission 38.146 ms, Total 46.440 ms
Execution Time: 50.745 ms

### Table definition:

CREATE TABLE iclab.blockpage (
id                          BIGSERIAL   PRIMARY KEY,
url_id                      INTEGER     NOT NULL,
full_url_id                 INTEGER     NOT NULL,
experiment_id               INTEGER     NOT NULL,
blockpage_reason_id         INTEGER,
html_tag_id                 INTEGER     NOT NULL,
body_len                    INTEGER,
blockpage_diff              REAL,
has_blockpage_regex         BOOLEAN,
http_status                 INTEGER,
redirect_num                INTEGER     NOT NULL,
response_failure            INTEGER,
FOREIGN KEY (experiment_id)         REFERENCES iclab.experiment_results(id),
FOREIGN KEY(url_id)                 REFERENCES iclab.URL(id),
FOREIGN KEY(url_id)                 REFERENCES iclab.URL(id),
FOREIGN KEY(blockpage_reason_id)    REFERENCES iclab.blockpage_reason(id),
FOREIGN KEY(html_tag_id)            REFERENCES iclab.html_tag(id)
);

CREATE UNIQUE INDEX blockpage_experiment_id_url_id_redirect_num_blockpage_reason__
ON iclab.blockpage(experiment_id , url_id, full_url_id, redirect_num, html_tag_id);

## optimization – Value Maximisation Algorithm with multiple costs

So in front of me lies different items. To buy each item you will need a certain amount of multiple things. For example, to buy a lamp, you will need to pay 3 apples, 4 oranges and 17 bananas. Each item has it’s monetary value, and some items can only be unlocked after another item is bought.

To rephrase:

There are n items each with a value of kv.

For each item k, it will cost you a different amount of w, x, y, z.

For some item ki, another item kj needs to be bought for ki to be buyable.

Given a certain amount of w, x, y and z, maximise the total value bought, identifying which items to buy.

I’m figuring out what algorithm I can probably look into.
If you take away the item unlocking part then it looks like a knapsack with multiple weights on each item. What is my best bet on this?

## optimization – How to create index to improve performance of an aggregate function that creates a table in oracle

I am creating an Oracle ORDS API using APEX_JSON. I recently started using bind variables instead of string concatenation using ||. I am trying to use an in clause in my where condition.

The problems begin here. The field I need to have on the left side of in is a number and the parameter to my stored procedure needs to be varchar2 as it is a comma seperated list of numbers.

Example (edited for brevity)

CREATE OR REPLACE PROCEDURE GET_CATEGORYPRODS (
PCATEGORYID IN NUMBER,
COMMASEPPRODUCTIDS IN VARCHAR2
) AS

l_cursor               SYS_REFCURSOR;
v_stmt_str             STRING(5000);
v_name                 NUMBER; --PRODUCT.NAME%TYPE;
v_displayorder         NUMBER; --PRODUCTCATEGORY%TYPE;
BEGIN
v_stmt_str := 'SELECT
P.NAME,
PC.DISPLAYORDER
FROM
PRODUCT P
INNER JOIN
PRODUCTCATEGORY PC
ON P.PRODUCTID = PC.PRODUCTID
WHERE
PC.CATEGORYID := :CATEGORYID
AND
(P.PRODUCTID IN (SELECT * FROM TABLE(STRING_TO_TABLE_NUM(:COMMASEPPRODUCTIDS))) -- PREVIOUSLY WHERE || OCCURRED
OR (:COMMASEPPRODUCTIDS IS NULL))';

s_counter := 0;

OPEN l_cursor FOR v_stmt_str
USING pcategoryid, commasepproductids, commasepproductids;

FETCH l_cursor INTO
v_productid,
v_displayorder;

APEX_JSON.OPEN_ARRAY;
LOOP
EXIT WHEN l_cursor%notfound;
apex_json.open_object;
apex_json.write('ProductID', v_productid);
apex_json.write('DisplayOrder', v_displayorder);
apex_json.close_object;
END LOOP;
apex_json.close_all;

END GET_CATEGORYPRODS;

Sample of parameters
'97187,142555,142568,48418,43957,44060,45160,45171,333889,333898'

To handle this problem, I created an aggregate function that takes in a string, splits on the commas, and pipes the row to a custom type.

Custom Type

create or replace type tab_number is table of number;

Aggregate Function

create or replace FUNCTION string_to_table_num (
p VARCHAR2
)

RETURN tab_number
PIPELINED IS
BEGIN
FOR cc IN (SELECT rtrim(regexp_substr(str, '(^,)*,', 1, level), ',') res
FROM (SELECT p || ',' str FROM dual)
CONNECT BY level <= length(str)
- length(replace(str, ',', ''))) LOOP
PIPE ROW(lower(cc.res));
END LOOP;

END;

The query slowed down significantly. I figured some optimization was needed but I had never done any sort of optimization before. After some research, I found EXPLAIN PLAN and ran it on the orginal query. I couldn’t get a good answer because of the bind variables, so I decided to run it on the aggregate function.

EXPLAIN PLAN QUERIES

explain plan for select * from TABLE(string_to_table_num('97187,142555,142568,48418,43957,44060,45160,45171,333889,333898'));

SELECT *
FROM   TABLE(DBMS_XPLAN.DISPLAY);

When I ran EXPLAIN PLAN for the aggregate function the results were:

Plan hash value: 127161297

---------------------------------------------------------------------------------------------------------
| Id  | Operation                         | Name                | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                  |                     |  8168 | 16336 |    29   (0)| 00:00:01 |
|   1 |  COLLECTION ITERATOR PICKLER FETCH| STRING_TO_TABLE_NUM |  8168 | 16336 |    29   (0)| 00:00:01 |
---------------------------------------------------------------------------------------------------------

As I stated before, I am a noob to analyzing and optimizing queries, but 8168 Rows and 16336 bytes seems to be a lot for such a simple function. I looked into it, and found that the problem may be the lack of indexing of the pipelined table. I tried to add an index to the type tab_number but it turned it into a PL/SQL object that needed to be declared in a query, not a function.

I am pretty lost with this one. If you have any suggestions for any of the scenarios I mentioned, I am all ears. Thanks in advance.

## mathematical optimization – How to express that at least 4 of 14 variables in linear programming are greater than 10?

That’s is quite likely impossible (but depends on the other constraints). Linear programs have a convex polytope as feasible set. The that you describe is not convex. See here for a 3-dimensional example where we want at least two of the three variable to be greater or equal to 1:

RegionPlot3D(
Or @@ (And @@ Thread(# >= 1) & /@ Subsets({x, y, z}, {2})),
{x, -2, 2}, {y, -2, 2}, {z, -2, 2}
)

You see, clearly not convex.

## Implementing Bemporad optimization algorithm – MathOverflow

I need to reproduce the results of a relatively old paper of a paper and one of the steps is to solve an IQP problem, the algorithm suggested is this one. Which I don’t know it’s the best way to do it since it’s quite old (I have understanding of continuous optimization, but when it comes to discrete I know bits and pieces). Also I can’t really find a C/C++ implementation of any IQP solver, but this one to me doesn’t look particularly difficult to implement.

Section 3.2. Reports the algorithm which I’ll write down here for reference:

1. Take the original MIQP, relax all integrality constraints, mark the relaxed QP with its number of guaranteed switches, i.e.−1. Set $$f_{opt}=1$$,$$k_c=−1$$,$$x_{opt}=(1;…;1)$$ and
initialize with the relaxed QPthe list of problems to be solved.

2. If the list of problems is empty, terminate and output $$f_{opt},x_{opt}$$.

3. If there are problems on the list marked by $$k_c$$, select one of them, remove it from the list, and solve it.If the QP is feasible, denote its cost by $$f*$$ and its solution by $$x*$$. Go to step 5. If the QP is infeasible go to 2.

4. If there are no problems on the list marked by $$k_c$$,increase $$k_c$$ by 1 and go to 2.

5. Fathoming by worse cost: If $$f*geq f_{opt}$$,then go to 2

6. Integer feasibility : If $$f* < f_{opt}$$ and $$x*$$ satisfies the integrality constraints, then set $$f_{opt}=f*$$ and $$x_{opt}=x*$$ .Go to 2

7. Feasibility but not integer feasibility Separate the problem. Mark the sub problems by the number of guaranteed switches in the fixed integer variables. Add the subproblems to the list of problems. Goto 3.

It’s not 100% clear to me how I form a subproblem to be solved however (I guess this is step 7).
Can you help?

## mathematical optimization – Nmaximize error : The function value Indeterminate is not a number at

I have been looking on the StackExchange for solutions to my issue… but I can’t find. So I am asking for a solution to the following problem:

First I define some functions, the function to be maximized, V, the parameters and then the NMaximize function for given values of a parameter h and the constraints.
I get some results but also the following message :
Nmaximize error : The function value Indeterminate is not a number at {0.554465,1.91298,3.00862,4.06643*10^-6,0.}
The function value Indeterminate is not a number at {1.63675,0.,1.02183,0.167442,0.231841}
The function value Indeterminate is not a number at {0.0972852,1.26903,2.63931,1.6129,0.}
Further output of NMaximize:: nnum will be supressed during this calculation.

Could you help me with this program ? Am I doing something wrong ?

G(P_) := 0.1 + (Gamma)/(1 + (Gamma) P);
B(P_) := 0.125 - (Beta)/(1 + (Beta) P);
q = (2 n (1 - h))/Q;
A(P_) := B(P) + q;
L(s_) := n (1 - (Theta) (1 - s))*(1 - h);
F(x_, y_) := x^(Epsilon) y^(1 - (Epsilon));
Cons1(k_, s_, c_, d_) := F(k, L(s)) - n (c + d) - k;
Cons2(k_, P_, s_) := P - (Eta)/(Delta) F(k, L(s));
Cons3(s_, P_) := n*s - n*G(P)/A(P);

V(c_?NumericQ, d_?NumericQ, s_?NumericQ, k_?NumericQ, P_?NumericQ) :=
n u(c, s) + (Zeta) n u(d, s);

n = 40000; (Gamma) = 0.005; (Beta) = 0.005; Q = 150000; (Epsilon)
= 0.3; (Eta) = 0.1; (Delta) = 0.05; (Zeta) = 0.9; (Sigma) = 0.2;
(Theta) = 0.1;

lockdown = {h, 0, 0.9, 0.05};

OutMax1 =
Table(Maximize({Abs(V(c, d, s, k, P))}, {c, d, s, k, P} (Element)
ImplicitRegion({c >= 0 && d >= 0 && k >= 0 && P >= 0 && s >= 0 &&
1 > s && Cons1(k, s, c, d) == 0 && Cons2(k, P, s) == 0 &&
Cons3(s, P) == 0 }, {c, d, s, k, P})), Evaluate(lockdown));

## program optimization – Minimizing series of XORs

Suppose you receive a list of $$n$$ instructions on $$k$$ boolean variables where each instruction has the form

$$x_i leftarrow x_i oplus x_j,$$

(where $$oplus$$ is the binary XOR) can we efficiently find a minimal series of instructions (of the same form) that computes the same result, using up to $$m$$ initially zero extra temporaries?